| paper | Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements |
| authors | — |
| venue | AAAI 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 19
statement extracted from the paper’s text layer
Given rational masses of agent types, each with a positive entitlement and additive costs for finitely many recurring indivisible chore classes, and rational per-capita supplies of those classes, decide whether and constructively output a finite-support mass allocation over integral chore bundles such that every positive-mass agent assignment satisfies 1WEF against every other assignment, with complexity polynomial in the type count, chore-class count, and binary input length.
Agent types carry entitlement and per-class additive costs; masses describe population multiplicity; decision variables assign mass to integral bundle configurations; feasibility requires complete use of chore supplies and ex-post 1WEF for every bundle in the support.
The type-level picking sequence does not directly preserve the paper's individual latest-pick invariant, so polynomial-bit batching and polynomial-support representations for the integral-bundle distribution remain unproved.
fatal: False
The mirror targets Theorem 19's polynomial-time 1WEF chore-allocation result; it leaves the goods-side WEFX results, WEFX and XWEF impossibility results, and the two-agent approximation results unaddressed.
The strongest positive case is a population-continuous mirror of Theorem 19, rather than of the paper’s two-agent WEFX results.
Theorem 19, proved in this paper using Lemmas 20 and 21, states that for any number of agents, arbitrary positive weights, and additive chore costs, a complete 1WEF allocation can be computed in polynomial time. This is the paper’s clearest many-agent computational anchor.
Call the mirror Continuous 1WEF Chore Allocation. An instance contains:
A solution assigns mass \(\lambda_{\theta,b}\) of type-\(\theta\) agents to each integral bundle \(b\in\mathbb Z_{\ge0}^{G}\). Thus every individual still receives an indivisible bundle; only the population assignment is continuous. The constraints are
\[ \sum_b\lambda_{\theta,b}=\mu_\theta \]
for every type \(\theta\), and
\[ \sum_{\theta,b}\lambda_{\theta,b}b_g=q_g \]
for every chore class \(g\). The allocation is complete because every chore copy is assigned.
For every pair of positive-mass assignments \((\theta,b)\) and \((\phi,d)\), require
\[ \frac{\min_{g:b_g>0} c_\theta(b-e_g)}{w_\theta} \le \frac{c_\theta(d)}{w_\phi}, \]
with the natural zero convention for an empty own bundle. This is exactly the paper’s 1WEF condition, applied to every individual bundle appearing with positive mass. The computational task is to output a finite-support mass allocation satisfying these constraints. There is no additional welfare objective: the objective is exact 1WEF feasibility and construction, just as in Theorem 19.
The regime is plausible. Think of a large care, staffing, or public-service system with millions of worker slots but only a few dozen contract/location/skill types. Each type has the same workload entitlement and the same costs for a finite catalogue of recurring undesirable shifts or tasks. The chores remain indivisible shifts or assignments, and the number of agents is much larger than the number of types. A type is complete: it includes entitlement, all relevant costs, and every other parameter used by the allocation problem.
This is a genuine high-multiplicity lift. Given rational \(\mu\) and \(q\), choose a common denominator \(N\), create \(N\mu_\theta\) named agents of each type, and \(Nq_g\) indivisible chore copies of each class. Applying Theorem 19 to that finite instance and aggregating identical agents gives a feasible \(\lambda\). Conversely, any rational finite-support \(\lambda\) can be expanded into such a finite allocation. Thus the mirror has the desired two-way dictionary. Population mass is fractional; individual bundles and chore copies are not.
I would expect this mirror to be Class A, but the continuous theorem would be new. Algorithm 3’s weighted picking sequence is especially promising: among identical agents, the counters \(t_i/w_i\) can be maintained by type, and repeated identical chores can be processed in batches rather than one copy at a time. Additivity means that the “cheapest remaining chore” operation reduces to a type–chore-class comparison. The main target would be a running time polynomial in the number of agent types, chore classes, and input bit-length, rather than in the expanded population size \(N\).
The mirror generates several concrete questions: can Algorithm 3 be batched with polynomial bit complexity when masses and supplies are binary-encoded rationals; can every solution be represented with polynomial support; and what is the minimum-cost allocation among all continuous 1WEF allocations? A further direction is to ask whether the paper’s impossibility results for WEFX and XWEF survive when agents may be split across integral bundles by mass.
I would not use Theorems 8 or 9 as anchors: they are finite impossibility constructions rather than computational results. Nor would I rely on Theorems 10 or 11, since their two-agent assumptions do not naturally scale to a population of many agents. Theorem 19 is enough for a strong case.
The weakest point is that the paper’s \(O(l^2)\) algorithm is polynomial in the explicitly listed number of chores, not automatically in the logarithmic description length of enormous repeated supplies. “Batching the algorithm” is therefore a research claim, not something already proved. There is also a real modelling choice in replacing arbitrary item-specific chores by recurring chore classes. But this is a defensible high-multiplicity regime, not a fractional relaxation of indivisibility, and it preserves the paper’s central question: how should unequal-entitlement agents be assigned indivisible chores so that no one envies another beyond one chore?
Theorem 19 is the only serious anchor, and it is also where the negative case is weakest. Still, the proposed mirror has a fundamental trilemma.
1WEF is an ex-post, individual-level property. It depends on the particular bundle an agent receives and on the particular chore removed from that bundle. Aggregate per-type loads cannot express it. For example, with chore costs \(6,6,1\), assigning \(\{6,6\}\) to one agent and \(\{1\}\) to another violates 1WEF, whereas assigning \(\{6\}\) and \(\{6,1\}\) satisfies it. Yet both allocations have exactly the same aggregate per-agent item totals. Replacing bundles by expected loads therefore changes the theorem into divisible, ex-ante fair division, outside ChoCo’s scope.
The proposed \(\lambda_{\theta,b}\) repair preserves the theorem only by retaining a distribution over integral bundles. But then the continuous population has not replaced the individual allocation problem; it has wrapped a configuration encoding around it. The paper’s proof depends on each named agent’s counter \(t_i\), latest pick, and final chore. A type-level counter is insufficient: identical agents can have different bundles and different last chores. To preserve the invariant, the formulation must retain the distribution of those individual states. If that distribution has compact support, proving such a bound is a new high-multiplicity configuration problem; if it does not, the supposed continuum has simply reproduced the discrete allocation at a different encoding.
The same trilemma defeats the stronger variants. Aggregate flows lose ex-post 1WEF; lotteries impose only ex-ante fairness; replacing “one chore” by a positive mass changes the fairness axiom; and recurring chore classes make this primarily a two-sided high-multiplicity resource-allocation problem rather than a population-continuization of the paper’s result. The staffing scenario is plausible, but plausibility of repeated types does not make an inherently bundle-level guarantee a population property.
This is not an airtight red verdict. The proposed \(\lambda\)-model is a legitimate high-multiplicity question, and existing high-multiplicity work would support—not undermine—that modelling choice. The honest conclusion is that the universal negative case fails: Theorem 19 survives as a defensible, though probably technically modest, continuous mirror.
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.