Answer: \(\mathrm{NP}\text{-complete}\)
Corollary 2 — class: hardness
Given a finite goods set \(O\), a finite utility-type set \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\), per-capita supplies \(q_o\), and additive utilities \(u_t\), decide whether nonnegative masses \(x_{t,B}\) over integral bundles \(B\subseteq O\) satisfy \(\sum_B x_{t,B}=\mu_t\) and \(\sum_{t,B:o\in B}x_{t,B}=q_o\), while no two positive-mass bundles \(B,D\) have an assigned type \(t\) with \(x_{t,B}>0\), \(u_t(D)>u_t(B)\), and \(u_r(D)>u_r(B)\) for every active type \(r\) with \(\mu_r>0\).
A society is given by its support: the list \(T\) of \(\tau\) utility types with positive masses \(\mu_t\), each a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input also gives a finite goods set \(O\), with \(m=|O|\), binary rational per-capita supplies \(q_o\in[0,1]\), and nonnegative binary rational additive item utilities \(u_t(o)\). Let \(L\) be the total input bit length.
Bundles are all subsets \(B\subseteq O\), including the empty bundle; they are implicit rather than listed in the input. Each recipient receives an integral bundle, with at most one copy of each good.
A mass allocation consists of real numbers \(x_{t,B}\geq0\) satisfying \(\sum_{B\subseteq O}x_{t,B}=\mu_t\) for every \(t\), and \(\sum_{t\in T}\sum_{B\ni o}x_{t,B}=q_o\) for every \(o\); all supply must be allocated.
Call it free of unanimous envy if there are no \(t,s\in T\) and \(B,D\subseteq O\) with \(x_{t,B}>0\), \(x_{s,D}>0\), \(u_t(D)>u_t(B)\), and \(u_r(D)>u_r(B)\) for every \(r\in T\). Comparisons include recipients of the same type; indifference does not approve envy.
Is deciding whether such a mass allocation free of unanimous envy exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finitely many agents with nonnegative rational additive utilities and a complete allocation of indivisible goods, existence of an allocation free of unanimous envy is the intended NP-complete decision problem of the [discrete hardness result](https://jair.org/index.php/jair/article/download/13778/26864/32482).
No result settling exactly the mass problem above was located in the literature search.
The decision problem is \(\mathrm{NP}\)-complete. Hardness holds even with exactly two distinct, nonproportional utility types, strictly positive item utilities, masses \(\mu_1=\mu_2=\tfrac12\), and supplies \(q_o=\tfrac12\) for every good.
The proof below applies directly to the specified mass model.
For bundles \(B,D\subseteq O\), write \(B\prec D\) if \(u_r(B)<u_r(D)\) for every \(r\in T\). Call a family of bundles an antichain if it contains no pair satisfying \(B\prec D\).
Given a mass allocation, define its aggregate bundle masses by
\(y_B=\sum_{t\in T}x_{t,B}\).
They satisfy
\(\sum_{B\subseteq O}y_B=1,\qquad \sum_{B\ni o}y_B=q_o\quad\text{for every }o\in O.\)
Lemma. A mass allocation free of unanimous envy exists if and only if there are nonnegative aggregate masses satisfying these equations whose positive support is an antichain.
Proof. Suppose \(x\) is free of unanimous envy. If \(y_B>0\) and \(y_D>0\), there are types \(t,s\) with \(x_{t,B}>0\) and \(x_{s,D}>0\). If \(B\prec D\), every type—including \(t\)—strictly prefers \(D\) to \(B\). This would violate the definition. Thus the positive support of \(y\) is an antichain.
Conversely, given such aggregate masses, set
\(x_{t,B}=\mu_t y_B.\)
Then
\(\sum_Bx_{t,B}=\mu_t,\qquad \sum_t\sum_{B\ni o}x_{t,B}=\left(\sum_t\mu_t\right)q_o=q_o.\)
Any unanimous-envy violation would involve two positive aggregate masses with \(B\prec D\), contradicting the antichain property. \(\square\)
In particular, the positive type masses impose no additional restriction on existence beyond their sum being one. The utility types determine which bundle pairs are forbidden.
We reduce from the standard \(\mathrm{NP}\)-complete problem PARTITION: given positive binary integers \(a_1,\ldots,a_n\), decide whether some index set \(I\) satisfies
\(\sum_{i\in I}a_i=\tfrac12\sum_{i=1}^n a_i.\)
We may restrict to \(n\geq2\): inputs with fewer items are decidable directly, so this restriction preserves hardness.
Create goods \(O=\{o_1,\ldots,o_n\}\), two types of mass \(\tfrac12\) each, and supplies \(q_{o_i}=\tfrac12\). Define utilities by
\(u_1(o_i)=a_i\quad\text{for every }i,\)
\(u_2(o_1)=a_1+\tfrac12,\qquad u_2(o_i)=a_i\quad\text{for }i\geq2.\)
These are strictly positive binary rationals. The two utility vectors are distinct and nonproportional: their common positive value on \(o_2\) would force any proportionality factor to be one, whereas their values on \(o_1\) differ. The construction has polynomial encoding length.
For any bundle \(B\), let
\(w(B)=\sum_{o_i\in B}a_i,\qquad A=\sum_{i=1}^n a_i.\)
We first establish the exact comparison rule
\(B\prec D\quad\Longleftrightarrow\quad w(B)<w(D).\)
The forward implication follows from \(u_1=w\). For the reverse implication, integer weights give \(w(D)-w(B)\geq1\), while
\(u_2(D)-u_2(B)=w(D)-w(B)+\tfrac12\bigl(\mathbf{1}_{o_1\in D}-\mathbf{1}_{o_1\in B}\bigr)\geq\tfrac12>0.\)
Thus both types strictly prefer \(D\).
Suppose a mass allocation free of unanimous envy exists, and aggregate it as in Section 1. All occupied bundles must have the same integer weight, say \(c\): otherwise the comparison rule would make the smaller-weight bundle unanimously dominated.
Using the supply equations and exchanging finite sums gives
\(c=\sum_B y_Bw(B)=\sum_{i=1}^n a_i\sum_{B\ni o_i}y_B=\tfrac12\sum_{i=1}^n a_i=\tfrac A2.\)
Here the first equality uses that the occupied bundles all have weight \(c\) and their masses sum to one.
At least one bundle has positive mass. Its weight is therefore \(A/2\), providing a solution to PARTITION.
Conversely, suppose \(B\subseteq O\) has \(w(B)=A/2\). Its complement \(C=O\setminus B\) also has weight \(A/2\).
Set \(y_B=y_C=\tfrac12\), with all other aggregate masses zero. Every good belongs to exactly one of \(B,C\), so its supply is exactly \(\tfrac12\). Since \(u_1(B)=u_1(C)\), neither bundle strictly unanimously dominates the other.
The lemma therefore supplies a valid allocation. Explicitly, each type receives mass \(\tfrac14\) of each bundle.
This proves both directions of the reduction and establishes \(\mathrm{NP}\)-hardness under the stated restrictions. The same reduction also works with a single type having utility \(u_1=w\).
It remains to prove membership in \(\mathrm{NP}\). We show that every yes-instance admits a certificate containing at most \(m+1\) bundles and polynomial-length rational masses.
Start with any feasible aggregate distribution whose support is an antichain. Among all feasible aggregate distributions supported within this finite family, choose one with minimum support size. Write its positive masses as \(y_1,\ldots,y_k\), on bundles \(B_1,\ldots,B_k\).
For each bundle define the column
\(v_j=(1,\mathbf{1}_{o_1\in B_j},\ldots,\mathbf{1}_{o_m\in B_j})^{\mathsf T}.\)
The aggregate constraints are
\(\sum_{j=1}^k y_jv_j=b,\qquad b=(1,q_{o_1},\ldots,q_{o_m})^{\mathsf T}.\)
These columns are linearly independent. Indeed, otherwise there would be nonzero real coefficients \(\alpha_j\) with \(\sum_j\alpha_jv_j=0\). The first coordinate gives \(\sum_j\alpha_j=0\), so some coefficients are positive and some negative.
Define
\(\delta=\min_{\alpha_j>0}\frac{y_j}{\alpha_j},\qquad y'_j=y_j-\delta\alpha_j.\)
All new masses are nonnegative, at least one becomes zero, and the aggregate constraints remain satisfied. Their support remains within the original antichain. This contradicts minimum support size.
Consequently \(k\leq m+1\).
The matrix with columns \(v_j\) has column rank \(k\). Select \(k\) rows forming a nonsingular square matrix \(C\), and let \(b'\) be the corresponding coordinates of \(b\). The masses are uniquely determined by
\(Cy=b'.\)
All entries of \(C\) are zero or one. Let \(D\) be the product of the denominators of the input supplies. Its binary length is \(O(L)\), and every coordinate of \(Db'\) is an integer between zero and \(D\).
Let \(C_j\) replace column \(j\) of \(C\) by \(Db'\). Cramer’s rule gives
\(y_j=\frac{\det C_j}{D\det C}.\)
The determinant expansion yields \(|\det C|\leq k!\) and \(|\det C_j|\leq Dk!\): every product for \(C_j\) contains exactly one entry from its replaced column. Since \(\det C\neq0\), each mass therefore has a rational encoding of length \(O(L+k\log k)\).
These rational values equal the original masses, because the selected system has a unique solution. Hence they satisfy all aggregate equations, including the rows not selected.
A certificate lists the at most \(m+1\) bundles as incidence vectors and their rational masses. A verifier checks:
The last condition is exactly the antichain condition. All checks use polynomially many exact rational operations on polynomial-length numbers. By the lemma, acceptance certifies a valid mass allocation.
Thus the problem belongs to \(\mathrm{NP}\).
The specified mass-allocation existence problem is \(\mathrm{NP}\)-complete, even under the two-type restrictions proved above. Therefore a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the stated mass problem: the decision problem is \(\mathrm{NP}\)-complete. I found no major or minor mathematical issues.
If \(y_B>0\), then some type has positive mass on \(B\), because \(T\) is finite and all allocation entries are nonnegative. Thus, if two occupied bundles satisfy \(B\prec D\), recipients occupying those bundles witness precisely the prohibited unanimous envy. The additional condition involving the envying recipient’s type is satisfied because the comparison is strict for every type.
Conversely, \(x_{t,B}=\mu_t y_B\) satisfies each type’s mass equation and every supply equation, using \(\sum_t\mu_t=1\). Any unanimous-envy violation would imply a forbidden comparison between two occupied aggregate bundles. This also handles comparisons between recipients of the same type.
Consequently, the aggregate formulation preserves the original problem exactly.
The source problem is the standard \(\mathrm{NP}\)-complete PARTITION problem on positive binary integers, stated with its exact target equality. Restricting to \(n\geq2\) removes only directly decidable exceptional inputs and preserves hardness.
The constructed instance has two positive masses summing to one, supplies in the permitted range, and strictly positive binary rational utilities. Its encoding length is polynomial in the source encoding length.
The nonproportionality argument is valid: equality of the positive utilities on \(o_2\) forces a proportionality factor of one, which contradicts the differing utilities on \(o_1\).
The implication \(B\prec D\Rightarrow w(B)<w(D)\) follows immediately from the first utility type.
In the reverse direction, integrality gives \(w(D)-w(B)\geq1\). The perturbation to the second type’s utility difference is at least \(-\tfrac12\), so that difference is at least \(\tfrac12>0\). Therefore both types strictly prefer \(D\).
Equal-weight bundles cannot be strictly unanimously comparable because the first type is indifferent. Hence the equivalence covers all bundle pairs, including the empty bundle.
For a feasible allocation, the aggregation lemma and comparison rule force every occupied bundle to have one common integer weight \(c\). The displayed finite-sum calculation correctly uses normalization and the exact supply equations to obtain \(c=A/2\). Normalization ensures at least one occupied bundle exists, so such a bundle supplies a PARTITION solution. If \(A\) is odd, this equality is impossible, as required.
Conversely, a partition bundle and its complement both have weight \(A/2\). Positivity of the source weights ensures these bundles are distinct. Assigning aggregate mass \(\tfrac12\) to each allocates exactly the prescribed supply of every good. Their equal first-type utilities exclude strict unanimous dominance in either direction.
The explicit type-level allocation gives each type total mass \(\tfrac12\). Thus the construction proves the claimed hardness restrictions.
The original occupied family is finite, even though bundles are implicit in the input. A feasible distribution of minimum support size within that family therefore exists.
If its columns were dependent, the leading coordinate would force the nonzero dependence coefficients to have both signs. The specified positive value of \(\delta\) preserves nonnegativity, preserves every equation, and eliminates at least one occupied bundle without introducing any new bundle. This contradicts minimum support size.
Consequently, the columns are independent and their number is at most \(m+1\).
Column independence guarantees a nonsingular square submatrix obtained by selecting rows. The product \(D\) of supply denominators has binary length \(O(L)\) and clears the selected right-hand side.
Cramer’s rule is applied correctly. The determinant bounds \(\lvert\det C\rvert\leq k!\) and \(\lvert\det C_j\rvert\leq Dk!\) follow from the stated determinant expansion. They give the claimed polynomial encoding length. Uniqueness of the selected system ensures these rational masses equal the existing feasible masses and satisfy all remaining equations.
The certificate checks exactly normalization, supplies, and absence of strict unanimous dominance. Exact additive-utility comparisons involve polynomially many rational operations with polynomial bit lengths. Thus membership in \(\mathrm{NP}\) is established.
No additional clarification or repair is needed. The proof establishes ordinary NP-completeness; it does not claim strong NP-completeness.
⟨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.