| paper | How to Fairly Allocate Easy and Difficult Chores |
| authors | — |
| venue | AAMAS 2022 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.7
statement extracted from the paper’s text layer
Given a finite set \(T\) of complete easy/difficult worker types with rational mass vector \(\mu\), chore classes \(R\), rational \(p>1\), and rational per-capita supplies \(\rho\), find a finite-support rational kernel \(y_{t,B}\) over integer bundles \(B\in\mathbb Z_{\ge 0}^{R}\), where \(d_t(B)=\sum_{r\in R}d_t(r)B_r\) and \(d_t(r)\in\{1,p\}\), satisfying \(\sum_B y_{t,B}=\mu_t\) and \(\sum_{t,B}y_{t,B}B_r=\rho_r\), such that every ordered pair of supported assignments \((t,B),(u,D)\) satisfies chore-EF1—either \(B=\varnothing\) or some \(r\) with \(B_r>0\) has \(d_t(B-\mathbf e_r)\le d_t(D)\)—and no feasible \(y'\) admits a type-preserving coupling \(\pi_{t,B,D}\) with weak cost improvement everywhere and strict improvement on positive mass.
A repeated-task high-multiplicity chore market: \(\mu\) is worker-type mass, \(\rho\) is per-capita supply of indivisible chore classes, \(y\) distributes integer bundle configurations, and feasibility asks for chore-EF1 plus population-level PO under type-preserving couplings.
The positive-mass Pareto notion can erase single-agent improvement witnesses, while least-spender, ownership, and entitlement histories may fail to collapse to finitely many type-level states; no exact rounding theorem or aggregate polynomial algorithm is established.
fatal: False
The mirror covers Theorem 3.7’s bivalued-chore EF1+PO result and its Fisher-equilibrium mechanism; it leaves Theorem 4.1 and Corollary 4.16 on MMS, plus goods and weakly lexicographic variants, outside scope.
The strongest honest case is for a Class A mirror of the paper’s bivalued-chore result. The paper contains no numbered NP-hardness theorem of its own: the statement that MMS values are NP-hard for general additive utilities is background cited to Garey and Johnson, not a named hardness result proved here. My lead anchor is therefore the paper’s main algorithmic result, Theorem 3.7, proved by the authors: for bivalued chores, Algorithm 1 computes a Pareto-optimal and EF1 allocation in polynomial time.
A natural continuous setting is a large organization allocating recurring, indivisible chore jobs among a large population of workers or residents. There are finitely many chore classes \(R=\{1,\ldots,q\}\), such as kitchen cleaning, laundry, refuse collection, and snow removal. A type \(t\) is a complete easy/difficult profile \(e_t\in\{0,1\}^q\). Its disutility for one chore of class \(r\) is
\[ d_t(r)= \begin{cases} 1 & \text{if }e_{tr}=0,\\ p & \text{if }e_{tr}=1, \end{cases} \qquad p>1, \]
so \(d_t(B)=\sum_r d_t(r)B_r\) for an integer bundle \(B\in\mathbb Z_{\ge 0}^q\). The population is a distribution \(\mu\) over the finite type set \(T\), with \(\mu_t\) the mass of type \(t\). Thus agents with the same difficulty profile are genuinely interchangeable for the problem.
Let \(\rho_r\) be the number of class-\(r\) chores per unit population. A continuous allocation is a finite-support kernel \(y_{t,B}\), where \(y_{t,B}\) is the mass of type-\(t\) agents receiving the integer bundle \(B\). It must satisfy
\[ \sum_B y_{t,B}=\mu_t \]
for every type \(t\), and
\[ \sum_{t,B} y_{t,B}B_r=\rho_r \]
for every chore class \(r\). The intended finite approximation has \(N\mu_t\) agents of type \(t\) and \(N\rho_r\) distinct, indivisible chores of class \(r\), for increasingly large \(N\). The continuous object is \(\mu\), not a fractional chore: every agent in the limiting allocation still receives an integer bundle.
Call \(y\) EF1 if, for every two supported assignments \((t,B)\) and \((u,D)\), there is one chore class \(r\) occurring in \(B\) or \(D\) such that
\[ d_t(B-\mathbf e_r)\le d_t(D-\mathbf e_r), \]
interpreting removal from a bundle in which \(r\) does not occur as leaving that bundle unchanged. This is exactly the paper’s chore version of EF1, expressed in costs rather than negative utilities.
Call \(y\) Pareto optimal if there is no other feasible kernel \(y'\) and no coupling \(\pi_{t,B,D}\) between the old and new bundles such that every type-\(t\) agent weakly lowers her cost,
\[ d_t(D)\le d_t(B), \]
with strict improvement for positive mass of agents. The continuous problem is therefore:
Given rational \((T,\mu,p,\rho)\), find a finite-support rational kernel \(y\) satisfying the supply constraints, EF1, and this population-level notion of Pareto optimality.
There is no scalar welfare objective in the source problem; the objective is feasibility—produce an EF1 and PO allocation. Equivalently, one may minimize \(0\) subject to these conditions.
This is a credible high-multiplicity version of the authors’ problem rather than a softened divisible-resource problem. The utility class is unchanged, the “one item” in EF1 remains one indivisible chore, and Pareto comparisons are made agent by agent through the coupling. Only irrelevant names have disappeared. The regime is one in which \(N\gg\tau\): for fixed \(q\), there are at most \(2^q\) difficulty types, while a large facility may have thousands of workers and many repeated jobs. The same construction also supplies the required dictionary back to finite elections: rational \(\mu\) and \(\rho\) can be scaled by \(N\) to obtain an ordinary finite instance.
I would expect this mirror to be tractable, hence Class A. The reason is not merely that the finite problem is already in P. Theorem 3.7’s mechanism is unusually compatible with aggregation. The algorithm maintains a Fisher-market equilibrium; Proposition 3.2 says equilibrium allocations are PO, Lemma 3.5 turns price-EF1 into EF1, and Theorem 3.3 establishes that for bivalued utilities ordinary PO coincides with fractional PO. These are precisely the structural facts one would want when replacing named agents by type masses. Price, minimum-pain-per-buck, and alternating-path conditions can be stated over finitely many types, while a configuration formulation uses integer bundles as columns. A likely route is a type-aggregated Fisher algorithm or a configuration LP with a pricing oracle for bivalued bundles.
The result would not be a new hardness-dissolution theorem: Theorem 3.7 already gives polynomial time for the discrete problem. Its value for ChoCo would instead be to test whether the Fisher-market structure survives the population limit, and to obtain an exact rounding theorem from a continuous kernel back to large finite allocations. The important computational questions are whether a finite-support equilibrium certificate always exists, whether the aggregate price-reduction process has polynomially many type-level events, and whether a continuous EF1+PO solution can be rounded while preserving EF1 exactly or with an error that vanishes as \(N\) grows.
I would not claim that this automatically mirrors Theorem 4.1 or Corollary 4.16. MMS is tied explicitly to the finite number \(n\) of agents, so a continuum version needs a separate convention—probably a limit of MMS values along \(N\)-replicated instances. Theorem 4.1 is a promising follow-up, but including it here would overstate the case.
The weak point is that EF1 is intrinsically discrete. If one instead fixes a finite chore set and replaces the agents by a nonatomic population, most agents receive nothing and “remove one item” becomes degenerate. My mirror avoids that pathology by using a repeated-task high-multiplicity regime and retaining integer bundles. That is a modeling choice, and the opposing analyst can reasonably argue that the joint scaling of workers and recurring chores is less canonical than the voting mirror. But it is a genuine scenario, not a trick: large organizations really do allocate many repeated indivisible tasks among many agents with a small number of difficulty profiles. On that regime, Theorem 3.7 has a precise, recognizably continuous population analogue.
The only serious anchor is Theorem 3.7, so the easy objections do not work: this is a named polynomial-time computational result, and the paper does not already study the continuous-population version. The negative case must instead question whether the proposed population limit preserves the problem’s substance.
If the item set \(M\) remains fixed while the number of agents grows, it degenerates. At most \(|M|\) agents receive chores, so almost all population mass is empty-handed. EF1 and Pareto optimality then concern a vanishing exceptional set, while any mass-based notion ignores precisely the agents and chores on which the finite problem turns.
The proponent’s rescue—scaling the number of chores with the population—is the strongest possible repair. But it changes the object into a two-sided high-multiplicity allocation model: besides \(\mu\), one needs per-capita supplies \(\rho\), chore classes, and a distribution over integer bundle configurations. The continuous variable is no longer just the society; it is a measure over discrete allocations. That may be a worthwhile new problem, but it is not a direct population continuization of Theorem 3.7.
More seriously, EF1 and PO are not stable under this limit. EF1 tolerates exactly one physical chore, while PO can be witnessed by improving one named agent. Two sequences can have the same limiting \((\mu,\rho)\) while differing by one exceptional agent or chore, yet differ in finite EF1 or PO. Requiring strict improvement for positive mass erases such witnesses; retaining them requires atoms and restores the discrete model. Replacing individual comparisons by expected costs avoids this problem only by abandoning EF1.
The paper’s algorithm also does not aggregate by preference type as cleanly as the proponent suggests. Its proof depends on ownership of individual chores, least spenders, MPB alternating paths, and “entitled” chores whose transfer history matters. Two agents of the same easy/difficult type may have different bundles and different entitlement states. Aggregating them therefore creates cohorts of configurations, potentially as numerous as the original agents. The equivalence between PO and fractional PO in Theorem 3.3 does not remove EF1’s one-item, support-dependent constraints.
There is even a formal mismatch in the proposed EF1 condition: for chores, the paper removes a chore from the envying agent’s bundle, requiring \(d_t(B-\mathbf e_r)\le d_t(D)\); the displayed condition also permits removing \(r\) from \(D\). That is repairable, but correcting it does not resolve the limit problem.
Still, the universal negative is not honestly airtight. A large workforce repeatedly assigning atomic jobs with finitely many difficulty profiles is a plausible high-multiplicity regime, and a measure over integer bundles is a coherent object. Thus I would reject the claim that Theorem 3.7 has no worthwhile mirror in any scenario. The strongest defensible criticism is narrower: the proposed mirror is not yet a justified continuization, and its tractability does not follow from the Fisher-market proof.
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.