Answer: \(\mathrm{NP}\text{-complete}\)
Proposition 21 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximatewhat is the complexity of the eef existence problem with stratified 0–1-preferences ? By “stratified 0–1-preferences”, we mean that the preferences are given by a set of pairs ⟨xk, p⟩, where xk is an object and p is a priority level. Comparing two sets of objects comes down to compare lexicographically the vectors where the component at index i is the number of objects of priority i in the share of the agent. Notice that this problem is not an instance of the eef existence problem with additive preferences, nor an instance of the eef existence problem with logical numerical preferences under logical form.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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 society is given by its support: the list of \(\tau\ge1\) valuation types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) goods \(G\), nonnegative binary-rational per-capita supplies \(q_g\), and explicitly given values \(v_{t,g}\in\{0,1\}\), with \(u_t(B)=\sum_{g\in B}v_{t,g}\).
An allocation assigns actual integral bundles to individuals: nonnegative real masses \(z_{t,B}\), indexed by \(B\subseteq G\), satisfy \(\sum_Bz_{t,B}=\mu_t\) and \(\sum_{t,B:g\in B}z_{t,B}\le q_g\). Empty bundles and disposal are allowed; there are no transfers.
Envy-freeness means \(u_t(B)\ge u_t(C)\) whenever \(z_{t,B}>0\) and \(z_{s,C}>0\), including \(s=t\).
A Pareto improvement consists of another feasible allocation \(z'\) and nonnegative real transport masses \(w_{t,B,C}\) satisfying \(\sum_Cw_{t,B,C}=z_{t,B}\), \(\sum_Bw_{t,B,C}=z'_{t,C}\), and \(w_{t,B,C}>0\Rightarrow u_t(C)\ge u_t(B)\), with \(\sum_{t,B,C:u_t(C)>u_t(B)}w_{t,B,C}>0\). Pareto efficiency means no such improvement exists; competing allocations need not be envy-free.
Is deciding whether an envy-free, Pareto-efficient mass allocation exists solvable in polynomial time, or is it NP-hard? State running times in \(m\), \(\tau\), and the total input bit length \(L\).
For finite agents and single-copy indivisible goods, existence with binary additive valuations is NP-complete ([Bouveret–Lang](https://www.lamsade.dauphine.fr/~lang/papers/bouveret-lang08.pdf)).
For finite agents, envy-free and Pareto-efficient lotteries exist under expected-utility comparisons and swap-closed feasibility ([Cole–Tao](https://arxiv.org/abs/1906.07257)); this concerns ex ante fairness, whereas the conditions above compare realized bundles. No result settling the stated mass problem was identified.
The decision problem is \(\mathrm{NP}\)-complete. Hardness holds even when all masses and supplies are dyadic rationals, every supply is positive, \(\tau=m\), and every type except one values at most three goods.
The proof below applies directly to the stated mass model. The neighboring results of [Bouveret–Lang, Proposition 21](https://www.lamsade.dauphine.fr/~lang/papers/bouveret-lang08.pdf) and [Cole–Tao](https://arxiv.org/abs/1906.07257) concern finite agents and ex ante comparisons, respectively.
For each good \(g\), define its total valuing mass and its useful consumption by
\(M_g=\sum_{t:v_{t,g}=1}\mu_t,\qquad x_g(z)=\sum_{t:v_{t,g}=1}\sum_{B:g\in B}z_{t,B}.\)
Write
\(c_g=\min\{q_g,M_g\},\qquad W=\sum_{g\in G}c_g.\)
Every feasible allocation satisfies \(x_g(z)\le c_g\). Its total utility is
\(U(z)=\sum_{t,B}z_{t,B}u_t(B)=\sum_g x_g(z)\le W.\)
Lemma 1. A feasible allocation is Pareto-efficient exactly when \(x_g(z)=c_g\) for every good \(g\), equivalently when \(U(z)=W\).
Proof. Suppose \(x_g(z)<c_g\) for some good. First remove \(g\) from every bundle assigned to a type that does not value it. This preserves all individuals’ utilities and leaves consumption of \(g\) equal to \(x_g(z)\).
Since \(x_g(z)<M_g\), there is a type \(t\) valuing \(g\) and a bundle \(B\) missing \(g\) with \(z_{t,B}>0\). Since \(x_g(z)<q_g\), choose
\(0<\delta\le\min\{z_{t,B},q_g-x_g(z)\}.\)
Give \(B\cup\{g\}\), instead of \(B\), to mass \(\delta\) of these individuals. Consumption of every other good is unchanged, and consumption of \(g\) remains at most \(q_g\).
These operations define an admissible transport: individuals losing an unvalued good retain their utility, the selected mass gains one utility unit, and everyone else retains their bundle. Thus the original allocation is not Pareto-efficient.
Conversely, suppose \(U(z)=W\). Any Pareto improvement with transport \(w\) would satisfy
\(U(z')-U(z)=\sum_{t,B,C}w_{t,B,C}\bigl(u_t(C)-u_t(B)\bigr)>0.\)
Every summand with positive transport is nonnegative, and strictly improving transport has positive total mass. This contradicts \(U(z')\le W\). Finally, because each \(x_g(z)\le c_g\), equality of their sums holds exactly when equality holds for every good. \(\square\)
This lemma uses the specified transport definition and allows the competing allocation to violate envy-freeness.
Lemma 2. In any envy-free allocation, every type \(t\) has a single integer utility \(k_t\): every positively assigned bundle \(B\) satisfies \(u_t(B)=k_t\).
Proof. For two positively assigned bundles \(B,C\) of type \(t\), self-comparison gives both \(u_t(B)\ge u_t(C)\) and \(u_t(C)\ge u_t(B)\). Hence they are equal. Their common value is an integer between \(0\) and \(m\). \(\square\)
For an integer vector \(k=(k_1,\ldots,k_\tau)\), define
\(\mathcal B_t(k)=\{B\subseteq G:u_t(B)=k_t\text{ and }u_s(B)\le k_s\text{ for every }s\}.\)
An allocation has envy-free utility vector \(k\) exactly when it uses only bundles from \(\mathcal B_t(k)\) for each type \(t\). Its total utility is then \(\sum_t\mu_t k_t\).
Consequently, existence is equivalent to finding a vector \(k\) satisfying
\(\sum_t\mu_t k_t=W\)
for which the following linear system is feasible:
Polynomial certificate size. Put \(R=\tau+m\). Add one nonnegative slack variable to each supply inequality. The resulting system has \(R\) equality rows, coefficients in \(\{0,1\}\), and rational right-hand sides.
If feasible, this system has a basic feasible solution with at most \(R\) positive variables, hence at most \(R\) positive bundle masses. To justify this support bound, more than \(R\) positive columns would be linearly dependent; a sufficiently small perturbation in both directions along that dependence would preserve feasibility, contradicting extremality.
These positive masses also have polynomial bit length. Take a common denominator of the input masses and supplies; its bit length is \(O(L)\). A nonsingular basis has order at most \(R\), and Hadamard’s inequality bounds its determinant by \(R^{R/2}\). Cramer’s rule therefore bounds each mass’s numerator and denominator bit lengths by \(O(L+R\log R)\).
Thus a certificate consists of at most \(m+\tau\) bundles, their type indices, and rational masses of polynomial bit length. Feasibility, all realized-bundle envy comparisons, and \(U(z)=W\) can be checked in \(\operatorname{poly}(m,\tau,L)\) time. Lemma 1 verifies Pareto efficiency. The problem belongs to \(\mathrm{NP}\).
We reduce from Independent Set on a simple graph \(\Gamma=([n],E)\), with threshold \(2\le K\le n\). This restriction remains \(\mathrm{NP}\)-complete: instances outside this range are decidable directly and can be mapped to fixed yes- or no-instances within the range.
Let \(\ell=|E|\) and \(s=n+\ell\). Set
\(N=n+1+s(K+2),\qquad P=2^{\lceil\log_2 N\rceil},\qquad a=P^{-1},\qquad b=(K+2)a,\qquad \Delta=1-Na.\)
Then \(\Delta\ge0\), and all these numbers are dyadic rationals.
There are vertex goods \(x_1,\ldots,x_n\), one additional good \(h\), and one distinct private good \(p_o\) for each auxiliary type \(o\) below.
| Type | Valued goods | Mass |
|---|---|---|
| Distinguished type \(T_*\) | \(\{x_1,\ldots,x_n\}\) | \(a\) |
| Receiver \(R_i\), for each vertex \(i\) | \(\{x_i,h\}\) | \(a\) |
| Vertex observer \(A_i\), for each vertex \(i\) | \(\{x_i,h,p_{A_i}\}\) | \(b\), except \(A_1\) has mass \(b+\Delta\) |
| Edge observer \(F_e\), for each edge \(e=\{i,j\}\) | \(\{x_i,x_j,p_{F_e}\}\) | \(b\) |
All unlisted values are zero. Supplies are
\(q_{x_i}=a,\qquad q_h=Ka,\qquad q_{p_o}=\mu_o.\)
The masses sum to
\((n+1)a+sb+\Delta=Na+\Delta=1.\)
Every mass and supply is positive. The valuation vectors are pairwise distinct, so the support size is exactly
\(\tau=1+n+s=2n+\ell+1=m.\)
The distinguished type values \(n\) goods; every other type values at most three.
All supplies are at most the corresponding valuing masses:
Therefore Lemma 1 says that efficiency requires every good’s entire supply to be consumed by individuals valuing it. Here
\(W=(n+K)a+\sum_o\mu_o,\)
where the sum ranges over all observers.
Suppose \(I\subseteq[n]\) is an independent set of size \(K\). Assign one bundle to each type:
Each vertex good is consumed by mass \(a\), either of \(T_*\) or its receiver. Good \(h\) is consumed by exactly \(K\) receivers, of total mass \(Ka\). Every private good is consumed by its owner’s entire mass. All supplies are therefore consumed by valuers, proving efficiency.
For envy-freeness:
These comparisons cover every pair of positively assigned bundles, proving envy-freeness.
Now suppose an envy-free, Pareto-efficient mass allocation exists. Let \(k_t\) be its uniform utilities from Lemma 2.
Step 1: Every observer has utility exactly one.
Efficiency forces useful consumption of \(p_o\) to equal \(\mu_o\). Since only observer \(o\) values \(p_o\), every positively assigned bundle of \(o\) contains \(p_o\). Thus \(k_o\ge1\).
For a vertex observer, its other valued goods have total supply
\(q_{x_i}+q_h=(K+1)a<b\le\mu_{A_i}.\)
For an edge observer, its other valued goods have total supply
\(q_{x_i}+q_{x_j}=2a<b\le\mu_{F_e}.\)
If \(k_o\ge2\), every individual of observer type \(o\) would receive at least one other valued good. Their consumption of those goods would be at least \(\mu_o\), contradicting the displayed supply bound. Hence \(k_o=1\). In particular, observers receive none of their other valued goods in positive-mass bundles.
Step 2: Every receiver has utility exactly one.
Vertex observer \(A_i\), whose utility is one, values both \(x_i\) and \(h\). Envy-freeness therefore prohibits any positively assigned receiver bundle from containing both. Thus \(k_{R_i}\le1\).
Efficiency requires useful consumption \(q_h=Ka>0\) of \(h\). Its valuers are receivers and vertex observers; Step 1 excludes the latter. Hence some positive-mass receiver bundle contains \(h\). Every receiver values that bundle at least one, so envy-freeness gives \(k_{R_i}\ge1\) for every \(i\).
Therefore \(k_{R_i}=1\) for all receivers.
Step 3: The distinguished type has utility exactly \(K\).
Using Steps 1–2, total utility is
\(U(z)=a k_{T_*}+na+\sum_o\mu_o.\)
Efficiency and Lemma 1 give
\(U(z)=W=(n+K)a+\sum_o\mu_o.\)
Because \(a>0\), these equalities imply \(k_{T_*}=K\).
Step 4: A distinguished bundle identifies an independent set.
The distinguished type has positive mass, so choose any positively assigned bundle \(B\) of that type. Define
\(I=\{i:x_i\in B\}.\)
Step 3 gives \(|I|=K\). For every edge \(e=\{i,j\}\), edge observer \(F_e\) has utility one and values both \(x_i,x_j\). Envy-freeness implies
\(|B\cap\{x_i,x_j\}|\le u_{F_e}(B)\le1.\)
Thus no edge has both endpoints in \(I\). The set \(I\) is independent.
This necessity argument permits arbitrary splitting across bundles and arbitrary real masses. It does not assume that a type receives only one bundle.
The construction has \(m=\tau=2n+\ell+1\). Since \(K\le n\), every numerical entry has \(O(\log(n+\ell))\) bits. The explicitly written valuation table and numerical data have total length \(O((n+\ell)^2)\), and the construction takes polynomial time.
The reduction proves \(\mathrm{NP}\)-hardness. Together with Section 2, it proves \(\mathrm{NP}\)-completeness.
Certificate verification takes \(\operatorname{poly}(m,\tau,L)\) time.
An explicit deterministic algorithm enumerates all utility vectors \(k\in\{0,\ldots,m\}^{\tau}\). For each vector, it:
Polynomial-time linear programming therefore gives running time
\((m+1)^\tau\,2^{O(m)}\operatorname{poly}(m,\tau,L).\)
A polynomial-time algorithm for unrestricted instances would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes \(\mathrm{NP}\)-completeness for the stated mass model, including the claimed restrictions. I found no major or minor mathematical issues requiring repair.
Useful consumption satisfies both \(x_g(z)\le q_g\), by feasibility, and \(x_g(z)\le M_g\), because an integral bundle contains each good at most once. Thus \(x_g(z)\le c_g\).
The identity \(U(z)=\sum_g x_g(z)\) follows from binary additive valuations. All sums are finite, even though their indexing sets can be exponentially large. Consequently, \(U(z)\le W\) is valid.
Removing \(g\) from bundles of nonvaluing types preserves their utilities and changes no other good’s consumption. Afterwards, total consumption of \(g\) is \(x_g(z)\).
Since \(x_g(z)<M_g\), some positive mass of a valuing type lacks \(g\). Since \(x_g(z)<q_g\), the proposed positive \(\delta\) exists. Adding \(g\) to that mass preserves feasibility and strictly increases its utility.
The described removal and addition operations induce a transport satisfying the task’s marginal conditions. Every transported individual weakly improves, and mass \(\delta>0\) strictly improves. This argument does not require the competing allocation to be envy-free.
The transport marginal equations justify the displayed expression for \(U(z')-U(z)\). Binary additive utilities give integer differences; any strictly improving transport has difference at least one. Therefore positive total strictly improving mass implies \(U(z')-U(z)>0\), contradicting the universal upper bound \(W\).
Finally, the nonnegative deficits \(c_g-x_g(z)\) sum to zero exactly when every deficit is zero. Both equivalences in Lemma 1 are established.
Zero supplies, goods valued by no type, supplies exceeding valuing mass, and disposal cause no exception to this reasoning.
Self-comparison forces all positive bundles of each type to have equal utility. Positive type masses ensure that every type has at least one positive bundle, so every \(k_t\) is defined. Its range is correctly bounded by \(0\le k_t\le m\).
The definition of \(\mathcal B_t(k)\) imposes precisely the required conditions: each recipient obtains its designated utility, and every other type evaluates that bundle at no more than its own designated utility. This covers comparisons between different types and within a type.
Accordingly, fixed-vector feasibility together with \(\sum_t\mu_t k_t=W\) is equivalent to envy-free, Pareto-efficient existence. There is no restriction here to rational allocations or to one bundle per type.
Adding supply slacks produces a finite standard-form system with \(R=m+\tau\) rows and coefficients in \(\{0,1\}\). The basic-feasible-solution assertion applies: the variables are nonnegative, and a nonempty feasible set admits a basic feasible solution. In this instance the bundle variables and slacks are also bounded by their respective mass and supply constraints.
At an extreme point, positive columns must be linearly independent, exactly as the prover’s perturbation argument states. Hence at most \(R\) variables are positive, including slacks, and at most \(R\) bundle masses are positive.
The bit bounds also check out. A common denominator has bit length \(O(L)\). Hadamard’s determinant bound and Cramer’s rule give mass numerator and denominator lengths \(O(L+R\log R)\). The exponential number of available columns does not affect these bounds for a selected basis.
A certificate therefore has polynomial total length. Exact rational feasibility, all comparisons among its positive bundles, and \(U(z)=W\) can be verified in \(\operatorname{poly}(m,\tau,L)\) time. Membership in \(\mathrm{NP}\) is established.
Independent Set on simple graphs with an integer threshold is an appropriate \(\mathrm{NP}\)-complete source problem. Restricting to \(2\le K\le n\) is legitimate because the excluded cases are directly decidable and fixed yes- and no-instances exist within the restriction. [Independent Set complexity reference](https://www.cs.uic.edu/~block/courses/cs505-spring2025/lecture-05.html).
The numerical construction satisfies \(P\ge N\), hence \(\Delta\ge0\). All constructed masses and supplies are positive dyadic rationals, and their sum is exactly one.
Counting the goods and types gives \(m=\tau=2n+\ell+1\). The valuation vectors are distinct: observers have distinct private goods, receivers have distinct vertex goods, and the distinguished type lacks \(h\) and private goods. All nondistinguished types value at most three goods.
The valuing-mass checks are sufficient to show \(c_g=q_g\) for every constructed good. Thus the formula
\(W=(n+K)a+\sum_o\mu_o\)
is correct.
Given an independent set of size \(K\), each vertex good is assigned to exactly mass \(a\), \(h\) to mass \(Ka\), and each private good to its owner’s entire mass. All consumption is useful, so Lemma 1 establishes efficiency.
Receivers and observers have utility one. Each evaluates every assigned singleton at at most one. Receivers and vertex observers evaluate the distinguished bundle at at most one; edge observers do so because the selected vertices are independent. The distinguished type has utility \(K\) and evaluates every other bundle at at most one.
These checks cover all positive assigned bundles. No envy comparison is omitted.
Observer utilities. Efficient private-good consumption forces every positive owner bundle to contain its private good. Hence observer utilities are at least one. Uniform utility at least two would require additional valued consumption of at least the observer’s mass. The bounds
\((K+1)a<(K+2)a\le\mu_{A_i}\)
and
\(2a<(K+2)a\le\mu_{F_e}\)
rule this out. Thus every observer has utility exactly one and receives none of its other valued goods in a positive bundle.
Receiver utilities. Observer \(A_i\)’s envy constraint prohibits a positive receiver-\(i\) bundle containing both \(x_i\) and \(h\), giving \(k_{R_i}\le1\). Efficient useful consumption of positive supply \(Ka\) forces a receiver bundle containing \(h\), since vertex observers cannot consume it usefully. Every receiver values that bundle, giving \(k_{R_i}\ge1\). Therefore every receiver utility equals one.
Distinguished utility. Substituting the established utilities into \(U(z)=W\) yields \(a k_{T_*}=Ka\). Since \(a>0\), \(k_{T_*}=K\).
Extraction. Positive distinguished mass guarantees a positive distinguished bundle. It contains exactly \(K\) vertex goods. Each edge observer’s envy constraint prevents this bundle from containing both endpoints of its edge. The extracted set is therefore independent.
No step assumes indivisible type masses, rational allocation masses, or a single bundle per type.
Since \(K\le n\), \(N\) and \(P\) have bit length \(O(\log(n+\ell))\). The numerical entries inherit this bound, and the explicit valuation table has size \(O((n+\ell)^2)\). The reduction is polynomial.
The deterministic algorithm examines \((m+1)^\tau\) utility vectors. Each explicit feasibility system has at most \(\tau2^m\) bundle variables and polynomial-size coefficients. Rational linear feasibility is decidable in time polynomial in the explicitly encoded system length; its hypotheses are satisfied here. [Linear-programming reference](https://www2.isye.gatech.edu/~nemirovs/lmco_run.pdf).
Therefore the claimed bound
\((m+1)^\tau\,2^{O(m)}\operatorname{poly}(m,\tau,L)\)
is valid.
The contextual descriptions agree with [Bouveret–Lang, Proposition 21](https://www.lamsade.dauphine.fr/~lang/papers/bouveret-lang08.pdf) and [Cole–Tao’s ex ante existence result](https://arxiv.org/abs/1906.07257). Neither result is used to transfer a conclusion to the mass problem. The submitted proof independently addresses realized-bundle envy and the specified transport definition.
No additional clarification or mathematical repair is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.