Answer: An exact equilibrium is computable in time and oracle calls polynomial in \(m,\tau,L\), with welfare \(W^*\). The requested guarantee holds with \(C=1\).
Theorem 3.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm SuperAdditiveMC-CWE returns a MC-CWE outcome that O(√m)-approximates the optimal social welfare over all assignments. Furthermore, it can be implemented in a polynomial number of demand queries.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) item kinds, \(\tau\) buyer types with normalized monotone super-additive valuations \(v_t:2^M\to\mathbb Q_{\ge0}\), rational masses \(\mu_t\ge0\) summing to \(1\), and rational per-capita supplies \(b_j\ge0\), compute a welfare-maximizing market-clearing equilibrium. The allocation variables \(x_{t,S}\ge0\) must satisfy \(\sum_S x_{t,S}=\mu_t\) and \(\sum_{t,S:j\in S}x_{t,S}\le b_j\); each positive-mass bundle \(S\) must maximize \(v_t(S)-\sum_{j\in S}p_j\) at item prices \(p_j\ge0\), and unused supply must have price zero. What is the complexity in \(m,\tau\), input bit length, and valuation-oracle access?
Let \(M\) contain \(m\ge1\) item kinds. A society is given by its support: \(\tau\ge1\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts listed types, not possible valuations. Supplies are binary rationals \(b_j\ge0\).
Each type has a normalized monotone super-additive valuation \(v_t:2^M\to\mathbb Q_{\ge0}\). Buyers consume at most one copy of each kind. Access consists of value queries and exact demand queries at nonnegative rational item prices; a demand query may return any maximizing bundle.
An allocation consists of rational masses \(x_{t,S}\ge0\), with \(\sum_{S\subseteq M}x_{t,S}=\mu_t\) and \(\sum_{t,S:j\in S}x_{t,S}\le b_j\). The empty bundle is permitted.
An equilibrium additionally has rational prices \(p_j\ge0\): whenever \(x_{t,S}>0\), \(S\in\arg\max_{T\subseteq M}\{v_t(T)-\sum_{j\in T}p_j\}\); any kind with unused supply has price zero. These are item prices, with no seller-chosen prebundling.
Write \(W(x)=\sum_{t,S}x_{t,S}v_t(S)\), and let \(W^*\) be the maximum welfare over feasible allocations without equilibrium constraints. Let \(L\) include the input encoding length and a bound on the binary length of each valuation returned by an oracle.
Can an exact equilibrium with welfare at least \(W^*/(C\sqrt m)\), for a universal constant \(C\), always be computed in time and oracle calls polynomial in \(m,\tau,L\), or is this approximation guarantee impossible within those bounds?
For discrete super-additive buyers, a polynomial-demand-query algorithm achieves an \(O(\sqrt m)\) welfare approximation using seller-chosen bundles. [Feldman–Lucier](https://arxiv.org/html/1401.2702v2)
For unit buyer capacities and unit supplies, fractional Walrasian allocations and supporting prices are characterized by optimality conditions, and the price problem admits polynomial demand-based computation. This result does not explicitly state the arbitrary rational mass-and-supply formulation above. [Nisan–Segal](https://web.stanford.edu/~isegal/prices.pdf)
An exact equilibrium can always be computed in time and oracle calls polynomial in \(m,\tau,L\). Moreover, its welfare is exactly \(W^*\). Thus the requested guarantee holds with \(C=1\).
The allocation model permits rational masses of buyers to receive different bundles. This makes the configuration linear program the actual welfare optimization problem. The proof below extends the fractional optimality conditions discussed by [Nisan–Segal, Section 9.1](https://web.stanford.edu/~isegal/prices.pdf) to the stated rational masses and supplies.
Write \(p(S)=\sum_{j\in S}p_j\). Consider the finite, though exponentially large, linear program \(P\):
\[ \max_x \sum_{t=1}^{\tau}\sum_{S\subseteq M}v_t(S)x_{t,S}, \]
subject to
\[ \sum_{S\subseteq M}x_{t,S}=\mu_t \quad\text{for every }t, \]
\[ \sum_{t=1}^{\tau}\sum_{S\subseteq M:\,j\in S}x_{t,S}\le b_j \quad\text{for every }j, \qquad x_{t,S}\ge0. \]
This program is feasible: assign every type its entire mass on the empty bundle. Its feasible region is compact, since every coordinate satisfies \(0\le x_{t,S}\le\mu_t\). Its data are rational, so an optimal rational solution exists. Consequently, its optimum is precisely the \(W^*\) in the question.
Associate a dual variable \(u_t\) with each type equality and a nonnegative dual variable \(p_j\) with each supply inequality. The dual program \(D\) is
\[ \min_{u,p} F(u,p) =\sum_{t=1}^{\tau}\mu_tu_t+\sum_{j\in M}b_jp_j, \]
subject to
\[ u_t+p(S)\ge v_t(S) \quad\text{for every }t,\ S\subseteq M, \qquad p_j\ge0. \]
Although equality-constraint dual variables are initially unrestricted, the constraint for \(S=\varnothing\) gives \(u_t\ge0\), because normalization means \(v_t(\varnothing)=0\).
The dual is feasible: take \(p=0\) and \(u_t=v_t(M)\), using monotonicity. Strong linear programming duality therefore gives attained primal and dual optima with common value \(W^*\).
For any primal-feasible \(x\) and dual-feasible \((u,p)\), the duality gap has the following exact decomposition:
\[ F(u,p)-W(x) = \sum_{t,S}x_{t,S}\bigl(u_t+p(S)-v_t(S)\bigr) + \sum_jp_j\left(b_j-\sum_{t,S:\,j\in S}x_{t,S}\right). \]
To verify the identity, expand the right side, use \(\sum_Sx_{t,S}=\mu_t\), and cancel the two occurrences of total payments. Every summand is nonnegative by feasibility.
Now take optimal primal and dual solutions. Their gap is zero, so every summand is zero.
If \(x_{t,S}>0\), it follows that
\[ v_t(S)-p(S)=u_t. \]
Dual feasibility also gives
\[ v_t(T)-p(T)\le u_t \quad\text{for every }T\subseteq M. \]
Thus every positively allocated bundle maximizes that type’s utility.
If kind \(j\) has unused supply, its supply slack is strictly positive. The corresponding zero product in the gap decomposition forces \(p_j=0\).
These are precisely the equilibrium conditions in the question. Hence optimal primal and dual solutions produce an equilibrium of welfare \(W^*\).
Conversely, suppose \((x,p)\) is any equilibrium and define
\[ u_t=\max_{S\subseteq M}\bigl(v_t(S)-p(S)\bigr). \]
The empty bundle ensures \(u_t\ge0\), and these variables are dual feasible. The equilibrium demand condition makes every positively weighted bundle term in the gap decomposition zero. The unused-supply condition makes every supply term zero. Therefore \(F(u,p)=W(x)\); weak duality implies \(W(x)=W^*\).
Thus every equilibrium under the stated definition is welfare optimal.
Query every \(v_t(M)\), and let
\[ V=\max_{1\le t\le\tau}v_t(M). \]
If \(V=0\), monotonicity and nonnegativity imply that all valuations vanish. Assigning everyone the empty bundle at zero prices is then an optimal equilibrium. Henceforth assume \(V>0\).
The dual optimum is unchanged by adding
\[ 0\le u_t\le V,\qquad 0\le p_j\le V. \]
Indeed, start with any dual-feasible \((u,p)\) and replace each coordinate by its minimum with \(V\). Consider a constraint \(u_t+p(S)\ge v_t(S)\).
If none of its participating coordinates exceeds \(V\), the constraint is unchanged. Otherwise, at least one participating coordinate becomes \(V\); all others remain nonnegative. Its left side is therefore at least \(V\), while monotonicity gives \(v_t(S)\le V\). So the clipped vector remains feasible.
Every objective coefficient is nonnegative, so clipping cannot increase the objective. This argument also applies when only an arbitrary subset of the bundle constraints is retained—a fact needed for allocation recovery.
Given a rational candidate \((u,p)\), first check the coordinate bounds. If they hold, all prices are nonnegative, so the allowed demand oracle can be used.
For each type \(t\), request any bundle
\[ S_t\in\arg\max_{S\subseteq M}\bigl(v_t(S)-p(S)\bigr), \]
and query its value. If \(v_t(S_t)-p(S_t)>u_t\), return the violated original constraint
\[ u_t+p(S_t)\ge v_t(S_t). \]
Otherwise every bundle constraint for that type holds, because the returned bundle attains the maximum utility. After checking all types, either a violated constraint has been returned or feasibility has been established.
One separation call uses at most \(\tau\) demand queries and \(\tau\) value queries. Arbitrary tie-breaking causes no difficulty: every maximizing bundle gives the same maximum utility.
We use the following standard rational linear programming theorem, in its constraint-generation form.
Oracle LP theorem. Let a finite rational linear program have \(d\) variables, a known rational bounding box, and polynomial bounds on the binary lengths of its objective and inequality coefficients. Suppose a strong separation oracle either certifies feasibility or returns a violated original inequality. Then exact optimization requires polynomial time and polynomially many oracle calls. Moreover, one can obtain polynomially many original inequalities such that retaining them together with the bounding box preserves the optimum.
The last assertion is the usual primal-recovery property: retained dual constraints identify enough primal variables to recover an optimal primal solution. See [Lecture 8, Section 3, “Using the Dual”](https://www.dcs.warwick.ac.uk/~u2470130/E0249/Notes/lec8.pdf).
Here the dimension is \(d=m+\tau\). The bounding box is \([0,V]^d\). Bundle inequalities have coefficients in \(\{0,1\}\), and their right sides have binary length bounded by \(L\). Objective coefficients are the explicitly supplied rational masses and supplies. Section 4 supplies the required strong separation oracle.
For completeness, the exponential number of inequalities does not introduce exponentially long optimum values. At any vertex of the boxed dual, select \(d\) linearly independent tight inequalities. Their coefficient matrix \(A\) has entries in \(\{-1,0,1\}\), so Hadamard’s inequality gives
\[ |\det A|\le d^{d/2}. \]
Each selected right side has denominator at most \(2^L\). Clearing these denominators and applying Cramer’s rule shows that the coordinates have a common denominator at most \(2^{dL}d^{d/2}\). The objective coefficients have a common denominator at most \(2^{dL}\). Therefore an optimum value has denominator at most
\[ Q=2^{2dL+d^2}. \]
The same bound applies to every restriction obtained by deleting bundle constraints while keeping the box. Coordinate magnitudes are bounded by \(V\), so numerators also have polynomial binary length. In particular, distinct such optimum values differ by at least \(Q^{-2}\). The rational oracle theorem therefore applies to exact optimization, with polynomial precision requirements.
It returns an exact optimal dual vector \((u^*,p^*)\) and a polynomial-size set \(\mathcal K\) of type–bundle constraints preserving the boxed optimum. Add every empty-bundle constraint if necessary; adding these constraints preserves that optimum.
Let \(D_{\mathcal K}\) retain only the bundle constraints indexed by \(\mathcal K\), together with nonnegativity. The clipping argument shows that adding the box does not change its optimum. Hence the *unboxed* \(D_{\mathcal K}\) also has optimum \(W^*\).
Its primal \(P_{\mathcal K}\) is exactly the welfare program of Section 2 restricted to variables \(x_{t,S}\) with \((t,S)\in\mathcal K\). It has polynomially many variables and constraints. It is feasible because all empty-bundle variables were included, and bounded because the type masses bound every coordinate.
Strong duality gives optimum \(W^*\) for \(P_{\mathcal K}\). Solve this explicit rational program exactly and extend its solution by zero on all omitted variables. The resulting \(x^*\) is feasible and optimal for the full welfare program.
Pairing \(x^*\) with the full dual optimizer \((u^*,p^*)\), Section 3 proves that \((x^*,p^*)\) is the required exact equilibrium.
This recovery step determines the appropriate mixture of bundles; it does not require a demand oracle to enumerate all bundles tied at the final prices.
The allocation can be returned sparsely, listing only positive masses. Introduce one slack variable for each of the \(m\) supply inequalities. The restricted primal then has \(m+\tau\) equality rows. An optimal basic feasible solution therefore has at most \(m+\tau\) positive variables, counting supply slacks, and hence at most \(m+\tau\) positive allocation masses. Such an optimal basic solution can be found by standard polynomial-time rational LP methods.
Its masses have polynomial binary length: each basis uses at most \(m+\tau\) columns with entries in \(\{0,1\}\), and its right side consists of the input masses and supplies, so Cramer’s rule again supplies polynomial bounds. Prices likewise have polynomial binary length by the boxed-dual argument.
The entire computation consequently uses polynomial time and polynomially many permitted oracle calls in \(m,\tau,L\), without expanding rational masses into individual buyers.
The proof does not require super-additivity. The discrete seller-bundling approximation concerns allocations subject to different constraints; the fractional masses permitted here make exact welfare optimization possible. The computed equilibrium satisfies \(W(x^*)=W^*\), and therefore
\[ W(x^*)\ge \frac{W^*}{\sqrt m} \qquad\text{for every }m\ge1. \]
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. It establishes polynomial-time computation of an exact equilibrium with welfare \(W^*\), which implies the requested guarantee with \(C=1\). I found no major or minor mathematical issues.
The configuration LP exactly represents the allocation model in USER_TASK: its variables are masses assigned to type–bundle pairs, its type constraints allocate each type’s full mass, and its supply constraints count consumption of each item kind.
The feasibility argument is valid because the empty bundle consumes no items. Compactness follows from finitely many variables and the bounds \(0\le x_{t,S}\le\mu_t\). Rational LP data ensure the existence of a rational optimum. Thus the program’s optimum is indeed \(W^*\).
This formulation uses the intended fractional allocation model and does not introduce seller-chosen bundles or change the buyers’ consumption restrictions.
The dual is correct:
Normalization makes the empty-bundle constraint \(u_t\ge0\). Monotonicity verifies that \(p=0\) and \(u_t=v_t(M)\) are dual feasible.
The primal is feasible and bounded, and the dual is feasible. Therefore the stated application of finite-dimensional LP strong duality, including attainment, is justified.
The displayed duality-gap identity is algebraically correct. Expanding its right side cancels the allocation payments and uses the type equalities to produce the dual objective.
Every term is nonnegative. Consequently, optimal primal and dual solutions satisfy both required conditions:
The converse is also correct. At an equilibrium, defining \(u_t\) as maximum utility yields dual feasibility. Both groups of terms in the gap identity vanish, so primal and dual objective values agree. Weak duality then establishes welfare optimality.
Thus the stronger claim that every equilibrium under the stated definition has welfare \(W^*\) is justified.
The \(V=0\) case is handled correctly: monotonicity and nonnegativity imply that every bundle value is zero. The proposed empty allocation and zero prices satisfy all equilibrium conditions.
For \(V>0\), coordinatewise clipping at \(V\) preserves feasibility. If a participating coordinate changes, that coordinate alone contributes \(V\), while all other contributions are nonnegative and \(v_t(S)\le V\). Otherwise the constraint is unchanged.
Clipping cannot increase the objective because every objective coefficient is nonnegative. The argument remains valid after deleting bundle constraints, as required later.
It also covers zero supplies and supplies exceeding total buyer mass; neither introduces an unstated restriction.
The separation procedure is valid under exactly the permitted oracle access.
Coordinate bounds are checked before demand queries, so all queried prices are nonnegative rationals. A maximizing bundle identifies the maximum utility even with arbitrary tie-breaking. Querying its value therefore either produces a violated original bundle inequality or certifies all bundle inequalities for that type.
The stated bounds of at most \(\tau\) demand queries and \(\tau\) value queries per separation call are correct. Returned inequalities have explicit polynomial-size representations.
The stated rational oracle LP theorem is applicable: the dimension is \(d=m+\tau\), the rational bounding box is known, coefficient lengths are bounded, and the separation oracle returns original violated inequalities.
The cited constraint-recovery assertion is supported by Section 3 of the [Warwick lecture notes](https://www.dcs.warwick.ac.uk/~u2470130/E0249/Notes/lec8.pdf), which describes retaining polynomially many dual constraints and solving the corresponding restricted primal.
The numerical checks are sound:
Here \(d\ge2\), so the determinant contribution fits within the chosen exponent. The same bounds apply to boxed restrictions. Distinct optimum values with denominators at most \(Q\) differ by at least \(Q^{-2}\).
These calculations support polynomial precision requirements. The argument invokes exact rational oracle optimization, rather than assuming that an arbitrary approximate optimizer is already exact.
The recovery argument correctly addresses the main difficulty beyond computing prices.
Adding empty-bundle constraints preserves the boxed optimum: they hold throughout the box, and a full dual optimizer satisfies them. The clipping argument then establishes equality of boxed and unboxed restricted optimum values.
There is no dual-sign problem in identifying the restricted primal. Although the restricted dual explicitly requires \(u_t\ge0\), its retained empty-bundle constraints already impose that requirement on the unrestricted variables associated with primal type equalities.
The restricted primal is feasible because every type has an empty-bundle variable, and bounded because of the type mass constraints. Strong duality therefore gives its optimum as \(W^*\). Extending its solution by zeros preserves feasibility and welfare in the full primal.
Pairing this allocation with the full dual optimizer is legitimate: complementary slackness applies to any primal and dual optimal pair. No enumeration of all tied demand bundles is assumed.
After introducing supply slacks, the restricted primal has \(m+\tau\) equality rows. The stated bound of at most \(m+\tau\) positive allocation masses follows from choosing an optimal basic feasible solution.
The basis coefficients and rational right sides give polynomial binary lengths for allocation masses. The boxed-dual calculation gives the corresponding price bound. Sparse output is therefore polynomial in size, without expanding rational masses into individual buyers.
Finally, \(W(x^*)=W^*\), nonnegative welfare, and \(m\ge1\) imply the requested inequality with \(C=1\).
The proof does not use super-additivity, which is consistent with proving the result for a larger valuation class. No additional mathematical clarification or repair 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.