| paper | Ordinal Maximin Share Approximation for Chores |
| authors | — |
| venue | AAMAS 2022 |
| filed under | fairalloc · shares |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4.1
statement extracted from the paper’s text layer
Given rational population masses \(\mu_t\) over complete additive valuation types \(t\in T\), rational per-capita supplies \(\sigma_j\) of \(q\) replicated indivisible chore categories, and \(\sum_t\mu_t=1\), define \(\theta_{t,2/3}\) as the maximum \(\lambda\) for which a finite-support distribution \(y_b\) over integral bundles \(b\in\mathbb{Z}_{\ge0}^{q}\) satisfies \(\sum_b y_b=2/3\), \(\sum_b b_jy_b=\sigma_j\) for every \(j\), and \(v_t\cdot b\ge\lambda\) whenever \(y_b>0\). Compute a finite-support mass assignment \(x_{t,b}\ge0\) satisfying \(\sum_bx_{t,b}=\mu_t\), \(\sum_{t,b}b_jx_{t,b}=\sigma_j\), and \(v_t\cdot b\ge\theta_{t,2/3}\) whenever \(x_{t,b}>0\).
A high-multiplicity replicated-chore model: complete valuation types \(v_t\in\mathbb{Q}_{\le0}^{q}\) carry masses \(\mu_t\), category \(j\) has \(\sigma_jN\) indistinguishable copies in a rational clone, each agent receives an integral bundle \(b\), and \(x_{t,b}\) assigns population mass to bundles subject to the per-type ordinal MMS threshold.
The opponent's strongest point is that the paper proves polynomial time only for explicitly listed agents and chores, so a polynomial algorithm in \(q\), \(\tau\), and the binary encoding of \(\mu\) and \(\sigma\) is not established.
fatal: False
The mirror covers the algorithmic guarantees of Theorems 4.1 and 6.1 in a replicated high-multiplicity regime; it leaves the exact \(3/4\) existence boundary, Proposition 5.1's heuristic limitation, and the paper's finite-instance runtime proofs without direct transfer.
There is a credible positive case, but it is a high-multiplicity extension rather than a literal continuum with the paper’s fixed finite set of chores. The strongest anchor is Theorem 4.1.
The natural regime is a large system of households, municipalities, or industrial sites sharing recurring standardized burdens: waste-processing tasks, inspections, emissions-reduction tasks, or maintenance duties. There are \(N\) agents but only \(\tau\ll N\) complete burden types. A type \(t\) specifies the agent’s entire additive valuation vector \(v_t\in\mathbb{Q}_{\le 0}^q\) over \(q\) chore categories. The population is given by rational masses \(\mu_t\), with \(\sum_t\mu_t=1\). Chores also scale with the population: category \(j\) has \(\sigma_j N\) indivisible copies, where \(\sigma_j\in\mathbb{Q}_{\ge 0}\). This scaling is essential: with a fixed finite chore set and \(N\to\infty\), almost every agent would receive nothing and MMS would become vacuous.
An individual still receives an integral bundle \(b\in\mathbb{Z}_{\ge0}^q\), with value \(u_t(b)=\sum_jv_{tj}b_j\). Continuity enters only through the allocation of indistinguishable agents to whole bundles. Let \(x_{t,b}\) be the mass of type-\(t\) agents receiving bundle \(b\). Feasibility requires \(\sum_bx_{t,b}=\mu_t\) for every \(t\), and \(\sum_{t,b}b_jx_{t,b}=\sigma_j\) for every chore category \(j\). Thus \(x\) is a mass-assignment kernel, not a fractional allocation of an individual chore.
The appropriate continuum MMS benchmark is also a high-multiplicity limit. For \(\delta\in(0,1]\), define \(\theta_{t,\delta}\) as the largest \(\lambda\) for which there is a finite-support distribution \(y_b\) over integral bundles satisfying \(\sum_by_b=\delta\), \(\sum_bb_jy_b=\sigma_j\) for every \(j\), and \(u_t(b)\ge\lambda\) whenever \(y_b>0\). This is the limiting value of the finite \(1\)-out-of-\(\lfloor\delta N\rfloor\) MMS: \(y_b\) records the mass of MMS bundles of configuration \(b\). Clearing denominators recovers an ordinary finite instance with repeated valuation types and repeated chore copies, while any finite allocation gives an empirical \(x\). This is the relevant rational-clone equivalence.
The lead problem is therefore:
\(2/3\)-MMS\(_\infty\) Chores. Given \((\mu,\sigma,(v_t)_{t\in T})\), find a feasible mass assignment \(x\) such that \(x_{t,b}>0\) implies \(u_t(b)\ge\theta_{t,2/3}\) for every positive-mass type \(t\). Equivalently, one may maximize the largest \(\delta\) for which such an assignment exists.
This is a faithful population version of the problem solved by Theorem 4.1, proved in this paper: “Given an additive chores instance, a \(1\)-out-of-\(\lfloor 2n/3\rfloor\) MMS allocation exists and can be computed in polynomial time.” The paper’s ordered-instance reduction is especially compatible with the regime: task categories can have a common severity order, while types differ in the magnitudes they assign to those categories. The paper itself treats ordered instances as sufficient through Lemma 2.1, which it attributes to Barman and Krishna Murthy.
I would expect \(2/3\)-MMS\(_\infty\) Chores to be Class A, at least when the number of chore categories and valuation types are the principal parameters. The proof of Theorem 4.1 does not need exact MMS computation. It uses four simple threshold quantities and a greedy bag-filling procedure. In the high-multiplicity model, the corresponding operations should become quantile and mass operations over chore categories, followed by a type-level configuration or transportation computation. The central question is whether the bag-filling process can be compressed to polynomially many type and quantile events rather than expanded over \(N\) agents and \(N\sigma_j\) chore copies.
My second anchor is Theorem 6.1, also proved here. It gives a polynomial-time \(1\)-out-of-\(\lfloor\lfloor3n/4\rfloor-a\log\lfloor3n/4\rfloor\rfloor\) MMS allocation for integer-valued chores. Its high-multiplicity analogue is:
\(\varepsilon\)-slack \(3/4\)-MMS\(_\infty\) Chores. Given the same input and a rational \(\varepsilon>0\), find a feasible mass assignment \(x\) such that every type-\(t\) bundle used by \(x\) has value at least \(\theta_{t,3/4-\varepsilon}\).
The normalization explains why this is not an arbitrary strengthening. The paper’s guarantee uses \(\lfloor3N/4\rfloor-a\log N\) bundles, whose ratio to \(N\) tends to \(3/4\), since \(a\log N/N\to0\). Thus the natural continuum question is whether the additive logarithmic loss disappears in the population limit. For fixed \(\varepsilon>0\), I expect this problem also to be Class A, using a high-multiplicity version of the paper’s bin-packing approximation and configuration-LP machinery. The exact \(\varepsilon=0\) boundary is a worthwhile follow-up: discontinuities in the MMS value, or difficulty in separating configurations, could make exact \(3/4\)-MMS continuum-specific hard.
The paper’s Proposition 5.1 supports the regime but is not a separate anchor here. It constructs identical-valuation instances in which Algorithm 1 behaves like First Fit Decreasing and fails to reach a stronger MMS ratio. That is useful evidence that repeated types are not artificial: the paper’s own negative example already has essentially one agent type and arbitrarily many agents. But Proposition 5.1 is a limitation of one algorithm, not an NP-hardness or general complexity theorem.
There is no numbered NP-hardness result in this paper. The statement that computing a single-agent MMS value is NP-hard is cited background in Section 1.2, attributed to earlier work, rather than a theorem proved here. I therefore would not present it as a hardness anchor. It does, however, identify the likely boundary of the mirror: exact computation of \(\theta_{t,\delta}\) is itself a high-multiplicity bin-packing/configuration problem. Hardness driven by the number and numerical structure of chore categories may survive even when \(\tau=1\); that would be Class B or Class C depending on the precise encoding.
The weakest point is that resource scaling is unavoidable but changes the literal instance family. A fixed finite set of indivisible chores cannot support a nondegenerate atomless population. The proposed repeated-copy model is therefore an extension of the authors’ problem, not merely replacing \(n_t\) by \(\mu_t\). I think it remains author-recognizable because it preserves additive negative valuations, complete allocation, integral bundles, MMS partitions, and the same bag-filling/bin-packing structure, while matching the paper’s collective-responsibility applications.
The main questions generated are whether rational-clone equivalence holds with bounded MMS loss, whether the threshold construction in Theorem 4.1 admits a polynomial type-level implementation, whether high-multiplicity bin-packing pricing is polynomial in \(\tau\), \(q\), and encoding length, and whether the \(3/4\) limit is attainable exactly or only with fixed \(\varepsilon\)-slack. Even if exact MMS pricing proves hard, that would make this a useful ChoCo case: population multiplicity removes named-agent overhead, while the genuine combinatorics remain in chore configurations rather than disappearing.
The strongest case against the proposed mirror is that it survives only by moving the continuity to the resource side and thereby changing the paper’s problem.
For Theorem 4.1, cloning agents while keeping the paper’s finite chore set \(M\) fixed gives no meaningful limit. Once \(d\) grows proportionally with \(N\), the MMS partition has more and more empty bundles; adding zero-valued dummy chores avoids this only by changing the MMS benchmark itself. Thus the literal population limit degenerates.
The proposed repair—\(\sigma_jN\) copies of \(q\) chore categories—is coherent, but it is not a mere continuization of Theorem 4.1. It replaces named, item-specific chores by exchangeable resource types, restricts valuations to vectors over those types, and replaces an allocation of \(M\) by a distribution over integral bundle configurations. If \(q\) is fixed, this is a new replicated-chore/bin-packing model. If \(q\) grows enough to preserve the paper’s arbitrary item structure, the fixed finite type-space advantage disappears. The paper’s ordered-instance reduction does not close this gap: its reverse mapping uses item-specific picking sequences and does not supply a population-level aggregation theorem.
Nor does Theorem 4.1 itself yield the claimed continuous algorithm. In the explicit clone expansion, Algorithm 1 can simply be run on \(N\) agents and \(O(N)\) chores, so the continuum notation adds no computational content. In the implicit model, “batching” the greedy process is precisely the unresolved problem: each bundle assignment changes the remaining category masses and the set of eligible agent types. The natural variables \(x_{t,b}\) range over potentially exponentially many integral configurations, and the paper proves neither a compact formulation nor a separation procedure. The four threshold values in the theorem establish a finite-instance guarantee, not a polynomial algorithm in \((\mu,\sigma)\).
Theorem 6.1 has the same defect. Hoberg–Rothvoss is invoked with running time polynomial in the explicit number \(m\) of chores. It does not automatically become an algorithm polynomial in the number of chore categories and the binary encoding of their multiplicities. The observation that \(a\log N/N\to0\) establishes only a ratio limit. MMS is an ordinal threshold over integral bundle values, so convergence to a \(3/4\) population benchmark requires additional regularity assumptions. Under fixed \(q\), bounded values, and carefully chosen rational scaling, such a limit may well exist—but that is again a new high-multiplicity configuration problem, not a consequence of Theorem 6.1.
Proposition 5.1 does not strengthen the case. Its one-type construction shows that Algorithm 1 can reproduce First Fit Decreasing; it does not give a computational result about the fair-division problem or a population-level objective. Its natural mirror would be asymptotic analysis of one heuristic, rather than continuization of the paper’s fairness guarantees.
The negative case therefore is not that repeated agent types are incoherent, nor that high-multiplicity work is prior art—both would be wrong. The honest claim is narrower: neither named theorem transfers to a continuous society without simultaneously introducing a new replicated-resource model and a new configuration algorithm. That is a substantial modelling leap, not a mirror already latent in the paper.
I cannot honestly make the universal negative airtight. With recurring standardized chores, fixed \(q\), rational masses, and per-capita chore supply, the proponent’s rational-clone construction is a legitimate high-multiplicity problem. If ChoCo regards such extensions as worthwhile in their own right, this paper probably has a viable mirror; the negative case mainly shows that the paper itself does not yet justify it.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.