Answer: Polynomial-time solvable in \(m,\tau,L\), with an exact rational optimal allocation.
Corollary 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateEvery PD Auction weakly increases all prices pj(S) until ter- mination, yielding an efficient assignment in a finite number of steps. This follows from Theorems 1 and 2. Since valuations are finite, there can only be a finite number of unit price increases.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given goods \(G\), complete valuation types \(T\), rational type masses \(\mu_t\) summing to \(1\), rational per-capita supplies \(q_g\), and explicit monotone valuation tables \(v_t(S)\), find an exact rational allocation \(x_{t,S}\) maximizing \(\sum_{t\in T}\sum_{S\subseteq G}x_{t,S}v_t(S)\), subject to \(\sum_{S\subseteq G}x_{t,S}=\mu_t\), \(\sum_{t\in T,\,S\ni g}x_{t,S}\le q_g\), and \(x_{t,S}\ge0\). Each unit of mass receives an integral bundle \(S\).
Let \(G\) be a finite set of \(m\) goods. A society is given by its support: a list \(T\) of \(\tau\) complete valuation types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has an explicit table \(v_t:2^G\to\mathbb{Z}_{\ge0}\), with \(v_t(\varnothing)=0\) and monotone valuations. Supplies \(q_g\in\mathbb{Q}_{\ge0}\) are binary-encoded per-capita quantities; unused supply is permitted. Let \(L\) be the total input bit length, including all valuation tables.
An allocation specifies rational masses \(x_{t,S}\ge0\): mass \(x_{t,S}\) of type \(t\) receives the integral bundle \(S\subseteq G\). A type's mass may be split among bundles, including the empty bundle.
Find an allocation maximizing \(\sum_{t\in T}\sum_{S\subseteq G}x_{t,S}v_t(S)\), subject to \(\sum_{S\subseteq G}x_{t,S}=\mu_t\) for every \(t\), and \(\sum_{t\in T}\sum_{S\ni g}x_{t,S}\le q_g\) for every \(g\).
Is this exact allocation problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For finite bidders and indivisible goods, an ascending primal-dual auction terminates after finitely many steps with a welfare-maximizing assignment; the result supplies no polynomial-time bound. [de Vries, Schummer, and Vohra](https://www.kellogg.northwestern.edu/faculty/schummer/ftp/research/pdhetero/pdhetero.pdf)
No prior result addressing exactly this continuous problem was verified.
The exact allocation problem is solvable in time polynomial in \(m,\tau,L\). The decisive assumptions are that valuation tables are explicit and type masses may be split among bundles.
1. The number of variables is bounded by the input length.
Introduce one variable \(x_{t,S}\) for each \(t\in T\) and \(S\subseteq G\). There are \(N=\tau 2^m\) such variables.
The input explicitly contains all \(N\) valuation entries. Each entry requires at least one bit, including entries equal to zero. Consequently, \(N\le L\). Thus enumerating every type–bundle pair takes time polynomial in \(m,\tau,L\), despite the exponential dependence on \(m\) alone.
2. Construct an explicit rational linear program.
For each good \(g\), introduce a nonnegative slack variable \(s_g\), representing unused supply. Solve the following linear program:
\[ \max \sum_{t\in T}\sum_{S\subseteq G}v_t(S)x_{t,S}, \]
subject to
\[ \sum_{S\subseteq G}x_{t,S}=\mu_t \qquad(t\in T), \]
\[ \sum_{t\in T}\sum_{\substack{S\subseteq G\\g\in S}}x_{t,S}+s_g=q_g \qquad(g\in G), \]
and \(x_{t,S}\ge0,\ s_g\ge0\).
There are \(N+m\) variables and \(\tau+m\) equality constraints. Every constraint-matrix coefficient belongs to \(\{0,1\}\). The objective coefficients and right-hand sides are copied from the input.
Even a dense encoding therefore has bit length
\[ B=O\bigl((\tau+m)(N+m)+L\bigr), \]
up to polynomially bounded dimension metadata. Since \(N\le L\), this is polynomial in \(m,\tau,L\). The matrix can be constructed within the same polynomial bound by inspecting bundle membership.
3. Check feasibility and boundedness.
A feasible solution assigns every type the empty bundle: set \(x_{t,\varnothing}=\mu_t\), set every other allocation variable to zero, and set \(s_g=q_g\). Nonnegative supplies ensure feasibility.
For every feasible solution, nonnegativity and the type equation imply \(0\le x_{t,S}\le\mu_t\). Likewise, the supply equation implies \(0\le s_g\le q_g\). Hence the feasible region is bounded. It is also closed, because it is defined by finitely many linear equalities and non-strict inequalities. Being nonempty and compact, it admits a maximizer of the continuous linear objective.
4. Apply exact polynomial-time rational linear programming.
The standard rational linear-programming theorem states that an explicitly encoded rational linear program can be solved in polynomial time in its binary encoding length: the algorithm detects infeasibility or unboundedness, or returns an exact rational optimal solution. This is a bit-complexity guarantee, including polynomial output length, rather than merely an approximation guarantee. Exact polynomial-time algorithms and rational reconstruction are discussed in [*Linear Programming using Limited-Precision Oracles*, Section 1.3](https://optimization-online.org/wp-content/uploads/2019/12/7507.pdf).
All hypotheses hold here: the program is explicit, every coefficient is rational, its encoding length \(B\) is polynomially bounded, and it has an attained finite optimum. Applying the theorem therefore returns an exact rational optimum in time polynomial in \(m,\tau,L\).
Finally, the correspondence with the stated allocation problem is exact. Every permissible allocation extends to a feasible linear-program solution by setting each slack to unused supply. Conversely, discarding the slack variables from any feasible solution gives a permissible allocation with the same welfare. Thus the returned optimum solves the requested problem.
The running time may be exponential in \(m\) alone, because the explicitly supplied tables already have that size. It is polynomial in the input length requested here. No integrality constraint is imposed on allocation masses, and the proof requires no polynomial-time bound for the ascending auction.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The explicit valuation tables make the linear program polynomial in the stated input size, and exact rational linear programming supplies the required allocation. No major or minor mathematical issues were found.
The count \(N=\tau 2^m\) is correct: there is one allocation variable for every type and every subset of goods.
The bound \(N\le L\) follows from the explicit-table encoding specified in the task. Every valuation entry, including zero, occupies at least one bit. The prover does not assume a succinct representation or confuse support size with the number of possible valuation types.
Enumerating these pairs and inspecting bundle membership takes polynomial time in \(m,\tau,L\). Exponential dependence on \(m\) alone does not contradict the requested complexity bound.
Assessment: Correct.
The type equations enforce that all of each type’s mass is assigned, with splitting permitted. The supply equations, together with nonnegative slack variables, exactly express the supply inequalities and permission to leave supply unused.
The variable and equality counts are correct:
All matrix coefficients belong to \(\{0,1\}\). The objective coefficients are the input valuations, with zero coefficients for the slack variables; the right-hand sides are the input masses and supplies.
The dense encoding estimate
\[
B=O\bigl((\tau+m)(N+m)+L\bigr)
\]
correctly accounts for the matrix and numerical input, up to the stated dimension metadata. Encoding nonnegativity and the zero objective coefficients adds only polynomial overhead. Since \(N\le L\), construction and encoding are polynomial in the requested parameters.
Assessment: Correct.
The proposed allocation assigns mass \(\mu_t\) to the empty bundle for each type. It satisfies every type equation and consumes no goods. Setting \(s_g=q_g\) therefore satisfies every supply equation.
All these values are nonnegative rationals under the task’s assumptions. Zero supplies cause no difficulty.
Assessment: Correct.
For every feasible point, nonnegativity and the type equation give \(0\le x_{t,S}\le\mu_t\). Likewise, the supply equation gives \(0\le s_g\le q_g\).
Thus the real feasible polyhedron is bounded. It is closed and nonempty, so compactness and continuity establish attainment of a finite optimum.
The compactness argument establishes real attainment; the exact rational LP theorem invoked next supplies rational attainment and an exact rational output. The proof does not rely on treating the rational feasible points themselves as a compact set.
Assessment: Correct.
The prover states the relevant theorem with sufficient precision: an explicitly binary-encoded rational LP can be solved in polynomial bit complexity, returning an exact rational optimum when an attained finite optimum exists. Its statement includes the polynomial output-length guarantee needed for this task.
The cited [Section 1.3 of *Linear Programming using Limited-Precision Oracles*](https://optimization-online.org/wp-content/uploads/2019/12/7507.pdf) explicitly discusses polynomial-time methods for obtaining exact rational LP solutions, including recovery from sufficiently accurate approximations. Thus the citation supports the exactness claim, rather than only approximate optimization.
The application satisfies the stated hypotheses:
No unverified oracle, integrality assumption, or auction running-time bound is used.
Assessment: Correct.
Every permissible allocation extends to a feasible LP solution by using its unused supplies as slacks. Conversely, deleting the slacks gives a permissible allocation. The objective is unchanged in both directions.
Consequently, an exact rational LP optimum is exactly an allocation maximizing the requested welfare.
The argument also covers \(m=0\): the empty bundle remains available, and the supply constraints are absent. Positive masses summing to one ensure the support is nonempty. Neither monotonicity nor strict positivity of supplies is needed by the argument.
The scope statement correctly distinguishes polynomial time in the explicit input length from polynomial time in the number of goods alone. It fully answers the task’s polynomial-time alternative.
Assessment: Correct.
No mathematical repair or additional clarification is required. The formulation, encoding bound, exact-solution guarantee, and correspondence establish the claimed result.
⟨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.