Answer: \(\mathrm{NP}\)-hard, even for \(\tau=1\), strictly positive integer valuations, and \(q_b=1/2\) for every good type.
Theorem 12 — class: algorithmic
Given finitely many complete agent types \(a\in[d]\), good types \(b\in[t]\), rational masses \(\mu_a>0\) summing to \(1\), rational additive values \(v_{ab}\ge 0\), and rational per-capita supplies \(q_b\ge 0\), decide whether and construct a finite-support assignment \(\lambda_{a,z}\ge 0\) of type mass to integral bundles \(z\in\mathbb{Z}_{\ge 0}^t\). Require \(\sum_z\lambda_{a,z}=\mu_a\) for every \(a\), \(\sum_{a,z}\lambda_{a,z}z_b=q_b\) for every \(b\), and \(v_a\cdot z\ge v_a\cdot z'\) whenever \(\lambda_{a,z}>0\) and \(\lambda_{a',z'}>0\). Each unit of mass receives an integral bundle; the computational task is to decide whether such an envy-free assignment exists and output one if it does.
A society is given by its support: \(\tau=d\geq1\) complete additive valuation types, each with positive binary-rational mass \(\mu_a\), where \(\sum_a\mu_a=1\). Here \(\tau\) is the support size, not the number of possible types; write \(m=t\geq1\) for the number of good types.
Values \(v_{ab}\geq0\) and per-capita supplies \(q_b\geq0\) are binary rationals. Every valuation vector is nonzero; vectors proportional by a positive factor represent the same type and are merged. Supplies are arbitrary, without a lower-bound promise. Let \(L\) be the total input bit length.
An assignment has finite support on pairs \((a,z)\), with integral bundles \(z\in\mathbb Z_{\geq0}^{m}\) and nonnegative masses \(\lambda_{a,z}\). It must satisfy \(\sum_z\lambda_{a,z}=\mu_a\) for every \(a\) and \(\sum_{a,z}\lambda_{a,z}z_b=q_b\) for every \(b\).
Envy-freeness requires \(v_a\cdot z\geq v_a\cdot z'\) for every two positive-mass pairs \((a,z),(a',z')\), including pairs within the same type; indifference is allowed. Each individual receives an integral bundle. A constructed assignment lists its positive-mass pairs, with bundle coordinates and rational masses encoded in binary.
Can existence be decided and a finite-support envy-free assignment constructed in time polynomial in \(m,\tau,L\), or is deciding existence \(\mathrm{NP}\)-hard?
For finite societies with \(n_a\) agents of each valuation type, \(n=\sum_a n_a\), and \(r=\gcd(n_1,\ldots,n_d)\), a polynomial-time construction is known when every good-type count is divisible by \(r\) and exceeds a threshold \(\nu=O(n^2/r)\), holding the good-type count and normalized valuation separation fixed; the threshold improves to \(O(n)\) when all agents have distinct valuations. [Source](https://arxiv.org/html/2512.10892v1#S6.SS3).
Unrestricted discrete envy-free existence is NP-hard. [Source](https://arxiv.org/html/2512.10892v1#S1). No result settling the exact mass-assignment problem above was identified in the search.
Deciding existence is \(\mathrm{NP}\)-hard, even when \(\tau=1\), every valuation coordinate is a positive integer, and every supply is \(1/2\). Thus a polynomial-time algorithm that decides existence and constructs an assignment would imply \(\mathrm{P}=\mathrm{NP}\).
We prove this by a polynomial-time many-one reduction from PARTITION. The encoding explicitly excludes bundles containing repeated copies that could otherwise invalidate the reduction.
Suppose \(\tau=1\), \(\mu_1=1\), and the valuation vector is \(v\).
For any two positive-mass bundles \(z,z'\), envy-freeness requires both \(v\cdot z\geq v\cdot z'\) and \(v\cdot z'\geq v\cdot z\). Hence all positive-mass bundles have a common value \(U\). The mass and supply constraints imply
\(U=\sum_z\lambda_z(v\cdot z)=v\cdot\left(\sum_z\lambda_z z\right)=v\cdot q.\)
Consequently, every positive-mass bundle must be an integral solution of \(v\cdot z=v\cdot q\). This holds regardless of whether the masses themselves are rational.
PARTITION asks whether positive integers \(a_0,\ldots,a_{k-1}\), encoded in binary, admit a subset whose sum is half their total. This problem is \(\mathrm{NP}\)-complete; see [Karp’s original paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
We may assume that \(W:=\sum_{i=0}^{k-1}a_i\) is even: multiplying every input integer by \(2\) preserves the answer and ensures this condition.
Define
\(A:=\max_i a_i,\qquad B:=k+1,\qquad R:=kA+1,\)
\(D:=RB^{k-1}+A,\qquad H:=kD+1.\)
Construct a society with one valuation type of mass \(1\) and \(m=2k\) good types, arranged in pairs \((i,+)\), \((i,-)\). Set
\(v_{i,+}:=H+RB^i+a_i,\qquad v_{i,-}:=H+RB^i,\)
and
\(q_{i,+}=q_{i,-}:=\frac12.\)
These data satisfy all input requirements. In particular, all valuations are strictly positive integers, the single valuation vector is nonzero, and there is no type-merging issue.
The value forced by Section 1 is
\(U:=v\cdot q=kH+R\sum_{i=0}^{k-1}B^i+\frac W2.\)
Write \(C:=R\sum_{i=0}^{k-1}B^i+W/2\). For each index, \(RB^i+a_i/2\leq D\); therefore
\(0\leq C\leq kD<H.\)
Let an arbitrary integral bundle have coordinates \(x_i:=z_{i,+}\) and \(y_i:=z_{i,-}\), and suppose \(v\cdot z=U\). Define
\(K:=\sum_{i=0}^{k-1}(x_i+y_i)\)
and
\(E:=R\sum_{i=0}^{k-1}B^i(x_i+y_i)+\sum_{i=0}^{k-1}a_i x_i.\)
Then \(v\cdot z=HK+E\).
Every good has value at least \(H\), while
\(U=kH+C<(k+1)H.\)
Thus \(K\leq k\). Each item contributes at most \(D\) to \(E\), so
\(0\leq E\leq KD\leq kD<H.\)
The equality \(HK+E=kH+C\), with both remainders \(E,C\) between \(0\) and \(H-1\), now gives
\(K=k,\qquad E=C.\)
Set \(\alpha:=\sum_i a_i x_i\). Since \(\sum_i x_i\leq K=k\),
\(0\leq\alpha\leq kA<R.\)
Also \(0\leq W/2<R\). Reducing the equality \(E=C\) modulo \(R\) therefore gives the exact equality
\(\alpha=\frac W2.\)
Subtracting these equal low-order terms and dividing by \(R\) yields
\(\sum_{i=0}^{k-1}B^i(x_i+y_i)=\sum_{i=0}^{k-1}B^i.\)
Each coefficient \(c_i:=x_i+y_i\) satisfies \(0\leq c_i\leq k=B-1\). Thus these coefficients are valid base-\(B\) digits. Uniqueness of base-\(B\) representation implies \(c_i=1\) for every \(i\). Explicitly, reduction modulo \(B\) gives \(c_0=1\); subtracting this digit and dividing by \(B\) repeats the argument for each subsequent digit.
Hence
\(x_i+y_i=1,\qquad x_i,y_i\in\{0,1\}.\)
Together with \(\sum_i a_i x_i=W/2\), this proves that the indices with \(x_i=1\) form a solution to PARTITION.
If the society has an envy-free assignment, then PARTITION is feasible.
Its total mass is \(1\), so at least one positive-mass bundle exists. Section 1 gives that bundle value \(U\), and Section 3 extracts a partition from it.
If PARTITION is feasible, then the society has an envy-free assignment.
Let \(S\) satisfy \(\sum_{i\in S}a_i=W/2\). Construct \(z\) by choosing good \((i,+)\) when \(i\in S\), and good \((i,-)\) otherwise. Its value is
\(v\cdot z=kH+R\sum_i B^i+\frac W2=U.\)
Let \(\bar z\) be its coordinatewise complement: \(\bar z_{i,+}=1-z_{i,+}\) and \(\bar z_{i,-}=1-z_{i,-}\). Since the sum of all valuation coordinates is \(2U\),
\(v\cdot\bar z=2U-v\cdot z=U.\)
Assign mass \(1/2\) to each of \(z,\bar z\). Their total mass is \(1\), and their average in every coordinate is \(1/2\), exactly the required supply. Their equal values establish envy-freeness. This is a valid assignment with two integral bundles and binary-encoded rational masses.
Thus the constructed society admits an assignment if and only if the PARTITION instance is feasible.
Every constructed valuation coordinate has bit length
\(O\!\left(k\log(k+1)+\log(A+1)\right).\)
There are \(2k\) coordinates, and the masses and supplies have constant bit length. All constructed integers can therefore be computed and encoded in time polynomial in the PARTITION input length.
This completes the polynomial-time reduction and proves \(\mathrm{NP}\)-hardness for the exact mass-assignment problem. The hardness already occurs with a single supported valuation type; allowing arbitrary masses does not remove it.
⟨structured verdict parsed — rendered above⟩
The output correctly proves that deciding existence is \(\mathrm{NP}\)-hard, even with one supported valuation type, strictly positive integer valuations, and every supply equal to \(1/2\). The reduction addresses the exact assignment model in USER_TASK. No major or minor mathematical issues were found.
The cited theorem is that PARTITION on binary-encoded positive integers is \(\mathrm{NP}\)-complete. This is the appropriate source problem; its binary encoding is essential to the complexity conclusion. The theorem is also explicitly confirmed in [MIT’s complexity lecture notes](https://people.csail.mit.edu/rrw/6.045-2020/lec17-color.pdf).
Multiplying every input integer by \(2\) preserves the answer and ensures an even total. This remains valid when the original total is odd: an equal partition of the doubled instance would imply an equal partition of the original instance. The preprocessing increases each integer’s bit length by at most one.
The construction uses nonempty PARTITION instances, so \(k\geq1\) and \(A\) is defined. This is a standard valid restriction of the source problem.
For one valuation type, envy-freeness applies in both directions to every pair of positive-mass bundles. Therefore their values must coincide.
Because the support is finite and the masses sum to \(1\), averaging that common value gives exactly \(v\cdot q\). Thus every positive-mass bundle satisfies the claimed integral equation.
This argument does not require rational masses. Consequently, permitting arbitrary nonnegative real masses cannot invalidate the reduction’s necessity direction.
All constructed valuations are strictly positive integers, hence admissible binary rationals. The sole type has mass \(1\), its vector is nonzero, and the type-merging requirement causes no difficulty. Every supply is the admissible binary rational \(1/2\).
The target value is computed correctly:
\[
U=kH+R\sum_{i=0}^{k-1}B^i+\frac W2.
\]
Since \(B^i\leq B^{k-1}\) and \(a_i/2\leq A\), the stated bound on each summand of \(C\) is correct. Consequently,
\[
0\leq C\leq kD<H.
\]
For any nonnegative integral bundle of value \(U\), each item contributes at least \(H\). Since \(U<(k+1)H\), its item count satisfies \(K\leq k\).
Each item’s contribution beyond \(H\) is at most \(D\), including the plus goods. Hence
\[
0\leq E\leq KD\leq kD<H.
\]
Both decompositions \(HK+E\) and \(kH+C\) therefore have remainders in the required range. Uniqueness of quotient and remainder gives \(K=k\) and \(E=C\). There is no circular dependence in these bounds.
The bound
\[
0\leq\alpha\leq kA<R
\]
follows from \(\sum_i x_i\leq k\). Also, \(W\leq kA\), so \(0\leq W/2<R\). Both quantities are integers because preprocessing ensures even \(W\).
Reduction modulo \(R\) therefore establishes exact equality, rather than merely congruence:
\[
\alpha=W/2.
\]
After subtracting these terms, the base-\(B\) equation is correct. Each coefficient satisfies \(0\leq c_i\leq k=B-1\), so no carries are possible. The explicitly stated digit-extraction argument establishes \(c_i=1\) for every index.
Nonnegative integrality then gives \(x_i,y_i\in\{0,1\}\), and the selected indices have sum \(W/2\). This verifies the crucial exclusion of bundles with repeated copies.
An assignment of total mass \(1\) has at least one positive-mass bundle. The preceding argument extracts a partition from that bundle, establishing necessity.
Conversely, the displayed bundle from a partition has value \(U\). Its coordinatewise complement is nonnegative and integral, and its value is also \(U\), since the total of all valuation coordinates is \(2U\).
Mass \(1/2\) on each bundle gives total mass \(1\), supplies exactly \(1/2\) in every coordinate, and envy-freeness. The two bundles are distinct because their coordinates are binary and complementary. Their rational masses satisfy the required output encoding.
The stated coordinate bit-length bound is correct. The power \(B^{k-1}\) has bit length proportional to \(k\log(k+1)\); the remaining products and sums add only logarithmic factors already covered by the bound.
With \(2k\) coordinates, the complete output instance has polynomial bit length and can be computed using polynomial-time integer arithmetic.
Thus the many-one reduction is valid. The output establishes the hardness alternative requested by USER_TASK. It does not claim membership in \(\mathrm{NP}\) or strong \(\mathrm{NP}\)-hardness, and neither is needed.
No repair or additional clarification is necessary.
⟨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.