Answer: \(\mathrm{NP}\text{-hard}\), even with two equally weighted types, two rounds, and positive integer utilities.
Theorem 7 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateFor every n ⩾2 and k ∈nN, an allocation sequence that is proportional and Pareto-optimal overall al- ways exists, and can be computed in time O(nmk · m).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu\) over utility types \(t\), item labels \(I\), a population-to-supply ratio \(r\), and \(k\) rounds, find a nonnegative mass distribution \(q_{t,h}\) over histories \(h=(S_1,\ldots,S_k)\) of integral bundles such that \(\sum_h q_{t,h} = \mu_t\), each item has normalized capacity \(1/r\) in every round, and every supported type-history satisfies overall proportionality: \(\sum_l u_t(S_l) \ge (k/r) \sum_o u_t(o)\); among these schedules maximize aggregate welfare.
A society is given by its support: the list of the \(\tau\) utility types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) item labels \(I\). Each type has additive, time-independent utilities \(u_t(o)\in\mathbb Q\), which may be positive, negative, or zero. The input includes a binary rational population-to-supply ratio \(r\geq2\) and a positive integer \(k\), encoded in unary, with \(k/r\in\mathbb Z_{>0}\). Let \(L\) be the total binary encoding length of the rational input data.
A history is \(h=(S_1,\ldots,S_k)\), with \(S_\ell\subseteq I\); empty bundles are allowed. A schedule assigns nonnegative rational masses \(q_{t,h}\) satisfying \(\sum_hq_{t,h}=\mu_t\) and exhaustive allocation \(\sum_t\sum_{h:o\in S_\ell}q_{t,h}=1/r\) for every \(o\in I\) and every round \(\ell\).
Every pair with \(q_{t,h}>0\) must satisfy overall proportionality: \(\sum_{\ell=1}^ku_t(S_\ell)\geq(k/r)\sum_{o\in I}u_t(o)\). Maximize aggregate welfare \(\sum_{t,h}q_{t,h}\sum_{\ell=1}^ku_t(S_\ell)\) over such schedules.
Is exact welfare maximization for this mass allocation problem solvable in time polynomial in \(m,\tau,k,L\), or is it NP-hard?
For finite societies with \(n\geq2\) and \(k\in n\mathbb Z_{>0}\), an overall proportional and Pareto-optimal sequence always exists and can be found by exponential enumeration; computing such a sequence is also FPT in \(n+m\). [Source](https://arxiv.org/html/2304.01644)
No result settling this support-encoded mass welfare problem was located.
Exact welfare maximization is \(\mathrm{NP}\)-hard, even when \(\tau=2\), \(\mu_1=\mu_2=1/2\), \(r=k=2\), and all utilities are positive integers. The two types can moreover have identical utilities except for a one-unit difference on one item.
We prove this by a polynomial reduction from positive-integer SUBSET SUM: given binary-encoded positive integers \(a_1,\ldots,a_N,T\), determine whether some subset sums to \(T\). This is a standard \(\mathrm{NP}\)-hard problem; see [Knapsack and Subset Sum with Small Items](https://arxiv.org/html/2105.04035v1).
Given the SUBSET SUM instance, put \(A=\sum_{i=1}^{N}a_i\) and \(M=1+T+A\). Introduce item labels
\(\displaystyle I=\{p_1,\ldots,p_N,b_1,\ldots,b_N,s\}\),
with positive integer weights
\(\displaystyle w_{p_i}=M5^{i-1}+a_i,\qquad w_{b_i}=M5^{i-1},\qquad w_s=M\sum_{i=1}^{N}5^{i-1}+T.\)
For a vector \(d\) indexed by \(I\), write \(w\cdot d=\sum_{o\in I}w_od_o\).
Encoding lemma. The SUBSET SUM instance is a YES-instance if and only if there exists \(d\in\{-1,0,1\}^{I}\) satisfying \(d_s=1\) and \(w\cdot d=0\).
Proof. Suppose such a vector exists. Write \(\alpha_i=d_{p_i}\) and \(\beta_i=d_{b_i}\). Expanding the equality gives
\(\displaystyle 0=M\sum_{i=1}^{N}(1+\alpha_i+\beta_i)5^{i-1}+T+\sum_{i=1}^{N}a_i\alpha_i.\)
The last two terms have absolute value at most \(T+A=M-1\). They are a multiple of \(M\), so they must equal zero. Consequently,
\(\displaystyle T+\sum_{i=1}^{N}a_i\alpha_i=0,\qquad \sum_{i=1}^{N}(1+\alpha_i+\beta_i)5^{i-1}=0.\)
Each coefficient \(c_i=1+\alpha_i+\beta_i\) belongs to \(\{-1,0,1,2,3\}\). Reducing the second equality modulo \(5\) forces \(c_1=0\), since zero is the only multiple of \(5\) in this set. Dividing by \(5\) and repeating forces every \(c_i=0\).
Thus \(\alpha_i+\beta_i=-1\). Because both coordinates belong to \(\{-1,0,1\}\), the only possibilities are
\(\displaystyle (\alpha_i,\beta_i)=(-1,0)\quad\text{or}\quad(0,-1).\)
It follows that \(\sum_{i:\alpha_i=-1}a_i=T\), giving the required subset.
Conversely, let \(J\subseteq\{1,\ldots,N\}\) satisfy \(\sum_{i\in J}a_i=T\). Set \(d_s=1\), and choose
\(\displaystyle (d_{p_i},d_{b_i})=(-1,0)\ \text{for }i\in J,\qquad (d_{p_i},d_{b_i})=(0,-1)\ \text{for }i\notin J.\)
Every coefficient \(1+d_{p_i}+d_{b_i}\) vanishes, and the remaining term is \(T-\sum_{i\in J}a_i=0\). Hence \(w\cdot d=0\). This proves the lemma.
Use the item labels above, and set
\(\displaystyle \tau=2,\qquad \mu_1=\mu_2=\frac12,\qquad r=k=2.\)
These satisfy all input promises, including \(k/r=1\). Define utilities by
\(\displaystyle u_2(o)=2w_o,\qquad u_1(o)=2w_o+\mathbf{1}_{\{o=s\}}.\)
All utilities are positive integers. Let \(W=\sum_{o\in I}w_o\).
For a history \(h=(S_1,S_2)\), define its count vector and deviation vector by
\(\displaystyle x_o(h)=\mathbf{1}_{\{o\in S_1\}}+\mathbf{1}_{\{o\in S_2\}},\qquad d_o(h)=x_o(h)-1.\)
Thus \(x(h)\in\{0,1,2\}^{I}\) and \(d(h)\in\{-1,0,1\}^{I}\).
Since \(k/r=1\), proportionality for a positive-mass history is precisely
\(\displaystyle 2w\cdot d(h)+d_s(h)\geq 0\quad\text{for type }1,\)
and
\(\displaystyle 2w\cdot d(h)\geq 0\quad\text{for type }2.\)
We first show that every positive-mass history, for either type, satisfies \(w\cdot d(h)\geq 0\).
This follows directly for type \(2\). For type \(1\), the number \(w\cdot d(h)\) is an integer. If it were negative, it would be at most \(-1\); since \(d_s(h)\leq 1\), we would have
\(\displaystyle 2w\cdot d(h)+d_s(h)\leq -2+1=-1,\)
contradicting proportionality.
Now consider any feasible schedule. Exhaustive allocation in each of the two rounds gives, for every item \(o\),
\(\displaystyle \sum_{t,h}q_{t,h}x_o(h)=\frac12+\frac12=1.\)
Also, \(\sum_{t,h}q_{t,h}=\mu_1+\mu_2=1\). Therefore
\(\displaystyle \sum_{t,h}q_{t,h}d_o(h)=0\)
for every item, and hence
\(\displaystyle \sum_{t,h}q_{t,h}\,w\cdot d(h)=0.\)
Every summand is nonnegative. Consequently, every positive-mass history satisfies
\(\displaystyle w\cdot d(h)=0.\)
For type \(1\), proportionality now further implies \(d_s(h)\geq 0\), or equivalently \(x_s(h)\in\{1,2\}\).
This argument applies to arbitrary rational mixtures of histories.
For any feasible schedule, its welfare is
\(\displaystyle \sum_{t,h}q_{t,h}\sum_{o\in I}u_t(o)x_o(h)=2\sum_{o\in I}w_o\sum_{t,h}q_{t,h}x_o(h)+\sum_hq_{1,h}x_s(h).\)
Using exhaustive allocation, this becomes
\(\displaystyle 2W+\sum_hq_{1,h}x_s(h).\)
Suppose the SUBSET SUM instance is a NO-instance. A positive-mass type-\(1\) history with \(x_s(h)=2\) would give a vector \(d(h)\) with \(d_s(h)=1\) and \(w\cdot d(h)=0\), contradicting the encoding lemma. Thus every such history has \(x_s(h)=1\), and every feasible schedule has welfare
\(\displaystyle 2W+\sum_hq_{1,h}=2W+\frac12.\)
There is a feasible schedule achieving this value: for each type, assign mass \(1/4\) to each of the histories \((I,\varnothing)\) and \((\varnothing,I)\). Every history receives every item exactly once, so proportionality holds with equality. Every item receives total mass \(1/2\) in each round.
Therefore, in a NO-instance, the exact optimum is \(2W+1/2\).
Suppose the SUBSET SUM instance is a YES-instance. By the encoding lemma, choose \(d\in\{-1,0,1\}^{I}\) with \(d_s=1\) and \(w\cdot d=0\). Define
\(\displaystyle x^{(1)}=\mathbf{1}+d,\qquad x^{(2)}=\mathbf{1}-d.\)
Both vectors belong to \(\{0,1,2\}^{I}\), and they satisfy
\(\displaystyle x^{(1)}_o+x^{(2)}_o=2\quad\text{for every }o,\qquad w\cdot x^{(1)}=w\cdot x^{(2)}=W.\)
Also, \(x^{(1)}_s=2\) and \(x^{(2)}_s=0\).
We explicitly realize these counts while meeting the supply constraint in each round. For any vector \(x\in\{0,1,2\}^{I}\), define
\(\displaystyle H(x)=\bigl(\{o:x_o\geq 1\},\{o:x_o=2\}\bigr).\)
This history has count vector \(x\). Let \(H^{\mathrm{rev}}(x)\) denote the history obtained by swapping its rounds.
For type \(t\), assign mass \(1/4\) to each of \(H(x^{(t)})\) and \(H^{\mathrm{rev}}(x^{(t)})\), merging identical histories if necessary. These masses sum to \(1/2\) for each type. In each round, type \(t\) receives item \(o\) with mass \(x^{(t)}_o/4\). Hence its total allocated mass is
\(\displaystyle \frac{x^{(1)}_o+x^{(2)}_o}{4}=\frac12,\)
as required.
Every type-\(1\) history has utility \(2W+2\), exceeding its proportionality threshold \(2W+1\). Every type-\(2\) history has utility \(2W\), exactly its threshold. Thus the schedule is feasible, with welfare
\(\displaystyle \frac12(2W+2)+\frac12(2W)=2W+1.\)
No schedule can have greater welfare: the formula from Section 4 and the bounds \(x_s(h)\leq 2\), \(\sum_hq_{1,h}=1/2\) give
\(\displaystyle 2W+\sum_hq_{1,h}x_s(h)\leq 2W+1.\)
Therefore, in a YES-instance, the exact optimum is \(2W+1\).
There are \(m=2N+1\) items. Each constructed weight has binary length \(O(N+\log M)\), because \(5^{N-1}\) has binary length \(O(N)\). Moreover, \(\log M\) is polynomially bounded by the SUBSET SUM input length. All utilities and the threshold \(2W+1\) are therefore computable with polynomial encoding length and in polynomial time.
We have proved the exact equivalence:
Thus deciding whether the optimum is at least \(2W+1\) solves SUBSET SUM. Exact welfare maximization is consequently \(\mathrm{NP}\)-hard, even with the fixed parameters and positive utilities stated above. A polynomial-time algorithm in \(m,\tau,k,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned problem: exact welfare maximization is \(\mathrm{NP}\)-hard under the stated support encoding. I found no major or minor mathematical issues.
The prover uses the decision version of SUBSET SUM with binary-encoded positive integers: determine whether a subset of \(a_1,\ldots,a_N\) sums exactly to \(T\). This is an appropriate \(\mathrm{NP}\)-hard source problem. The cited paper explicitly describes this positive-integer problem and states its weak \(\mathrm{NP}\)-hardness. Weak hardness suffices for the claimed reduction with binary-encoded utilities. [Knapsack and Subset Sum with Small Items](https://arxiv.org/html/2105.04035v1)
The argument neither requires nor claims strong \(\mathrm{NP}\)-hardness.
The expansion of the weighted relation is correct. With \(d_s=1\), \(\alpha_i=d_{p_i}\), and \(\beta_i=d_{b_i}\), the equation \(w\cdot d=0\) becomes
\[
0=M\sum_{i=1}^{N}(1+\alpha_i+\beta_i)5^{i-1}
+T+\sum_{i=1}^{N}a_i\alpha_i.
\]
Since \(\alpha_i\in\{-1,0,1\}\), the residual term satisfies
\[
\left|T+\sum_{i=1}^{N}a_i\alpha_i\right|
\leq T+A=M-1.
\]
The displayed equality makes this residual an integer multiple of \(M\). The strict bound therefore forces it to vanish, and the remaining weighted sum also vanishes.
Each coefficient \(c_i=1+\alpha_i+\beta_i\) belongs to \(\{-1,0,1,2,3\}\). Reducing the weighted sum modulo \(5\) forces \(c_1=0\), because this coefficient range contains no other multiple of \(5\). Successive division by \(5\) and reduction modulo \(5\) correctly forces all coefficients to vanish. Negative coefficients do not invalidate this reasoning.
The equation \(\alpha_i+\beta_i=-1\), with both coordinates in \(\{-1,0,1\}\), has exactly the two possibilities listed by the prover. Consequently, the indices with \(\alpha_i=-1\) form a subset summing to \(T\).
Conversely, the stated vector constructed from a target-sum subset lies in the required coordinate domain, has \(d_s=1\), and makes both parts of the expansion zero.
Assessment: Both directions of the encoding lemma are fully established.
The construction satisfies every relevant input promise:
For any history, \(x_o\in\{0,1,2\}\) and \(d_o=x_o-1\in\{-1,0,1\}\). Subtracting each type’s proportionality threshold gives exactly
\[
2w\cdot d+d_s\geq0
\]
for type \(1\), and
\[
2w\cdot d\geq0
\]
for type \(2\).
Assessment: The translation of proportionality into deviation inequalities is correct.
Type \(2\)’s proportionality directly implies \(w\cdot d\geq0\). For type \(1\), integrality is used correctly: if \(w\cdot d<0\), then \(w\cdot d\leq-1\), while \(d_s\leq1\). Thus its proportionality expression would be at most \(-1\), a contradiction.
Exhaustive allocation gives total expected count \(1\) for every item across the two rounds. Since total population mass is also \(1\), each item’s expected deviation is zero. Multiplication by the fixed weights and summation therefore gives
\[
\sum_{t,h}q_{t,h}\,w\cdot d(h)=0.
\]
Every term corresponding to positive mass is nonnegative. There are finitely many histories, so this equality forces \(w\cdot d(h)=0\) for every positive-mass pair \((t,h)\).
Type \(1\)’s proportionality then correctly reduces to \(d_s(h)\geq0\), hence \(x_s(h)\in\{1,2\}\).
Assessment: This conclusion applies to arbitrary feasible rational mixtures. The proof does not assume a single history per type or an integral allocation.
Separating the common utility \(2w_o\) from type \(1\)’s additional utility on \(s\) correctly gives
\[
\text{welfare}=2W+\sum_hq_{1,h}x_s(h).
\]
In a NO-instance, a positive-mass type-\(1\) history with \(x_s=2\) would yield precisely the vector excluded by the encoding lemma. Since type-\(1\) histories already satisfy \(x_s\in\{1,2\}\), every used type-\(1\) history must have \(x_s=1\). The resulting welfare is exactly \(2W+1/2\).
The proposed baseline schedule is feasible: each type’s two masses sum to \(1/2\); every used history receives each item exactly once across both rounds; and the two types together allocate mass \(1/2\) to each item in each round. Proportionality holds with equality.
Assessment: The claimed NO-instance optimum is both an upper bound and an attained value.
The vectors \(x^{(1)}=\mathbf1+d\) and \(x^{(2)}=\mathbf1-d\) have valid count coordinates, add coordinatewise to \(2\), and both have weighted sum \(W\). Their counts on \(s\) are respectively \(2\) and \(0\), as claimed.
The history \(H(x)\) realizes the prescribed count vector. Giving it and its reversal mass \(1/4\) each makes an item’s allocated mass in either round equal to \(x_o/4\). This calculation remains correct when the histories coincide and their masses are merged.
Therefore, combining the two types gives allocated mass \(1/2\) for every item in every round. Type \(1\)’s used histories have utility \(2W+2\), above their threshold \(2W+1\); type \(2\)’s have utility \(2W\), equal to their threshold.
The welfare is \(2W+1\). The universal bound \(x_s\leq2\), together with total type-\(1\) mass \(1/2\), proves that no feasible schedule has larger welfare.
Assessment: The YES-instance optimum is exactly the stated value, attained by rational masses.
The bit-length analysis is correct. Each power \(5^{i-1}\) has \(O(N)\) bits, and the sum appearing in \(w_s\) also has \(O(N)\) bits. Each weight therefore has \(O(N+\log M)\) bits. Computing \(A\), \(M\), the powers, the weights, and the utilities requires polynomial time in the source input length.
Summing the weights to obtain \(W\) preserves polynomial bit length, so the decision threshold \(2W+1\) is also polynomially encodable. The number of utilities is linear in \(N\), and the unary parameter \(k=2\) is constant.
Thus the construction is a polynomial reduction to deciding whether feasible welfare reaches \(2W+1\). Its YES and NO optima are separated exactly as claimed. An exact welfare maximization algorithm would decide this threshold question and therefore solve SUBSET SUM.
Assessment: The \(\mathrm{NP}\)-hardness conclusion follows. No claim of membership in \(\mathrm{NP}\), or of \(\mathrm{NP}\)-completeness, is needed.
No repair or additional clarification is required.
⟨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.