| paper | Fair and Efficient Allocation of Indivisible Chores with Surplus |
| authors | Hannaneh Akrami, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta |
| 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 1
statement extracted from the paper’s text layer
Given a finite type set \(\Theta\), rational distribution \(\mu\), additive disutilities \(d_\theta(c)\) for chore kinds \(c\in C\), rational base occurrence masses \(q_c\), and a finite admissible family \(\mathcal B\subseteq\mathbb Z_{\ge0}^{|C|}\) of whole bundles, find \(x_{\theta,B}\ge0\) and duplicate masses \(\sigma_c\ge0\) satisfying \(\sum_B x_{\theta,B}=\mu_\theta\) and \(\sum_{\theta,B}x_{\theta,B}B_c=q_c+\sigma_c\), minimizing \(\sum_c\sigma_c\) or deciding whether it is at most \(1\), subject to support-wise \(\mathrm{EF1}\) and fractional Pareto optimality under the same augmented supply \(q+\sigma\).
A high-multiplicity recurring-workload allocation model with employee-type mass \(\mu_\theta\), repeated chore-kind supply \(q_c\), whole-bundle configurations \(B\), allocation masses \(x_{\theta,B}\), duplicate supply \(\sigma_c\), and objective \(\min\sum_c\sigma_c\), subject to support-wise \(\mathrm{EF1}\) and \(\mathrm{fPO}\).
Theorem 1 is polynomial in the expanded \(n,m\), not in the number \(\tau\) of types; merging same-type agents loses support-specific bundle information, and without a finite workload bound the configuration space may be infinite.
fatal: False
The mirror covers Theorem 1's \(\mathrm{EF1}\), \(\mathrm{fPO}\), and \((n-1)\)-surplus guarantee and its polynomial construction; it leaves Theorem 2's exactly-three-agent result and the auxiliary market propositions untouched.
The strongest positive case is Theorem 1, and I would build the mirror around that result alone.
Theorem 1 is proved in this paper. It states that, for additive disutilities, an allocation with at most \(n-1\) surplus chores exists that is both EF1 and fPO, and that such an allocation is computable in polynomial time. The paper’s use of a polynomial-time approximate CEEI algorithm is cited from elsewhere, but the EF1–fPO–surplus theorem itself is proved here.
A natural high-multiplicity setting is a large organisation with a recurring workload: reviewing papers, processing applications, auditing files, or performing household or corporate chores. There are \(\tau\) employee types, where a type records the complete disutility vector \(d_\theta(c)\) for the chore categories \(c\). The population is represented by \(\mu_\theta\), the fraction of employees of type \(\theta\), with \(\tau\) small compared with the number of employees. The paper itself gives essentially this interpretation when it motivates duplicate chores by repeated reviewing or recurring monthly chores.
The chores remain indivisible for every individual employee. What becomes continuous is the distribution of employees among types and among whole bundles. If \(N\) is a finite population realizing \(\mu\), then \(N\mu_\theta\) employees have type \(\theta\). A normalized chore supply \(q_c\) means \(Nq_c\) distinct occurrences of chore \(c\). Thus the continuum is the limit of ordinary instances with many identical agents and repeated discrete chore occurrences; it is not a model in which one employee receives \(0.37\) of a chore.
I would call the resulting problem Continuous EF1–fPO Surplus Allocation. An instance consists of:
The decision variables are \(x_{\theta,B}\ge 0\), the mass of type-\(\theta\) employees receiving the whole bundle \(B\), and \(\sigma_c\ge0\), the mass of duplicate occurrences of chore \(c\). They must satisfy \(\sum_{B\in\mathcal B}x_{\theta,B}=\mu_\theta\) for every \(\theta\), and \(\sum_{\theta,B}x_{\theta,B}B_c=q_c+\sigma_c\) for every chore \(c\). The normalized surplus is \(\sum_c\sigma_c\).
The output must satisfy three conditions. First, its surplus is at most one unit per unit population, \(\sum_c\sigma_c\le1\), which is the continuum counterpart of the paper’s \(n-1\) bound: for a finite population of size \(N\), the bound becomes \((N-1)/N\).
Second, it is EF1 at the individual level. Thus, for every source type \(\theta\), every bundle \(B\) receiving positive mass, and every target bundle \(B'\) receiving positive mass, either \(d_\theta(B)\le d_\theta(B')\), or there is a chore \(c\) in \(B\) such that \(d_\theta(B-\{c\})\le d_\theta(B')\). This retains the paper’s exact chores version of EF1 rather than replacing it by a type-average condition.
Third, it is fPO relative to the same augmented chore supply \(q+\sigma\). Formally, there must be no measurable fractional reassignment \(z\) of the chore occurrences such that every individual’s disutility weakly decreases and a positive mass of individuals strictly improves. The produced allocation still gives each individual an integral bundle; fractional allocations appear only in the Pareto-dominance test, exactly as in the paper’s definition of fPO.
The computational version asks whether such an allocation exists with \(\sum_c\sigma_c\le1\), and the natural optimization version minimizes \(\sum_c\sigma_c\). For rational data, multiplying by a common denominator turns a continuous solution into a finite high-multiplicity allocation: \(N\mu_\theta\), \(Nq_c\), \(Nx_{\theta,B}\), and \(N\sigma_c\) are all integer counts. Conversely, finite allocations can be summarized by their empirical type-and-bundle masses. That gives the required two-way high-multiplicity dictionary.
I would expect this mirror to be Class A, at least in the bounded-workload regime. The paper’s proof already has the right architecture: compute an approximate Fisher equilibrium, make the payment graph acyclic, and round while preserving a payment-EF1 property. With a continuum of identical agents, the rounding can split the mass of one type among several whole bundles without making arbitrary named-agent choices. A weighted payment graph over types should replace the graph with \(n\) duplicated agent vertices, and the \(n-1\) discrete surplus bound should become a total surplus-mass bound of at most one. The Fisher-equilibrium certificate should continue to provide fPO.
The main further questions are computational rather than merely definitional: can the type-aggregated algorithm run in time polynomial in \(\tau\), the number of chore kinds, and the encoding length, rather than in the expanded population size \(N\)? Can the minimum surplus be computed exactly? When is zero surplus possible? Can the bound \(1\) be improved in the continuum, even though the finite algorithm’s \(n-1\) bound is tight for that algorithm? And can one characterize when the EF1 support of each type has a polynomial-size representation, avoiding enumeration of all bundles?
My weakest point is that Theorem 1’s polynomial running time is stated in \(n\) and \(m\), not in the number of distinct agent types. The paper does not itself prove that its algorithm compresses to \(\mathrm{poly}(\tau)\), and EF1 is a condition on every bundle in the support, not merely on average type disutilities. Also, if one insists on a fixed finite set of physical chores while the population grows, the limit is degenerate: almost everyone receives nothing. The mirror therefore needs the paper’s own recurring-workload interpretation, with discrete chore occurrences scaling alongside the large population.
That is a real limitation, but it does not undermine the core case. Theorem 1 supplies a named polynomial result whose essential mechanism is already market-based and whose finite instances naturally admit many indistinguishable agents. I would not use Theorem 2 as a second anchor: its restriction to exactly three agents is much less convincingly a population continuization.
The strongest negative case is that the proponent has not actually continuized Theorem 1; they have proposed a new repeated-workload configuration problem inspired by it.
Theorem 1 is a genuine computational anchor, so the “no named result” objection is unavailable. Nor is identity a decisive objection: with complete disutility vectors, agents of one type are interchangeable. The real problem is scaling the chores.
If the paper’s finite chore set \(M\) is held fixed while the population grows, the mirror degenerates. Once \(N>|M|\), some agents receive nothing. Empty bundles have disutility \(0\), so EF1 is immediate, and no Pareto improvement can strictly improve an agent already at \(0\). Thus zero surplus is already EF1 and fPO. The theorem’s content disappears.
The proposed repair—scaling chore supply with population—is plausible, but it is a substantive extension. With repeated chore kinds, an individual bundle is a multiset \(b\in\mathbb Z_{\ge 0}^{|C|}\), not a subset of the paper’s finite item set. In the limit, the configuration family is generally infinite. If one fixes a finite catalogue \(\mathcal B\), one has imposed a new workload bound; if one allows all bundles, the variables \(x_{\theta,B}\) do not give a finite algorithm. The main difficulty becomes configuration generation and support-wise EF1 constraints, neither of which is supplied by Theorem 1.
In particular, the suggested “weighted payment graph” is not an automatic compression. The proof uses separate agent vertices because different copies of the same type may receive different bundles and undergo different edge deletions. Merging them into one weighted vertex loses precisely that information. Splitting the type back into support vertices can require a number of pieces depending on the clone denominator or on the number of chores, so the paper’s polynomial algorithm in \(n\) does not imply an algorithm polynomial in \(\tau\). EF1 is especially problematic: it constrains every pair of bundles in the support, through a disjunction involving removal of one particular chore, rather than an aggregate type average.
The normalized surplus bound also has no uniquely stable limit. The finite guarantee becomes \(\sigma\le (N-1)/N\), hence \(\sigma\le1\), but one unit of surplus mass is macroscopic—roughly one extra chore per employee—not an infinitesimal remnant of the finite \(n-1\) correction. The paper’s tight example makes the instability clear: one fixed chore gives the trivial fixed-supply limit, while \(N\) repeated copies of that chore let every agent receive one with zero surplus.
So, under a strict direct-mirror standard, the negative case is strong: fixed supply is vacuous, while scalable supply, multiset configurations, and type-split support create a new model whose compact complexity is wholly unproved.
But I cannot honestly turn that into the requested universal verdict. The paper itself motivates repeated reviewing and recurring chores, and the proponent’s whole-bundle configuration measure has a valid rational-clone interpretation. Asking whether EF1 and fPO admit a \(\mathrm{poly}(\tau,m,L)\) high-multiplicity algorithm is a legitimate computational question. The objection establishes “extension rather than direct mirror,” not “no worthwhile mirror in any scenario.” I would therefore reject a red verdict; at most this is an amber warning about fidelity and missing compression results.
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.