Answer: Exactly solvable in polynomial time in \(m,\tau,L\), achieving approximation factor \(1\) with supply relaxation \(0\).
Proposition 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIn a multi-unit combinatorial auction with m distinct goods, it is NP- hard to approximate the Social Welfare within factor better than m1/2, even if we allow a multiplicative (1 + ε)-relaxation of the supply constraints, for any ε < 1.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) goods with rational per-capita supplies \(b_\ell\), and \(\tau\) types with rational masses \(\mu_t\) summing to \(1\), where type \(t\) has value \(v_t\) and an integral demanded bundle \(d_t\in\mathbb{Z}_{\ge 0}^m\), choose served masses \(x_t\in[0,\mu_t]\) to maximize \(\sum_t v_t x_t\), subject to \(\sum_t d_t(\ell)x_t\le b_\ell\) for every good \(\ell\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Masses satisfy \(\sum_t\mu_t=1\).
There are \(m\ge2\) goods, with \(m\) unrestricted, and positive rational per-capita supplies \(b_\ell\). Type \(t\) has a positive rational value \(v_t\) and a nonzero demanded bundle \(d_t\in\mathbb Z_{\ge0}^m\), encoded in binary.
Serving mass \(x_t\in[0,\mu_t]\) gives every served individual its entire demanded bundle; unserved individuals have value zero. Welfare is \(W(x)=\sum_t v_t x_t\).
Define \(\mathrm{OPT}(b)=\max\{W(x):0\le x_t\le\mu_t,\ \sum_t d_t(\ell)x_t\le b_\ell\text{ for every }\ell\}\). A \(\rho\)-approximation with supply relaxation \(\varepsilon\) returns such bounded masses satisfying \(\sum_t d_t(\ell)x_t\le(1+\varepsilon)b_\ell\) and \(W(x)\ge\mathrm{OPT}(b)/\rho\).
For fixed rational constants \(0<\delta<1/2\) and \(0\le\varepsilon<1\), is an \(m^{1/2-\delta}\)-approximation with supply relaxation \(\varepsilon\) computable in polynomial time in \(m,\tau,L\), or is achieving this guarantee NP-hard, where \(L\) is the total input bit length?
For discrete single-minded bidders, achieving an \(m^{1/2-\delta}\)-approximation is NP-hard for every fixed \(0<\delta<1/2\), even with supply relaxation \(0\le\varepsilon<1\). [Krysta, Telelis, and Ventre (2015)](https://ranger.uta.edu/~weems/NOTES6319/PAPERSTWO/Mechanisms_for_Multi-unit_Comb.pdf)
No result for exactly this continuous formulation was verified.
The continuous formulation is exactly solvable in polynomial time in \(m,\tau,L\), with zero supply relaxation. Consequently, it admits the requested \(m^{1/2-\delta}\)-approximation for every stated choice of \(\delta\) and \(\varepsilon\).
This conclusion uses precisely the specified service rule: each \(x_t\) may be any real number in \([0,\mu_t]\). Serving part of a type’s mass still gives every served individual its entire bundle.
Index the explicitly listed support by \(t\in\{1,\ldots,\tau\}\). Define the matrix \(D\in\mathbb{Z}_{\ge0}^{m\times\tau}\) by \(D_{\ell t}=d_t(\ell)\), and let \(v=(v_1,\ldots,v_\tau)\) and \(\mu=(\mu_1,\ldots,\mu_\tau)\).
Consider the rational linear program:
Its feasible set and objective coincide exactly with those defining \(\mathrm{OPT}(b)\). Thus this is an exact formulation of the given problem.
We apply the standard polynomial-time rational linear programming theorem: a linear program with explicitly given binary rational coefficients can be solved in time polynomial in its encoding length; when feasible with finite optimum, an exact rational optimizer can be returned. See [Khachiyan, *Polynomial algorithms in linear programming*](https://www.mathnet.ru/eng/zvmmf5239).
All hypotheses hold here:
The theorem therefore returns an exact optimizer \(x^\star\) in polynomial time in \(m,\tau,L\), with \(W(x^\star)=\mathrm{OPT}(b)\).
For completeness, exact output does not require excessively long numbers. A linear objective on a nonempty compact polytope has an optimal vertex. Such a vertex is determined by \(\tau\) linearly independent active constraints. Clearing their rational denominators gives an integer system whose coefficients have polynomial bit length. Cramer’s rule and determinant bounds then give polynomial bit length for every coordinate of that vertex.
Return \(x^\star\) from the preceding algorithm. Its bounds satisfy \(0\le x_t^\star\le\mu_t\), and for every good \(\ell\),
\(\sum_{t=1}^{\tau}d_t(\ell)x_t^\star\le b_\ell\le(1+\varepsilon)b_\ell\),
where the second inequality follows from \(\varepsilon\ge0\) and \(b_\ell>0\).
Since \(m\ge2\) and \(0<\delta<1/2\), the requested factor \(\rho=m^{1/2-\delta}\) satisfies \(\rho>1\). Nonnegativity of welfare therefore gives
\(W(x^\star)=\mathrm{OPT}(b)\ge\mathrm{OPT}(b)/m^{1/2-\delta}\).
Both required conditions hold. In fact, the algorithm achieves approximation factor \(1\) with supply relaxation \(0\).
The cited hardness proof makes goods correspond to graph edges and bidders correspond to vertices. With unit supplies, serving both endpoints of an edge consumes two units, which exceeds \(1+\varepsilon\) when \(\varepsilon<1\). Its conclusion that served bidders form an independent set depends on each bidder’s binary service decision. See [Krysta, Telelis, and Ventre, Proposition 1](https://ranger.uta.edu/~weems/NOTES6319/PAPERSTWO/Mechanisms_for_Multi-unit_Comb.pdf).
The continuous formulation permits partial service of each type’s mass. A small instance illustrates the resulting difference. Take \(m=\tau=3\), masses \(\mu_t=1/3\), values \(v_t=1\), supplies \(b_\ell=1/3\), and demands
\(d_1=(1,1,0),\quad d_2=(1,0,1),\quad d_3=(0,1,1)\).
The continuous allocation \(x_1=x_2=x_3=1/6\) consumes exactly \(1/3\) of every good and has welfare \(1/2\). Summing the three supply constraints gives \(2(x_1+x_2+x_3)\le1\), so its welfare is optimal.
By contrast, if one imposed the additional restrictions \(x_t\in\{0,\mu_t\}\), any two served types would consume \(2/3\) of their shared good. Since \((1+\varepsilon)/3<2/3\), at most one type could be served even under the allowed relaxation, yielding welfare at most \(1/3\).
Thus whole bundles for served individuals are compatible with continuous type masses. The given problem has an exact polynomial-time solution without any integrality assumption.
⟨structured verdict parsed — rendered above⟩
The prover resolves the target correctly. The continuous problem is an explicitly represented rational linear program, and the stated polynomial-time LP theorem applies. The returned exact optimizer satisfies the requested approximation guarantee with zero supply relaxation. No major or minor mathematical issues were found.
The formulation uses one variable \(x_t\) for each of the \(\tau\) explicitly listed support types. Its constraints are exactly the specified bounds \(0\le x_t\le\mu_t\) and supply inequalities \(Dx\le b\), and its objective is exactly \(W(x)=v^{\mathsf T}x\).
There is no change to the service rule: continuous variation of the served mass is expressly permitted by the task. The formulation does not require dividing an individual’s demanded bundle.
Assessment: Correct and exact.
The invoked theorem is stated sufficiently precisely: explicitly encoded rational linear programs admit polynomial-time solution in their binary encoding length, including an exact rational optimizer when feasible with finite optimum. This is the standard rational LP theorem associated with [Khachiyan’s polynomial-time algorithms](https://www.mathnet.ru/eng/zvmmf5239).
The hypothesis checks are valid:
The theorem applies in the binary bit model. The argument claims polynomial time in the input size, not strongly polynomial time, so there is no unsupported complexity strengthening.
Assessment: Correct; all required hypotheses are verified.
The supplementary output-size argument is valid. A nonempty compact polytope has an optimal vertex, and a vertex in \(\mathbb R^\tau\) has \(\tau\) linearly independent active constraints determining it.
Clearing denominators preserves polynomial coefficient bit length. Cramer’s rule and determinant bounds imply polynomial bit length for the resulting rational coordinates. These are routine standard facts, and their use here requires no additional mathematical argument.
This paragraph supports output representability; the earlier LP theorem supplies the polynomial-time method for finding the optimizer.
Assessment: Correct.
The returned optimizer obeys \(0\le x_t^\star\le\mu_t\). For every good, the chain
\(\sum_t d_t(\ell)x_t^\star\le b_\ell\le(1+\varepsilon)b_\ell\)
is valid because \(\varepsilon\ge0\).
Since \(m\ge2\) and \(0<\delta<1/2\), the factor \(m^{1/2-\delta}\) exceeds \(1\). Welfare and its optimum are nonnegative, so exact optimality implies the requested welfare inequality.
The argument includes \(\varepsilon=0\), arbitrary support size, and unrestricted \(m\). Computing the approximation factor is unnecessary because the algorithm returns an exact optimizer.
Assessment: Correct.
The description of the cited reduction matches [Krysta, Telelis, and Ventre, Proposition 1](https://ranger.uta.edu/~weems/NOTES6319/PAPERSTWO/Mechanisms_for_Multi-unit_Comb.pdf): goods represent edges, bidders represent vertices, and a bidder demands the incident edges. Under unit supply and relaxation less than \(1\), serving both endpoints violates the shared good’s supply constraint.
The prover correctly identifies the dependence on binary service decisions. It does not apply that discrete conclusion to continuous type masses.
Assessment: Correct. This comparison is explanatory; the polynomial-time conclusion already follows from the LP argument.
All example data satisfy the task: the masses sum to \(1\), supplies and values are positive rational numbers, and demands are nonzero nonnegative integer vectors.
For \(x_1=x_2=x_3=1/6\), each good receives two contributions of \(1/6\), totaling \(1/3\). Welfare is \(1/2\). Each variable occurs in two supply constraints, so their sum gives \(2(x_1+x_2+x_3)\le1\), establishing optimality.
Under the explicitly additional restrictions \(x_t\in\{0,\mu_t\}\), every pair of served types consumes \(2/3\) of a shared good. This exceeds \((1+\varepsilon)/3\) for every allowed \(\varepsilon<1\). Thus the stated discrete welfare upper bound of \(1/3\) is correct.
Assessment: All computations and strict inequalities check out.
No repair or additional clarification is required. The output establishes exact polynomial-time solvability of the continuous formulation and consequently the requested approximation guarantee.
⟨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.