| paper | New Algorithms for the Fair and Efficient Allocation of Indivisible Chores |
| authors | Jugal Garg, Aniket Murhekar, John Qin |
| venue | IJCAI 2023 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given two complete agent types \(T=\{1,2\}\) with rational masses \(\mu_t\) satisfying \(\sum_t\mu_t=1\), \(k\) indivisible chore kinds with rational per-capita supplies \(q_j\), and rational additive disutilities \(d_t(j)\), find a finite-support rational allocation law \(z_{t,B}\) over integral bundles \(B\in\mathbb Z_{\ge0}^{k}\) such that \(\sum_B z_{t,B}=\mu_t\), \(\sum_{t,B}z_{t,B}B_j=q_j\), and \(d_t^{-1}(B)\le d_t(B')\) for every pair of supported classes \((t,B)\) and \((h,B')\), where \(d_t^{-1}(B)=0\) for \(B=0\) and otherwise \(d_t^{-1}(B)=\min_{j:B_j>0}d_t(B-e_j)\). The allocation must also admit no type-symmetric fractional reassignment \(u_{t,B,j}\ge0\) satisfying \(\sum_{t,B}z_{t,B}u_{t,B,j}=q_j\), \(\sum_jd_t(j)u_{t,B,j}\le d_t(B)\) for every supported class, and strict inequality for one class.
A high-multiplicity two-type chore-allocation model in which \(\mu\) is agent mass, \(q\) is per-capita supply of still-indivisible chore copies, \(z\) distributes mass over integral bundles, and feasibility asks for an \(\mathrm{EF1}+\mathrm{fPO}\) allocation.
Jointly scaling chore supply is an extension rather than a fixed-inventory population limit, and Theorem 3 does not establish polynomial-time compression of binary multiplicities or of the support of \(z\).
fatal: False
It covers Theorem 3’s two-type chore result in a binary-multiplicity, per-capita form; it leaves Theorem 1, Theorem 2, Theorem 4, Lemma 8, and the goods remark untouched.
The strongest positive case is the paper’s Theorem 3, proved here rather than cited: “Given a two-type chore allocation instance, an EF1 + fPO allocation exists and can be computed in strongly polynomial-time.” This is the one result I would anchor. Theorem 1 and Theorem 4 are restricted to three agents, which is a poor high-multiplicity regime; Theorem 2 is an existence obstruction rather than a computational anchor.
The natural regime is a large organization assigning recurring unpleasant tasks to a very large workforce. There are two complete worker types, for example two ergonomic or training profiles, and every worker of a given type has exactly the same additive disutility vector over standardized chore kinds. The organization has many repeated copies of each chore kind. Thus \(n\) is very large, \(\tau=2\), and the number of distinct disutility types and chore kinds is small relative to the number of workers and chore copies. This is precisely the kind of two-type high-multiplicity situation that Theorem 3 itself identifies, rather than an arbitrary population being forced into two types after the fact.
My lead problem is Two-Type EF1-fPO\(_\infty\). An instance contains two agent types \(T=\{1,2\}\), rational masses \(\mu_1,\mu_2\) with \(\mu_1+\mu_2=1\), finitely many chore kinds \(J\), rational supplies \(q_j\) of each chore kind per unit population, and two rational additive disutility vectors \(d_t\), where \(d_t(j)\) is the disutility of type \(t\) for chore kind \(j\). A type is complete: if the application has eligibility, workload, or capacity data, those belong to the type as well.
A bundle is an integral multiset \(B\in\mathbb Z_{\ge 0}^{J}\); \(B_j\) is the number of copies of chore kind \(j\) in it, and \(d_t(B)=\sum_j d_t(j)B_j\). The instance may specify a finite catalogue of allowable integral bundle configurations, or use the natural catalogue of all bundles up to a stated workload cap. The decision variable is a finite-support mass distribution \(z_{t,B}\), where \(z_{t,B}\) is the mass of type-\(t\) agents receiving bundle \(B\). It must satisfy \(\sum_B z_{t,B}=\mu_t\) and \(\sum_{t,B}z_{t,B}B_j=q_j\) for every chore kind \(j\).
The allocation is EF1 when, for every \(t,h\in T\) and every \(B,B'\) with \(z_{t,B}>0\) and \(z_{h,B'}>0\), \(d_t^{-1}(B)\le d_t(B')\), where \(d_t^{-1}(B)\) is \(d_t(B)\) after removing one most costly chore in \(B\), and is \(0\) for an empty bundle. This is deliberately a support-wise condition: it does not replace individual envy by comparison of average disutilities.
It is fPO when there is no type-symmetric fractional reassignment that weakly improves every positive-mass bundle class and strictly improves one. Formally, there must be no nonnegative quantities \(u_{t,B,j}\) such that \(\sum_{t,B}z_{t,B}u_{t,B,j}=q_j\) for every \(j\), \(\sum_jd_t(j)u_{t,B,j}\le d_t(B)\) for every supported \((t,B)\), and strict inequality for at least one supported class. Symmetrization is without loss here because agents sharing both a type and a current bundle are indistinguishable. The required output is a finite-support rational \(z\) satisfying these constraints; the optimization objective is feasibility, namely to output such an EF1+fPO allocation.
This is not merely a fractional-chores relaxation. Every bundle in the support is integral. If all input masses have common denominator \(D\), then \(D\mu_t\) gives numbers of cloned agents and \(Dq_j\) gives numbers of indivisible chore copies. A rational allocation law \(z\) expands to an ordinary finite allocation by assigning \(Dz_{t,B}\) cloned agents the integral bundle \(B\). Conversely, a finite allocation of identical copies produces such a bundle census. The model is therefore an extension of the paper’s problem to a repeated-agent/repeated-chore regime, with population and inventory scaled together. It is not a literal fixed-\(M\), atomless-agent limit.
I expect this problem to be Class A, at least for the natural repeated-chore catalogue. The reason is that the proof of Theorem 3 is already cohort-based. Algorithm 3 partitions chores between the two type groups, maintains competitive-equilibrium payments, transfers chores when they enter the other type’s MPB set, and uses RoundRobin only among agents with identical disutility functions. In the mass version, those operations become transfers of chore-copy mass and a cyclic distribution over integral bundles within each cohort. The paper’s Lemma 1 gives the crucial certificate: a pEF1 competitive equilibrium implies EF1, while the welfare theorem gives fPO. The expected continuous algorithm should therefore have complexity governed by the number of types, chore kinds, payment breakpoints, and the encoding length of the masses, rather than by the number of cloned workers.
That expectation is not an automatic consequence of Theorem 3. A proof would need to show that the RoundRobin allocation law has polynomial-size support and that the payment-transfer process can be compressed when chore multiplicities are given in binary. With an arbitrary bundle catalogue, support compatibility might itself introduce new hardness. The most interesting follow-up questions are whether the compact version has a strongly polynomial or merely polynomial-time algorithm, how accurately a rational mass solution rounds to a finite clone allocation, whether the result extends beyond two types, and where EF1 must be replaced by EFX. The paper’s Theorem 2 suggests that the last question may have a genuine non-existence boundary.
The weakest point is the required joint scaling of chores and agents. If only the population becomes nonatomic while the paper’s finite set of named chores remains fixed, almost everyone receives nothing and EF1 becomes degenerate. My mirror therefore adds repeated chore supply, which makes it an extension rather than a direct population-only mirror. That concession is unavoidable, but it does not make the model artificial: recurring standardized chores assigned among large interchangeable cohorts are a credible high-multiplicity version of the authors’ own two-type chore-allocation problem, and the central EF1, fPO, additive-disutility, and competitive-equilibrium semantics remain intact.
The proponent has found the one genuinely serious mirror, and the negative case is therefore narrow. Still, under ChoCo’s strict scope, Theorem 3 does not yield a worthwhile population continuization.
The key point is that the paper already permits arbitrarily many agents of the same two disutility types. Thus the proposed continuous agent population adds little to the theorem’s structure: the input already consists of two interchangeable cohorts, and Algorithm 3 explicitly exploits that symmetry through RoundRobin. If the finite chore set \(M\) is held fixed while \(n\) grows, at most \(|M|\) agents can receive nonempty bundles. Almost all population mass receives nothing, and EF1 becomes essentially vacuous: empty agents do not envy, while a singleton bundle becomes harmless after removing its sole chore. The pure population limit therefore loses the problem’s content.
The proponent’s repair is to scale the chore inventory as well. That may be a sensible high-multiplicity fair-division problem, but it is no longer a mirror obtained by continuizing the population. It introduces a new compressed resource model: chore copies become kinds with multiplicities \(q_j\), and the output is a distribution \(z_{t,B}\) over integral bundle configurations. The nontrivial computational question is then compression of the chore inventory and configuration space, not the continuous treatment of society.
This distinction remains under the strongest version of the proposal: two worker types, binary-encoded repeated chore supplies, integral bundles, and exact EF1+\(\mathrm{fPO}\). Theorem 3 is polynomial in the number of individual chores, not in the logarithms of their multiplicities. Its proof transfers chores one copy at a time and invokes RoundRobin over the expanded instance. Nothing in the theorem supplies a polynomial bound on the number of distinct bundle configurations or payment phases in the compressed representation. With an explicit catalogue, the problem depends on that catalogue; with all bundles up to a cap, the catalogue may be exponentially large. The support-wise EF1 requirement is also not a linear constraint: the positive bundle classes must form a mutually compatible support. So \(z\) is not simply the continuous society vector \(\mu\); it is an additional configuration-distribution object.
That does not make the repeated-inventory problem illegitimate. It makes it a new two-sided high-multiplicity allocation problem whose relationship to Theorem 3 must itself be established. If ChoCo admits that move, the anchor survives; existing high-multiplicity work would support it rather than undermine it. But if “continuization” means what the programme says—making the population, and only the population, continuous—then Theorem 3 has no nondegenerate mirror. The proponent’s own concession about joint scaling is therefore not a minor technical weakness but the entire substance of the proposed analogue.
I would not claim that this defeats every conceivable modelling extension. The honest negative conclusion is conditional: Theorem 3 cannot support the universal negative only because the proposed joint-scaling model is plausibly worthwhile. Under the programme’s strict population-only reading, however, the anchor fails.
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.