| paper | Efficiency and Envy-freeness in Fair Division of Indivisible Goods: Logical Representation and Complexity |
| authors | S. Bouveret, Jérôme Lang |
| venue | JAIR 2008 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 21
statement extracted from the paper’s text layer
Given rational type masses \(\mu_t\), per-capita supplies \(q_g\), and \(0\)-\(1\) additive valuations \(u_t(B)=\sum_{g\in B}v_{t,g}\), does there exist a mass allocation \(z_{t,B}\) over integral bundles \(B\subseteq G\) satisfying \(\sum_B z_{t,B}=\mu_t\), \(\sum_{t,B:g\in B}z_{t,B}\le q_g\), envy-freeness, and Pareto efficiency?
A finite set of complete valuation types carries population mass \(\mu_t\); integral bundles are assigned by mass \(z_{t,B}\), goods have per-capita capacities \(q_g\), and the objective is existence of an envy-free Pareto-efficient allocation.
The mirror covers the additive \(0\)-\(1\) and monotonic-cube EEF hardness results, but leaves the paper's other preference languages, efficiency criteria, and complexity classifications unmirrored.
The strongest positive case is a genuine high-multiplicity version of the paper’s EEF-existence problem. The lead anchor is Proposition 21.
The natural regime is a recurring allocation market: many people belong to a small number of eligibility or needs classes, and each class has the same valuation for standardized indivisible goods. Stocks are replenished proportionally with population size. Thus a type is a complete \(0\)-\(1\) valuation vector, population mass is the fraction of agents of that type, and \(q_g\) is the per-capita supply of good \(g\). If the population is replicated \(K\) times, there are \(Kq_g\) copies of each good. The goods remain indivisible for every individual; only the distribution of agents across integral bundles is continuous.
Formally, let \(G\) be the goods, \(T\) the finite type set, \(\mu_t\) the mass of type \(t\), and \(q_g\) the supply of \(g\) per unit population. A solution is a mass table \(z_{t,B}\), where \(B\subseteq G\) is an integral bundle, \(\sum_B z_{t,B}=\mu_t\), and \(\sum_{t,B:g\in B}z_{t,B}\le q_g\). Envy-freeness means that, for almost every pair of agents \(v,w\), \(u_{\theta(v)}(B_v)\ge u_{\theta(v)}(B_w)\). Pareto efficiency means that no feasible reassignment makes everyone weakly better off and a positive mass strictly better off. The decision question is whether such an allocation exists.
I would call this problem \(\mathrm{EEF}^{01}_\infty\): given rational \(\mu\), rational per-capita supplies \(q\), and \(v_{t,g}\in\{0,1\}\), with \(u_t(B)=\sum_{g\in B}v_{t,g}\), does an envy-free and Pareto-efficient mass allocation exist?
The anchor is Proposition 21, proved in this paper: “EEF existence with additive \(0\)-\(1\)-preferences is NP-complete.” Here EEF means existence of an allocation that is simultaneously envy-free and Pareto-efficient; every atomic utility \(u_i(x_j)\) is either \(0\) or \(1\). The paper proves hardness by reducing Exact Cover by 3-Sets, and proves membership in NP by observing that Pareto efficiency and envy-freeness can both be checked polynomially for a proposed finite allocation.
The paper’s reduction survives the population limit. Given an Exact-Cover instance \((S,\mathcal C)\), with \(|S|=3q\), let \(N=3|\mathcal C|\). For every \(S_i\in\mathcal C\), create one population type \(t_i\) of mass \(3/N\). Its valued goods are the three main goods \(m_a\) for \(a\in S_i\), together with three private dummy goods \(d_{i,1},d_{i,2},d_{i,3}\). Give every good supply \(1/N\) per capita. In a finite realization, this means \(3K\) agents of type \(t_i\) and \(K\) copies of every good, for arbitrary \(K\); hence the number of agents can be arbitrarily larger than the number of types.
The exact-cover forcing is not destroyed by fractional population mass. Pareto efficiency requires each private dummy to be assigned to its unique interested type. Let \(y_i\) be the mass of main goods from \(S_i\) assigned to type \(t_i\). The three private dummies contribute exactly one unit of average utility per type-\(i\) agent, while \(0\le y_i\le 3/N\). Envy-freeness forces all agents of the same type to have the same integer utility, so \(1+y_i/(3/N)\) must be an integer. Therefore \(y_i\) is either \(0\) or \(3/N\). A type either receives no main goods or consumes all three main-good supplies corresponding to \(S_i\). Capacity makes selected sets disjoint, and Pareto efficiency requires every main good to be assigned to some selected set. Thus the selected sets form an exact cover. Conversely, an exact cover gives an EEF allocation by giving selected types their three main goods plus their dummies, and giving the other types only their dummies.
So the expected classification is Class B: NP-hardness transfers. The combinatorics live in the goods and the incidence structure of the types, not in the number of named agents. I would not yet claim NP-completeness for the unrestricted continuous problem without fixing a compact representation theorem for mass allocations, but NP-hardness already gives the relevant continuization result.
A second, independent anchor is Proposition 12, also proved in the paper: “EEF existence for agents having dichotomous preferences restricted to cubes of objects is NP-complete. The same result holds if preferences are required to be monotonic.” A monotonic cube is a demand set \(D_t\subseteq G\), with \(u_t(B)=1\) exactly when \(D_t\subseteq B\).
The corresponding problem, \(\mathrm{EEF}^{\square}_\infty\), has the same mass-allocation input, but each type is specified by a monotonic demand set \(D_t\). The continuous question is whether there is a feasible allocation of integral bundles that is envy-free and Pareto-efficient under these dichotomous preferences.
The paper’s Exact-Cover reduction again gives a direct mirror. For each \(S_i\in\mathcal C\), create a type of mass \(1/N\) demanding \(\{x_a:a\in S_i\}\). For each \(a\in S\), create a type of mass \(2/N\) demanding \(\{x_a,x'_a\}\). Give both \(x_a\) and \(x'_a\) supply \(1/N\). The pair type cannot receive a positive mass of satisfying bundles: envy-freeness would require its whole mass to be satisfied, but that would need \(2/N\) copies of each good while only \(1/N\) exists. If some element \(a\) were not covered by a satisfied set type, both \(x_a\) and \(x'_a\) could be assigned to a positive mass of the pair type, contradicting Pareto efficiency. Capacity then forces the satisfied set types to be disjoint and covering. Hence this mirror is also expected to be Class B.
These are problems the authors should recognise as their own: same indivisible bundles, same envy-freeness, same Pareto criterion, and the same preference languages. The only substantive change is replacing named multiplicities by type masses and scaling the supply of recurring goods. This is not cake-cutting, fractional goods, probabilistic preferences, or continuity of the outcome space.
The weakest point is precisely that supply scaling. If the paper’s one-shot finite stock is regarded as essential, then an atomless population with fixed goods degenerates: almost everyone receives nothing. The mirror therefore needs the recurring-market interpretation explicitly. A second caveat is that the high-multiplicity gain is not itself what causes the hardness; the reductions remain hard because goods and type-incidence constraints retain integrality. That is not a defect under the programme’s trichotomy: it is the desired Class B case, showing where continuization stops helping.
The natural follow-up questions are whether these continuous problems are NP-complete under a compact bundle-support encoding, whether fixed \(\tau\) or fixed \(|G|\) yields tractability, and whether replacing exact envy-freeness by EF1, bounded envy, or minimum envy causes the mass formulation to collapse to a flow or configuration LP.
The strongest negative case is that the paper’s literal model is a one-shot allocation of a fixed finite set of goods. With an atomless population and fixed stock, only a null fraction can receive goods. Under monotonic preferences, envy-freeness then makes the limit either infeasible or trivial. Thus the direct fixed-stock limit is not worthwhile.
That objection does not survive the programme’s permitted co-modification of supplies. Once each good has per-capita supply, the proposed model is a genuine high-multiplicity fair-division problem: agents still receive integral bundles, while the population and stock are represented by masses. The objection that goods have been “fractionalized” is incorrect; only aggregate assignment is fractional.
Nor can Proposition 21 be defeated technically. Let \(N=3|\mathcal C|\), give each set type mass \(3/N\), and each good supply \(1/N\). In any Pareto-efficient allocation, each type’s three private dummy goods are assigned to it, giving average utility \(1\). If \(r_i\) is the total mass of its three main goods, envy-freeness among identical agents forces their common integral utility to satisfy
\[ 1+\frac{r_i}{3/N}\in\mathbb Z. \]
Since \(0\le r_i\le 3/N\), this implies \(r_i\in\{0,3/N\}\). A type therefore either receives none of its main goods or consumes all three. Pareto efficiency requires every main good to be consumed, and capacity forces the selected sets to form an exact cover. The reduction is a valid high-multiplicity mirror, and its hardness is precisely a legitimate Class B result.
Proposition 12 survives similarly after normalizing the masses. A pair type of mass \(2/M\) with supplies \(1/M\) for each demanded good cannot have any positive mass receiving a satisfying bundle without creating within-type envy. Pareto efficiency then forces those goods to be consumed by satisfied set types; capacity makes selected sets disjoint and covering. Again, the exact-cover structure remains.
One can object that proportional supplies describe a recurring standardized market rather than divorce settlements or a single satellite-allocation instance. But the programme explicitly allows that kind of co-modification, and the paper’s own mathematical problem supports such a scenario. Existing high-multiplicity work would strengthen, not weaken, the case.
So the honest conclusion is that the universal negative case is weak. The fixed-stock interpretation degenerates, but a plausible per-capita-supply interpretation defeats that objection and preserves both named computational anchors.
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.