Answer: \(\mathrm{NP\text{-}complete}\), even when every supply equals \(1/2\)
Theorem 4.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor 0/1-utilities esw-EF-PA is solvable in 𝑂(𝑚2.5) time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(\Theta\) with rational masses \(\mu_\theta\), a finite catalogue \(R\) with rational per-capita supplies \(q_r\) of indivisible copies, binary liked sets \(L_\theta\), and \(t\in\mathbb{N}\), decide whether there exist \(x_{\theta r}\ge0\) such that \(x_{\theta r}=0\) for \(r\notin L_\theta\), \(\sum_{r\in L_\theta}x_{\theta r}=t\mu_\theta\) for every \(\theta\), and \(\sum_\theta x_{\theta r}\le q_r\) for every \(r\); equivalently, does an envy-free mass allocation of whole bundles exist in which every agent receives utility at least \(t\)?
Given a finite set \(R\) of goods, an additive utility \(u:R\to\mathbb N_0\), and rational per-capita supplies \(\rho\in\mathbb Q_{\geq 0}^{R}\), write \(u(B)=\sum_{r\in B}u(r)\) for \(B\subseteq R\). A feasible equal-utility allocation is masses \(x_B\geq0\) and \(U\geq1\) with \(\sum_{B\subseteq R}x_B=1\), \(\sum_{B\ni r}x_B\leq\rho_r\) for every \(r\in R\), and \(x_B>0\Rightarrow u(B)=U\).
Target. Is deciding whether a feasible equal-utility allocation exists solvable in polynomial time, or is it NP-hard?
Nearest known results. In the discrete indivisible-goods setting, deciding whether identical-utility agents admit an envy-free partial allocation in which every agent receives positive utility is strongly NP-hard, even with threshold \(1\). No verified result is recorded here for the distribution-over-types formulation above.
Under the standard binary encoding of utilities and rational supplies, deciding whether a feasible equal-utility allocation exists is \(\mathrm{NP}\)-complete. Hardness already holds when every utility is strictly positive and every supply is exactly \(1/2\).
Thus the problem is not polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\).
Use Equal-Subset-Sum:
Given positive integers \(a_1,\ldots,a_n\), decide whether there are disjoint nonempty index sets \(P,Q\subseteq\{1,\ldots,n\}\) such that
\[ \sum_{i\in P}a_i=\sum_{i\in Q}a_i. \]
This problem is \(\mathrm{NP}\)-complete; the positive-integer restriction is standard [Mucha, Nederlof, Pawlewicz, and Węgrzycki](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.73).
Given an Equal-Subset-Sum instance \(a_1,\ldots,a_n\), introduce one good \(r_i\) for every index \(i\), and set
\[ u(r_i)=a_i,\qquad \rho_{r_i}=\frac12. \]
This construction is polynomial-time and uses only strictly positive utilities.
We prove that the constructed allocation instance is feasible if and only if the Equal-Subset-Sum instance is positive.
Suppose there are disjoint nonempty sets \(P,Q\) with
\[ \sum_{i\in P}a_i=\sum_{i\in Q}a_i=:U. \]
Because all \(a_i\) are positive, \(U\geq 1\). Define
\[ x_{\{r_i:i\in P\}}=\frac12,\qquad x_{\{r_i:i\in Q\}}=\frac12, \]
and set all other masses to zero.
Both supported bundles have utility \(U\), and the total mass is one. Since \(P\cap Q=\varnothing\), every good occurs in at most one supported bundle. Its total consumption is therefore either zero or \(1/2=\rho_{r_i}\). Hence the allocation is feasible.
Suppose a feasible equal-utility allocation \(x\) exists, with common utility \(U\geq1\). Let
\[ \mathcal S=\{B\subseteq R:x_B>0\} \]
be its support.
Every \(B\in\mathcal S\) is nonempty because all utilities are positive and \(u(B)=U\geq1\).
The support cannot consist of a single bundle. Indeed, if \(\mathcal S=\{B\}\), then \(x_B=1\). For every \(r_i\in B\), the consumption of \(r_i\) would be one, contradicting \(\rho_{r_i}=1/2\).
Therefore there are distinct bundles \(B,C\in\mathcal S\). They satisfy
\[ u(B)=u(C)=U. \]
Neither can contain the other. For example, if \(B\subsetneq C\), strict positivity gives
\[ u(C)=u(B)+u(C\setminus B)>u(B), \]
a contradiction.
Consequently \(B\setminus C\) and \(C\setminus B\) are both nonempty. They are disjoint, and cancellation of the common intersection gives
\[ u(B\setminus C) =u(B)-u(B\cap C) =u(C)-u(B\cap C) =u(C\setminus B). \]
Thus
\[ P=\{i:r_i\in B\setminus C\},\qquad Q=\{i:r_i\in C\setminus B\} \]
are disjoint nonempty equal-sum subsets of the original instance.
This proves the correctness of the reduction and hence \(\mathrm{NP}\)-hardness.
Let \(m=|R|\), and suppose a feasible allocation exists for some common utility \(U\). For each supported bundle \(B\), let \(\chi_B\in\{0,1\}^m\) be its incidence vector.
There is always a feasible allocation supported on at most \(m+1\) bundles. Indeed, if more than \(m+1\) bundles have positive mass, the vectors
\[ (1,\chi_B)\in\mathbb R^{m+1} \]
are linearly dependent. Hence there are coefficients \(d_B\), not all zero, satisfying
\[ \sum_B d_B=0,\qquad \sum_B d_B\chi_B=0. \]
Perturbing the masses in the direction \(d\) preserves both total mass and every resource consumption. Choosing the perturbation magnitude maximally while retaining nonnegativity makes at least one supported mass zero. Repetition reduces the support to at most \(m+1\) bundles.
For any fixed collection of at most \(m+1\) bundles, the feasible weights form a rational polytope whose matrix has entries in \(\{0,1\}\) and whose right-hand side consists of the rational supplies and one. If this polytope is nonempty, it has a rational basic feasible point of polynomial encoding length, by Cramer’s rule and the Hadamard determinant bound.
A certificate therefore consists of at most \(m+1\) bundles and their rational masses. In polynomial time one can verify:
Thus the problem belongs to \(\mathrm{NP}\).
The distribution-over-bundles formulation does not remove the discrete subset-sum obstruction. Fractional masses suffice to mix two equal-sum bundles, while the capacity \(1/2\) ensures that any feasible allocation exposes two distinct equal-utility bundles. The decision problem is therefore \(\mathrm{NP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The prover correctly resolves the target. The reduction establishes \( \mathrm{NP} \)-hardness under binary encoding, including the claimed restriction to strictly positive utilities and supplies equal to \( 1/2 \). The certificate argument establishes membership in \( \mathrm{NP} \). No substantive gap or false statement was found.
The stated Equal-Subset-Sum problem asks for disjoint, nonempty index sets \(P,Q\) with equal sums. This matches the standard formulation. The cited paper describes precisely this problem as \( \mathrm{NP} \)-complete and explicitly records that instances may be restricted to positive integers through polynomial reductions. See [Mucha–Nederlof–Pawlewicz–Węgrzycki](https://drops.dagstuhl.de/storage/00lipics/lipics-vol144-esa2019/LIPIcs.ESA.2019.73/LIPIcs.ESA.2019.73.pdf).
The prover does not claim strong \( \mathrm{NP} \)-hardness, so the numerical size of the \(a_i\) under binary encoding causes no issue.
The construction assigns one good \(r_i\) to each input index, with
\[ u(r_i)=a_i,\qquad \rho_{r_i}=\frac12. \]
This is computable in polynomial time. Each utility is strictly positive, and every supply has constant-size rational encoding.
Given disjoint nonempty equal-sum sets \(P,Q\), the two corresponding bundles receive mass \(1/2\) each.
The checks are correct:
Thus every positive Equal-Subset-Sum instance maps to a feasible allocation instance.
Because the supported masses sum to one, the support is nonempty. Every supported bundle is nonempty because all item utilities are positive while the common utility satisfies \(U\geq1\).
The proof that the support cannot be a singleton is correct: a unique supported bundle would have mass one, so each good in that nonempty bundle would be consumed with mass one, violating its \(1/2\) supply.
Hence there are distinct supported bundles \(B,C\). Since all goods have strictly positive utility, neither bundle can properly contain the other while having equal utility. Therefore both differences \(B\setminus C\) and \(C\setminus B\) are nonempty and disjoint.
The cancellation calculation
\[ u(B\setminus C)=u(B)-u(B\cap C) =u(C)-u(B\cap C)=u(C\setminus B) \]
is valid by additivity. Translating these bundle differences back to index sets gives the required disjoint, nonempty equal-sum subsets.
Thus the reverse implication is established.
The support-reduction argument is sound. If more than \(m+1\) bundles are supported, their vectors \((1,\chi_B)\in\mathbb R^{m+1}\) are linearly dependent. A dependence preserves both total mass and every resource-consumption coordinate. Since the dependence coefficients sum to zero and are not all zero, they have both signs, so a maximal feasible perturbation eliminates at least one positive mass. Repetition leaves at most \(m+1\) supported bundles without changing feasibility or their common utility.
For a fixed collection of at most \(m+1\) bundles, the feasible-weight region is a bounded rational polytope. A nonempty such polytope has a rational basic feasible point. Standard determinant bounds give polynomial binary encoding length because:
The proposed certificate therefore has polynomial length. All required properties—bundle utilities, rational masses, total mass, and supply inequalities—are verifiable using polynomial-time integer and rational arithmetic.
The reduction proves \( \mathrm{NP} \)-hardness, and the certificate argument proves membership in \( \mathrm{NP} \). Consequently the claimed \( \mathrm{NP} \)-completeness result follows. It fully answers the target’s polynomial-time-versus-hardness question.
⟨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.