| paper | Fair Division of Chores with Budget Constraints |
| authors | Edith Elkind, Ayumi Igarashi, Nicholas J. Teh |
| venue | SAGT 2024 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m=r\), \(\tau\), and \(L\); an envy-free allocation always exists under the unrestricted residual-support condition. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 9
Given budget types \(b\in[\tau]\) with masses \(\mu_b>0\), budgets \(B_b\), and divisible chore types \(k\in[r]\) with per-capita supplies \(q_k\), find per-agent bundles \(X_b=(X_{b,k})_{k\in[r]}\) and residual supplies \(R_k=q_k-\sum_b\mu_bX_{b,k}\ge0\) such that \(\sum_k s_kX_{b,k}\le B_b\), every \(Y\le X_b\) with \(\sum_k s_kY_k\le B_{b'}\) satisfies \(\sum_k d_kY_k\le\sum_k d_kX_{b'}\), and every finite \(Y\) supported on \(\{k:R_k>0\}\) with size at most \(B_{b'}\) satisfies the same inequality; find such an allocation in time polynomial in \(\tau\), \(r\), and the encoding length.
A symmetrized divisible-chore allocation model over budget types: \(\mu_b\) is population mass, \(X_b\) is the common bundle of type \(b\), \(\sum_b\mu_bX_{b,k}\le q_k\) are aggregate capacity constraints, and the objective is to find an EF allocation including the residual housekeeper condition.
The proponent treats \(X_b=x_b/\mu_b\) as automatically representing every individual bundle of type \(b\), without fully justifying symmetrization or the finite-bundle interpretation of a positive residual supply.
fatal: False
The mirror covers the general EF2 algorithmic result and the polynomial-time divisible-EF result, while leaving the EFX existence theorem and special-case EF1 results unexamined.
I think there is a genuine continuous mirror, with the strongest case coming from the paper’s general EF2 result rather than its household story. The right regime is a large workforce performing recurring, standardized tasks: many employees, a small number of contract or workload classes, and many repeated copies of each task type. A household of four people is not a useful limit object; a large maintenance, care, or operations workforce is.
My lead anchor is Theorem 3 (thm:ef2), proved in this paper, together with Theorem 2’s proof that the underlying DensestFirst algorithm runs in \(O((n+m)^2)\) time. Theorem 3 says that, for indivisible chores with objective sizes \(s(c)\), objective disutilities \(d(c)\), and agent-specific budgets, DensestFirst returns an EF2 allocation. The algorithm repeatedly chooses a live agent with minimum current disutility, gives that agent a feasible remaining chore of maximum density \(d(c)/s(c)\), breaking ties toward smaller chores, and removes an agent when no remaining chore fits her budget. The resulting allocation, including the housekeeper’s residual bundle, satisfies the paper’s EF2 condition for every agent and the housekeeper.
The corresponding problem is:
High-Multiplicity Indivisible EF2 Chore Allocation. The input contains finitely many budget types \(b\in[\tau]\), with population masses \(\mu_b\ge 0\) and \(\sum_b\mu_b=1\), and finitely many chore types \(k\in[r]\). Type \(b\) has budget \(B_b\); chore type \(k\) has size \(s_k\), disutility \(d_k\), and per-capita supply \(q_k\). A finite realization with population \(N\) has \(N\mu_b\) agents of type \(b\) and \(Nq_k\) indistinguishable copies of chore type \(k\).
An integral bundle is \(z\in\mathbb Z_{\ge0}^r\), with \(s(z)=\sum_k s_kz_k\) and \(d(z)=\sum_kd_kz_k\). The solution is a finite-support distribution \(\lambda_{b,z}\), where \(\lambda_{b,z}\) is the mass of type-\(b\) agents receiving bundle \(z\), satisfying \(\sum_z\lambda_{b,z}=\mu_b\), \(s(z)\le B_b\) whenever \(\lambda_{b,z}>0\), and \(\sum_{b,z}\lambda_{b,z}z_k\le q_k\) for every chore type \(k\). The unused mass \(u_k=q_k-\sum_{b,z}\lambda_{b,z}z_k\) belongs to the housekeeper.
For each target type \(b'\), let \(D_{b'}\) be the smallest disutility of a bundle used by that type. For every used source bundle \(z\), every \(b'\), and every integral subbundle \(y\le z\) with \(s(y)\le B_{b'}\), the allocation must satisfy \(d(y-h)\le D_{b'}\) for some subbundle \(h\le y\) containing at most two chores. The same requirement applies to every finite \(y\) that can be formed from chore types with positive residual mass \(u_k>0\), representing the housekeeper’s EF2 condition in the \(N\to\infty\) limit.
This is a population-continuous question, not a fractionalization of an individual chore: every unit of agent mass receives an integral bundle in the finite realization. The fractional \(\lambda_{b,z}\) records only how much of the population receives each integral bundle. The task supplies must scale with population; otherwise a fixed finite chore set would leave almost every agent empty-handed. That scaling is forced by the population mirror, not an attempt to replace the paper’s problem by divisible allocation.
I would expect this problem to be a Class A candidate, though not claim that Theorem 3 proves it automatically. The proof of EF2 uses density orderings, budget feasibility, and comparisons between bundles, rather than the names of individual agents. Those arguments appear amenable to bulk processing over budget types, with a configuration or flow formulation whose size depends on \(\tau\), \(r\), and the input precision rather than on \(N\). The central algorithmic question is whether the relevant configuration pricing problem can be separated efficiently. It could instead reveal continuum-specific hardness, particularly with binary-encoded sizes, but it is plainly the same computational question in a high-multiplicity regime.
A second, cleaner anchor is Theorem 9 (thm:divisible_ef), proved in Appendix B. It states that, for divisible chores under budget constraints, an EF allocation exists and can be computed in polynomial time. In the formal model this concerns objective sizes and disutilities; the appendix observes a stronger version allowing subjective disutilities.
Its population mirror is Population-Continuous EF for Divisible Chores. Given budget masses \(\mu_b\), budgets \(B_b\), and per-capita chore supplies \(q_k\), the decision variables are \(x_{b,k}\), the amount of chore type \(k\) assigned to the mass of agents of type \(b\). The average bundle of type \(b\) is \(X_b=(x_{b,k}/\mu_b)_k\), with \(\sum_k s_kX_{b,k}\le B_b\). The residual \(R=q-\sum_bx_b\) is the housekeeper’s per-capita residual supply.
The requested solution is an \(x\) such that, for every pair of types \(b,b'\), every fractional subbundle \(Y\le X_b\) with \(s(Y)\le B_{b'}\) satisfies \(d(Y)\le d(X_{b'})\); the analogous condition must hold for every feasible fractional bundle drawn from the residual supply \(R\). This is exactly the paper’s EF predicate, with the society represented by masses of budget types rather than named agents. I would expect this version to be Class A: the paper’s density-domination and \(LP_1/LP_2\) machinery should compress naturally from \(n\) agents to \(\tau\) agent types and capacity constraints such as \(\sum_kx_{b,k}s_k\le\mu_bB_b\).
The paper’s Section 6 is not a novelty collision. Its chores are divisible, but its society is still a finite list of named agents. The proposed mirror makes the population itself continuous; in the EF2 mirror, even the individual bundles remain indivisible.
The weakest point is the indivisible EF2 formulation’s limiting treatment of the housekeeper and the two-chore relaxation. A referee could object that EF2 is inherently an individual-level notion and that taking \(N\to\infty\) changes the residual-pool semantics. I think that objection identifies a real technical task—finite-\(N\) rounding and convergence should be proved—but not a fatal modelling flaw. The workforce scenario, the budget-type notion, and the repeated task supply are all natural high-multiplicity assumptions, and the resulting question is precise enough to be handed to an algorithm designer.
The supplied paper contains no named NP-hardness, coNP-hardness, \(\#\)P-hardness, W[1]-hardness, or FPT theorem, so I cannot honestly offer a hardness anchor. The positive case is therefore for a legitimate and potentially tractable population-continuous extension of their EF2 and divisible-EF problems, not for a demonstrated dissolution of discrete hardness.
The negative case is weaker than the proponent’s, because the paper has exactly the sort of named computational results the programme wants, and a credible high-multiplicity regime exists.
The best objection to the EF2 mirror is that the proposed formulation is not yet faithful. The paper’s EF2 condition compares every target agent’s bundle, whereas the proponent compares against \(D_{b'}\), the minimum disutility among bundles used by budget type \(b'\). That is unnecessarily strong. A faithful version must quantify over every bundle \(z'\) with \(\lambda_{b',z'}>0\). Likewise, the housekeeper’s condition cannot merely inspect finite bundles formed from the normalized residual \(u_k\): if \(u_k>0\), then a realization with population \(N\) contains \(Nu_k\) copies, so every fixed finite bundle of that chore type eventually becomes available.
More seriously, once these corrections are made, the problem is no longer a compressed application of DensestFirst. The algorithm’s state is the distribution of integral bundles, not merely the masses of budget types. Its minimum-disutility choice and its EF2 proof depend on the evolving order statistics of individual bundles. A faithful high-multiplicity formulation therefore becomes a configuration problem over integral bundles, potentially with exponentially many configurations. That is a new packing-and-fairness problem, not something Theorem 3 automatically solves. Still, this is not a valid objection under the programme’s rules: configuration LPs and their pricing problems are precisely the sort of computational question the programme is meant to expose. With positive chore sizes and bounded budgets, each bundle is finite, and \(\lambda_{b,z}\) is a genuine active population variable. The workforce scenario is also entirely plausible. Thus this anchor survives the negative case.
The divisible-EF anchor has a sharper formulation defect. The vector \(X_b=x_b/\mu_b\) is an average bundle, but EF in the paper is an individual condition. An average bundle can satisfy EF even when some individual bundles do not. The repair is natural, however: because sizes and disutilities are objective and chores are divisible, agents of the same budget type can be symmetrized and all assigned their type-average bundle. This yields a legitimate \(\tau\)-type high-multiplicity problem. In that repaired version, population mass is not merely notation: it determines aggregate chore capacities, while the per-agent bundles remain fractional.
The housekeeper again requires care. If \(R_k>0\) is a positive residual per-capita supply, then the finite realization contains \(NR_k\) residual units. The limiting EF condition must therefore test every finite bundle of type \(k\), not only bundles bounded by the normalized vector \(R\). This is a non-commuting normalization issue, but it does not destroy the mirror; it supplies a precise proof obligation for the finite-to-continuum dictionary.
So the strongest honest case against is that both proposed statements are under-specified, and that the divisible version may collapse to a fairly routine \(\tau\)-type LP after symmetrization. Neither point defeats the corrected mirrors. The EF2 version is a particularly credible Class A/Class C candidate because its integral bundle distributions create a genuine configuration-pricing problem. I would not recommend a negative verdict: the supplied case has technical gaps, but it has not shown that any worthwhile continuous mirror is impossible.
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.