Answer: Polynomial-time solvable, in \((m+\tau+L)^{O(1)}\) bit operations, hence \(L^{O(1)}\) for the explicitly listed input.
Theorem 5.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateWINNER-DETERMINATION is NP-hard, even restricted on the classes {A | in-deg(A) = 0} and {A | out-deg(A) = 0}, and under atomic bids. The reason for the above intractability is that interactions among bidders may be too complex to be analyzed. To bound these interactions, we next consider a structural restriction based on a hypergraph encoding, which is more general than graph (near)acyclicity.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite goods set \(G\), bidder types \(T\) with rational masses \(\mu_t\) summing to \(1\), integral packages \(I_t\), payments \(p_t\), and rational per-capita inventory \(b_g\), choose accepted masses \(x_t\in[0,\mu_t]\) to maximize \(\sum_{t\in T}p_tx_t\), subject to \(\sum_{t\in T}I_t(g)x_t\le b_g\) for every \(g\in G\).
Let \(G\) be a finite goods set with \(m=|G|\). A society is given by its support: a list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\) satisfying \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type submits one atomic bid with a package \(I_t\in\mathbb Z_{\ge0}^{G}\) and payment \(p_t\in\mathbb Q\); negative payments mean the auctioneer pays the bidder. Inventory is \(b\in\mathbb Q_{\ge0}^{G}\). Packages consume goods and produce none; unused inventory may be discarded, and there is no required final inventory.
Accepted masses \(x_t\in[0,\mu_t]\) may be split arbitrarily and yield revenue \(\sum_{t\in T}p_tx_t\), subject to \(\sum_{t\in T}I_t(g)x_t\le b_g\) for every \(g\in G\). Integers and rationals are binary encoded; let \(L\) be the total input bit length, including a rational revenue threshold \(q\).
Is deciding whether there exist feasible accepted masses with revenue at least \(q\) solvable in polynomial time, or is it NP-hard? State running times in \(m\), \(\tau\), and \(L\).
Discrete winner determination is NP-hard even with atomic bids and no goods produced, and also with atomic bids and no goods consumed. These hardness results concern accepting whole bid occurrences; they do not classify divisible accepted masses.
The decision problem is polynomial-time solvable. An exact algorithm runs in \((m+\tau+L)^{O(1)}\) bit operations, and hence in \(L^{O(1)}\) for the explicitly listed input. Divisibility makes the problem a rational linear feasibility problem.
Enumerate the support as \(T=\{1,\ldots,\tau\}\), and define \(A_{g,t}=I_t(g)\). Introduce one real variable \(x_t\) for each listed type. Consider the following system:
This system has \(\tau\) variables and \(m+2\tau+1\) inequalities.
Equivalence. If accepted masses meet the requested revenue threshold, they satisfy the first group by their permitted ranges, the second group by inventory feasibility, and the last inequality by the revenue requirement. Conversely, any solution to this system specifies permissible accepted masses, respects every inventory constraint, and has revenue at least \(q\). Arbitrary splitting is expressly permitted, so there is no additional integrality condition.
Thus the answer to the auction decision problem is exactly the feasibility answer for this rational linear system.
We use the standard polynomial-time rational linear feasibility theorem: given a rational matrix \(C\) and rational vector \(d\), feasibility of \(Cz\le d\) over the reals can be decided exactly in time polynomial in the number of variables, the number of inequalities, and the total binary encoding length. This is the linear programming result established by [Khachiyan](https://www.mathnet.ru/eng/dan42319).
Its hypotheses hold here: all package entries are integers, and all masses, payments, inventories, and the threshold are rational and binary encoded. Forming the system only copies input coefficients, changes signs, and inserts coefficients from \(\{-1,0,1\}\).
Even using a dense representation, its encoding length \(B\) satisfies
\(B=O\!\left(L+m\tau+\tau^2\right).\)
The additional terms account for explicitly storing the inventory matrix and the bound rows, including zero entries. Construction takes \(O(L+m\tau+\tau^2)\) bit operations. Applying rational linear feasibility then takes
\(\operatorname{poly}\!\left(\tau,m+2\tau+1,B\right)=(m+\tau+L)^{O(1)}\)
bit operations. Since the goods and support are explicitly listed, \(m\) and \(\tau\) are bounded by the input length, giving \(L^{O(1)}\) overall.
The theorem decides feasibility exactly, including equality at the revenue threshold and feasible sets of lower dimension. No numerical tolerance assumption is needed. This is a polynomial bit-complexity bound; it does not assert strongly polynomial running time.
Negative payments cause no difficulty. Indeed, given any feasible acceptance vector, replacing \(x_t\) by zero whenever \(p_t<0\) weakly decreases every inventory use because \(I_t(g)\ge0\), and weakly increases revenue because \(p_tx_t\le0\). Hence these types may also be discarded before solving.
The cited discrete hardness results impose whole-occurrence acceptance. That restriction is absent here: each \(x_t\) ranges over an interval. Only the \(\tau\) listed types require variables; neither possible types nor bid occurrences need to be enumerated. The present problem belongs to \(\mathsf{P}\), so NP-hardness under polynomial-time reductions would imply \(\mathsf{P}=\mathsf{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the task. The decision problem is solvable exactly in \((m+\tau+L)^{O(1)}\) bit operations, hence in \(L^{O(1)}\) for the explicitly listed input. No major or minor mathematical issues were found.
Introducing one real variable \(x_t\) for each supported type matches the task: accepted masses may be split arbitrarily and range over \([0,\mu_t]\). No integer variables or enumeration of possible types is required.
The proposed constraints accurately encode:
The inequality directions and signs are correct, including when payments or the threshold are negative. There are exactly \(\tau\) variables and \(m+2\tau+1\) scalar inequalities.
Both directions of the claimed equivalence follow directly from the task’s definitions. Every permissible acceptance vector satisfies the displayed system, and every solution of that system is a permissible acceptance vector meeting the threshold.
The formulation correctly imposes no final-inventory equality: unused inventory may be discarded. It also correctly imposes no whole-occurrence acceptance restriction.
The prover precisely states the required theorem: feasibility of a finite rational system \(Cz\le d\) over the reals is decidable exactly in time polynomial in its dimensions and binary encoding length.
This is a valid standard linear-programming theorem. The [cited Khachiyan paper](https://www.mathnet.ru/eng/dan42319) establishes polynomial-time feasibility for arbitrary integer-coefficient linear inequalities; the rational formulation stated by the prover is the standard corresponding version.
All hypotheses hold as written: every coefficient and right-hand side is rational and finitely binary encoded. There is no unverified boundedness, full-dimensionality, or strict-feasibility assumption.
The bound
\[
B=O(L+m\tau+\tau^2)
\]
is valid for a conventional dense encoding. Original numerical coefficients contribute \(O(L)\) bits; storing the additional constant entries and zeros contributes \(O(m\tau+\tau^2)\) bits.
The stated construction cost is consistent with copying coefficients, changing signs, and writing those entries. Applying the feasibility theorem therefore gives \((m+\tau+L)^{O(1)}\) bit operations.
The explicitly represented inventory and support ensure that \(m\) and \(\tau\) are bounded by the input length, so the conclusion \(L^{O(1)}\) follows. The prover appropriately distinguishes this bound from a strongly polynomial guarantee.
The cited feasibility theorem supports exact decisions at the threshold and for lower-dimensional feasible sets. The argument does not depend on numerical tolerances.
Zero inventories, zero packages, zero payments, and an empty goods set are all covered by the formulation. Negative thresholds introduce no exception. Positive masses summing to one already exclude an empty support for a valid input.
The optional deletion argument is correct: setting a coordinate with \(p_t<0\) to zero preserves its bounds, weakly decreases every inventory use, and weakly increases revenue.
The discussion of discrete hardness correctly distinguishes whole-occurrence acceptance from divisible masses. The final conditional statement about NP-hardness and \(\mathsf{P}=\mathsf{NP}\) is also correct.
None. The write-up establishes the claimed complexity classification without a missing lemma or repair.
⟨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.