Answer: Exact welfare maximization is \(\mathrm{NP}\)-hard, already with one type and two hidden layers; deciding whether the optimum is at least \(B\) is \(\mathrm{NP}\)-complete.
Theorem 2 (MILP) — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe MVNN-based WDP max a∈F P i∈N N (W i,bi) i (ai) can be equivalently formulated as the following MILP:5 max a∈F,zi,k,µi,k,ηi,k,yi,k (X i∈N W i,Kizi,Ki−1 ) (11) s.t. for i ∈N and k ∈{2, . . . , Ki −1} zi,1 = ai (12) W i,k−1zi,k−1 + bi,k−1 ≤ηi,k (13) ηi,k ≤W i,k−1zi,k−1 + bi,k−1 + yi,k · Li,k 1 (14) 0 ≤ηi,k ≤(1 −yi,k) · Li,k 2 (15) ηi,k −µi,k · Li,k 3 ≤zi,k ≤ηi,k (16) 1 −(1 −µi,k) · Li,k 4 ≤zi,k ≤1 (17) yi,k ∈{0, 1}di k, µi,k ∈{0, 1}di k (18) 4To account for a general cutoff t ̸= 1 in the bReLU, one needs to adjust (9) by replacing the left- and rightmost 1 with t. 5To account for a general cutoff t ̸= 1 in the bReLU, one needs to adjust (17) by replacing the left- and rightmost 1 with t.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) item types, a support \(T\) of \(\tau\) valuation types with rational masses \(\mu_t\) summing to \(1\), rational per-capita item supplies \(q_j\), and a rational-parameter MVNN \(v_t\) for each type, compute a welfare-maximizing mass assignment \(x_{t,S}\): maximize \(\sum_{t\in T}\sum_{S\subseteq[m]}x_{t,S}v_t(S)\), subject to \(\sum_{S\subseteq[m]}x_{t,S}=\mu_t\), \(\sum_{t\in T}\sum_{S\ni j}x_{t,S}\le q_j\), and \(x_{t,S}\ge0\). Each unit of mass receives an integral bundle; ask for the exact computational complexity and algorithms as functions of \(m\), \(\tau\), network size, and input bit length.
Let \(m\ge1\). A society is given by its support: a list \(T\) of \(\tau\ge1\) valuation types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts listed types, not possible valuations.
Each type has an explicitly encoded rational MVNN: starting with the bundle indicator \(z^0=\mathbf1_S\), hidden layers apply \(z^k=\phi(W^kz^{k-1}+b^k)\) coordinatewise, where \(\phi(u)=\min\{1,\max\{0,u\}\}\), all weights are nonnegative and hidden biases nonpositive. The scalar output is a nonnegative linear readout with zero bias. Thus \(v_t(S)\ge0\) is monotone and \(v_t(\varnothing)=0\); network depths and widths are unrestricted inputs.
Supplies \(q_j\ge0\) are binary rationals. An assignment splits each type's mass among integral bundles \(S\subseteq\{1,\ldots,m\}\), including the empty bundle, with no additional bundle restrictions. Its variables satisfy \(x_{t,S}\ge0\), \(\sum_Sx_{t,S}=\mu_t\), and \(\sum_t\sum_{S\ni j}x_{t,S}\le q_j\).
The computational problem is to maximize \(\sum_t\sum_Sx_{t,S}v_t(S)\) exactly and compute an optimal assignment, represented by its nonzero bundle-mass entries. Let \(H\) be the total explicitly encoded network size and \(L\) the total input bit length, including a rational threshold \(B\).
Is this exact welfare-maximization problem polynomial-time solvable in \(m,\tau,H,L\), or is it NP-hard, already for deciding whether the optimum is at least \(B\)?
For finitely many agents and one copy of each item, MVNN welfare maximization has an equivalent succinct MILP formulation; this establishes neither polynomial-time solvability nor a hardness classification ([source](https://arxiv.org/pdf/2109.15117)).
No result settling this exact mass-assignment problem was located in the literature search.
The exact welfare-maximization problem is \(\mathrm{NP}\)-hard. Its threshold decision problem is \(\mathrm{NP}\)-complete.
Hardness holds already with:
The proof explicitly allows arbitrary splitting of the type’s mass among bundles.
We reduce from satisfiability of conjunctive normal form formulas with at most three literals per clause, a standard \(\mathrm{NP}\)-complete problem. See [Karp’s original paper](https://www2.seas.gwu.edu/~simhaweb/champalg/tsp/papers/KarpOriginal.pdf).
Let the input formula be \(F=C_1\land\cdots\land C_r\), on Boolean variables \(y_1,\ldots,y_n\). We may assume \(n\ge1\) and \(r\ge1\): adding a fresh variable and a tautological clause enforces these conditions without changing satisfiability.
Introduce two items \(u_i^+,u_i^-\) for each variable, and two selector items \(a,b\). Thus the item set is
\(\mathcal M=\{u_i^+,u_i^-:1\le i\le n\}\cup\{a,b\},\qquad m=2n+2.\)
There is one type, with mass \(1\). Set \(q_j=\tfrac12\) for every item, and set \(B=1\).
For each clause \(C_k\), define its literal-item set
\(P_k=\{u_i^+:y_i\text{ occurs in }C_k\}\cup\{u_i^-:\neg y_i\text{ occurs in }C_k\}.\)
Let \(Q_k\) be obtained from \(P_k\) by exchanging \(u_i^+\) and \(u_i^-\) for every variable.
Consider the following list of \(K=n+1+2r\) item sets:
Define \(v(S)=1\) precisely when \(S\) intersects every set in this list; otherwise define \(v(S)=0\).
This valuation is monotone. We next give its explicit permitted MVNN encoding.
Write the listed sets as \(R_1,\ldots,R_K\). For a bundle indicator \(z^0=\mathbf1_S\), the first hidden layer has one neuron per listed set:
\(h_\ell=\phi\!\left(\sum_{j\in R_\ell}z^0_j\right),\qquad 1\le\ell\le K.\)
Its weights belong to \(\{0,1\}\), and its biases are zero. Since the inputs are Boolean,
\(h_\ell=1\ \Longleftrightarrow\ S\cap R_\ell\ne\varnothing,\)
and otherwise \(h_\ell=0\).
The second hidden layer consists of one neuron:
\(g=\phi\!\left(\sum_{\ell=1}^{K}h_\ell-(K-1)\right).\)
Its weights are all \(1\), and its bias is the nonpositive integer \(-(K-1)\). Because the first-layer outputs are Boolean, \(g=1\) exactly when all of them equal \(1\); otherwise \(g=0\).
Finally, use the scalar readout \(v(S)=g\), with weight \(1\) and zero bias. This realizes the required valuation exactly and gives \(v(\varnothing)=0\).
The first hidden layer has width \(K\), and the second has width \(1\). Even when every matrix entry, including zeros, is explicitly encoded, the network uses \(O((n+r)(n+1))\) entries. Its largest bias has magnitude \(K-1\). Consequently, the entire constructed instance has polynomial encoding length and is computable in polynomial time.
Lemma. Every bundle \(S\) with \(v(S)=1\) has \(|S|\ge n+1\). Moreover, a bundle with \(v(S)=1\) and \(|S|=n+1\) exists if and only if \(F\) is satisfiable.
Proof. A valuable bundle must intersect all \(n\) variable pairs and the selector pair. These \(n+1\) pairs are disjoint, so it contains at least \(n+1\) items.
If it contains exactly \(n+1\) items, it contains exactly one item from each pair. There are two selector cases.
If \(a\in S\), then \(b\notin S\). The requirements involving \(P_k\cup\{b\}\) therefore force \(S\cap P_k\ne\varnothing\) for every clause. Define \(y_i\) to be true exactly when \(u_i^+\in S\). Since exactly one of \(u_i^+,u_i^-\) is selected, intersection with \(P_k\) means that clause \(C_k\) has a true literal. Hence this assignment satisfies \(F\).
If \(b\in S\), then \(a\notin S\). Now the requirements involving \(Q_k\cup\{a\}\) force \(S\cap Q_k\ne\varnothing\) for every clause. Define \(y_i\) to be true exactly when \(u_i^-\in S\). By the definition of \(Q_k\), these intersections again mean that every clause has a true literal.
Conversely, if \(\sigma\) satisfies \(F\), select \(a\) and, for every variable, select \(u_i^+\) when \(\sigma(y_i)\) is true and \(u_i^-\) when it is false. This bundle has size \(n+1\). It intersects every variable pair and the selector pair, every \(P_k\) because \(\sigma\) satisfies \(F\), and every \(Q_k\cup\{a\}\) because it contains \(a\). Its value is therefore \(1\). This proves the lemma.
Suppose \(\sigma\) satisfies \(F\). Let \(S_\sigma\) be the bundle constructed in the lemma, and let \(S_\sigma^c=\mathcal M\setminus S_\sigma\).
We already know \(v(S_\sigma)=1\). Its complement contains \(b\), exactly one item from each variable pair, and intersects every \(Q_k\): exchanging the variable items exchanges \(P_k\) with \(Q_k\). It also intersects every \(P_k\cup\{b\}\) because it contains \(b\). Thus \(v(S_\sigma^c)=1\).
Assign mass \(\tfrac12\) to each of these complementary bundles. Every item appears in exactly one of them, so each item’s consumption is exactly \(\tfrac12\). The assignment is feasible and has welfare \(1\).
No assignment can have welfare greater than \(1\), since total mass is \(1\) and every bundle value is at most \(1\). Therefore, when \(F\) is satisfiable,
\(\operatorname{OPT}=1.\)
Suppose \(F\) is unsatisfiable. By the lemma, every bundle of value \(1\) has at least \(n+2\) items.
For any feasible mass assignment, write its bundle masses as \(x_S\). Summing all item-supply constraints gives
\(\displaystyle \sum_{S\subseteq\mathcal M}x_S|S|=\sum_{j\in\mathcal M}\sum_{S\ni j}x_S\le\sum_{j\in\mathcal M}q_j=n+1.\)
Because \(v(S)\) is Boolean, the welfare equals the total mass assigned to valuable bundles. Consequently,
\(\displaystyle (n+2)\sum_{S\subseteq\mathcal M}x_Sv(S)\le\sum_{S\subseteq\mathcal M}x_S|S|\le n+1.\)
It follows that
\(\displaystyle \operatorname{OPT}\le\frac{n+1}{n+2}<1.\)
This inequality applies to every fractional assignment, regardless of how many bundles receive positive mass.
Combining the two cases proves
\(F\text{ is satisfiable}\ \Longleftrightarrow\ \operatorname{OPT}\ge B,\qquad B=1.\)
Thus the threshold decision problem, and hence exact welfare maximization, is \(\mathrm{NP}\)-hard.
We now prove membership in \(\mathrm{NP}\), allowing all networks and rational inputs specified in the question.
Introduce one nonnegative slack variable for each item-supply constraint. The assignment problem becomes a finite linear program
\(\max c^\top y\quad\text{subject to}\quad Ay=b,\quad y\ge0,\)
with \(d=\tau+m\) equality rows. All entries of \(A\) belong to \(\{0,1\}\). Its columns comprise the bundle-mass variables and the supply slacks.
The matrix has row rank \(d\): the empty-bundle column for each type is its type-row unit vector, and each slack column is its item-row unit vector.
The feasible set is nonempty, since assigning each type entirely to the empty bundle is feasible. It is bounded: each bundle mass is at most its type mass, and each slack is at most its item supply. It is also closed. Thus it is a nonempty compact polytope, and a linear objective attains its maximum at a vertex.
At a vertex, the columns corresponding to positive coordinates are linearly independent. Indeed, a dependence would give a nonzero vector \(h\), supported on those coordinates, with \(Ah=0\). For sufficiently small \(\varepsilon>0\), both \(y+\varepsilon h\) and \(y-\varepsilon h\) would remain nonnegative and feasible. Their midpoint would be \(y\), contradicting that \(y\) is a vertex.
Therefore some optimal assignment has at most \(d=\tau+m\) positive bundle-mass entries.
Extend the positive-coordinate columns of this vertex to a basis of \(d\) columns of \(A\). The resulting square matrix \(A_0\) is nonsingular and has entries in \(\{0,1\}\). The vertex coordinates on these columns solve \(A_0y_0=b\).
Let \(D_b\) be the product of the denominators of the entries of \(b\). Its bit length is \(O(L)\), and the integer entries of \(D_bb\) also have bit length \(O(L)\).
By Cramer’s rule, each coordinate is a ratio with denominator \(D_b\det(A_0)\) and numerator a determinant obtained by replacing one column of \(A_0\) with \(D_bb\). Determinant expansion bounds their bit lengths by \(O(L+d\log d)\). Hence the nonzero bundle masses admit polynomial-length rational encodings.
A certificate lists at most \(\tau+m\) entries, each specifying a type, an \(m\)-bit bundle indicator, and a rational mass. The type-mass equalities and supply inequalities can be checked by exact rational arithmetic.
Each network can also be evaluated exactly in polynomial time. To justify the bit bound, fix the clipping outcomes during an evaluation. Each remaining neuron expression expands into sums of products along directed paths. A path uses each encoded parameter occurrence at most once. Thus every intermediate denominator divides the product of all network-parameter denominators, whose bit length is \(O(L)\).
Hidden outputs lie in \([0,1]\), and preactivations and the final readout have magnitudes bounded by the sums of the relevant encoded coefficient magnitudes. Their numerators therefore also have polynomial bit length. Exact evaluation uses polynomially many operations on polynomial-length integers.
The verifier can consequently compute the certificate’s exact welfare and compare it with \(B\) in polynomial time. Whenever \(\operatorname{OPT}\ge B\), the sparse optimal assignment above supplies such a certificate.
The threshold decision problem therefore belongs to \(\mathrm{NP}\) and is \(\mathrm{NP}\)-complete. In particular, a polynomial-time exact optimization algorithm in \(m,\tau,H,L\) would imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. The reduction establishes \(\mathrm{NP}\)-hardness despite arbitrary mass splitting, and the certificate argument establishes \(\mathrm{NP}\)-completeness of the threshold decision problem. No major or minor mathematical issues were found.
Satisfiability of CNF formulas with at most three literals per clause is the appropriate \(\mathrm{NP}\)-complete source problem; this matches the problem listed in [Karp’s cited paper](https://www2.seas.gwu.edu/~simhaweb/champalg/tsp/papers/KarpOriginal.pdf).
The normalization to \(n,r\ge1\) is valid: adding a fresh variable and a tautological clause preserves satisfiability and the bound on clause length.
The constructed instance satisfies the task’s input conditions. It has \(m=2n+2\) items, one listed type of positive mass \(1\), binary-rational supplies \(1/2\), and threshold \(B=1\). The proof introduces no additional bundle restrictions.
The list has exactly \(K=n+1+2r\) sets. Every set is nonempty, including when a clause is empty, because each clause-derived set includes a selector item.
On Boolean bundle indicators, the first-layer preactivation is a nonnegative integer. Clipping therefore produces exactly the indicator that the bundle intersects the corresponding set.
The second-layer sum is an integer between \(0\) and \(K\). Its shifted value is \(1\) when all \(K\) first-layer outputs equal \(1\), and is nonpositive otherwise. Thus the second neuron implements the stated conjunction exactly.
All weights are nonnegative and belong to \(\{0,1\}\); all hidden biases are nonpositive integers; and the readout has weight \(1\) and zero bias. The empty bundle has value \(0\). The network therefore satisfies every required MVNN restriction.
The dense first-layer matrix has \(K(2n+2)\) entries, and the remaining layer and readout have polynomial size. Encoding the bias \(-(K-1)\) requires only logarithmically many bits in \(K\). The polynomial construction-size claim is correct.
The \(n\) variable pairs and the selector pair are disjoint. Intersecting all of them requires at least \(n+1\) items. Equality forces exactly one item from each pair.
In the selector-\(a\) case, the absence of \(b\) makes each intersection with \(P_k\cup\{b\}\) equivalent to intersection with \(P_k\). Under the stated assignment convention, a selected literal item represents a true literal. Hence every clause is satisfied.
In the selector-\(b\) case, the absence of \(a\) forces intersections with \(Q_k\). The reversed assignment convention is consistent with the exchange defining \(Q_k\): selecting \(u_i^-\) represents a true positive literal, while selecting \(u_i^+\) represents a true negative literal.
The converse checks every category of required intersection. A satisfying assignment therefore produces a valuable bundle of size \(n+1\), as claimed. The argument also remains valid for repeated literals and tautological clauses.
The complement of the constructed bundle contains \(b\) and exactly the opposite item from each variable pair. Consequently, exchanging literal items carries the original bundle’s intersections with \(P_k\) to its complement’s intersections with \(Q_k\). The remaining clause-derived requirements are met by the selector items.
Both complementary bundles therefore have value \(1\). Giving each mass \(1/2\) consumes exactly \(1/2\) of every item and uses total mass \(1\). This is a feasible assignment with welfare \(1\).
The upper bound of \(1\) follows directly from Boolean valuations and total mass \(1\). Thus the claimed equality \(\operatorname{OPT}=1\) is established.
The lemma implies that every valuable bundle has at least \(n+2\) items when the formula is unsatisfiable.
Summing the supply constraints counts every bundle once for each item it contains. The resulting bound is correctly computed as
\(\sum_S x_S|S|\le(2n+2)/2=n+1\).
For every bundle, \((n+2)v(S)\le|S|\): this follows from the size bound for valuable bundles and from nonnegativity for zero-value bundles. Multiplication by nonnegative bundle masses and summation therefore gives the stated welfare bound
\(\operatorname{OPT}\le(n+1)/(n+2)<1\).
This argument applies to all feasible mass assignments, with no restriction on their support size. It directly addresses the continuous splitting permitted by the task.
The two cases establish precisely
\(F\text{ satisfiable}\Longleftrightarrow\operatorname{OPT}\ge1\).
Together with polynomial construction size, this is a polynomial-time many-one reduction to the threshold problem. The advertised restricted hardness result follows. An exact optimization algorithm would also decide this threshold problem, so the optimization-hardness conclusion is justified.
Adding supply slacks gives the stated equality-form LP with \(d=\tau+m\) rows and coefficients in \(\{0,1\}\). Empty-bundle columns and slack columns supply all \(d\) coordinate unit vectors, proving full row rank.
Feasibility follows from assigning every type to the empty bundle. Each bundle mass is bounded by its type mass, and each slack is bounded by its corresponding finite supply. Since there are finitely many variables, the feasible region is a nonempty compact polytope.
The standard assertion that a linear objective attains an optimum at a vertex applies under these hypotheses. The supplied perturbation argument correctly proves that the positive-coordinate columns at a vertex are linearly independent. Thus there are at most \(d\) positive coordinates in total, and consequently at most \(d\) positive bundle-mass entries.
The exponential number of available columns does not invalidate this existence argument or require their enumeration by the certificate verifier.
Full row rank permits extending the independent positive-coordinate columns to a square nonsingular basis. The added coordinates are zero, so the original vertex indeed solves the resulting basis system.
Clearing the right-hand-side denominators with \(D_b\) produces integers of \(O(L)\) bit length. Cramer’s rule gives the claimed numerator and denominator forms. Determinant expansion introduces at most a factorial factor in \(d\), whose logarithm is \(O(d\log d)\).
The resulting \(O(L+d\log d)\) bound is valid. Hence the sparse assignment has polynomial total encoding length, including its type identifiers and bundle indicators.
The denominator argument is valid for the explicitly encoded feedforward networks. Once actual clipping outcomes are fixed, an expression expands along directed paths; a path cannot use a parameter occurrence twice. Reduced denominators therefore divide the product of the encoded parameter denominators, which has polynomial bit length.
Hidden outputs are bounded between \(0\) and \(1\). Preactivations and the final readout consequently have the stated magnitude bounds in terms of encoded coefficients. Together with the denominator bound, this gives polynomial numerator bit length as well.
Exact evaluation requires polynomially many rational operations and clipping comparisons. The listed masses, type totals, item consumption, and welfare comparison can likewise be checked in polynomial time. Feasibility and welfare at least \(B\) provide sound acceptance; the sparse optimal assignment provides completeness whenever \(\operatorname{OPT}\ge B\).
Thus membership in \(\mathrm{NP}\), and therefore \(\mathrm{NP}\)-completeness, is established for the general input model.
No repair or additional mathematical 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.