Bayesian Optimization-Based Combinatorial Assignment* (aaai23-25726)

Given finite bidder types \(T\) with rational masses \(\mu_t\), rational per-item capacities \(\beta_j\), current MVNN acquisition functions \(A_t\), and forbidden queried bundles \(Q_t\), compute a maximum-value mass assignment \(y_{t,S}\) over bundles \(S\), subject to \(\sum_S y_{t,S}=\mu_t\), \(\sum_{t,S:j\in S} y_{t,S}\le\beta_j\), \(y_{t,S}=0\) for \(S\in Q_t\), and \(y_{t,S}\ge0\).

Let \(M=\{1,\ldots,m\}\), with \(m\geq1\); bundles are all subsets \(S\subseteq M\), including the empty bundle.
A society is given by its support: the list \(T\) of \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each acquisition function \(A_t\) is an explicitly encoded rational MVNN of unrestricted depth and width: starting from the indicator vector of \(S\), each hidden layer applies \(z\mapsto\min\{c,\max\{0,Wz+b\}\}\) componentwise, with \(W\geq0\), \(b\leq0\), and rational cutoff \(c>0\); the scalar output is a nonnegative linear combination of the last hidden layer, with no output bias. Thus \(A_t(\varnothing)=0\).
The input also contains nonnegative binary-rational capacities \(\beta_j\) and explicitly listed forbidden bundles \(Q_t\subseteq2^M\), encoded as indicator vectors.
Compute an exact maximum of \(\sum_{t\in T}\sum_{S\subseteq M}y_{t,S}A_t(S)\), subject to \(\sum_{S\subseteq M}y_{t,S}=\mu_t\), \(\sum_{t\in T}\sum_{S\ni j}y_{t,S}\leq\beta_j\), \(y_{t,S}=0\) for \(S\in Q_t\), and \(y_{t,S}\geq0\). Report infeasibility when necessary; any maximizing assignment is permitted and may be represented by its nonzero entries.
Let \(H\) be the total network encoding size excluding rational bit lengths, \(q=\sum_t|Q_t|\), and \(L\) the total input bit length; state running times in \(m,\tau,H,q,L\).

Is exact maximum-value mass assignment polynomial-time solvable in \(m,\tau,H,q,L\), or is it NP-hard? For the decision formulation, a binary-rational threshold \(B\) is supplied, and the question is whether a feasible assignment has value at least \(B\).

