| paper | Best-of-Both-Worlds Fair Allocation of Indivisible and Mixed Goods |
| authors | Xiao-Lin Bu, Zihao Li, Shengxin Liu, Xinhang Lu, Biaoshuai Tao |
| venue | WINE 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 5.1
statement extracted from the paper’s text layer
Given \(m\) indivisible good kinds, rational \(0<a<b\), a finite type set \(T\subseteq\{a,b\}^{m}\) with rational mass distribution \(\mu\), and rational per-capita supplies \(\rho\in\mathbb{Q}_{\ge 0}^{m}\), compute a polynomial-size lottery or compact sampler over measurable assignments of integral bundles to a unit-mass population. Type-level expected bundles must satisfy ex-ante \(\mathrm{EF}\), while almost every realization must satisfy ex-post \(\mathrm{EFX}\) and continuum \(\mathrm{fPO}\), in time polynomial in \(m\), \(|T|\), and input length \(L\), rather than in the denominator-cleared population \(Q\).
A type-capacitated BoBW allocation model where \(\mu_\theta\) is agent mass, \(\rho_g\) is per-capita supply, and decision variables are type-level expected bundles and weights on integral bundle configurations. Feasibility requires aggregate supplies, ex-ante \(\mathrm{EF}\), almost-sure \(\mathrm{EFX}\), and almost-sure continuum \(\mathrm{fPO}\).
The opponent's strongest residual concern is that \(\rho\)-scaled instances are exact cloning closures, so the new difficulty may be succinct representation rather than a population-specific complexity phenomenon; the proponent identifies this as the compression problem but cannot yet show its eventual landscape.
fatal: False
The mirror covers Theorem 5.1's \(n\)-agent bi-valued indivisible-goods guarantee, including algorithmic construction, ex-ante \(\mathrm{EF}\), ex-post \(\mathrm{EFX}\), and ex-post \(\mathrm{fPO}\), with Lemmas 5.3–5.5 as supporting claims. It leaves the two-agent results and the mixed-goods results, including Theorems 3.2, 3.3, and 4.1, outside the mirror.
The strongest positive case is a population-continuized version of the paper’s indivisible-goods result, anchored in Theorem 5.1.
The natural regime is a large institution allocating many copies of a small catalogue of indivisible resources: for example, a university assigning millions of students to repeated course seats, devices, or service slots. Suppose there are \(n\gg m,\tau\) agents, but only \(\tau\) distinct valuation types. A type is the complete high/low valuation vector over the \(m\) good kinds: for \(\theta\subseteq [m]\),
\[ u_\theta(g)= \begin{cases} b & g\in\theta,\\ a & g\notin\theta, \end{cases} \qquad 0<a<b. \]
The society is a distribution \(\mu\) over the explicitly listed types, where \(\mu_\theta\) is the population fraction of type \(\theta\). Each good kind \(g\) has a per-capita supply \(\rho_g\). Thus a finite realization with population \(Q\) has \(Q\mu_\theta\) agents of type \(\theta\) and \(Q\rho_g\) distinct copies of good \(g\), whenever these quantities are integral. Goods remain indivisible for every individual agent; only the population and the aggregate supply scale continuously.
This is a sensible high-multiplicity regime: millions of agents share a small number of preference profiles, while the institution has proportionally many copies of each resource. It is not the degenerate model with a fixed finite set of goods and an ever-growing population, in which almost everyone receives nothing.
The anchor is Theorem 5.1, proved in this paper. It states:
In the indivisible-goods setting with bi-valued utilities, the paper’s Algorithm \(\ref{alg:efx_fpo}\) computes in polynomial time an integral allocation sampled from a randomized allocation that is ex-ante envy-free, ex-post EFX, and ex-post fractionally Pareto optimal.
The paper proves this through Lemma 5.3, which establishes that every sampled integral allocation is EFX; Lemma 5.4, which establishes ex-ante EF; and Lemma 5.5, which establishes fPO. The final polynomial-time claim is also proved in the paper. The fPO argument uses the cited First Welfare Theorem, but the algorithm and the combined guarantee are the authors’ result.
I would call the continuous problem Continuous BoBW-EFX-fPO Allocation.
An instance consists of:
A deterministic allocation is a measurable assignment \(A\) sending almost every unit-mass agent to an integral bundle \(A(\omega)\in\mathbb{Z}_{\ge0}^m\), with
\[ \int A_g(\omega)\,\diff\omega=\rho_g \]
for every good kind \(g\). If an agent receives \(k\) copies of a good kind, removing one good means replacing \(k\) by \(k-1\).
A randomized allocation is a lottery over such deterministic allocations. It must be type-symmetric ex ante: every agent of type \(\theta\) has the same expected bundle \(x_\theta\). The required conditions are:
\[ u_\theta(x_\theta)\ge u_\theta(x_{\theta'}) \]
for every pair of positive-mass types \(\theta,\theta'\), giving ex-ante EF; almost every realized allocation must satisfy EFX, meaning that for almost every pair of agents \(\omega,\omega'\), and every good copy in \(\omega'\)’s bundle,
\[ u_{\theta(\omega)}(A(\omega)) \ge u_{\theta(\omega)}(A(\omega')-\{g\}); \]
and every realization must be fPO: there must be no measurable fractional allocation \(Y\) of the same per-capita supplies such that every agent weakly improves and a positive-mass set improves strictly.
The computational task is to output a polynomial-size randomized sampler, or an equivalent compact finite-support description, whose realizations satisfy these conditions and whose type-level expected bundles satisfy ex-ante EF. The desired running time is polynomial in \(m\), \(\tau\), and the encoding length \(L\) of \(a,b,\mu,\rho\), rather than polynomial in the denominator-cleared population \(Q\).
This is recognisably the authors’ problem. The fairness notions are unchanged, the utilities are unchanged, and indivisibility is preserved at the individual level. The only new feature is that agents with the same complete valuation vector are represented by mass rather than by names. The paper’s own machinery suggests how the compression might work: the high-value relation becomes a capacitated type–good bipartite graph; maximum matchings become max-flow computations; minimal unmatchable groups become capacitated Hall obstructions; and repeated rounds, freezing, and reservation counters can potentially be batched instead of executed once per named agent. The Fisher-market price certificate used for fPO also has a natural type-capacitated interpretation.
I expect this mirror to be Class A: tractable through capacitated matching, configuration-style optimization, and a compact representation of the randomized allocation. But that is a conjectural classification for the continuized problem, not something already proved by Theorem 5.1. The finite theorem runs in polynomial time in the number of named agents; it does not automatically imply a running time polynomial in the binary encoding of huge multiplicities. Establishing that compression is precisely the new computational question.
The main further questions are whether exact ex-ante EF can be preserved by a polynomial-size type-level sampler; whether the permutation argument can be replaced by exchangeable random priorities over positive-mass type cohorts; and whether the bi-valued restriction remains the exact tractability boundary. The paper’s discussion of tri-valued impossibility makes the last question especially interesting: one could ask whether that obstruction survives unchanged in the high-multiplicity model or whether some part of it is caused by the small finite population.
My weakest point is the supply scaling. The paper starts with a finite set of goods, whereas my mirror introduces proportionally many copies of each good kind. Without that co-modification, a continuum of agents facing finitely many goods is not a meaningful analogue. A referee could therefore say that the model is a new repeated-resource problem rather than a literal replacement of \(n\) by a continuum. I think the objection is manageable: high multiplicity necessarily requires repeated copies when the original resources are indivisible, and the paper permits arbitrary additive goods, so identical copies are a legitimate special case. The genuine challenge is not whether the mirror exists, but whether Theorem 5.1’s individual-level algorithm can be compressed to the \((\mu,\rho)\) description. That is a substantive continuous-computation question, not merely a renaming of the paper’s lottery.
The source gate does not help the negative case: Theorem 5.1 is plainly a named polynomial-time computational result. The best objection is therefore that its proposed population mirror has no nontrivial population limit.
With the original finite inventory held fixed, the continuum collapses. If \(Q\) agents share \(m\) goods, each good has normalized mass \(1/Q\), which tends to zero. In the atomless limit the goods disappear from the measurable allocation almost everywhere, so EFX and fPO reduce to a trivial assignment residue. This is not a meaningful mirror of the paper’s BoBW problem.
The proposed repair—per-capita supplies \(\rho_g\)—is coherent, but it changes the object into a repeated-resource problem. For rational \(\mu\) and \(\rho\), clearing denominators produces \(Q\mu_\theta\) agents and \(Q\rho_g\) copies of each good kind. Conversely, any finite allocation with duplicate valuation profiles pushes forward to such a mass allocation. EFX is preserved cell by cell, and fPO is preserved by averaging any putative continuum improvement over the finite cells. Ex-ante EF is likewise exactly the same expected-utility inequality after symmetrizing agents of the same type.
Thus the scaled model is not a new continuum semantics for Theorem 5.1; it is the closure of its finite instances under cloning. The paper’s matching and freezing machinery would become capacitated matching and batched counters. If that compression succeeds, the result is a useful high-multiplicity implementation theorem. If it fails, the obstruction lies in succinctly representing integral bundle configurations or a huge lottery, not in the population continuum.
The proponent’s “uniform random permutation” also does not survive literally: there is no finite computable permutation of an atomless population to sample. The strongest repair is a type-level lottery or a compact configuration decomposition. But that turns the proposed question into a representation problem for the existing randomized allocation, rather than a new fairness problem. The tri-valued question has the same issue: it changes the utility domain, while any disappearance of the finite impossibility is a consequence of cloning and mass splitting, not a population-specific phenomenon.
One could add geography, eligibility, personalized budgets, or named relationships to make mass genuinely load-bearing, but those are new allocation models that the paper does not study. Keeping finitely many complete valuation types leaves \(\mu\) and \(\rho\) as capacities; letting the number of types grow with \(Q\) abandons the high-multiplicity regime.
So the strongest negative verdict is “green but thin”: fixed resources give a degenerate limit, while scaled resources give a legitimate but clone-equivalent high-multiplicity extension whose only genuinely new task is compact computation. I cannot honestly defend the requested universal claim that no worthwhile mirror exists. The proponent has identified a sensible open succinctness problem, though not yet demonstrated that it contains a population-specific complexity landscape.
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.