| paper | Connections between Fairness Criteria and Efficiency for Allocating Indivisible Chores |
| authors | Ankang Sun, Bo Chen, X. V. Doan |
| venue | ATAL 2021 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: feasibility holds exactly when \(\sum_{e\in E}q_e\le r\). A decision algorithm takes \(O(L+mL^2)\) bit operations. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Corollary 3.8
statement extracted from the paper’s text layer
Given finite worker types \(T\), rational masses \(\mu_t\), additive type costs \(c_t(e)\) for chore categories \(e\in E\), per-capita chore supplies \(q_e\), and workload cap \(r\), decide whether there exists finite-support rational mass variables \(x_{t,b}\) over integral bundles \(b\in\mathbb{Z}_{\ge 0}^{E}\) with \(\sum_e b_e\le r\), satisfying \(\sum_b x_{t,b}=\mu_t\), \(\sum_{t,b}b_e x_{t,b}=q_e\), and \(c_t(b)\le(3/2)\operatorname{MMS}_t(2,b\uplus b')\) for every positively supported pair \((t,b),(u,b')\).
A high-multiplicity indivisible-chore assignment model: \(x_{t,b}\) is the mass of type-\(t\) workers receiving integral bundle \(b\); aggregate bundle counts are fractional, costs are additive, and the objective is feasibility of support-wise \(3/2\)-PMMS, optionally followed by minimum aggregate social cost.
The paper's round-robin proof gives no bit-complexity or structural reason that the proposed support-wise configuration-feasibility problem admits a compressed analogue.
fatal: False
The mirror covers Corollary 3.8 and its Proposition 3.7 implication for \(3/2\)-PMMS, while leaving the paper's other fairness-transfer propositions and prices-of-fairness results untreated.
The strongest honest positive case is a narrow Class A mirror of Corollary 3.8, rather than a hardness-dissolution result. The paper has no in-paper NP-hardness theorem: its remark that exact EF existence is NP-complete cites [6], so it cannot serve as an anchor. But Corollary 3.8 is a named algorithmic result and explicitly states that, for additive indivisible chores, the round-robin algorithm outputs a \(3/2\)-PMMS allocation in polynomial time. It is proved in this paper, using the paper’s Proposition 3.7—also proved there—which says that every \(\alpha\)-EF1 allocation is \(\frac{2\alpha+1}{\alpha+1}\)-PMMS, giving \(3/2\)-PMMS when \(\alpha=1\), together with the known polynomial-time round-robin EF1 algorithm.
I would mirror this with Continuous \(3/2\)-PMMS Recurring-Chore Assignment. The population consists of finitely many worker types \(T\), where type \(t\) has an additive cost vector \(c_t(e)\) over a finite catalogue \(E\) of chore categories. The society is a rational mass distribution \(\mu\), with \(\mu_t\) the fraction of workers of type \(t\). The regime is a large maintenance, hospital, or municipal-workforce setting: perhaps millions of workers, tens of worker types, and a fixed catalogue of recurring task categories. Workers of the same type have identical costs, skill constraints, and workload rules.
The crucial co-modification is that chore supply scales with population. Let \(q_e\) be the number of copies of chore category \(e\) per unit population. A worker still receives an integral bundle; only the aggregate assignment is fractional. With a workload cap \(r\), let
\[ \mathcal B_r=\left\{b\in\mathbb Z_{\ge 0}^{E}:\sum_{e\in E}b_e\le r\right\}. \]
The decision variable is \(x_{t,b}\), the mass of type-\(t\) workers receiving bundle \(b\). It must satisfy
\[ \sum_{b\in\mathcal B_r}x_{t,b}=\mu_t \]
for every type \(t\), and
\[ \sum_{t\in T}\sum_{b\in\mathcal B_r} b_e x_{t,b}=q_e \]
for every chore category \(e\). Costs are \(c_t(b)=\sum_e b_e c_t(e)\).
Fairness must remain individual and support-wise, not type-average fairness. For every \(t,u\) with positive mass and every \(b,b'\) with \(x_{t,b}>0\) and \(x_{u,b'}>0\), require
\[ c_t(b)\le \frac32\,\operatorname{MMS}_t(2,b\uplus b'), \]
where
\[ \operatorname{MMS}_t(2,b\uplus b') = \min_{z+z'=b\uplus b'} \max\{c_t(z),c_t(z')\}. \]
Thus the problem is: given rational \((\mu,q,c)\), output a finite-support rational allocation \(x\) satisfying the supply equations and these \(3/2\)-PMMS inequalities. The anchored search objective is feasibility—construct such an allocation. A natural optimization extension would minimize
\[ \sum_{t,b}x_{t,b}c_t(b) \]
among all feasible \(3/2\)-PMMS allocations, but that efficiency objective is not claimed by Corollary 3.8 itself.
This is a genuine high-multiplicity mirror. If all inputs have denominator dividing \(N\), then \(N\mu_t\) workers of type \(t\) and \(Nq_e\) copies of chore \(e\) produce a finite instance whose workers receive integral bundles. Conversely, a repeated finite instance compresses to \(x\). No chore is fractionally assigned to an individual, and PMMS is not replaced by an average-cost condition. The continuum lies in the population and in the aggregate assignment measure.
I would expect this problem to be Class A, at least fixed-parameter tractable in the chore catalogue size \(m=|E|\) and workload cap \(r\). The paper’s round-robin argument supplies the right structural intuition; the new work is to compress its sequential certificate into a type-level configuration or flow representation without expanding the common denominator of \(\mu\) and \(q\). Full polynomial time in \((m,\lvert T\rvert,L)\) is an open target, not something the paper already proves. Further questions include whether the \(3/2\) guarantee is tight in the mass model, whether minimum-social-cost \(3/2\)-PMMS allocation is tractable, and whether support-wise PMMS becomes hard when \(m\) and \(r\) are unrestricted.
The weakest point is substantial: Corollary 3.8 is a short algorithmic corollary, not one of the paper’s central complexity classifications, and its finite round-robin proof uses an ordering of named agents that a bare population distribution does not contain. Moreover, scaling chore supplies creates a recurring-task model rather than literally keeping the paper’s fixed set of \(m\) chores. But that scaling is necessary to avoid the degenerate limit in which almost every continuum agent receives nothing, and it is precisely the permitted co-modification for a meaningful high-multiplicity population model. Under a strict requirement of a hardness anchor, this paper has no compliant positive case; under the stated allowance for named polynomial-time results, the continuous \(3/2\)-PMMS problem is a defensible, concrete mirror.
The negative case must concede that Corollary 3.8 is a genuine named algorithmic result. The paper’s external statement that EF existence is NP-complete cannot be used as an anchor, and Proposition 3.7 is only the structural implication behind the corollary. Thus everything turns on whether Corollary 3.8 has a meaningful population-continuous counterpart.
With the paper’s actual object—a fixed set \(E\) of indivisible chores—the continuum degenerates. If the number of agents grows while \(m=|E|\) stays fixed, at most \(m\) agents receive nonempty bundles. Almost all population mass receives \(\emptyset\), and the individual fairness conditions become either vacuous for almost everyone or depend on zero-mass exceptional recipients. This is not a useful high-multiplicity limit of the paper’s allocation problem.
The proposed repair is to introduce recurring chore categories with per-capita supply \(q_e\). That is a plausible model of a large maintenance or hospital workforce, but it is no longer merely continuizing the population. It adds a scalable item population, a workload model, and a configuration space of integral bundles. Those additions may define an interesting new problem, but they are not supplied by Corollary 3.8 and are not consequences of its proof.
More importantly, the corollary gives no high-multiplicity algorithm. Round-robin is polynomial in the explicitly listed number of agents. If rational masses are cleared to a denominator \(N\), running the paper’s algorithm takes time polynomial in \(N\), which may be exponential in the binary encoding length of the masses. The central ChoCo question—whether the repeated instance can be solved in time polynomial in the type count and encoding length—remains entirely open. The positive case therefore offers a speculative new problem, not a continuous version of the paper’s computational result.
The proposed support-wise definition of PMMS exposes a deeper mismatch. For \(x_{t,b}>0\) and \(x_{u,b'}>0\), the condition
\[ c_t(b)\le \frac32\,\operatorname{MMS}_t(2,b\uplus b') \]
is a pairwise compatibility condition on integral configurations. The feasible set of \(x\) is consequently a union of faces determined by which configurations are simultaneously used; it is not the linear aggregate-feasibility problem suggested by the round-robin theorem. If one replaces it by type-average or expected-bundle fairness, the resulting condition may be amenable to linear programming, but it is no longer PMMS for the individuals in the paper. If one preserves individual PMMS, the continuum has not produced a canonical continuous fairness constraint; it has produced a new integral-configuration compatibility problem.
Proposition 3.7 does not rescue the mirror. Its proof is a pointwise inequality applied to one finite allocation and one pair of agents. Under the support-wise interpretation, the same inequality simply applies to every pair of supported configurations. Under an averaged interpretation, it need not survive. Either way, there is no new population-level theorem or complexity phenomenon to study.
The recurring-chore scenario is the strongest point for the positive case, and I would not call it nonsensical. A compressed algorithm for that model could be worthwhile as a new high-multiplicity fair-allocation problem. But it would be a follow-up motivated by the corollary, not a continuous mirror of the paper’s contribution: the fixed-supply version collapses, while the nondegenerate version changes the item universe and introduces the substantive computational structure itself. I therefore find the negative case strong against this particular anchor, though not an airtight proof of the universal claim that no researcher could ever extract a valuable recurring-chore model from 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.