The discrete MVNN winner-determination problem admits an exact succinct MILP formulation with four linear constraints per hidden neuron; this is a formulation result, not a polynomial-time guarantee ([Weissteiner et al., 2023](https://arxiv.org/pdf/2208.14698)).
No result settling the exact continuous problem above was located in the literature search.

Result

Exact maximum-value mass assignment is \(\mathrm{NP}\)-hard. Its threshold decision formulation is \(\mathrm{NP}\)-complete.

Hardness holds even with one type, no forbidden bundles, capacities all equal to \(1/2\), and a network consisting of one hidden layer with weights in \(\{0,1\}\), zero biases, and cutoff \(1\).

1. A reduction from maximum cut

We use the known \(\mathrm{NP}\)-completeness of unweighted maximum cut: given a finite simple undirected graph \(G=(V,E)\) and an integer \(K\), decide whether some cut contains at least \(K\) edges. This is established by [Garey, Johnson, and Stockmeyer](https://www.sciencedirect.com/science/article/pii/0304397576900591). We may assume \(E\ne\varnothing\): adding a disjoint edge increases the maximum cut size by exactly one.

Identify the items with the vertices, so \(M=V\) and \(m=|V|\). Construct an instance with

\[ \]
\( \tau=1,\qquad \mu_1=1,\qquad Q_1=\varnothing,\qquad \beta_v=\frac12\quad(v\in V). \)

For every edge \(e=\{u,v\}\), introduce a hidden neuron

\( h_e(x)=\min\{1,\max\{0,x_u+x_v\}\}. \)

Let the output be

\( A(S)=\sum_{e\in E}h_e(\mathbf 1_S). \)

This is an admissible MVNN: all weights are nonnegative, all biases are zero, every cutoff is positive, and the output has unit weights and no bias. In particular, \(A(\varnothing)=0\).

On indicator inputs, \(h_e(\mathbf 1_S)\) equals one exactly when \(S\) contains at least one endpoint of \(e\). Thus \(A(S)\) counts the edges touched by \(S\).

The network has \(|E|\) hidden neurons and \(m|E|\) entries in its dense input-weight matrix. Consequently, both \(H\) and \(L\) are polynomial in the source input size. The construction is polynomial-time.

Exact value of the constructed instance

Define

\( \delta_G(S)=\{\{u,v\}\in E:|\{u,v\}\cap S|=1\},\qquad C(G)=\max_{S\subseteq V}|\delta_G(S)|. \)

Write \(d_G(v)\) for the degree of \(v\). For each edge,

\( h_{\{u,v\}}(\mathbf 1_S)=\frac{\mathbf 1_{\{u\in S\}}+\mathbf 1_{\{v\in S\}}+\mathbf 1_{\{\{u,v\}\in\delta_G(S)\}}}{2}. \)

Indeed, both sides equal zero if neither endpoint is selected and equal one if either one or both endpoints are selected. Summing over edges gives

\( A(S)=\frac12\sum_{v\in V}d_G(v)\mathbf 1_{\{v\in S\}}+\frac12|\delta_G(S)|. \)

A feasible assignment for this single type is a probability distribution \(y_S\) over bundles. Define its inclusion marginals by

\( p_v=\sum_{S\ni v}y_S. \)

Feasibility implies \(p_v\le\frac12\). Therefore,

\( \sum_S y_S A(S)=\frac12\sum_{v\in V}d_G(v)p_v+\frac12\sum_S y_S|\delta_G(S)|\le\frac14\sum_{v\in V}d_G(v)+\frac12C(G)=\frac{|E|+C(G)}2. \)

The first inequality uses nonnegative degrees, the marginal capacities, and the fact that every cut has size at most \(C(G)\).

For the reverse bound, choose \(S^\star\) attaining \(C(G)\), and assign mass \(1/2\) to each of \(S^\star\) and \(V\setminus S^\star\). Every vertex then has inclusion marginal exactly \(1/2\), so this assignment is feasible. The two bundles induce the same cut, and the displayed identity yields value

\( \frac{A(S^\star)+A(V\setminus S^\star)}2=\frac{|E|+C(G)}2. \)

Hence the constructed instance satisfies the exact identity

\( \boxed{\operatorname{OPT}=\frac{|E|+C(G)}2}. \)

This argument establishes both a bound for every fractional assignment and a matching fractional assignment.

Threshold equivalence

Supply the threshold

\( B=\frac{|E|+K}{2}. \)

It is a binary-rational number of polynomial encoding length. The identity proves

\( \operatorname{OPT}\ge B\quad\Longleftrightarrow\quad C(G)\ge K. \)

Every constructed instance is feasible, since all mass may be assigned to the empty bundle. Thus the reduction proves \(\mathrm{NP}\)-hardness even on always-feasible instances. It also proves hardness of computing a maximizing assignment, because its exact value can be evaluated and compared with \(B\).

2. Polynomial-size certificates for the general problem

We now prove that the decision formulation belongs to \(\mathrm{NP}\), including for unrestricted network depth and arbitrary forbidden lists.

Exact network evaluation has polynomial bit complexity

Fix a bundle and one explicitly encoded network. Evaluation uses rational arithmetic and comparisons.

Let \(D\) be the product of the denominators of all rational parameters in that network. Its binary length is \(O(L)\).

For the fixed input, each clipped neuron returns either zero, its cutoff, or its affine preactivation. After fixing these choices, recursively expanding an output produces a sum of terms consisting of a bias, cutoff, or input coordinate multiplied by weights along a directed path. The network is feedforward, so a path never repeats a parameter occurrence. Every term therefore has denominator dividing \(D\); sums retain this property.

Every hidden activation is bounded by its cutoff. Each input parameter has magnitude at most \(2^L\), so preactivations and the scalar output have magnitude at most \((H+1)2^{2L}\). Together with the denominator bound, this gives rational representations of \(O(L+\log(H+1))\) bits for the evaluated quantities.

Thus exact evaluation takes \(O(H\,\operatorname{poly}(L))\) bit operations. In particular, unrestricted depth does not cause exponential arithmetic bit growth.

A sparse optimum exists

Remove forbidden variables and introduce nonnegative capacity slacks \(s_j\). The constraints become

\( Cz=b,\qquad z\ge0, \)

where \(z\) contains the allowed assignment variables and the slacks, \(C\) has entries in \(\{0,1\}\), and there are

\( r=\tau+m \)

rows. The right-hand side consists of the masses and capacities.

The feasible set is compact: every assignment variable satisfies \(0\le y_{t,S}\le\mu_t\), and every slack satisfies \(0\le s_j\le\beta_j\). Hence, if feasible, the linear objective attains its maximum.

Choose an optimum \(z^\star\) having the smallest possible number of positive coordinates. Its corresponding columns of \(C\) are linearly independent. To prove this, suppose a nonzero vector \(d\), supported on those coordinates, satisfies \(Cd=0\). Both \(z^\star+\varepsilon d\) and \(z^\star-\varepsilon d\) are feasible for sufficiently small positive \(\varepsilon\). Optimality forces the objective’s scalar product with \(d\) to be zero; otherwise one direction improves the objective. Moving in a direction until a positive coordinate first becomes zero then produces an optimum with smaller support, a contradiction.

Therefore \(z^\star\) has at most \(r\) positive coordinates. In particular, a maximizing assignment has at most \(m+\tau\) nonzero entries.

The masses have polynomial encoding length

Let \(k\le r\) be the number of positive coordinates of this optimum. Their independent columns contain a nonsingular \(k\times k\) row submatrix \(U\), whose entries are zero or one. The positive coordinates solve

\( Uz^\star_{\mathrm{supp}}=b'. \)

Let \(R\) be the product of the denominators in the original right-hand side. Its bit length is \(O(L)\), and \(Rb'\) is integral with entries of magnitude at most \(2^{2L}\).

Cramer’s rule gives each positive coordinate as

\( z^\star_i=\frac{\det U_i}{R\det U}, \)

where \(U_i\) replaces one column of \(U\) with \(Rb'\). Hadamard’s determinant inequality gives

\( |\det U|\le k^{k/2},\qquad |\det U_i|\le 2^{2L}k^{k/2}. \)

Thus each coordinate has rational encoding length

\( O\!\left(L+r\log(r+1)\right). \)

These bounds concern the constraint matrix and right-hand side; they do not depend on the exponentially many possible bundles.

Verification

If the threshold decision instance is a yes-instance, a sparse optimum is a certificate meeting the threshold. The certificate lists at most \(m+\tau\) type–bundle pairs and their rational masses.

A verifier checks:

• nonnegativity and the type-mass equalities;
• all item-capacity inequalities;
• membership against the explicitly listed forbidden bundles;
• the objective value, using exact network evaluation.

The certificate length and verification time are both \(\operatorname{poly}(m,\tau,H,q,L)\), with the threshold encoding included in \(L\). Therefore the decision problem belongs to \(\mathrm{NP}\), and the reduction proves it is \(\mathrm{NP}\)-complete.

3. Exact algorithm and running time

There is an exact algorithm with running time

\( 2^{O(m)}\operatorname{poly}(m,\tau,H,q,L). \)

Enumerate all bundles for each type, discard forbidden bundles, and evaluate every remaining objective coefficient exactly. This produces a rational LP with at most \(\tau2^m\) assignment variables and \(m+\tau\) mass and capacity constraints.

The expanded encoding length is

\( 2^{O(m)}\operatorname{poly}(m,\tau,H,q,L), \)

by the network-evaluation bit bound. Polynomial-time algorithms for explicitly given rational LPs then determine feasibility and the exact optimum; see [Khachiyan’s polynomial-time linear-programming result](https://www.mathnet.ru/eng/dan42319).

A sparse maximizing assignment can also be obtained within this running time. For example, after obtaining the optimum value, impose it as an equality and successively minimize and fix every coordinate of the expanded feasible vector. These polynomially many exact LP calls produce a vertex of the optimal face, hence a vertex of the original feasible polytope. Its assignment support has size at most \(m+\tau\), by the column-independence argument above.

Consequently, the problem is polynomial-time solvable for fixed \(m\), but a polynomial-time algorithm in all of \(m,\tau,H,q,L\) would imply \(\mathrm{P}=\mathrm{NP}\). The exponential number of LP columns is essential to this distinction; succinct MILP formulations do not supply a polynomial-time guarantee.

⟨structured verdict parsed — rendered above⟩

Verdict: proved. The output resolves the assigned continuous problem: exact optimization is \(\mathrm{NP}\)-hard, and the threshold decision problem is \(\mathrm{NP}\)-complete. I found no mathematical errors or substantive gaps.

• Source problem and reduction domain.

The cited source establishes \(\mathrm{NP}\)-completeness of unweighted maximum cut, as required by the reduction. The statement used is precise: the input is a finite simple undirected graph and an integer threshold, and the question concerns the existence of a cut meeting that threshold. [Garey, Johnson, and Stockmeyer](https://doi.org/10.1016/0304-3975%2876%2990059-1).

Restricting to graphs with at least one edge is harmless. The stated disjoint-edge operation increases the optimum by exactly one, with the corresponding threshold shift understood. It also ensures that the constructed instance has \(m\geq1\) and a nonempty hidden layer.

• Admissibility and encoding size of the constructed MVNN.

Each edge neuron has nonnegative weights, zero bias, and cutoff \(1\). The output uses nonnegative unit coefficients and no bias. Thus the construction satisfies every network restriction in USER_TASK.

The single mass is positive and normalized, the capacities are admissible binary rationals, and the forbidden list is empty. The dense matrix contains \(m|E|\) entries, each of constant bit length. Consequently, the construction is polynomial in the explicitly encoded graph input.

• Edge identity and objective decomposition.

The per-edge identity is correct in all three cases: neither endpoint selected, exactly one selected, and both selected. Summing it yields the stated decomposition
\(A(S)=\frac12\sum_{v\in V}d_G(v)\mathbf1_{\{v\in S\}}+\frac12|\delta_G(S)|\).

There is no confusion between touched edges and cut edges: the degree term accounts for the difference.

• Upper bound for every fractional assignment.

Because the unique type has mass \(1\), every feasible assignment is a probability distribution. The capacity constraints give \(p_v\leq\frac12\). Nonnegative degrees justify bounding the degree contribution term by term.

Every bundle defines a cut of size at most \(C(G)\), so its average cut size is also at most \(C(G)\). The use of \(\sum_v d_G(v)=2|E|\) is correct. Therefore the upper bound \(\frac{|E|+C(G)}2\) holds for all feasible fractional assignments, not merely deterministic bundles.

• Matching feasible assignment.

Giving mass \(\frac12\) to a maximum-cut bundle and its complement satisfies the mass equality and makes every inclusion marginal exactly \(\frac12\). Both bundles are allowed and induce the same cut.

Substitution into the verified objective identity gives precisely \(\frac{|E|+C(G)}2\). Isolated vertices cause no problem. The assumption \(m\geq1\) ensures that a bundle and its complement are distinct. Thus the claimed exact optimum identity is established.

• Threshold equivalence and hardness.

The threshold \(B=\frac{|E|+K}{2}\) has polynomial encoding length. The optimum identity gives the claimed equivalence in both directions, including thresholds outside the usual attainable cut range.

Assigning all mass to the empty bundle proves feasibility of every constructed instance. The reduction therefore establishes hardness of the continuous problem even on the stated restricted, always-feasible family.

Hardness of computing a maximizing assignment also follows under the task’s explicit representation by nonzero entries: its objective can be evaluated exactly in time polynomial in that representation and the input.

• Exact network evaluation and bit lengths.

The denominator argument is valid for the explicitly encoded feedforward networks in the task. After fixing clipping outcomes, each expanded term contains parameters along a directed path, with no repeated parameter occurrence. Hence its denominator divides the stated product \(D\); adding terms preserves that divisibility.

The magnitude bound is also valid. Hidden activations are bounded by their cutoffs, each parameter has magnitude at most \(2^L\), and each affine sum has at most \(H\) relevant terms. The stated bound \((H+1)2^{2L}\) therefore covers preactivations and output values.

Together, these bounds establish polynomial bit lengths independently of depth. The evaluation claim is sound when rational arithmetic maintains reduced fractions, as standard exact rational arithmetic does. The symbolic expansion is used only to bound denominators; the argument does not require enumerating paths.

• Existence of a sparse optimum.

Removing forbidden variables and adding capacity slacks gives the stated nonnegative equality system with \(\tau+m\) rows and entries in \(\{0,1\}\).

All assignment variables and slacks have finite bounds, so the feasible set is compact whenever nonempty. The objective therefore attains its maximum.

The minimum-support argument is correct: a dependence among positive-coordinate columns permits sufficiently small feasible perturbations in both directions. Optimality forces zero objective change along that dependence. Moving to the first zero coordinate then contradicts support minimality. Thus at most \(m+\tau\) positive coordinates are needed, including slacks.

• Certificate encoding and verification.

Independent support columns admit the asserted nonsingular square row submatrix. Clearing right-hand-side denominators and applying Cramer’s rule gives the displayed coordinate formula.

Both Hadamard bounds are correct. In particular, the replaced column has Euclidean norm at most \(2^{2L}\sqrt{k}\), giving the stated numerator bound. The resulting coordinate bit length is polynomial.

A certificate therefore needs only polynomially many explicitly encoded type–bundle pairs and polynomial-length rational masses. The listed verification checks cover every original constraint and the threshold condition. Explicit forbidden lists permit polynomial-time membership checking. These arguments establish membership in \(\mathrm{NP}\).

• Exact algorithm and stated running time.

Enumerating bundles produces at most \(\tau2^m\) assignment variables. The verified coefficient bit bounds make the expanded LP encoding length \(2^{O(m)}\operatorname{poly}(m,\tau,H,q,L)\).

The invoked rational-LP theorem applies to an explicitly given rational LP and supplies polynomial-time feasibility testing and exact optimization in its encoding length. The constructed LP meets those hypotheses; when feasible, it is bounded. The use of polynomial-time rational linear programming is consistent with the cited [Khachiyan result](https://www.mathnet.ru/eng/dan42319).

Successive exact coordinate minimization selects a vertex of the optimal face, which is also a vertex of the original polytope. The resulting assignment obeys the claimed support bound. Polynomially many LP calls relative to the expanded size preserve the stated exponential running time.

Consequently, the fixed-\(m\) polynomial-time claim and the implication that a polynomial-time algorithm in all input parameters would yield \(\mathrm{P}=\mathrm{NP}\) are justified.

Actionable feedback: No mathematical repair is required. The empty display-math block in the construction is a cosmetic formatting artifact and can be deleted.

⟨structured verdict parsed — rendered above⟩