d4-conf-wine-2010-0027 (d4-conf-wine-2010-0027)

Given \(m\) goods of unit supply and a finite support \(T\) of buyer types, with rational total population mass \(N>0\), type proportions \(\mu_t\ge 0\) summing to \(1\), and rational per-buyer budgets \(b_t\), utilities \(u_{tj}\), and transaction costs \(c_{tj}\), find prices \(p_j\ge\epsilon\) and per-member allocations \(x_{tj}\ge 0\) such that \(\sum_j(p_j+c_{tj})x_{tj}=b_t\) for every type \(t\); \(\sum_t N\mu_t x_{tj}\le 1\) for every good \(j\), with \(\sum_t N\mu_t x_{tj}\ge 1/(1+\epsilon)\) whenever \(p_j>\epsilon\); and \(x_{tj}>0\) only if \(u_{tj}\ge\alpha_t(p_j+c_{tj})/(1+\epsilon)\), where \(\alpha_t=\max_j u_{tj}/(p_j+c_{tj})\).

A society is given by its support: a list \(T\) of \(\tau\geq1\) buyer types, each with positive binary-rational mass \(a_t\). Here \(\tau=|T|\) is the support size, not the number of possible types; \(N=\sum_t a_t>0\) and \(\mu_t=a_t/N\), without requiring \(N=1\).
There are \(m\geq1\) divisible goods, each of unit supply. Type \(t\) has linear utilities with rational coefficients \(u_{tj}\geq0\), at least one positive, rational per-member budget \(b_t>0\), and finite rational transaction costs \(c_{tj}\geq0\) per unit. Its effective unit price is \(p_j+c_{tj}\).
The accuracy parameter \(0<\epsilon\leq1\) is binary rational. Let \(L\) be the total binary input length, including masses, budgets, utilities, costs, and \(\epsilon\).
An \(\epsilon\)-approximate equilibrium consists of rational prices \(p_j\geq\epsilon\) and nonnegative rational per-member allocations \(x_{tj}\), with \(\alpha_t=\max_j u_{tj}/(p_j+c_{tj})\), satisfying
\(\sum_j(p_j+c_{tj})x_{tj}=b_t\) for every type, and \(\sum_t a_t x_{tj}\leq1\) for every good;
\(p_j>\epsilon\Rightarrow\sum_t a_t x_{tj}\geq1/(1+\epsilon)\), and \(x_{tj}>0\Rightarrow u_{tj}\geq\alpha_t(p_j+c_{tj})/(1+\epsilon)\). Ties impose no additional restriction.

Is computing such an \(\epsilon\)-approximate equilibrium in \(\mathrm{P}\), with bit running time polynomial in \(m,\tau,L\), or is this search problem \(\mathrm{NP}\)-hard?

