| paper | Fairly Dividing Mixtures of Goods and Chores under Lexicographic Preferences |
| authors | — |
| venue | AAMAS 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 (EFX+PO when some agent has a top-ranked good)
statement extracted from the paper’s text layer
Given a finite set of complete lexicographic agent types \(T\), rational masses \(\mu_t\), recurring item classes \(K\) with rational per-capita supplies \(\beta_k\), and type-specific good/chore classifications and importance orders, under the promise that some positive-mass type has a good as its top-ranked class, output a census \(z_{t,B}\ge 0\) over integral bundles \(B\in\mathbb{Z}_{\ge 0}^{K}\) satisfying \(\sum_B z_{t,B}=\mu_t\) and \(\sum_{t,B}z_{t,B}B_k=\beta_k\). Require that every type receiving \(B\) satisfies EFX against every supported bundle \(D\), after deleting any relevant good copy from \(D\) or any relevant chore copy from \(B\), and that no feasible census admits a type-preserving mass coupling that weakly improves every agent and strictly improves positive mass.
A high-multiplicity allocation of recurring indivisible item copies: \(T\) is the finite set of complete agent types, \(\mu\) is their mass distribution, \(\beta\) gives per-capita item supplies, and \(z_{t,B}\) records the mass of type \(t\) receiving integral bundle \(B\); EFX is support-wise and PO is defined by mass couplings.
Replacing distinct items by interchangeable recurring classes changes the symmetric-difference semantics and leaves it unproved that batch elimination preserves EFX+PO or has a polynomial-size representation.
fatal: False
The mirror covers Theorem 3's EFX+PO result and Theorem 1's EF-existence decision problem; it leaves Theorem 2's non-existence result, Theorem 4's MMS algorithm, and the remaining propositions and corollaries.
The strongest case is a repeated-batch, high-multiplicity mirror of the paper’s lexicographic allocation model. It is an extension of the paper’s fixed-item model, but a credible one: the population becomes continuous while each individual still receives an indivisible bundle.
Let \(T\) be a finite set of complete agent types. A type includes its good/chore classification and its strict importance order over finitely many recurring item classes \(K\). The input gives rational masses \(\mu_t\), with \(\sum_t\mu_t=1\), and rational per-capita supplies \(\beta_k\) of each item class. A bundle is an integer vector \(B\in\mathbb Z_{\ge0}^{K}\): its coordinates count indivisible copies, so no item is fractionally assigned.
For a type \(t\), compare bundles lexicographically by the highest-ranked class whose multiplicity differs: more copies are preferred for a good class and fewer copies for a chore class. An allocation is a bundle census \(z_{t,B}\), where \(z_{t,B}\) is the mass of type-\(t\) agents receiving the whole bundle \(B\). It must satisfy
\[ \sum_B z_{t,B}=\mu_t \]
and
\[ \sum_{t,B} z_{t,B}B_k=\beta_k \]
for every item class \(k\). Thus mass may split across whole bundles, but an individual bundle remains integral.
This has the required high-multiplicity interpretation. If \(N\) clears all denominators, then \(N\mu_t\) gives the number of named agents of type \(t\), \(N\beta_k\) gives the number of copies of item class \(k\), and \(Nz_{t,B}\) gives the number of agents receiving \(B\). Conversely, every such finite repeated-agent/repeated-item allocation aggregates to a rational census.
My lead anchor is Theorem 3, “EFX+PO when some agent has a top-ranked good,” proved in this paper in Section 4.3. It states that, for a mixed lexicographic instance in which some agent’s top-ranked item is a good, an EFX and Pareto-optimal allocation always exists and can be computed in polynomial time.
The corresponding continuous problem is:
\[ \textsc{Batch-Lex-EFX+PO}_{\infty}. \]
The input is a rational type-mass vector \(\mu\), rational item supplies \(\beta\), type-specific good/chore classifications and importance orders, with the promise that some positive-mass type \(t\) has a good as its top-ranked class. The task is to output a bundle census \(z\) satisfying:
The Pareto condition should be interpreted agentwise, not merely by average utility. Formally, there must be no alternative census \(z'\) together with a coupling \(w^t_{B,D}\) of old and new bundles such that, for every type \(t\), almost every reassigned agent weakly prefers \(D\) to \(B\), with positive mass strictly preferring it. This is exactly the anonymous mass version of Pareto dominance: clearing denominators turns such a violation into a Pareto improvement for the corresponding finite clone instance.
This is recognizably the authors’ problem. The fairness predicate is still EFX, efficiency is still Pareto optimality, preferences are still lexicographic, and goods and chores may be subjective. The only substantive change is that the setting is a large population receiving recurring copies of roles, duties, supplies, or service slots. That is plausible for hospital systems, public housing, large course cohorts, or workforce scheduling: millions of agents may fall into a small number of priority profiles, while the relevant items recur at positive density.
I expect the bounded-load version of \(\textsc{Batch-Lex-EFX+PO}_{\infty}\) to be Class A. Theorem 3’s proof is not based on delicate individual identities. It repeatedly selects an agent with a highest-ranked achievable good, assigns it together with suitable common chores, and eliminates it. In a high-multiplicity setting, the natural analogue is to eliminate positive masses of exchangeable agents in batches, with transportation or configuration constraints handling the repeated copies. The open algorithmic issue is whether this greedy structure admits a polynomial-size type-level implementation without expanding rational denominators.
The main follow-up questions are whether one can prove polynomial support for \(z\), whether the batch elimination can be implemented in time polynomial in \(\tau=|T|\), \(|K|\), and the bit length of \(\mu,\beta\), and whether the EFX guarantee survives arbitrary mass splitting across bundle configurations. If it does, this would be a genuine Class A result of exactly the kind ChoCo is seeking: an indivisible fair-division problem becomes tractable after replacing many named agents by a compact type distribution.
A useful second anchor is Theorem 1, “EF for chores,” also proved in this paper in Section 4.1. It states that deciding whether a chores-only lexicographic instance admits an envy-free allocation is NP-complete.
Its continuous counterpart is:
\[ \textsc{Batch-Lex-EF-Chores}_{\infty}. \]
Here every item class is a chore for every type. The input is \((T,\mu,K,\beta,\triangleright)\), and the question is whether there exists a feasible census \(z\) such that, whenever \(z_{t,B}>0\) and \(z_{u,D}>0\),
\[ B\succeq_t D. \]
In words, every positive-mass agent of type \(t\) must weakly prefer its own bundle to every bundle received by any other positive-mass type. A feasible census is the certificate for YES; otherwise the answer is NO.
The natural regime is a large workforce receiving recurring unpleasant duties, with perhaps tens of chore-preference types rather than millions of individually different rankings. I would expect the genuine high-multiplicity, bounded-type version to be Class A or at least substantially easier than the discrete problem: the individual-agent combinatorics in Theorem 1 may collapse into threshold and transportation constraints over types. But I would not claim this without a proof. Integral bundle configurations and binary-encoded supplies could produce Class C hardness of their own.
If the number of types is allowed to grow with the population, hardness transfers trivially: assign each named agent its own type and give each type mass \(1/N\). That is a Class B slice, but it is not evidence against the compressed mirror. The interesting ChoCo question is whether Theorem 1’s hardness survives when \(N\) is enormous and \(\tau\ll N\).
The weakest point is the need to scale item supply along with population. With the paper’s fixed finite item set and \(N\to\infty\), almost everyone receives the empty bundle, so EFX and PO become largely vacuous. Repeated item copies therefore are not optional if the mirror is to remain meaningful. This makes the proposal an extension rather than a literal fixed-inventory limit, and repeated copies require an explicit anonymous multiset interpretation of lexicographic preferences. If the authors reject recurring item classes, the mirror largely collapses. If they accept them—as seems natural for recurring duties, housing slots, medical resources, and role assignments—the two problems above preserve their computational questions while exposing exactly where high multiplicity may remove or retain the original difficulty.
I would not anchor on Theorem 2, since it is a non-existence result rather than a computational classification, and I would postpone Theorem 4 because MMS depends explicitly on the finite number of agents and needs a nontrivial continuum benchmark. The proposed mirror therefore covers Theorem 3 emphatically and Theorem 1 as a harder companion, rather than stretching to cover the whole paper.
The strongest negative case is that the paper’s two computational anchors do not survive a population limit without changing the operative problem.
With the paper’s fixed set of \(m\) indivisible items, letting the number of agents grow makes the continuum degenerate: at most \(m\) agents receive anything, so almost every agent receives the empty bundle. Under an almost-everywhere interpretation, EF, EFX, and Pareto improvements largely ignore the finitely many exceptional recipients. Under a pointwise interpretation, those exceptional agents remain individually named, defeating the aggregation.
The proposed rescue—replicating items into recurring classes—has a deeper difficulty. If copies retain distinct ranks, they are not genuinely interchangeable, so the model still contains the paper’s named-item structure. If copies are identified and preferences become lexicographic over multiplicities, that is a legitimate multi-unit extension, but not the paper’s lexicographic preference model: “remove any item” becomes “decrease a class count,” and the symmetric-difference argument over a uniquely most-important item changes fundamentally.
This matters especially for Theorem 1. Under strict lexicographic preferences, two agents of the same type cannot receive distinct bundles in an envy-free allocation. If \(B\neq D\), one is strictly preferred, so the agent receiving the worse bundle envies the other. Hence a continuous census cannot use mass-splitting to smooth indivisibility: every positive-mass type must effectively receive one bundle. The magnitudes of the masses then disappear from the EF predicate; only which types and bundles have positive support matters. The proposed \(\textsc{Batch-Lex-EF-Chores}_{\infty}\) is therefore a multi-unit integer allocation problem with type multiplicities, not a population-continuization in which society’s distribution is computationally operative.
Theorem 3 is no safer. Its proof repeatedly eliminates one agent, gives that agent a specially chosen bundle, and uses the resulting individual ordering in its EFX and Pareto arguments. Eliminating a positive mass of agents of one type requires assigning them identical bundles; assigning different bundles creates cross-support EFX constraints, and the original induction no longer applies. The best repair is to formulate a new configuration-support problem over compatible bundles. That may be interesting, but it is not a continuous lift of the theorem’s algorithm; it is a new multi-unit fair-division problem whose fairness region is nonconvex and whose mass variables do not themselves relax EFX.
One could instead make masses matter by using ex-ante, average, or measure-valued EF/EFX. But then the guarantee is no longer the paper’s agentwise EF or EFX; it moves toward probabilistic or fractional outcome continuity, which the ChoCo programme explicitly places outside scope.
This negative case is not airtight. Recurring duties, course slots, housing units, or medical supplies do provide a plausible high-multiplicity regime, and a carefully defined multi-unit version could be worthwhile. The honest conclusion is therefore narrower: the proponent has not shown a clean continuous mirror of Theorems 1 or 3. Their proposal is either degenerate, preserves the individual problem almost unchanged, or changes fairness into a different notion. But claiming that no author-recognizable high-multiplicity fair-division model could ever be valuable would be too strong.
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.