Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 4.7 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAn EF-constrained PO allocation always exist and can be found in polynomial time for a single divisible good with piecewise-linear utility functions.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_t\), a rational per-capita supply \(\beta\), and rational nondecreasing piecewise-linear valuations \(v_t:[0,1]\to\mathbb{Q}_{\ge0}\), compute \(a\in[0,1]^\tau\) satisfying \(\sum_t\mu_ta_t=\beta\), \(v_t(a_t)\ge v_t(a_{t'})\) for all positive-mass types \(t,t'\), and such that no feasible EF allocation weakly improves every positive-mass type while strictly improving one.
Definitions. The input gives a finite type set \(T\), rational \(\mu_t\ge0\) with \(\sum_{t\in T}\mu_t=1\), rational \(\rho_g\in[0,1]\) for \(g\in[3]\), and one-breakpoint utilities \(u_t(z)=\sum_{g=1}^3 w_{t,g}\mathbf 1\{z_g\ge c_{t,g}\}\). Let \(\Omega=[0,1]\) with Lebesgue measure and a measurable \(\theta:\Omega\to T\) satisfying \(\lambda(\theta^{-1}(t))=\mu_t\). A feasible allocation is measurable \(x:\Omega\to[0,1]^3\) with \(\int_\Omega x_g\,d\lambda=\rho_g\) for every \(g\). It is EF if \(u_{\theta(\omega)}(x(\omega))\ge u_{\theta(\omega)}(x(\omega'))\) for \(\lambda\times\lambda\)-almost every \((\omega,\omega')\). It is PO if no feasible measurable \(y:\Omega\to[0,1]^3\) gives every agent weakly higher utility almost everywhere and a strictly higher utility on a set of positive measure.
Target. Is deciding whether such an EF and PO allocation exists solvable in polynomial time, or is it NP-hard?
Known results. For finitely many agents and at least three goods, deciding existence of an EF and PO allocation is NP-hard even with one-breakpoint piecewise-constant valuations.
Under the standard binary encoding of rational weights and breakpoints, deciding whether an EF and PO allocation exists is \(\mathrm{NP}\)-hard.
This holds even when every type has the fixed weights \((2,2,1)\), all types have equal mass, and \(\rho_1=\rho_2=\tfrac12\). The reduction is directly to the nonatomic model; the cited finite-agent hardness result is not needed.
Let \(A_t=\theta^{-1}(t)\), where \(\mu_t>0\).
Lemma. If \(x\) is EF, then there is a number \(U_t\) such that \(u_t(x(\omega))=U_t\) for almost every \(\omega\in A_t\).
Proof. Restrict the EF inequality to \(A_t\times A_t\). For almost every \((\omega,\omega')\in A_t\times A_t\),
\[ u_t(x(\omega))\geq u_t(x(\omega')). \]
Applying the same statement to the transposed pair gives the reverse inequality for almost every pair. Hence
\[ u_t(x(\omega))=u_t(x(\omega')) \]
for almost every \((\omega,\omega')\in A_t\times A_t\). By Fubini’s theorem, \(u_t\circ x\) is almost everywhere constant on \(A_t\). \(\square\)
Thus EF prevents a positive-mass type from being split between bundles giving that type different utility levels.
Let \(a_1,\ldots,a_n\) be positive integers, with \(n\geq2\), and put
\[ A=\sum_{i=1}^n a_i. \]
The PARTITION instance is a YES-instance precisely when some \(S\subseteq[n]\) satisfies
\[ \sum_{i\in S}a_i=\frac A2. \]
Construct one type for every \(i\in[n]\), with
\[ \mu_i=\frac1n. \]
For type \(i\), set
\[ c_{i,1}=\frac{i}{n+1},\qquad c_{i,2}=\frac{n+1-i}{n+1},\qquad c_{i,3}=\frac{a_i}{A}, \]
and
\[ w_{i,1}=w_{i,2}=2,\qquad w_{i,3}=1. \]
Finally, set
\[ \rho_1=\rho_2=\frac12,\qquad \rho_3=\frac1{2n}. \]
All these numbers have polynomial-length rational encodings.
For every type, the utility of a bundle has the following form:
Also,
\[ \frac1n\sum_{i=1}^n c_{i,1} = \frac1n\sum_{i=1}^n c_{i,2} = \frac12. \]
The first two breakpoint vectors form an antichain: if \(i\neq j\), then the bundle \((c_{j,1},c_{j,2})\) reaches at most one of type \(i\)'s first two breakpoints. Indeed, \(c_{j,1}\geq c_{i,1}\) requires \(j\geq i\), while \(c_{j,2}\geq c_{i,2}\) requires \(j\leq i\).
Suppose \(S\subseteq[n]\) satisfies \(\sum_{i\in S}a_i=A/2\).
Give every member of type \(i\) the bundle
\[ x_i= \begin{cases} (c_{i,1},c_{i,2},c_{i,3}),&i\in S,\\ (c_{i,1},c_{i,2},0),&i\notin S. \end{cases} \]
This defines a measurable allocation by setting \(x(\omega)=x_i\) on \(A_i\).
The first two resource equalities follow from the preceding average identities. For the third good,
\[ \int_\Omega x_3\,d\lambda = \frac1n\sum_{i\in S}\frac{a_i}{A} = \frac1{nA}\cdot\frac A2 = \frac1{2n}. \]
Thus \(x\) is feasible.
A type \(i\in S\) receives utility \(5\), the maximum possible utility, and therefore envies nobody.
A type \(i\notin S\) receives utility \(4\). Every bundle assigned to a different type \(j\neq i\) reaches at most one of type \(i\)'s first two breakpoints. Even if it reaches type \(i\)'s third breakpoint, its utility to type \(i\) is at most \(2+1=3\). Hence type \(i\) does not envy any other type.
Therefore \(x\) is EF.
Suppose a feasible allocation \(y\) weakly improves every agent.
Every agent currently has utility at least \(4\). Since utility at least \(4\) requires reaching both of the first two breakpoints, almost every type \(i\) agent must satisfy
\[ y_1\geq c_{i,1},\qquad y_2\geq c_{i,2}. \]
Every type \(i\in S\) agent already has the maximum utility \(5\). Hence such agents must also satisfy \(y_3\geq c_{i,3}\). Consequently,
\[ \int_\Omega y_3\,d\lambda \geq \frac1n\sum_{i\in S}c_{i,3} = \frac1{2n} = \rho_3. \]
Because \(y\) is feasible, equality must hold. All terms in the preceding lower bound are nonnegative, so \(y_3=c_{i,3}\) almost everywhere on types in \(S\), while \(y_3=0\) almost everywhere on types outside \(S\).
Thus types in \(S\) remain at their maximum utility, and types outside \(S\) cannot reach their third breakpoint on any positive-measure set. No agent can be strictly improved on a set of positive measure. Therefore \(x\) is PO.
Conversely, suppose that the constructed instance has an EF and PO allocation \(x\). By the EF lemma, every type \(i\) has an almost-everywhere constant utility \(U_i\).
Suppose \(U_k\leq3\) for some type \(k\). Let
\[ H=\{i:U_i=5\}. \]
Every type in \(H\) reaches its third breakpoint almost everywhere. Therefore
\[ m:=\frac1n\sum_{i\in H}c_{i,3}\leq\rho_3. \]
Construct another allocation \(y\) as follows. Give every type \(i\) exactly \(c_{i,1}\) and \(c_{i,2}\) of the first two goods. This uses exactly \(\rho_1=\rho_2=\tfrac12\).
For the third good, initially give \(c_{i,3}\) to every type \(i\in H\) and zero to all other types. This uses mass \(m\). Since \(m\leq\rho_3<1\), put
\[ \alpha=\frac{\rho_3-m}{1-m} \]
and replace the initial third coordinate \(b(\omega)\) by
\[ y_3(\omega)=b(\omega)+\alpha(1-b(\omega)). \]
Then \(0\leq y_3\leq1\) and
\[ \int_\Omega y_3\,d\lambda = m+\alpha(1-m) = \rho_3. \]
Types in \(H\) retain utility \(5\). Every other type reaches its first two breakpoints and therefore obtains utility at least \(4\), which is weakly above its current utility. Type \(k\) is strictly improved on all of \(A_k\), a set of measure \(1/n\). This contradicts PO.
Therefore \(U_i\geq4\) for every \(i\).
Because the maximum utility is \(5\), every \(U_i\) is now either \(4\) or \(5\). Define
\[ S=\{i:U_i=5\}. \]
Every type \(i\) reaches both of its first two breakpoints almost everywhere. The exact first-good resource constraint gives
\[ \int_\Omega\bigl(x_1(\omega)-c_{\theta(\omega),1}\bigr)\,d\lambda=0. \]
The integrand is nonnegative almost everywhere, so \(x_1=c_{i,1}\) almost everywhere on \(A_i\). Similarly, \(x_2=c_{i,2}\) almost everywhere on \(A_i\).
Every type in \(S\) also satisfies \(x_3\geq c_{i,3}\). Hence
\[ m:=\frac1n\sum_{i\in S}c_{i,3}\leq\rho_3. \]
The set \(S\) cannot contain every type, because that would give
\[ m=\frac1n\sum_{i=1}^n\frac{a_i}{A}=\frac1n>\frac1{2n}=\rho_3. \]
Suppose \(m<\rho_3\), and choose \(k\notin S\). Let \(E=\rho_3-m>0\). Because Lebesgue measure is atomless, there exists a measurable \(B\subseteq A_k\) of measure \(\delta>0\) sufficiently small that
\[ \delta c_{k,3}<E. \]
Give all types their first two breakpoints. Give every type in \(S\) its third breakpoint, give the agents in \(B\) the amount \(c_{k,3}\), and initially give every other agent zero of the third good. The remaining third-good supply can be distributed without decreasing anyone’s utility: if the current third coordinate is \(q_0\), use
\[ q=q_0+\beta(1-q_0), \qquad \beta= \frac{\rho_3-\int_\Omega q_0\,d\lambda} {1-\int_\Omega q_0\,d\lambda}. \]
The numerator is nonnegative and the denominator is positive because \(\rho_3<1\). This produces a feasible allocation. Types in \(S\) retain utility \(5\), every type outside \(S\) retains utility at least \(4\), and agents in \(B\) improve from \(4\) to \(5\). This contradicts PO.
Consequently \(m=\rho_3\), so
\[ \frac1{nA}\sum_{i\in S}a_i = \frac1{2n}. \]
Multiplying by \(nA\) yields
\[ \sum_{i\in S}a_i=\frac A2. \]
Thus \(S\) is a solution to the original PARTITION instance.
The reduction is polynomial and proves equivalence between the PARTITION instance and the existence of an EF and PO nonatomic allocation. Therefore the target problem is \(\mathrm{NP}\)-hard. This is an ordinary, potentially weak, hardness result; the proof does not establish strong \(\mathrm{NP}\)-hardness or membership in \(\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The reduction correctly proves weak \( \mathrm{NP} \)-hardness under binary encoding. The completeness and soundness arguments are internally consistent, handle the nonatomic setting directly, and establish the required equivalence with PARTITION.
No mathematical gap affecting the conclusion was found.
The restriction of the EF inequality to \( A_t \times A_t \) is valid because \( A_t \) is measurable. Applying the same almost-everywhere inequality after transposing the coordinates gives the reverse inequality on another full-measure subset. Their intersection therefore yields equality almost everywhere.
The Fubini conclusion that \( u_t \circ x \) is almost everywhere constant on \( A_t \) is valid. The assumption \( \mu_t>0 \) excludes the vacuous zero-measure case.
All constructed values lie in the required domains:
The integers \( A \), the fractions \( a_i/A \), and all other parameters have polynomial binary encoding length.
The identities for the average first- and second-good breakpoints are correct. The claimed antichain property is also correct: for \( j\ne i \), satisfying both inequalities would require simultaneously \( j\ge i \) and \( j\le i \), hence \( j=i \), a contradiction.
For the first two goods, assigning each type its corresponding breakpoint uses exactly the stated average \( 1/2 \).
For the third good, the calculation
\[ \frac1n\sum_{i\in S}\frac{a_i}{A}=\frac1{2n} \]
is correct when \( \sum_{i\in S}a_i=A/2 \). Thus all three resource equalities hold.
Types in \( S \) receive utility \( 5 \), which is the maximum possible utility.
A type outside \( S \) receives utility \( 4 \). By the antichain property, a bundle assigned to another type reaches at most one of its first two breakpoints. Even if it reaches the third breakpoint, its utility is at most \( 2+1=3 \). Comparisons with agents of the same type produce equal utility. Hence the allocation is EF.
Any weak Pareto improvement must give every agent utility at least \( 4 \), which indeed requires both first two breakpoints because omitting either limits utility to \( 3 \).
Every type in \( S \) must retain utility \( 5 \), so its agents must receive at least \( c_{i,3} \) of the third good. These mandatory amounts already integrate to the full third-good supply \( \rho_3 \). Since third-good quantities and all excesses over the mandatory amounts are nonnegative, equality forces:
Types in \( S \) are already at maximum utility, while types outside \( S \) cannot increase from \( 4 \) to \( 5 \) on a positive-measure set. Thus no strict Pareto improvement exists.
For \( H=\{i:U_i=5\} \), every member of \( H \) must reach its third breakpoint almost everywhere, so the lower bound \( m\le\rho_3 \) is valid.
The constructed replacement allocation uses exactly \( 1/2 \) of each of the first two goods. For the third good, \( m\le\rho_3<1 \) makes
\[ \alpha=\frac{\rho_3-m}{1-m} \]
well-defined and contained in \( [0,1] \). The transformation preserves the coordinate range \( [0,1] \) and gives integral exactly \( \rho_3 \).
Types in \( H \) remain at utility \( 5 \). Every other type originally has utility at most \( 4 \) and obtains at least \( 4 \). If some \( U_k\le3 \), type \( k \) is strictly improved on a set of measure \( 1/n \), contradicting PO. Therefore every \( U_i\ge4 \).
Because utilities can only take the values obtained from weights \( 2,2,1 \), the conclusion \( U_i\in\{4,5\} \) follows.
Utility at least \( 4 \) forces both first two breakpoints. The first-good integrand
\[ x_1(\omega)-c_{\theta(\omega),1} \]
is therefore nonnegative almost everywhere, and its integral is zero because both terms integrate to \( 1/2 \). Hence it vanishes almost everywhere. The identical argument applies to the second good.
For \( S=\{i:U_i=5\} \), the mandatory third-good consumption satisfies \( m\le\rho_3 \). The proof correctly excludes \( S=[n] \), since that would require \( 1/n>\rho_3 \).
If \( m<\rho_3 \), a positive-measure subset \( B\subseteq A_k \) with \( \lambda(B)c_{k,3}<\rho_3-m \) exists by atomlessness and positivity of \( c_{k,3} \). The proposed third-coordinate completion has a nonnegative numerator, positive denominator, and parameter in \( [0,1] \), so it gives a feasible allocation. It preserves every type’s utility and strictly improves almost every agent in \( B \), contradicting PO.
Thus \( m=\rho_3 \), and the final algebra correctly yields
\[ \sum_{i\in S}a_i=\frac A2. \]
The reduction establishes a many-one equivalence between PARTITION and the constructed existence problem. Since PARTITION is NP-hard under binary encoding, the target problem is NP-hard. The prover correctly limits the conclusion to potentially weak NP-hardness and does not claim membership in NP or strong NP-hardness.
None.
⟨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.