| paper | The Price of Fairness for Indivisible Goods |
| authors | Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, Warut Suksompong |
| venue | IJCAI 2019 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.3
Given two complete additive types \(a,b\) with \(\mu_a=\mu_b=1/2\), a finite set \(G\) of indivisible good slots with \(q_g=1/2\) for every \(g\in G\), and mass variables \(y_{t,B}\ge 0\) for integral bundles \(B\subseteq G\), compute \(\mathrm{EF1}^{\infty}(I)=\max_y \sum_{t,B}y_{t,B}v_t(B)\) subject to \(\sum_B y_{t,B}=\mu_t\), \(\sum_{t,B:g\in B}y_{t,B}=q_g\), and population-EF1 for every pair of positive-support bundles; compare this optimum with the unrestricted welfare optimum and determine the worst-case ratio.
A capacitated indivisible-goods configuration model with type masses \(\mu\), per-capita supplies \(q_g\), integral bundles \(B\subseteq G\), mass variables \(y_{t,B}\), additive values \(v_t(B)\), and support-wide EF1 constraints, maximizing \(\sum_{t,B}y_{t,B}v_t(B)\).
The two-agent sorting proof does not establish tractability or preservation of the \(2/\sqrt{3}\) guarantee once each type may split mass across several bundles subject to support-wide EF1 constraints.
fatal: False
The mirror directly covers the constructive two-agent EF1 welfare result and proposes related continuous formulations for general EF1 and strong MEW; it leaves the paper’s other price and strong-price results unmirrored.
The strongest honest case is that this paper admits a genuine high-multiplicity mirror, although there is an important limitation: it contains no numbered theorem whose printed statement says “NP-hard,” “in P,” “FPT,” or similar. The explicit NP-hardness statements occur only in prose. I therefore use Theorem 3.3 as an algorithmic anchor—its proof contains an explicit algorithm—and Theorems 3.1 and 5.3 as quantitative anchors.
The mirror should keep the goods indivisible. Let \(G\) be a finite set of good slots and \(T\) a finite set of complete agent types. Type \(t\) has additive utility \(v_t(B)=\sum_{g\in B}v_t(g)\) for an integral bundle \(B\subseteq G\), with \(\sum_gv_t(g)=1\). The society is a mass distribution \(\mu\) over \(T\). Good \(g\) has per-capita supply \(q_g\). An allocation is described by \(y_{t,B}\), the mass of type \(t\) receiving the integral bundle \(B\), satisfying
\[ \sum_{B\subseteq G}y_{t,B}=\mu_t \]
and
\[ \sum_{t,B:g\in B}y_{t,B}=q_g. \]
The aggregate variables are fractional, but every individual receives an indivisible bundle. Social welfare is
\[ \mathrm{SW}(y)=\sum_{t,B}y_{t,B}v_t(B). \]
Population-EF1 means that whenever \(y_{t,B}>0\) and \(y_{t',B'}>0\), there is some \(g\in B'\cup\{\varnothing\}\) such that
\[ v_t(B)\ge v_t(B'\setminus\{g\}). \]
Thus this is not average envy-freeness: every positive-mass agent must satisfy the paper’s original EF1 condition against every positive-mass bundle.
A convincing regime is a large housing, scholarship, or public-benefit allocation programme in which \(K\) households belong to each of only \(\tau\) complete utility types, with the numbers of indivisible item slots also scaling with \(K\). The relevant limit is \(K\gg \tau\), not a committee of seven individually idiosyncratic agents. Type membership includes the entire utility vector, so the high-multiplicity assumption is exact rather than cosmetic.
My lead anchor is Theorem 3.3, proved in this paper. It states that for two agents with additive normalized utilities, the price of EF1 is at most \(2/\sqrt{3}\): every instance has an EF1 allocation whose welfare is at least \(\sqrt{3}/2\) times optimal. The proof gives an explicit algorithm: sort goods by \(u_1(g)/u_2(g)\), locate the threshold \(s\) where the ratio crosses \(1\), then choose the least \(f\ge s\) satisfying \(u_1(L(f))\ge u_1(R(f+2))\), and allocate \(L(f)\) to agent \(1\) and \(R(f+1)\) to agent \(2\).
The corresponding continuous problem is:
“Continuous Two-Type EF1 Welfare.” Given two types \(a,b\), masses \(\mu_a=\mu_b=1/2\), rational additive utilities \(v_a,v_b\), and per-capita supply \(q_g=1/2\) for every good slot \(g\), compute an allocation \(y\) maximizing \(\mathrm{SW}(y)\) subject to population-EF1, and return its ratio to the unrestricted optimum.
This is recognisably the same question. The two named agents have simply become two large homogeneous cohorts, while each original good is represented by a positive mass of indivisible copies. I would expect this restricted mirror to be tractable—Class A—because the paper’s ratio ordering should induce a threshold structure, with the remaining mass assignment handled by a configuration LP. The first theorem to prove is whether the \(2/\sqrt{3}\) bound survives, or whether mass splitting improves the exact constant. Either outcome would be a meaningful continuous result.
The paper’s strongest general lower-bound anchor is Theorem 3.1, also proved here: the price of EF1 is \(\Omega(\sqrt n)\). Its construction has \(r-1\) specialised agents, one further specialised agent, and \(n-r\) uniform agents, with \(r=\lfloor\sqrt n\rfloor\). The optimum welfare is \(r\), whereas every EF1 allocation has welfare below \(2\).
The continuous version is:
“Continuous EF1 Price.” Given rational \(\mu\), utilities \(v_t\), and per-capita supplies \(q_g\), compute
\[ \mathrm{EF1}^\infty(I) = \max\{\mathrm{SW}(y):y\text{ is population-EF1}\}, \]
and determine the worst-case ratio
\[ \sup_I \frac{\mathrm{OPT}^\infty(I)} {\mathrm{EF1}^\infty(I)} \]
as a function of the number \(\tau\) of types and the number \(m\) of good slots.
The theorem’s obstruction survives the mirror. Let \(N=r^2\), \(m=N\), and use \(r+1\) types. Give each of the \(r\) specialised types mass \(1/N\), the uniform type mass \((N-r)/N\), and every good slot supply \(1/N\). Each specialised type values a private block of \(r\) goods at \(1/r\); the uniform type values every good at \(1/N\).
The optimum assigns each specialised type its block and has welfare \(r/N\). In any EF1 allocation, almost every uniform agent must receive at least one good: otherwise some positive mass receives no good while another positive mass receives at least two, violating EF1 for the empty uniform agents. Consequently at most \(r/N\) units of good mass can go to specialised types, and every allocated good contributes at most \(1/r\) to a specialised recipient. Hence every EF1 allocation has welfare below \(2/N\), giving a ratio exceeding \(r/2=\Omega(\tau)\).
Thus the original \(\Omega(\sqrt n)\) phenomenon is not merely an artefact of named individuals. The parameter changes from the number of agents to the number and geometry of types. I would expect the lower-bound phenomenon to transfer, while the unrestricted optimization problem is a plausible Class C candidate: EF1 is a disjunctive support condition over exponentially many integral bundles, so the continuum does not automatically produce one clean LP. The main further questions are whether the ratio is bounded by a polynomial in \(\tau\), and whether configuration-LP pricing can handle EF1 without reintroducing discrete hardness.
A useful boundary anchor is Theorem 5.3, proved here: for \(n>2\), the strong price of MEW is infinite. The paper constructs \(n\) agents and \(n\) goods so that every allocation has egalitarian welfare \(0\), while there is both a positive-welfare allocation and a zero-welfare MEW allocation.
The continuous problem is:
“Continuous Strong-MEW Welfare.” Given \((T,\mu,G,q,v)\), maximize the essential minimum utility
\[ \lambda(y)=\inf\{v_t(B):y_{t,B}>0\}, \]
let \(\mathrm{MEW}^\infty(I)\) be the allocations attaining the maximum \(\lambda(y)\), and compute
\[ \min_{y\in\mathrm{MEW}^\infty(I)}\mathrm{SW}(y). \]
The paper’s construction carries over with \(k\ge3\) types of mass \(1/k\), \(k\) goods of supply \(1/k\), type \(1\) valuing only \(g_1\), type \(2\) also valuing only \(g_1\), and type \(i\) for \(i\ge3\) valuing only \(g_{i-1}\). The collision over \(g_1\) means some positive mass must receive utility \(0\), so the maximum egalitarian welfare is \(0\). A cyclic shift allocation gives everyone utility \(0\) and has welfare \(0\), while another allocation has positive welfare. Therefore the strong price remains infinite.
Performance-wise, this negative result transfers exactly. Computationally, I would expect the general strong-MEW problem to be continuum-specifically hard: even after population integrality disappears, deciding which integral configurations meet a utility threshold resembles a knapsack/configuration-pricing problem.
The scope is therefore deliberately partial. I am not claiming that every result in the paper has a useful mirror, nor that its finite-agent constants survive unchanged. The case is that EF1 and MEW remain meaningful when the population is continuous, provided bundles stay integral and supplies scale per capita. Existing divisible-goods fair division is not a collision: it changes the goods, whereas this mirror changes only the population.
The weakest point is precisely the absence of a numbered complexity theorem in the paper. The positive case cannot honestly claim that the authors already prove an NP-hardness transfer or an LP algorithm for these continuous problems. Its strongest defensible claim is narrower: the paper’s central welfare questions have natural high-multiplicity formulations, one of them has a credible Class-A algorithmic route, and the paper’s finite-agent lower-bound phenomena survive as explicit continuous instances rather than disappearing automatically.
The strongest negative case begins with a mismatch of subject. This paper is primarily a worst-case welfare-analysis paper, not a computational-complexity paper. None of the three anchors is a numbered theorem about membership in \( \mathrm{P} \), NP-hardness, approximation, or parameterized complexity. Theorem 3.3 contains a constructive sorting argument, and some hardness claims occur in prose or footnotes, but the paper never identifies a computational problem whose high-multiplicity complexity is being classified. A continuous version would therefore have to invent the computational problem rather than continuize one from the paper.
There is also a serious modelling obstruction. In the original problem, goods are individual additive objects. To create \(K\) agents per type while keeping every agent supplied, one must create \(K\)-scale copies of the goods. Under the ordinary additive-copy interpretation, an agent’s total value for the available goods also scales with \(K\). After normalization, removing one good changes utility by \(O(1/K)\), so EF1 converges to exact envy-freeness. The paper’s crucial “remove one good” relaxation disappears in the limit.
The proponent avoids this by treating each \(g\in G\) as a slot that can be assigned to a fraction of the population, while each individual receives at most one copy of each slot. That is coherent, but it is not the paper’s additive indivisible-goods model. It is a capacitated assignment problem with substitute copies. The distinction matters: it is precisely what keeps one good macroscopically significant. Thus the proposed \(y_{t,B}\) model is a new fair-division model, not a high-multiplicity limit of the one in the paper. If one forbids type-splitting so that each type receives one bundle, the model reduces to replicating the paper’s few agents. If one allows splitting, one obtains a new configuration-support problem whose properties are not consequences of the paper’s results.
Theorem 3.3 is especially weak as an anchor. It concerns exactly two agents, so replicating the two utility types introduces no analogue of the paper’s \(n\)-agent population parameter. With unsplit cohorts, the continuous problem is simply the same two-bundle partition problem repeated at scale. With split cohorts, population-EF1 requires every bundle in one type’s support to be EF1 against every bundle in the other type’s support. The ratio-ordering proof for two named agents does not establish anything about this support-wide configuration problem. The proposed “Continuous Two-Type EF1 Welfare” question may be interesting, but it is a new problem whose justification comes from the invented slot model, not from Theorem 3.3.
Theorem 3.1 fares little better. In the proposed transfer, \(N=r^2\) is replaced by roughly \(r+1\) types, with the exceptional types having total mass \(O(1/r)\). The lower bound is therefore not a high-multiplicity phenomenon: the continuum limit \(K\to\infty\) does no work. The asymptotic parameter has merely been moved from the number of agents to the number of distinct utility types, while the welfare of the entire construction tends to zero. The large uniform cohort is only a device enforcing a support constraint against multi-good bundles. If one insists that all relevant types have macroscopic mass, the construction disappears; if one allows vanishing exceptional cohorts, the result is a type-geometry lower bound, not a population-continuization result. The proponent’s calculation may be correct for its slot model, but it does not mirror the paper’s \(\Omega(\sqrt n)\) phenomenon in the programme’s intended sense.
Theorem 5.3 is the strongest anchor, but it too lacks computational substance. The continuous translation has a fixed number of macroscopic types and a capacity collision, so it is a legitimate high-multiplicity scenario. Yet its conclusion is immediate: the maximum egalitarian welfare is \(0\), every allocation is MEW, and a zero-welfare MEW allocation exists. This is the same pigeonhole argument as in the finite instance, with each agent replaced by a cohort. It invokes no optimization machinery, separation problem, or complexity question. Replacing the minimum by an essential infimum does not change it. Requiring a positive welfare floor or using a lower quantile of the population could produce a worthwhile continuous problem, but that would no longer be the paper’s MEW or its strong-price theorem.
So the best case against is that every proposed anchor forces one of two choices. Preserve the paper’s exact indivisible-goods semantics, in which case EF1 degenerates when goods are replicated and the continuum contributes nothing. Or preserve macroscopic one-good effects by introducing slot capacities and population support constraints, in which case the result is a new capacitated fair-assignment model rather than a mirror of this paper. The paper itself supplies no named computational theorem to make that new model part of the continuization programme.
This negative case is not airtight. Large scholarship, housing, or benefit programmes with repeated utility types are plainly plausible high-multiplicity settings, and the slot model is coherent if its authors explicitly endorse it. In particular, the MEW collision is a genuine continuous boundary example. I therefore cannot honestly claim that no worthwhile continuous question can be formulated. The defensible negative conclusion is narrower: these three results do not, by themselves, provide a convincing computational mirror of this paper; the proponent’s case depends on importing a new multi-unit fair-division model and new algorithmic questions.
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.