Answer: \(\mathrm{NP}\text{-complete}\), already for \(\tau=1\) and \(q_\ell=\tfrac12\) for every category.
Proposition 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximate[PFS-Exist] is NP-complete, ∀n ≥2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many complete additive valuation types \(\mathcal T\), rational masses \(\mu_t\ge 0\) summing to \(1\), nonnegative values \(w_{t\ell}\), and rational per-capita supplies \(q_\ell\in[0,1]\), does there exist a mass assignment \(x_{t,S}\ge 0\) to integral bundles \(S\subseteq[m]\) such that \(\sum_S x_{t,S}=\mu_t\) for each \(t\), \(\sum_{t,S:\ell\in S}x_{t,S}=q_\ell\) for each category \(\ell\), and every bundle assigned positive mass satisfies \(\sum_{\ell\in S}w_{t\ell}\ge\sum_{\ell=1}^m q_\ell w_{t\ell}\)?
Let \(m\ge 1\) be the number of goods categories. A society is given by its support: a list \(\mathcal T\) of \(\tau\ge 1\) complete additive valuation types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type specifies binary-rational values \(w_{t\ell}\ge 0\) for every category; supplies are binary rationals \(q_\ell\in[0,1]\). Bundles are subsets \(S\subseteq[m]\), so each individual receives at most one unit of each category, with utility \(u_t(S)=\sum_{\ell\in S}w_{t\ell}\). Utility ties and empty bundles are allowed.
A feasible proportional assignment consists of real masses \(x_{t,S}\ge 0\) satisfying \(\sum_{S\subseteq[m]}x_{t,S}=\mu_t\) for every type and \(\sum_{t\in\mathcal T}\sum_{S\ni\ell}x_{t,S}=q_\ell\) for every category, with \(x_{t,S}>0\Rightarrow u_t(S)\ge\sum_{\ell=1}^m q_\ell w_{t\ell}\). Thus all supplies must be allocated and proportionality holds for every bundle receiving positive mass.
Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is deciding whether a feasible proportional assignment exists solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For finitely many agents and indivisible objects, deciding whether a complete allocation gives every agent at least \(1/n\) of her value for all objects is \(\mathrm{NP}\)-complete for every fixed \(n\ge 2\) ([Bouveret–Lemaître](https://recherche.noiraudes.net/resources/papers/AAMAS14-full.pdf)).
No result settling the exact support-encoded mass-assignment problem above was located in the literature search.
The problem is \(\mathrm{NP}\)-complete. Hardness already holds with \(\tau=1\), positive integer valuations, and \(q_\ell=\tfrac12\) for every category.
Suppose \(\tau=1\), so its mass is \(1\). Write its valuations as \(w_\ell\), its assignment masses as \(x_S\), and its proportionality threshold as \(h=\sum_{\ell=1}^m q_\ell w_\ell\).
Every assignment satisfying the mass and supply equalities has average utility
\(\displaystyle \sum_{S\subseteq[m]}x_Su(S)=\sum_{\ell=1}^m w_\ell\sum_{S\ni\ell}x_S=\sum_{\ell=1}^m w_\ell q_\ell=h.\)
If the assignment is proportional, every bundle of positive mass has utility at least \(h\). Since \(\sum_Sx_S=1\), it follows that
\(\displaystyle x_S>0\quad\Longrightarrow\quad u(S)=h.\)
Indeed, the nonnegative quantities \(x_S(u(S)-h)\) sum to zero, so each is zero. Thus allowing real assignment masses does not remove the requirement for a bundle attaining the threshold exactly.
We use the standard \(\mathrm{NP}\)-complete problem PARTITION: given positive integers \(a_1,\ldots,a_n\) in binary, decide whether some \(I\subseteq[n]\) satisfies \(\sum_{i\in I}a_i=\tfrac12\sum_{i=1}^n a_i\). Its completeness is established in [Karp’s original paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Construct an instance of the stated problem by setting
\(\displaystyle m=n,\qquad \tau=1,\qquad \mu_1=1,\qquad w_{1\ell}=a_\ell,\qquad q_\ell=\tfrac12\quad(\ell\in[m]).\)
These data satisfy all required hypotheses: the mass is positive and sums to one, valuations are nonnegative binary rationals, and supplies lie in \([0,1]\). If the PARTITION input has binary length \(B\), the output length is \(L=O(B+n)\), and the construction takes \(O(B+n)\) time.
Let \(A=\sum_{\ell=1}^m a_\ell\). The proportionality threshold is \(A/2\).
A partition gives a feasible assignment. Suppose \(S\subseteq[m]\) has value \(A/2\). Its complement also has value \(A/2\). Set
\(\displaystyle x_{1,S}=\tfrac12,\qquad x_{1,[m]\setminus S}=\tfrac12,\)
and set all other masses to zero. The type’s total mass is one. Each category belongs to exactly one of these two bundles, so its allocated mass is exactly \(\tfrac12=q_\ell\). Both bundles attain the proportionality threshold.
A feasible assignment gives a partition. Conversely, suppose a feasible proportional assignment exists. By Section 1, every positive-mass bundle has value exactly \(A/2\). At least one bundle has positive mass because the masses sum to one. That bundle therefore supplies a solution to PARTITION.
Consequently, the constructed instance is feasible if and only if the PARTITION instance is a yes-instance. This proves \(\mathrm{NP}\)-hardness under polynomial-time many-one reductions, already for the stated restricted instances.
We also prove membership in \(\mathrm{NP}\), including the necessary bound on rational certificate size.
For each type \(t\), define its admissible bundles by
\(\displaystyle \mathcal A_t=\left\{S\subseteq[m]:\sum_{\ell\in S}w_{t\ell}\geq\sum_{\ell=1}^m q_\ell w_{t\ell}\right\}.\)
After excluding inadmissible bundles, feasibility is precisely the system \(Ax=b,\ x\geq0\), where \(d=\tau+m\), and:
Thus \(A\) is a finite matrix with entries in \(\{0,1\}\).
Assume feasibility and choose a feasible solution with the smallest number \(r\) of positive coordinates.
Its corresponding columns must be linearly independent. Otherwise, let \(z\neq0\) be a dependence among those columns, so \(Az=0\). Summing the type rows gives \(\sum_jz_j=0\), because each column contains exactly one type-row entry equal to one. Hence \(z\) has both positive and negative coordinates.
Set \(\lambda=\min_{j:z_j>0}x_j/z_j\). Then \(x-\lambda z\) remains nonnegative, satisfies the same equalities, and has strictly fewer positive coordinates, a contradiction.
Therefore these columns are independent, and \(r\leq d\).
Select \(r\) rows on which these columns form a nonsingular square matrix \(C\). The supported masses are the unique solution of \(Cx=b'\), where \(b'\) consists of the selected entries of \(b\).
Let \(D\) be the product of the denominators of all entries of \(b\). Its binary length is \(O(L)\). Since all entries of \(b\) lie in \([0,1]\), the vector \(c=Db'\) has integer entries between zero and \(D\).
By Cramer’s rule,
\(\displaystyle x_j=\frac{\det C_j}{D\det C},\)
where \(C_j\) replaces column \(j\) of \(C\) by \(c\). The determinant expansion gives
\(\displaystyle 1\leq|\det C|\leq r!,\qquad |\det C_j|\leq r!D.\)
The second bound holds because each product in that expansion contains exactly one entry from \(c\), bounded by \(D\), and all remaining factors belong to \(\{0,1\}\).
Hence each mass has a rational representation using \(O(L+d\log(d+1))\) bits.
A certificate therefore lists at most \(d\) type–bundle pairs, each bundle represented by an \(m\)-bit incidence vector, together with their rational masses. Its total length is
\(\displaystyle O\!\left(d\bigl(m+L+d\log(d+1)\bigr)\right).\)
A verifier checks nonnegativity, every type-mass equality, every supply equality, and proportionality for every listed positive-mass bundle using exact rational arithmetic. Its running time is \(\operatorname{poly}(m,\tau,L)\). Thus the problem belongs to \(\mathrm{NP}\).
Combining Sections 2 and 3 proves \(\mathrm{NP}\)-completeness. A deterministic algorithm polynomial in \(m,\tau,L\) would therefore imply \(\mathrm{P}=\mathrm{NP}\).
For comparison, enumerating all \(\tau2^m\) type–bundle pairs, retaining admissible bundles, and solving the resulting rational linear feasibility problem gives a deterministic running time of \(2^{O(m)}\operatorname{poly}(m,\tau,L)\). The explicit linear program has only \(m+\tau\) equality constraints, but potentially exponentially many variables.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is correct: the support-encoded mass-assignment problem is \(\mathrm{NP}\)-complete, already with one type, positive integer valuations, and every supply equal to \(\tfrac12\). The reduction and the rational-certificate argument are rigorous. No repair is required.
For \(\tau=1\), the sole type has mass \(1\). The displayed identity
\[
\sum_S x_Su(S)=\sum_\ell w_\ell q_\ell=h
\]
follows directly from the supply equalities and exchanging finite sums.
Proportionality implies that every term \(x_S(u(S)-h)\) is nonnegative: it is zero when \(x_S=0\), and nonnegative when \(x_S>0\). The mass equality gives
\[
\sum_S x_S(u(S)-h)=h-h\sum_Sx_S=0.
\]
Consequently every positive-mass bundle attains utility exactly \(h\).
This argument correctly handles real assignment masses, utility ties, zero valuations, and empty bundles. It establishes a necessary condition for one-type feasibility; the prover does not incorrectly assert that one threshold-attaining bundle suffices for arbitrary supplies.
The source problem is stated correctly: binary-encoded positive integers must admit a subset whose sum is half the total. Its \(\mathrm{NP}\)-completeness is the standard result cited in [Karp’s paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
The constructed instance satisfies every input restriction:
Both directions are valid.
Forward direction. A subset of value \(A/2\) and its complement both meet the threshold. Assigning mass \(\tfrac12\) to each gives total mass \(1\) and supply \(\tfrac12\) in every category. Since the category set is nonempty, the subset and its complement are distinct, so the two mass declarations do not conflict.
Reverse direction. The averaging argument forces every positive-mass bundle to have value \(A/2\). At least one such bundle exists because the finite collection of masses sums to \(1\). It therefore supplies a PARTITION witness.
Odd totals cause no exception: the reverse implication still requires an integer-valued bundle to attain \(A/2\). The case of a single positive integer is also handled correctly.
Thus the reduction proves hardness for the exact continuous assignment problem in the task, without relying on the finite-agent allocation result.
Restricting variables to admissible bundles is exactly equivalent to the original proportionality condition. Inadmissible bundles must have zero mass, and admissible bundles may receive any nonnegative mass consistent with the equalities.
The matrix description is correct. Every column has precisely one type-row entry equal to \(1\), and its category entries encode the bundle. The right-hand side correctly records all type masses and supplies.
There are finitely many columns, despite their potentially exponential number. This suffices for the existence arguments used next.
A feasible solution with minimum support exists: support sizes belong to a finite set of integers.
If its supported columns were dependent, the stated dependence vector would satisfy \(\sum_jz_j=0\), obtained by summing the type rows. A nonzero such vector necessarily has both signs.
The chosen \(\lambda\) is positive and well-defined. For positive coordinates of \(z\), its definition ensures nonnegativity after subtraction; for negative coordinates, masses increase. At least one supported mass becomes zero, no unsupported mass becomes positive, and all equalities remain satisfied.
This contradicts minimality. Therefore the supported columns are independent and their number is at most \(d=\tau+m\). There is no missing assumption about boundedness or vertices.
Column independence guarantees a nonsingular square submatrix using \(r\) rows. The supported masses satisfy that square system uniquely.
The denominator product \(D\) has binary length \(O(L)\), since all denominators used are encoded in the input. Each selected right-hand-side entry lies in the unit interval, so multiplying by \(D\) produces an integer between zero and \(D\).
The Cramer’s-rule expression is correct. Both determinant bounds follow from the stated permutation expansion:
These bounds yield the claimed polynomial binary length for every mass. Possible determinant signs do not affect the encoding bound or the nonnegativity of the already feasible solution.
The certificate-length estimate also accommodates type identifiers: their encoding length is absorbed by the \(L\) term.
A certificate lists at most \(\tau+m\) bundles. Exact rational arithmetic checks all mass equalities, supply equalities, and utility inequalities in polynomial time in \(m,\tau,L\). Unlisted variables are zero, so these checks verify a complete assignment.
The exponential-time comparison is also valid. Enumeration creates at most \(\tau2^m\) variables, with polynomially bounded coefficient lengths. Polynomial-time feasibility testing for explicitly represented rational linear programs therefore gives the stated bound \(2^{O(m)}\operatorname{poly}(m,\tau,L)\).
The conclusion that a polynomial-time decision algorithm would imply \(\mathrm{P}=\mathrm{NP}\) follows correctly. The proof establishes ordinary \(\mathrm{NP}\)-completeness; it makes no unsupported claim of strong hardness.
⟨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.