Answer: Polynomial-time solvable: an exact maximizing allocation is computable in \(\operatorname{poly}(m,\tau,L)\) bit operations.
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe WDP is NP-complete for combinatorial auctions C = (A, P, b) with P := {[i, i + 2] : 1 ⩽i ⩽n −2} ∪{{i, j} : i, j ∈A}, even if all bids have value 1.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given ordered categories \(A=[n]\), rational per-capita supplies \(q_j\), and a rational distribution \(\mu\) over supported bidder types \(t=(S_t,1)\) with \(S_t\in\mathcal{B}_5=\{[i,i+2]\}\cup\{\{i,j\}:i\ne j\}\), compute a revenue-maximizing allocation of type mass \(x_t\), subject to \(0\le x_t\le\mu_t\) and \(\sum_{t:j\in S_t}x_t\le q_j\) for every category \(j\). Each unit of allocated mass receives its type’s whole bundle.
Given ordered categories \(A=\{1,\ldots,m\}\), with \(m\ge2\), define \(\mathcal B=\{\{i,i+1,i+2\}:1\le i\le m-2\}\cup\{\{i,j\}:1\le i<j\le m\}\).
A society is given by its support: a list of \(\tau\) distinct types \(t=(S_t,1)\), with \(S_t\in\mathcal B\), each with positive mass \(\mu_t\) encoded as a binary rational, and \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each category has a nonnegative binary rational per-capita supply \(q_j\). Serving mass \(x_t\) gives that mass its whole bundle, consumes \(x_t\) units of each category in \(S_t\), and earns revenue \(x_t\); unserved mass and unused supply are allowed.
Compute an exact revenue-maximizing allocation \(x\in\mathbb R^\tau\) subject to \(0\le x_t\le\mu_t\) and \(\sum_{t:j\in S_t}x_t\le q_j\) for every \(j\in A\); revenue is \(\sum_t x_t\), and any maximizer is acceptable. Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is this continuous revenue-maximization problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For discrete unit-supply goods and an explicitly listed set of unit-valued bids on these bundles, deciding whether pairwise disjoint accepted bundles achieve a given positive integer revenue threshold is NP-complete. [Source](https://eprints.illc.uva.nl/id/document/1379)
No result addressing exactly the stated continuous problem was identified in the literature search.
The continuous problem is solvable exactly in polynomial time in \(m,\tau,L\). It is an explicitly given rational linear program. The cited discrete hardness result concerns an additional integrality requirement.
Index the listed types by \(t\in\{1,\ldots,\tau\}\). Define the incidence matrix \(C\in\{0,1\}^{m\times\tau}\) by \(C_{jt}=1\) if \(j\in S_t\), and \(C_{jt}=0\) otherwise. Each column has two or three nonzero entries.
Consider the linear program
\(\displaystyle \max\{\mathbf 1^\top x:Cx\le q,\ x\le\mu,\ -x\le0\}.\)
This formulation is exactly equivalent to the allocation problem:
There are \(\tau\) variables and \(m+2\tau\) inequalities. Variables are needed only for the listed support types.
The feasible set is nonempty because \(x=0\) is feasible, using \(q_j\ge0\). It is closed and bounded because it lies in \(\prod_{t=1}^{\tau}[0,\mu_t]\). Thus the objective attains a maximum. Moreover, every feasible allocation satisfies \(\mathbf 1^\top x\le\sum_t\mu_t=1\).
We use the following standard rational linear programming theorem:
Theorem. Given an explicitly encoded linear program with rational coefficients, a deterministic algorithm can determine feasibility and boundedness and, when a finite optimum exists, return an exact rational optimal solution in a number of bit operations polynomial in the total encoding length.
The classical polynomial-time algorithms for rational linear programming are discussed by [Adler and Beling](https://adler.ieor.berkeley.edu/ilans_pubs/lp_algebraic_stoc_1992.pdf); exact solution computation is also treated by [Gleixner and Steffy](https://arxiv.org/abs/1912.12820).
All hypotheses hold here: the constraint matrix has entries in \(\{-1,0,1\}\), the right-hand sides are the input rationals and zeros, and the objective coefficients are ones. Section 1 establishes feasibility and a finite, attained optimum. Consequently, the theorem returns an exact maximizing allocation, including when some supplies are zero.
A dense encoding of this linear program has length
\(\displaystyle N=O\bigl(L+\tau(m+\tau)\bigr).\)
Indeed, the constraint matrix has \((m+2\tau)\tau\) constant-size entries, while the nonconstant numerical data are already included in \(L\). Constructing this encoding takes \(O\bigl(L+\tau(m+\tau)\bigr)\) bit operations.
Therefore, for some fixed polynomial \(p\), the complete algorithm has running time
\(\displaystyle T(m,\tau,L)\le p\bigl(L+\tau(m+\tau)\bigr).\)
This is a polynomial bound in all three requested parameters.
For completeness, we verify directly that an optimal allocation can have a polynomial-size rational encoding.
First replace each supply by \(q'_j=\min\{q_j,1\}\). This preserves feasibility: nonnegativity and \(\sum_t x_t\le1\) imply \((Cx)_j\le1\).
A linear objective on a nonempty bounded polytope has an optimal vertex. Let \(x^*\) be such a vertex. Its active constraint normals span \(\mathbb R^\tau\): otherwise, a nonzero vector orthogonal to all active normals would permit sufficiently small feasible perturbations in both directions, contradicting extremality. Select \(\tau\) independent active constraints and write them as \(Wx^*=d\).
Here \(W\) is a nonsingular integer matrix with entries in \(\{-1,0,1\}\), and every entry of \(d\) lies in \([0,1]\). Let \(D\) be the product of the denominators of the original input masses and supplies. Its binary length is \(O(L)\), and \(Dd\) is integral.
For coordinate \(k\), let \(W^{(k)}\) be obtained from \(W\) by replacing column \(k\) with \(Dd\). Cramer’s rule gives
\(\displaystyle x^*_k=\frac{\det W^{(k)}}{D\det W}.\)
Each column of \(W\) has Euclidean norm at most \(\sqrt{\tau}\); the replacement column has norm at most \(D\sqrt{\tau}\). Hadamard’s determinant inequality therefore gives
\(\displaystyle |\det W|\le\tau^{\tau/2},\qquad |\det W^{(k)}|\le D\tau^{\tau/2}.\)
Since \(\det W\) is a nonzero integer, this represents each coordinate using \(O\bigl(L+\tau\log(\tau+1)\bigr)\) bits. Thus exact output does not require exponentially many bits.
Accepting or rejecting an indivisible bid requires a binary variable. The continuous problem instead permits every \(x_t\in[0,\mu_t]\), so integrality is not among its constraints.
This distinction changes optimal revenue even on a small admissible instance. Take \(m=3\), with support bundles \(S_1=\{1,2\}\), \(S_2=\{1,3\}\), \(S_3=\{2,3\}\), masses \(\mu_1=1/2\), \(\mu_2=\mu_3=1/4\), and supplies \(q_1=q_2=q_3=1/4\).
The allocation \(x_1=x_2=x_3=1/8\) is feasible and earns \(3/8\). Summing the three supply inequalities gives \(2(x_1+x_2+x_3)\le3/4\), proving optimality.
If each type must instead be served entirely or not at all, type one is infeasible, and types two and three cannot both be served because they share category three. The optimum is then \(1/4\).
Thus the continuous formulation is not an exact encoding of discrete bid acceptance. Its polynomial-time solvability follows from rational linear programming, regardless of the discrete hardness result. In particular, NP-hardness under standard polynomial-time reductions would imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated task correctly. The continuous problem admits an exact polynomial-time algorithm, and the argument establishes this without relying on the discrete hardness result. No major or minor mathematical issues were found.
The incidence matrix correctly records consumption: its entry \(C_{jt}\) is one precisely when category \(j\) belongs to bundle \(S_t\). Consequently, \(Cx\le q\) expresses exactly the category supply constraints.
The inequalities \(x\le\mu\) and \(-x\le0\) express the permitted served masses, and the objective \(\mathbf1^\top x\) equals the specified revenue. No integrality, full-service, or supply-exhaustion restriction is inadvertently introduced.
The counts of \(\tau\) variables and \(m+2\tau\) inequalities are correct. In particular, the construction uses the explicitly listed support rather than all possible types.
The zero allocation is feasible because all supplies are nonnegative.
The feasible region is closed and contained in the bounded box \(\prod_{t=1}^{\tau}[0,\mu_t]\). Thus it is compact, and the linear objective attains its maximum.
The revenue bound \(\mathbf1^\top x\le1\) follows directly from the coordinate upper bounds and the normalization of the masses. These statements also cover zero supplies and feasible regions of lower dimension.
The prover states the required rational LP theorem with the relevant computational guarantee: an exact rational optimal solution, using polynomially many bit operations in the explicit encoding length. This is the appropriate theorem for the requested exact allocation.
The hypotheses are verified:
The references are consistent with the stated use. Adler and Beling discuss polynomial-time rational LP algorithms in the binary encoding model; Gleixner and Steffy treat exact solution computation. The latter reference discusses an oracle framework, but the prover does not mistakenly assume that framework alone supplies an unconditional algorithm. [Adler and Beling](https://adler.ieor.berkeley.edu/ilans_pubs/lp_algebraic_stoc_1992.pdf), [Gleixner and Steffy](https://arxiv.org/abs/1912.12820).
The dense constraint matrix contains \((m+2\tau)\tau\) constant-size entries. The remaining rational data are already covered by \(L\). Therefore the stated bound
\[
N=O\bigl(L+\tau(m+\tau)\bigr)
\]
is correct.
Constructing this explicit representation requires polynomial time, consistent with the stated construction bound. Applying the rational LP theorem gives
\[
T(m,\tau,L)\le p\bigl(L+\tau(m+\tau)\bigr)
\]
for a fixed polynomial \(p\).
This meets the task’s requirement to state a polynomial bound in \(m,\tau,L\). A particular polynomial exponent is not required.
Every step of the additional output-size argument is valid.
Replacing supplies by \(\min\{q_j,1\}\) preserves feasibility because every allocation satisfying the mass bounds has category consumption at most its total served mass, which is at most one.
The nonempty bounded polytope has an optimal vertex. The explanation that active constraint normals span \(\mathbb R^\tau\) is valid even when the polytope has lower dimension: otherwise sufficiently small perturbations in both directions would contradict extremality.
The selected matrix \(W\) is nonsingular and integral, and its right-hand side \(d\) lies in \([0,1]^\tau\). The product \(D\) of input denominators has binary length \(O(L)\), and \(Dd\) is integral, including for supplies replaced by one.
The stated Cramer’s-rule formula is correct. The column-norm bounds satisfy the hypotheses of Hadamard’s inequality and yield the displayed determinant bounds. These imply the claimed per-coordinate encoding length
\[
O\bigl(L+\tau\log(\tau+1)\bigr).
\]
There are only \(\tau\) coordinates, so the entire output has polynomial length.
The example uses three distinct admissible pair bundles, positive masses summing to one, and nonnegative rational supplies.
At the proposed allocation, every category consumes \(1/4\), and revenue is \(3/8\). Summing the supply constraints yields the stated upper bound, proving continuous optimality.
Under the explicitly described all-or-nothing modification, type one is infeasible, and types two and three cannot both be served. The claimed optimum \(1/4\) is correct. This is an illustrative comparison, not an asserted reduction from the cited discrete problem.
The argument also applies when \(m=2\), when \(\tau=1\), and when some or all supplies vanish. No omitted edge case breaks the conclusion.
No repair or additional clarification is necessary.
⟨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.