Answer: Feasibility and exact minimum-cost winner determination are polynomial-time solvable in \(m,\tau,L\).
Theorem 2.5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateConsider the winner determination problem in a combinatorial auction (single-unit or multi-unit), combina- torial reverse auction (single-unit or multi-unit), or a com- binatorial exchange (single-unit or multi-unit). Without free disposal, even finding a feasible solution is N P-complete (even with integer prices and integer units). PROOF. Clearly these problems are in N P because feasibil- ity can easily be checked in polynomial time. So, the beef is to prove that they are N P-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) items and \(\tau\) supplier types, where type \(t\) has integer ask vector \(q_t\), rational price \(p_t\), and population mass \(\mu_t\) with \(\sum_t \mu_t=1\), along with per-supplier demand \(d\in\mathbb{Q}_{\ge 0}^m\), determine whether there are accepted masses \(x_t\in[0,\mu_t]\) satisfying \(\sum_t q_{ti}x_t=d_i\) for every item \(i\); if feasible, find a minimum-cost choice minimizing \(\sum_t p_t x_t\).
A society is given by its support: a list of \(\tau\) supplier types with positive masses \(\mu_t\) encoded as binary rationals, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\ge 1\) items. Type \(t\) offers the bundle \(q_t\in\mathbb Z_{\ge 0}^m\) at cost \(p_t\in\mathbb Q_{\ge 0}\) per unit of accepted supplier mass. Demand is \(d\in\mathbb Q_{>0}^m\), measured per unit of total supplier mass. All numerical inputs use binary encoding; \(L\) is their total bit length.
Supplier mass is divisible: choose real accepted masses \(x_t\in[0,\mu_t]\). Each accepted supplier supplies its entire stated bundle. There is no free disposal, so feasibility requires \(\sum_{t=1}^{\tau}q_{ti}x_t=d_i\) for every \(i\in\{1,\ldots,m\}\). If feasible, find a choice minimizing \(\sum_{t=1}^{\tau}p_tx_t\).
Is this feasibility and minimum-cost winner determination problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For discrete combinatorial reverse auctions without free disposal, deciding feasibility is NP-complete, even with integer quantities and prices (Sandholm, Suri, Gilpin, and Levine).
That result concerns binary acceptance of asks and provides no complexity classification for divisible supplier masses.
Both feasibility and minimum-cost winner determination are solvable in polynomial time in \(m,\tau,L\). Divisible acceptance makes the stated problem a rational linear program.
Define \(Q\in\mathbb Z_{\ge 0}^{m\times\tau}\) by \(Q_{it}=q_{ti}\), and let \(p=(p_t)_{t=1}^{\tau}\) and \(\mu=(\mu_t)_{t=1}^{\tau}\). Consider the linear program
\[ \min_{x\in\mathbb R^\tau}p^\mathsf Tx \quad\text{subject to}\quad Qx=d,\qquad 0\le x\le\mu. \]
All vector inequalities are coordinatewise.
We verify that this formulation is exact:
Thus the original problem and this linear program have identical feasible choices and costs. In particular, the equality constraints preserve the prohibition on free disposal.
We use the standard polynomial-time theorem for rational linear programming: given an explicitly encoded rational linear program, one can decide feasibility and, when a finite optimum exists, compute an exact rational optimal solution in time polynomial in the program’s binary encoding length. This is a theorem about bit complexity, including exact solution recovery; see [Trevisan’s linear-programming notes, Sections 2.4–2.5](https://lucatrevisan.github.io/cs261/lecture05.pdf).
Here its hypotheses hold:
If the feasible set is nonempty, it is closed and contained in the bounded box \(\prod_{t=1}^{\tau}[0,\mu_t]\), hence compact. The continuous objective consequently attains its minimum. Moreover, every feasible choice satisfies
\[ 0\le p^\mathsf Tx\le\sum_{t=1}^{\tau}p_t\mu_t, \]
so the optimum is finite. The rational linear-programming theorem therefore returns either an infeasibility decision or an exact optimal accepted-mass vector, in polynomial time in \(m,\tau,L\).
Only the listed support types are used: the algorithm introduces no variables for unlisted possible types and does not expand rational masses into individual suppliers.
Binary acceptance would impose \(x_t\in\{0,\mu_t\}\). Those restrictions are absent here, and replacing them by intervals can change feasibility.
For example, take \(m=\tau=1\), \(\mu_1=1\), \(q_{11}=2\), \(p_1=1\), and \(d_1=1\). Divisible acceptance is feasible with \(x_1=\tfrac12\). Binary acceptance permits only \(x_1=0\) or \(x_1=1\), supplying respectively zero or two units, so neither satisfies demand exactly.
The cited discrete hardness result thus concerns a different feasible set. The linear-programming argument completely settles the stated divisible-mass problem.
⟨structured verdict parsed — rendered above⟩
The prover’s conclusion is correct: the stated feasibility and exact minimum-cost problem is solvable in polynomial time. The argument resolves the assigned task, and no major or minor mathematical issues were found.
The definition \(Q_{it}=q_{ti}\) gives the correct matrix dimensions: \(Q\) has \(m\) rows and \(\tau\) columns, so \(Qx\) records the total supply of each item.
The bounds \(0\le x_t\le\mu_t\) exactly describe the allowed accepted masses. Divisibility justifies the converse direction: every vector satisfying these bounds corresponds to an admissible selection of supplier mass. There is no additional integrality or all-or-nothing restriction in the task.
The constraint \(Qx=d\) enforces exact supply in every coordinate, including the prohibition on free disposal. The objective \(p^{\mathsf T}x\) correctly charges \(p_t\) per unit of accepted mass of type \(t\). Thus both directions of the claimed equivalence, including preservation of costs, are justified.
The prover states the needed theorem precisely enough: an explicitly encoded rational linear program admits polynomial-time feasibility determination and exact rational optimization when a finite optimum exists.
The cited source supports the claim. Sections 2.4–2.5 discuss polynomial-time algorithms, rational solution recovery, infeasibility determination, and input size measured in bits of rational coefficients. The prover relies on this standard theorem, without needing to reproduce its algorithm or proof. [Trevisan’s linear-programming notes](https://lucatrevisan.github.io/cs261/lecture05.pdf)
All coefficients in this instance are explicitly encoded rationals: integer bundle quantities are rational coefficients, and the masses, demands, and prices are rational by assumption. Real decision variables are permitted by the theorem. No full-dimensionality, strict feasibility, or independence of the constraints is required.
There are exactly \(\tau\) variables. Replacing each of the \(m\) equalities with two inequalities and retaining the two bounds for each variable gives \(2m+2\tau\) inequalities, as claimed.
Copying coefficients and changing their signs increases their bit lengths by at most a constant per occurrence. A dense representation adds only polynomially many zero and unit coefficients. Consequently, construction time and encoding length are polynomial in \(m,\tau,L\).
The argument correctly uses support size rather than the number of possible types. It introduces neither unlisted types nor a number of variables proportional to rational denominators.
The feasible set is closed because all its constraints are linear equalities or non-strict inequalities. It lies in the bounded box \(\prod_{t=1}^{\tau}[0,\mu_t]\). Therefore, when nonempty, it is compact, and the continuous linear objective attains a minimum.
The displayed bound follows coordinatewise from \(p_t\ge0\) and \(0\le x_t\le\mu_t\):
\(0\le p_tx_t\le p_t\mu_t\).
Summing gives exactly the claimed finite upper bound. Hence the theorem’s finite-optimum hypothesis is satisfied whenever the instance is feasible.
Zero prices, zero bundle coordinates, redundant constraints, and feasible sets of lower dimension are all covered by the formulation and theorem. An item with no available supply and positive demand simply makes the program infeasible. The argument does not assume that the optimum is unique or that accepted masses are strictly between their bounds.
The example satisfies every input restriction. With \(x_1=\tfrac12\), supply is \(2x_1=1\); the two binary choices supply \(0\) and \(2\), respectively. This correctly demonstrates that divisibility can change feasibility.
The example alone is not a complexity proof, and the prover does not use it as one. Polynomial solvability follows from the preceding linear-programming argument. The discussion appropriately explains why the supplied discrete hardness result does not classify the continuous problem.
No repair or additional clarification is needed.
⟨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.