For an explicit list of \(n\) buyers, an algorithm computes the same approximation in \(O(\epsilon^{-1}(n+\log m)mn\log(B/\epsilon))\) operations, where \(B=(1+\epsilon)\sum_i B_i\). A convex formulation also yields a claimed polynomial-time approximation to exact equilibrium, with logarithmic dependence on numerical precision. [Source](https://arxiv.org/html/1001.0393v2)
No result explicitly addressing the support-encoded mass problem above was verified.

Result

The search problem is in \(\mathrm{P}\): an equilibrium satisfying all the stated conditions can be computed with bit running time polynomial in \(m,\tau,L\).

The proof requires more than substituting the support size into the auction algorithm. We use convex optimization to approximate prices, then recover rational allocations by an exactly feasible rational linear program.

1. Absorbing the masses

Define aggregate budgets and allocations by
\[ W_t=a_tb_t,\qquad y_{tj}=a_tx_{tj}. \]

Then the budget and supply constraints become
\[ \sum_j(p_j+c_{tj})y_{tj}=W_t,\qquad \sum_t y_{tj}\leq1. \]

The market-clearing and approximate-optimality conditions are unchanged, because \(a_t>0\). Conversely, aggregate allocations give per-member allocations through \(x_{tj}=y_{tj}/a_t\).

These transformations preserve polynomial encoding length. Thus it suffices to solve a market with \(\tau\) buyers and rational budgets \(W_t\). No expansion into individual society members is needed.

We also divide each utility row by its positive maximum. Henceforth,
\[ 0\leq u_{tj}\leq1,\qquad \max_j u_{tj}=1. \]
This normalization preserves every bang-per-buck comparison and the required approximation condition.

2. An auxiliary equilibrium with a price floor

Set
\[ k=\epsilon/8,\qquad W'_t=(1+k)W_t,\qquad S'=\sum_tW'_t. \]

Consider the following convex program, with natural logarithms:
\[ \min_{p,\beta}\left\{\sum_jp_j-\sum_tW'_t\log\beta_t\right\}, \]
subject to
\[ p_j\geq\epsilon,\qquad \beta_t>0,\qquad p_j+c_{tj}\geq u_{tj}\beta_t. \]

This is the price–inverse-bang-per-buck formulation from Appendix A of the [cited paper](https://arxiv.org/html/1001.0393v2), with inflated budgets and a positive price floor. We establish the properties needed here explicitly.

For fixed \(\beta\), the minimizing prices are
\[ P_j(\beta)=\max\left\{\epsilon,\max_t(u_{tj}\beta_t-c_{tj})\right\}. \]
Consequently, the program reduces to minimizing
\[ f(\beta)=\sum_jP_j(\beta)-\sum_tW'_t\log\beta_t \]
over the positive orthant.

Existence. Put \(C=\max_{t,j}c_{tj}\) and \(H=\max_t\beta_t\). A type attaining \(H\) has some utility coefficient equal to \(1\), so
\[ f(\beta)\geq H-C-S'\log H. \]
This lower bound tends to infinity as \(H\) tends to infinity. If \(H\) stays bounded and any coordinate \(\beta_t\) tends to zero, its negative logarithmic term tends to infinity, while the other terms are bounded below. Thus finite sublevel sets are bounded and stay away from the boundary of the positive orthant. Continuity therefore gives a minimizer \(\beta^*\), with prices \(p^*=P(\beta^*)\).

Equilibrium allocations. The original program satisfies Slater’s condition: choose any positive \(\beta\), then choose all prices sufficiently large to make every inequality strict. Its differentiable convex objective and affine constraints therefore admit KKT multipliers at the optimum.

Let \(q^*_{tj}\geq0\) be the multipliers for
\(u_{tj}\beta_t-p_j-c_{tj}\leq0\), and let \(\rho_j\geq0\) be those for \(\epsilon-p_j\leq0\). Stationarity and complementary slackness give
\[ \sum_tq^*_{tj}+\rho_j=1,\qquad \sum_ju_{tj}q^*_{tj}=W'_t/\beta^*_t, \]
\[ q^*_{tj}>0\ \Longrightarrow\ p^*_j+c_{tj}=u_{tj}\beta^*_t,\qquad \rho_j(p^*_j-\epsilon)=0. \]

It follows that
\[ \sum_tq^*_{tj}\leq1,\qquad p^*_j>\epsilon\ \Longrightarrow\ \sum_tq^*_{tj}=1, \]
and, for every type,
\[ \sum_j(p^*_j+c_{tj})q^*_{tj} =\beta^*_t\sum_ju_{tj}q^*_{tj}=W'_t. \]

Every type receives a positive allocation somewhere because its budget is positive. The price inequalities, together with equality on allocated goods, show that
\[ \alpha^*_t=\max_j\frac{u_{tj}}{p^*_j+c_{tj}}=\frac1{\beta^*_t}. \]
Thus \(q^*\) allocates only exact maximizers at \(p^*\). These auxiliary prices and allocations may be irrational; they will serve only as witnesses.

3. Approximating the auxiliary prices in polynomial bit time

First obtain explicit bounds. If \(p^*_j>\epsilon\), full allocation and nonnegative transaction costs imply
\[ p^*_j =p^*_j\sum_tq^*_{tj} \leq\sum_t(p^*_j+c_{tj})q^*_{tj} \leq S'. \]
Therefore \(p^*_j\leq\max\{\epsilon,S'\}\).

Since some \(u_{tj}=1\) in every row,
\[ \beta^*_t\leq\max\{\epsilon,S'\}+C. \]
Also \(q^*_{tj}\leq1\), so the KKT utility equation gives
\[ W'_t/\beta^*_t=\sum_ju_{tj}q^*_{tj}\leq m, \qquad \beta^*_t\geq W'_t/m. \]

Define the rational numbers
\[ d=\min\left\{1,\frac{\min_tW'_t}{2m}\right\},\qquad R=S'+C+\epsilon+1,\qquad Q=[d,R]^\tau. \]
Then \(\beta^*\in Q\).

On this box, \(f\) is strongly convex with parameter
\[ \gamma=\frac{\min_tW'_t}{R^2}>0. \]
Indeed, the maximum-affine price terms are convex, and the Hessian of the logarithmic part has diagonal entries \(W'_t/\beta_t^2\geq\gamma\). Strong convexity and minimality imply
\[ f(\beta)-f(\beta^*)\geq \frac{\gamma}{2}\|\beta-\beta^*\|_2^2 \qquad(\beta\in Q). \]

Choose
\[ \eta=\epsilon^2/128,\qquad \Delta=\gamma\eta^2/2. \]
We next justify that a rational \(\widehat\beta\in Q\) with
\[ f(\widehat\beta)\leq f(\beta^*)+\Delta \]
can be computed in polynomial bit time.

The weak-optimization hypotheses

We use the standard ellipsoid weak-optimization theorem: given a compact convex body with explicitly known inner and outer balls and a polynomial-time weak separation oracle, rational weak linear optimization is polynomial in the dimension, geometric encoding lengths, and accuracy encoding length. It returns a point within the requested distance of the body whose linear objective is within the requested additive error of the optimum. This is the separation–optimization theorem of [Grötschel, Lovász and Schrijver](https://ir.cwi.nl/pub/10046/10046D.pdf).

Here are explicit hypotheses for its application.

A rational subgradient of \(f\) at any rational \(\beta\in Q\) is computable exactly: choose an active affine piece for each \(P_j\), then add the logarithmic gradient \((-W'_t/\beta_t)_t\). Its Euclidean norm is at most
\[ G=m+S'/d. \]
The price terms each have subgradients of norm at most \(1\), and the logarithmic gradient has norm at most its sum of absolute coordinates, which is at most \(S'/d\). Consequently \(f\) is \(G\)-Lipschitz on \(Q\).

Since \(d\leq1<R\),
\[ |f(\beta)|\leq M:=mR+S'(R+1/d)\qquad(\beta\in Q). \]
Consider the compact convex epigraph truncation
\[ K=\{(\beta,z):\beta\in Q,\ f(\beta)\leq z\leq M+2\}. \]

It contains a ball centered at
\[ \left(\frac{d+R}{2}\mathbf1,\ M+1\right) \]
of radius \(\min\{(R-d)/4,1/2\}\), and it lies in an origin-centered ball of radius \(\tau R+M+2\). All these parameters are rational and have polynomial encoding length.

For completeness, its weak separation oracle works as follows. A point outside \(Q\), or above \(z=M+2\), has an exact coordinate separator. Otherwise evaluate \(f(\beta)\) to additive error \(h/4\), obtaining \(v\). If \(v\leq z+h/2\), raising \(z\) to \(\max\{z,f(\beta)\}\) places the point in \(K\) within distance \(3h/4\). If \(v>z+h/2\), then \(f(\beta)>z\), and an exact rational subgradient \(g\) supplies the separator with normal \((g,-1)\). Indeed, every \((\beta',z')\in K\) satisfies
\[ g\cdot(\beta'-\beta)-(z'-z) \leq z-f(\beta)<0. \]
Logarithms of positive rationals can be evaluated to arbitrary additive accuracy in polynomial bit time. Thus this is a polynomial-time weak separation oracle.

Apply weak optimization to minimize \(z\), with accuracy
\[ \xi=\Delta/(G+2). \]
It returns a rational \((v,z)\) within distance \(\xi\) of \(K\), with \(z\leq f(\beta^*)+\xi\). Clamp each coordinate of \(v\) to \([d,R]\), obtaining \(\widehat\beta\).

There is \((\beta_0,z_0)\in K\) within distance \(\xi\) of \((v,z)\). Coordinatewise clamping cannot increase distance to \(\beta_0\), so
\[ f(\widehat\beta) \leq f(\beta_0)+G\xi \leq z_0+G\xi \leq z+(G+1)\xi \leq f(\beta^*)+\Delta. \]

All numerical parameters above have polynomial encoding length. This proves the required polynomial bit-time approximation. Strong convexity now yields
\[ \|\widehat\beta-\beta^*\|_2\leq\eta. \]
Define \(\widehat p_j=P_j(\widehat\beta)\). Since normalized utilities are at most \(1\),
\[ |\widehat p_j-p^*_j|\leq\eta \qquad\text{for every }j. \]

4. Handling the strict price-floor condition

Set the output prices to
\[ p_j= \begin{cases} \epsilon,&\widehat p_j\leq\epsilon+\eta,\\ \widehat p_j,&\widehat p_j>\epsilon+\eta. \end{cases} \]

These are rational and satisfy \(p_j\geq\epsilon\). Moreover,
\[ |p_j-p^*_j|\leq2\eta. \]
Crucially,
\[ p_j>\epsilon\ \Longrightarrow\ p^*_j\geq\widehat p_j-\eta>\epsilon. \]
Thus every good for which the output requires approximate clearing was fully allocated in the auxiliary equilibrium.

Put \(r=\epsilon/64\). Because \(p^*_j+c_{tj}\geq\epsilon\),
\[ (1-r)(p^*_j+c_{tj}) \leq p_j+c_{tj} \leq(1+r)(p^*_j+c_{tj}). \]

5. A feasible allocation witness

For each type, let
\[ D_t=\sum_j(p_j+c_{tj})q^*_{tj},\qquad \lambda_t=W_t/D_t,\qquad \widetilde y_{tj}=\lambda_tq^*_{tj}. \]
The effective-price bounds imply
\[ (1-r)W'_t\leq D_t\leq(1+r)W'_t, \]
hence
\[ \frac1{(1+k)(1+r)} \leq\lambda_t \leq\frac1{(1+k)(1-r)}. \]

For \(0<\epsilon\leq1\), our constants satisfy
\[ (1+k)(1-r) =1+\frac{7\epsilon}{64}-\frac{\epsilon^2}{512}\geq1, \]
\[ (1+k)(1+r) =1+\frac{9\epsilon}{64}+\frac{\epsilon^2}{512} \leq1+\epsilon. \]
Therefore
\[ \frac1{1+\epsilon}\leq\lambda_t\leq1. \]

The witness \(\widetilde y\) spends exactly \(W_t\) for every type. Its supply use is at most that of \(q^*\), so it never exceeds unit supply. If \(p_j>\epsilon\), then \(\sum_tq^*_{tj}=1\), giving
\[ \sum_t\widetilde y_{tj}\geq\frac1{1+\epsilon}. \]

It also satisfies approximate optimality. For every auxiliary allocated edge,
\[ \frac{u_{tj}}{p_j+c_{tj}}\geq\frac{\alpha^*_t}{1+r}, \]
while all edges satisfy
\[ \frac{u_{tj}}{p_j+c_{tj}}\leq\frac{\alpha^*_t}{1-r}. \]
Writing \(\alpha_t=\max_j u_{tj}/(p_j+c_{tj})\), we obtain
\[ \widetilde y_{tj}>0\ \Longrightarrow\ \frac{u_{tj}}{p_j+c_{tj}} \geq\alpha_t\frac{1-r}{1+r} \geq\frac{\alpha_t}{1+\epsilon}. \]
The last inequality follows from
\(r(2+\epsilon)\leq\epsilon\), which holds for \(r=\epsilon/64\).

Thus a feasible allocation exists at the computed rational prices. The witness itself need not be computed.

6. Recovering rational allocations exactly

Compute each \(\alpha_t\) exactly from the rational output prices, and define
\[ E=\left\{(t,j): \frac{u_{tj}}{p_j+c_{tj}}\geq\frac{\alpha_t}{1+\epsilon}\right\}. \]

Solve the rational linear feasibility problem
\[ y_{tj}\geq0,\qquad y_{tj}=0\text{ for }(t,j)\notin E, \]
\[ \sum_j(p_j+c_{tj})y_{tj}=W_t\qquad\text{for every }t, \]
\[ \sum_ty_{tj}\leq1\qquad\text{for every }j, \]
\[ \sum_ty_{tj}\geq\frac1{1+\epsilon} \qquad\text{for every }j\text{ with }p_j>\epsilon. \]

Section 5 proves real feasibility. This is a bounded rational polytope with \(\tau m\) variables, polynomially many constraints, and polynomial-length coefficients. Polynomial-time rational linear programming therefore returns an exactly feasible rational allocation of polynomial encoding length.

Finally output \(x_{tj}=y_{tj}/a_t\). The mass transformation proves that these allocations satisfy every original requirement, including exact budget exhaustion and exact supply feasibility. The allowed-edge definition imposes precisely the requested approximate-optimality condition and adds no tie restriction.

7. Bit complexity

Mass aggregation, utility normalization, all accuracy parameters, the computed prices, and the final linear program have polynomial encoding length. Weak convex optimization uses accuracy whose binary encoding length is polynomial in the input length; it therefore has logarithmic dependence on \(1/\epsilon\). The final rational linear program is also solvable in polynomial bit time.

Consequently, the stated support-encoded search problem is polynomial-time solvable.

⟨structured verdict parsed — rendered above⟩

The argument is correct in substance and establishes polynomial-time solvability, with a minor omission in matching the weak-separation oracle and geometric bounds to the precise conventions of the cited theorem. I found no false equilibrium identity, failed numerical bound, or substantive feasibility gap.

• Mass aggregation and utility normalization are valid.

Since every \(a_t>0\), the transformations \(W_t=a_tb_t\) and \(y_{tj}=a_tx_{tj}\) are reversible. They preserve budget exhaustion, aggregate supply use, the clearing condition, and the support of each allocation row. They require no expansion into individual buyers and no assumption that \(N=1\).

Products and quotients of the input rationals have polynomial encoding length. Dividing each utility row by its positive maximum preserves all bang-per-buck comparisons and the stated approximate-optimality inequality. The assumption that every row has a positive entry ensures this normalization is defined.

No issue.

• The auxiliary convex program has an optimum with the asserted allocation witnesses.

The elimination of prices is valid: for fixed positive \(\beta\), the objective is increasing in each price, so its minimizing feasible price is exactly \(P_j(\beta)\).

The existence argument checks out. A type attaining \(H\) has a normalized utility equal to \(1\), yielding the stated lower bound. It excludes escape to infinity. On bounded sets, a coordinate approaching zero makes its negative logarithmic term diverge, while the remaining terms have a common lower bound. Consequently, a nonempty finite sublevel set is compact within the positive orthant, and continuity gives an optimum.

Slater’s condition holds as written. The objective is differentiable and convex on its open domain, and all constraints are affine. The stated KKT equations have the correct signs and coefficients.

Complementary slackness justifies replacing effective prices by \(u_{tj}\beta_t^*\) on positive allocation edges. Thus the budget identity, supply inequalities, and exact clearing above the floor all follow. Positive budgets force every type to receive some positive allocation; equality on such an edge establishes \(\alpha_t^*=1/\beta_t^*\).

The attribution of the underlying formulation to Appendix A is accurate; the added price floor is handled explicitly in this output. [Source, Appendix A](https://arxiv.org/html/1001.0393v2)

No issue.

• The price bounds, box bounds, and conditioning estimates are correct.

For a good above the auxiliary floor, full allocation and nonnegative transaction costs give \(p_j^*\leq S'\). Goods at the floor satisfy the other branch of the bound.

The upper bound on \(\beta_t^*\) uses an entry with normalized utility \(1\). The lower bound follows from the KKT utility equation and \(0\leq q_{tj}^*\leq1\). Both place the optimum inside \(Q\).

The strong-convexity parameter \(\gamma\) is valid throughout \(Q\). Combining strong convexity with global minimality gives the stated quadratic objective-gap bound, including when the optimum is on the boundary of \(Q\).

The subgradient construction is valid at ties: any active affine piece supplies a subgradient. The norm bound \(G\), Lipschitz estimate, and absolute objective bound \(M\) are correct.

The asserted inner ball lies inside the box and between the epigraph boundary and the upper truncation. The origin-centered outer-ball bound is also valid. All listed rational parameters have polynomial encoding length, even when their magnitudes or reciprocals are exponentially large.

No substantive issue.

• The weak-optimization argument works, with one minor theorem-interface omission.

The oracle’s acceptance branch correctly certifies distance at most \(3h/4\) from \(K\). Its rejection branch produces a valid strict separating direction: the displayed inequality follows directly from the subgradient inequality and \(z'\geq f(\beta')\).

The cited separation–optimization equivalence supplies the required distance and additive-objective guarantees. Its formulation includes a norm convention for separating vectors and describes inner and outer balls with a common center. [Grötschel–Lovász–Schrijver, Section 1 and Theorem 3.1](https://ir.cwi.nl/pub/10046/10046D.pdf)

Minor issue: The output supplies the raw normal \((g,-1)\) without explicitly matching the theorem’s normalization convention, and supplies its outer ball around the origin rather than explicitly giving a concentric outer bound around the inner-ball center.

Minimum clarification: State the precise oracle convention being used, explain that the returned rational separator satisfies its normalization requirement with polynomial encoding length, and specify the corresponding outer bound about the required center. These are routine representation details; the separating inequality and geometric bounds are already established.

The subsequent optimization calculation is correct. Clamping cannot increase distance to the feasible box point, and the accumulated error is exactly bounded by \((G+2)\xi=\Delta\). Strong convexity therefore gives the required distance to \(\beta^*\), and the maximum-affine price map gives the asserted price accuracy.

Polynomial-time evaluation of logarithms to prescribed additive accuracy suffices here; the rational weights have polynomial bit length.

• The floor rounding and all approximation constants check out.

The rounding rule produces rational prices at least \(\epsilon\). Its error bound is valid, and the strict implication from an output price above the floor to an auxiliary price above the floor is correct. This explicitly handles the potentially discontinuous clearing requirement.

The effective-price comparison follows from \(2\eta/\epsilon=r\). Both expansions involving \(k\) and \(r\) are correct for the entire stipulated range \(0<\epsilon\leq1\).

In particular, the resulting bounds \(1/(1+\epsilon)\leq\lambda_t\leq1\) are valid.

No issue.

• The allocation witness satisfies every required constraint at the computed prices.

Each \(D_t\) is positive and obeys the stated bounds. Row scaling therefore exhausts the original aggregate budget exactly.

Since every scaling factor is at most \(1\), supply remains feasible. Since every scaling factor is at least \(1/(1+\epsilon)\), every output good above the floor meets approximate clearing.

The two effective-price comparisons correctly bound bang-per-buck ratios. Their combination yields the stated approximate-optimality condition. The final constant check \(r(2+\epsilon)\leq\epsilon\) holds throughout the required range.

The witness may be irrational without affecting this existence argument.

No issue.

• Exact rational allocation recovery and the final bit-complexity conclusion are justified.

The allowed-edge set is computable by exact rational comparisons, including ties. The witness proves feasibility of the displayed linear system.

Nonnegativity and the supply constraints bound every allocation coordinate by \(1\), so the feasible set is a bounded rational polytope. Polynomial-time rational linear programming applies even if this polytope has lower dimension, and returns an exactly feasible rational point of polynomial encoding length.

Dividing by the positive masses preserves polynomial encoding length and recovers all original per-member requirements.

The optimization accuracies have polynomial binary encoding length. Thus the claimed bit complexity does not inherit the auction algorithm’s dependence on \(1/\epsilon\), and the support-encoded target is addressed directly.

No additional issue.

The only requested revision is to make the cited weak-optimization theorem’s representation conventions explicit. No new equilibrium argument or numerical estimate is needed.

⟨structured verdict parsed — rendered above⟩