Answer: \(\mathrm{NP}\text{-hard}\) under polynomial-time oracle reductions
Theorem 3.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe optimization problem in (\ref{0-1game}) is NP-hard even for the case when there are only two non-zero entries in each bidding matrix.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(n\) candidates and a finite support of trader-offer types \(t=(A_t,π_t,q_t)\), each with a two-entry bidding matrix, binary-rational mass μ_t, limit price π_t, and per-trader order cap \(q_t\), where \(\sum_t μ_t=1\), compute the maximum per-capita worst-case profit. Choose accepted order volumes \(x_t\) and reserve \(r\) to maximize \(\sum_t π_t x_t-r\), subject to \(r\ge\sum_t x_t\mathbf{1}[A_t\bullet M_σ>0]\) for every permutation σ and \(0\le x_t\leμ_t q_t\).
A society is given by its support: a list of \(\tau\) trader-offer types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\ge 2\) candidates. Each type has a matrix \(A_t\in\{0,1\}^{m\times m}\) with exactly two entries equal to \(1\), a nonnegative binary-rational limit price \(\pi_t\), and a nonnegative binary-rational per-trader order cap \(q_t\). Let \(L\) be the total input bit length.
An outcome is a permutation \(\sigma\in S_m\), with permutation matrix \(M_\sigma\) whose entry \((i,j)\) is \(1\) precisely when candidate \(i\) occupies position \(j\). An accepted unit pays \(1\) if either selected candidate-position pair occurs, and \(0\) otherwise, including a single payment when both occur.
Orders are divisible: choose aggregate volumes \(x_t\in\mathbb R_{\ge0}\) and reserve \(r\in\mathbb R_{\ge0}\), with no starting orders. Define the maximum per-capita worst-case profit as \(\max\{\sum_t\pi_t x_t-r:0\le x_t\le\mu_t q_t,\ r\ge\sum_t x_t\mathbf1[A_t\bullet M_\sigma>0]\text{ for every }\sigma\in S_m\}\), where \(\bullet\) is the Frobenius inner product.
Is computing this exact optimum possible in time polynomial in \(m,\tau,L\), or is it NP-hard?
The finite-trader fixed-reward optimization is NP-hard even with exactly two selected entries per bid; it already permits divisible orders. [Agrawal, Wang, and Ye](https://optimization-online.org/wp-content/uploads/2008/04/1962.pdf).
The stated support-mass model is the same optimization with aggregate order caps, so the published result already covers it; this target is not open.
Computing the exact optimum is \(\mathrm{NP}\text{-hard}\). The published finite-trader theorem transfers to the stated support model through a polynomial-time transformation that preserves the optimum exactly.
Agrawal, Wang, and Ye’s Theorem 3.1 states that their fixed-reward optimization problem, equation (2), is \(\mathrm{NP}\text{-hard}\) even when each bidding matrix has exactly two nonzero entries. Their orders may be fractional, and equation (2) has no starting orders. Its payout is the indicator that at least one selected entry occurs, so two coincident entries still produce only one payment. These are precisely the relevant features of the present task. [Theorem 3.1, equation (2), and the divisible-order definition](https://optimization-online.org/wp-content/uploads/2008/04/1962.pdf).
Write an instance of that finite-trader problem as
\(\displaystyle V=\max\left\{\sum_{i=1}^{N}p_i y_i-r:\ 0\le y_i\le c_i,\quad r\ge\sum_{i=1}^{N}y_i\mathbf1[B_i\bullet M_\sigma>0]\ \text{for every }\sigma\in S_m\right\}.\)
Here each \(B_i\) has exactly two selected entries. The reserve inequalities already imply \(r\ge0\), because their right-hand sides are nonnegative.
We use this published hardness theorem as a known result. Its optimization–separation proof establishes hardness under polynomial-time oracle reductions; no stronger reduction notion is needed for the conclusion about polynomial-time exact computation.
Partition the finite offers into groups having identical matrix and limit price. For group \(t\), let these common data be \(A_t,\pi_t\), and set
\(\displaystyle C_t=\sum_{i\text{ in group }t}c_i.\)
Replacing the group’s individual accepted volumes by the aggregate volume
\(\displaystyle X_t=\sum_{i\text{ in group }t}y_i\)
preserves both revenue and payout in every outcome.
Moreover, the possible aggregate volumes are exactly \(0\le X_t\le C_t\). One direction follows by summing the individual bounds. For the other, when \(C_t>0\), any such \(X_t\) can be realized by
\(\displaystyle y_i=\frac{c_i}{C_t}X_t.\)
These volumes satisfy \(0\le y_i\le c_i\) and sum to \(X_t\). If \(C_t=0\), every individual volume and the aggregate volume must be zero.
Thus consolidation preserves the optimum exactly. Let \(k\le N\) be the number of resulting groups.
Choose masses as follows. If \(k=1\), set \(\mu_1=1\). If \(k\ge2\), set
\(\displaystyle \mu_t=2^{-t}\quad(1\le t<k),\qquad \mu_k=2^{-(k-1)}.\)
Every mass is positive and dyadic, and
\(\displaystyle \sum_{t=1}^{k}\mu_t=\sum_{t=1}^{k-1}2^{-t}+2^{-(k-1)}=1.\)
For each group, define its per-trader cap by
\(\displaystyle q_t=\frac{C_t}{\mu_t}.\)
Consequently,
\(\displaystyle \mu_tq_t=C_t.\)
The resulting society therefore has exactly the consolidated optimization problem:
\(\displaystyle \max\left\{\sum_{t=1}^{k}\pi_tX_t-r:\ 0\le X_t\le C_t,\quad r\ge\sum_{t=1}^{k}X_t\mathbf1[A_t\bullet M_\sigma>0]\ \text{for every }\sigma\in S_m\right\}.\)
Its optimum equals \(V\). The support size is \(\tau=k\), and each matrix still has exactly two selected entries.
Consolidation requires only comparisons and rational additions, with polynomial encoding size. Every reciprocal \(1/\mu_t\) is a power of two whose exponent is at most \(k-1\); therefore constructing \(q_t\) increases its binary encoding length by at most a polynomial amount. The masses themselves have polynomial total encoding length.
This construction works even under the stricter interpretation that binary-rational numbers must have finite binary expansions.
A polynomial-time algorithm in \(m,\tau,L\) for the society’s exact optimum would consequently compute the finite-trader optimum in polynomial time. By the published theorem, this is impossible unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The argument establishes the requested $\mathrm{NP}$-hardness under polynomial-time oracle reductions for binary-encoded rational inputs. The aggregation and support-mass transformation preserve the optimum exactly and have polynomial encoding size.
There is one minor issue: the additional claim about finite binary expansions requires a numerical restriction on the source instances that the write-up does not state.
The cited [Theorem 3.1 and equation (2)](https://optimization-online.org/wp-content/uploads/2008/04/1962.pdf) concern fixed-reward optimization with exactly two nonzero entries per bidding matrix. The source permits fractional accepted quantities and specifies the formulation without starting orders. Its indicator payout matches the task, including a single payment when both selected entries occur.
The displayed finite-trader formulation therefore correctly represents the cited optimization problem. Nonnegative accepted quantities make every payout nonnegative, so the reserve inequalities imply $r\ge0$.
The qualification concerning polynomial-time oracle reductions is appropriate. The prover invokes the published optimization-hardness theorem rather than claiming to supply an independent optimization–separation proof. That is consistent with the task’s explicit instruction that the published result already covers the finite-trader problem.
Grouping offers by identical matrix and price is valid even when their caps differ.
For each group, both its revenue and its payout in every permutation depend only on the sum of accepted quantities. Summing the individual bounds gives $0\le X_t\le C_t$.
Conversely, for $C_t>0$, the displayed allocation satisfies
$$
0\le \frac{c_i}{C_t}X_t\le c_i,
\qquad
\sum_{i\text{ in group }t}\frac{c_i}{C_t}X_t=X_t.
$$
The zero-cap case is handled correctly. Consequently, consolidation preserves feasibility and objective values in both directions.
The proposed masses are positive. For $k\ge2$, their sum is correctly computed as
$$
\sum_{t=1}^{k-1}2^{-t}+2^{-(k-1)}=1.
$$
The separate case $k=1$ is correct.
Setting $q_t=C_t/\mu_t$ gives a nonnegative cap and exactly reproduces the aggregate bound $\mu_tq_t=C_t$. The prices, matrices, outcome constraints, and objective are preserved. Thus the resulting support-model optimum equals the source optimum.
Grouping and rational addition have polynomial bit complexity. Each reciprocal mass is a power of two with exponent at most $k-1$, so multiplying a binary-encoded rational cap by that reciprocal increases its representation size polynomially. The total mass encoding is also polynomial.
The transformation therefore transfers polynomial-time exact optimum computation back to the finite-trader problem. The stated hardness conclusion and its consequence unless $\mathrm{P}=\mathrm{NP}$ follow.
Where: “This construction works even under the stricter interpretation that binary-rational numbers must have finite binary expansions.”
Issue: The construction preserves finite binary expansions if the source prices and caps already have them, but the write-up does not state that the invoked hardness theorem holds under that restriction. Choosing dyadic masses alone does not establish this: a source cap $C_t=1/3$ remains nondyadic after multiplication by any power of two.
Minimum clarification: State the numerical restriction on the source hardness instances and identify why those instances satisfy it, or remove this additional claim. This does not affect the main reduction for binary-encoded rational inputs.
⟨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.