d4-conf-aaai-2023-0472 (d4-conf-aaai-2023-0472)

Given a finite type set \(\mathcal T\) of size \(\tau\), rational masses \(\mu_t\geq 0\) summing to \(1\), per-buyer budgets \(b_t\), per-population-unit supplies \(q_j\), and efficiently evaluable \(C^2\), concave, degree-one homogeneous utilities \(u_t:\mathbb R^m_+\to\mathbb R_+\), compute an \(\epsilon\)-competitive equilibrium consisting of prices \(p\geq 0\) and per-buyer bundles \(x_t\). Require each type's budget-constrained utility regret, each supply violation in \(\sum_t\mu_t x_{tj}\leq q_j\), and each market-clearing residual \(p_j(q_j-\sum_t\mu_t x_{tj})\) to be at most \(\epsilon\); is this possible in time polynomial in \(m,\tau\), the input bit length, and \(1/\epsilon\)?

A society is given by its support: the list of the \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) divisible goods, positive rational supplies \(q_j\) per population unit, positive rational budgets \(b_t\) per buyer, and rational accuracy \(0<\epsilon<1\).
Each type has a locally non-satiated, continuous, concave, degree-one homogeneous utility \(u_t:\mathbb R_+^m\to\mathbb R_+\), twice continuously differentiable on \(\mathbb R_{++}^m\). Utilities depend only on the buyer's own bundle.
Utilities are encoded by evaluation programs returning values within \(2^{-k}\) at rational arguments \(y\), with a common fixed polynomial running-time bound in the description length, \(\operatorname{bits}(y)\), and \(k\). Let \(L\) be the total binary input length, including these descriptions.
An \(\epsilon\)-competitive equilibrium consists of rational prices \(p\in\mathbb R_+^m\) and per-buyer bundles \(x_t\in\mathbb R_+^m\), satisfying \(p\cdot x_t\leq b_t\) and \(\sup_{y\in\mathbb R_+^m:p\cdot y\leq b_t}u_t(y)-u_t(x_t)\leq\epsilon\) for every type.
Writing \(d_j=\sum_t\mu_t x_{tj}\), require \(\max\{0,d_j-q_j\}\leq\epsilon\) and \(|p_j(q_j-d_j)|\leq\epsilon\) for every good; budgets fix the monetary units.

Does this equilibrium search problem admit an algorithm polynomial in \(m,\tau,L,1/\epsilon\), or is it NP-hard?

For finitely many buyers, [Zhao, Goktas, and Greenwald](https://arxiv.org/pdf/2303.06307) assert polynomial-time approximation of equilibrium allocations and last-iterate convergence at rate \(O(1/T)\) under continuous, jointly concave, own-bundle homogeneous, twice continuously differentiable utilities.
For ordinary finite CCH Fisher markets, [Goktas, Viqueira, and Greenwald](https://arxiv.org/pdf/2107.08153) characterize equilibrium allocations and prices exactly. Neither verified statement specifies the evaluator model and simultaneous absolute-error requirements above.

1. Result

The search problem is polynomial-time solvable under the stated evaluator model. In fact, the algorithm below has running time polynomial in \(m,\tau,L,\log(1/\epsilon)\).

The proof uses a bounded convex–concave saddle problem. Its parameters account explicitly for small type masses, large utility values, exact budget feasibility, and both market-error requirements. No derivative oracle or supplied bound on second derivatives is needed.

Evaluator outputs are understood in the usual binary rational encoding, so their output length is bounded by their running time.

2. A value-oracle optimization fact

We use the following standard theorem: a convex body with a known interior ball and outer radius can be weakly optimized in deterministic oracle-polynomial time from a weak membership oracle. Here weak optimization with tolerance \(\delta\) returns a point within distance \(\delta\) of the body, whose linear objective is within \(\delta\) of the objective at every point whose \(\delta\)-ball lies in the body. This is the Yudin–Nemirovskii theorem, presented as Theorem 4.3.2 and Corollary 4.3.12 in [Grötschel, Lovász, and Schrijver](https://link.springer.com/chapter/10.1007/978-3-642-97881-4_5).

We need its following consequence, including exact feasibility of the returned point.

Lemma. Let \(K=\prod_{i=1}^n[\ell_i,r_i]\) be a nondegenerate rational box. Suppose \(f:K\to\mathbb R\) is convex, has an arbitrary-precision value oracle, and satisfies \(|f|\leq M\) and a known Lipschitz bound \(C\). Then a rational \(z\in K\) satisfying

\(f(z)\leq\min_{y\in K}f(y)+\zeta\)

can be computed in oracle-polynomial time. The numerical parameters enter through their binary encoding lengths, including \(\log(1/\zeta)\).

Proof. Increase \(M\) if necessary so that \(M\geq1\), and consider the convex body

\(E=\{(z,s):z\in K,\ f(z)\leq s\leq M+1\}.\)

Let \(c\) be the midpoint of \(K\), and set

\(a=(c,M+1/2),\qquad r=\min\{1/4,\min_i(r_i-\ell_i)/4\}.\)

The Euclidean ball of radius \(r\) about \(a\) lies in \(E\): its first coordinates remain in \(K\), and its last coordinate lies strictly between \(M\) and \(M+1\). A rational outer radius is obtained directly from the box endpoints and \(M\).

A weak membership oracle for \(E\) follows from value evaluations. Reject points outside the box or above \(M+1\). For other points, evaluate \(f(z)\) with error at most \(\delta/4\), obtaining \(A\). If \(s\geq A\), the point is within distance \(\delta/4\) of \(E\), by increasing its last coordinate if necessary. If \(s<A\), moving its last coordinate downward by \(\delta/4\) leaves \(E\), so the point cannot have its \(\delta\)-ball contained in \(E\).

Let \(z^*\) minimize \(f\), and write \(w^*=(z^*,f(z^*))\). For \(0<\delta<r\), the point

\(w_\delta=(1-\delta/r)w^*+(\delta/r)a\)

has its \(\delta\)-ball contained in \(E\), by convexity. Its last coordinate is at most

\(f(z^*)+\delta(2M+1)/r.\)

Weakly minimize the last coordinate over \(E\). The returned rational point \((z,s)\) is within distance \(\delta\) of \(E\) and satisfies

\(s\leq f(z^*)+\delta(2M+1)/r+\delta.\)

Project \(z\) coordinatewise onto \(K\), obtaining the rational point \(\bar z\). A point of \(E\) within distance \(\delta\) of \((z,s)\) has first coordinates within distance \(2\delta\) of \(\bar z\). Consequently,

\(f(\bar z)\leq s+\delta+2C\delta \leq f(z^*)+\delta\bigl((2M+1)/r+2+2C\bigr).\)

Choose a positive rational \(\delta<r\) making the last error at most \(\zeta\). Its binary length is polynomial in the specified parameters. The weak optimization theorem then proves the lemma. Maximization of a concave function follows by changing its sign. \(\square\)

3. Explicit market parameters

First, the utilities are coordinatewise nondecreasing. Indeed, concavity and degree-one homogeneity give, for \(x,z\in\mathbb R_+^m\),

\(u_t(x+z)=2u_t((x+z)/2)\geq u_t(x)+u_t(z)\geq u_t(x).\)

Evaluate each \(u_t(\mathbf1)\) to error at most \(1/2\). From these outputs, compute a rational \(U\geq1\) satisfying \(u_t(\mathbf1)\leq U\) for every type. Its binary length is polynomial in \(L\). Monotonicity and homogeneity imply

\(u_t(y)\leq U\max_j y_j.\)

Define the positive rationals

\(B=\sum_t\mu_tb_t,\quad b_{\min}=\min_tb_t,\quad b_{\max}=\max_tb_t,\quad \mu_{\min}=\min_t\mu_t,\quad q_{\min}=\min_jq_j,\quad q_{\max}=\max_jq_j.\)

Choose

\(\rho=\min\{\epsilon/[64(1+q_{\max})],\ B/[64m(1+q_{\max})]\},\qquad P=1+8B/q_{\min},\)

and introduce the auxiliary utilities

\(v_t(y)=u_t(y)+\lambda\sum_jy_j,\qquad \lambda=\epsilon\rho/(64mb_{\max}).\)

These utilities remain continuous, concave, homogeneous, and twice continuously differentiable on the positive orthant. They are positive at every nonzero bundle.

Set

\(W=1+(U+m\lambda)b_{\max}/\rho,\)

\(\eta=\min\{1/16,\ \epsilon/(64W),\ [\epsilon\rho/(64B(1+\rho))]^2\},\)

\(\gamma=\min\{\mu_{\min}b_{\min}\eta/4,\ \epsilon/64,\ \epsilon P/128\},\)

and

\(h=\min\{1/2,\ b_{\min}\eta/(4mP)\},\qquad R_t=1+2b_t/\rho.\)

Every parameter is a positive rational of polynomial binary length. Their numerical magnitudes need not be polynomially bounded.

4. Computing a small saddle-point gap

Use the boxes

\(X=\prod_t[h,R_t]^m,\qquad Q=[\rho,P]^m,\)

and define

\(H(x,p)= \sum_t\mu_t\bigl[b_t\log v_t(x_t)-p\cdot x_t\bigr]+p\cdot q.\)

This function is continuous, concave in \(x\), and affine in \(p\). Hence the compact convex–concave minimax theorem applies:

\(\max_{x\in X}\min_{p\in Q}H(x,p) =\min_{p\in Q}\max_{x\in X}H(x,p)=V.\)

Write

\(F(x)=\min_{p\in Q}H(x,p),\qquad D(p)=\max_{x\in X}H(x,p).\)

Thus \(F\) is concave and \(D\) is convex.

We now verify that the optimization lemma applies using only utility evaluations.

Let \(R=\max_tR_t\). Throughout \(X\),

\(\lambda mh\leq v_t(x_t)\leq(U+m\lambda)R.\)

These are positive rational bounds of polynomial binary length. They make arbitrary-precision evaluation of \(\log v_t(x_t)\) polynomial-time: approximate \(v_t\) sufficiently accurately relative to its lower bound, then compute its logarithm. Logarithms of positive rationals have polynomial-time arbitrary-precision algorithms, for example by binary range reduction and the geometrically convergent series for \(\log((1+z)/(1-z))\).

There are also explicit Lipschitz bounds. Monotonicity gives \(\partial_jv_t\geq0\). Differentiating homogeneity gives Euler’s identity,

\(\sum_jx_{tj}\partial_jv_t(x_t)=v_t(x_t).\)

Therefore, on \(X\),

\(0\leq\partial_j\log v_t(x_t)\leq1/x_{tj}\leq1/h.\)

It follows that \(H(\cdot,p)\), uniformly over \(p\in Q\), has Lipschitz constant at most

\(C_x=m(B/h+P).\)

Consequently, \(F\) has the same bound. Similarly, \(D\) has Lipschitz constant at most

\(C_p=m(q_{\max}+R).\)

For completeness, choose an integer \(K_0\) of polynomial size such that the logarithm of every number between \(\lambda mh\) and \((U+m\lambda)R\) has absolute value at most \(K_0\). Then

\(M=1+BK_0+Pm(q_{\max}+R)\)

bounds the absolute values of \(H,F,D\).

The oracle for \(F\) is immediate: at rational \(x\), compute \(d_j=\sum_t\mu_tx_{tj}\) exactly, and use

\(F(x)=\sum_t\mu_tb_t\log v_t(x_t) +\sum_j\bigl[\rho\max\{q_j-d_j,0\}+P\min\{q_j-d_j,0\}\bigr].\)

To evaluate \(D(p)\) to any requested accuracy, apply the optimization lemma to the concave function \(H(\cdot,p)\) on \(X\), then evaluate it at the returned point. Thus the oracle for \(D\) is polynomial-time too. This adds only one level of nested optimization.

Apply the lemma to obtain rational \(x\in X\) and \(p\in Q\) satisfying

\(F(x)\geq V-\gamma/2,\qquad D(p)\leq V+\gamma/2.\)

Their saddle-point gap obeys

\(\mathcal G:=D(p)-F(x)\leq\gamma.\)

5. Buyer regret and exact budget repair

For each type define

\(\ell_t(y)=b_t\log v_t(y)-p\cdot y,\)

with value \(-\infty\) at \(y=0\), and let

\(w_t=\max\{v_t(y):y\geq0,\ p\cdot y\leq b_t\}.\)

Because every price is at least \(\rho\), this budget set is compact. Its maximizing value is positive, and

\(w_t\leq(U+m\lambda)b_t/\rho\leq W.\)

Homogeneity gives the exact identity

\(\max_{y\geq0}\ell_t(y)=b_t\log w_t-b_t.\)

To verify it, for any nonzero \(y\) put \(r=(p\cdot y)/b_t\). The bundle \(y/r\) spends exactly \(b_t\), so

\(\ell_t(y)\leq b_t\log w_t+b_t(\log r-r).\)

The scalar function \(\log r-r\) has its maximum \(-1\) at \(r=1\). A budget-maximizing bundle attains equality.

Such a maximizing bundle \(y_t^*\) satisfies \(y_{tj}^*\leq b_t/\rho\). Thus \(y_t^*+h\mathbf1\in[h,R_t]^m\), and monotonicity implies

\(\ell_t(y_t^*+h\mathbf1)\geq\ell_t(y_t^*)-mPh.\)

The saddle gap decomposes into two nonnegative terms:

\(\mathcal G= [D(p)-H(x,p)]+[H(x,p)-F(x)].\)

The first term is the sum of the type-weighted maximization gaps over their respective boxes. Hence, defining the unrestricted gap

\(g_t=b_t\log w_t-b_t-\ell_t(x_t),\)

we obtain

\(0\leq g_t\leq\gamma/\mu_t+mPh \leq b_{\min}\eta/2\leq b_t\eta.\)

This is where the choice involving \(\mu_{\min}\) protects even a type of very small mass.

Let \(s_t=p\cdot x_t>0\), and output the rational bundle

\(\widehat x_t=(b_t/s_t)x_t.\)

It satisfies the budget exactly: \(p\cdot\widehat x_t=b_t\).

Put

\(r_t=s_t/b_t,\qquad a_t=v_t(\widehat x_t)/w_t.\)

Budget feasibility gives \(0<a_t\leq1\). Homogeneity yields

\(g_t/b_t=-\log a_t+r_t-1-\log r_t.\)

Both terms on the right are nonnegative. Therefore,

\(a_t\geq e^{-\eta},\qquad w_t-v_t(\widehat x_t)\leq W(1-e^{-\eta})\leq W\eta.\)

Furthermore, every coordinate of \(\widehat x_t\) is at most \(b_t/\rho\). For the original utility,

\(\sup_{p\cdot y\leq b_t}u_t(y)-u_t(\widehat x_t) \leq W\eta+\lambda mb_{\max}/\rho \leq\epsilon/32.\)

Thus the required absolute utility regret holds for every type.

We also need a bound on the change in demand caused by normalization. For any \(r>0\),

\(r-1-\log r\geq \begin{cases} (r-1)^2/(2r),&r\geq1,\\ (r-1)^2/2,&r\leq1. \end{cases}\)

These inequalities follow by integrating \((z-1)/z\) between \(1\) and \(r\), and bounding the denominator. Since \(r_t-1-\log r_t\leq\eta\) and \(\eta\leq1/16\), they imply

\(|r_t-1|\leq2\sqrt\eta.\)

For \(r_t\geq1\), explicitly, \(r_t-1\leq\eta+\sqrt{\eta^2+2\eta}\leq2\sqrt\eta\); the other case gives the stronger bound \(\sqrt{2\eta}\).

Consequently,

\(S:=\sum_t\mu_t|s_t-b_t| \leq2B\sqrt\eta \leq\epsilon\rho/[32(1+\rho)].\)

6. Both market-error requirements

First consider the unnormalized demand \(d_j=\sum_t\mu_tx_{tj}\). The price component of the saddle gap is

\(\Delta:=H(x,p)-F(x)\)

\(=\sum_{j:d_j\leq q_j}(p_j-\rho)(q_j-d_j) +\sum_{j:d_j>q_j}(P-p_j)(d_j-q_j) \leq\gamma.\)

All summands are nonnegative.

Also,

\(p\cdot d=\sum_t\mu_ts_t\leq B+S\leq3B/2<2B,\)

where \(S\leq B/2\) follows from \(\eta\leq1/16\).

If \(d_j>q_j\), then

\(p_j<2B/q_j\leq2B/q_{\min}<P/2.\)

The corresponding summand of \(\Delta\) therefore gives

\(d_j-q_j\leq2\gamma/P\leq\epsilon/64,\qquad p_j(d_j-q_j)\leq\gamma.\)

If \(d_j\leq q_j\), then

\(p_j(q_j-d_j) =(p_j-\rho)(q_j-d_j)+\rho(q_j-d_j) \leq\gamma+\rho q_{\max}\leq\epsilon/32.\)

Hence, before normalization,

\(\max\{0,d_j-q_j\}\leq\epsilon/64,\qquad |p_j(q_j-d_j)|\leq\epsilon/32.\)

Now let \(\widehat d_j=\sum_t\mu_t\widehat x_{tj}\). Since normalization multiplies each type’s entire bundle by one scalar,

\(p_j|\widehat d_j-d_j| \leq\sum_t\mu_t|b_t/s_t-1|p_jx_{tj} \leq\sum_t\mu_t|b_t-s_t|=S.\)

Because \(p_j\geq\rho\), this also gives

\(|\widehat d_j-d_j|\leq S/\rho\leq\epsilon/32,\qquad p_j|\widehat d_j-d_j|\leq\epsilon/32.\)

Combining the bounds,

\(\max\{0,\widehat d_j-q_j\}\leq3\epsilon/64<\epsilon,\)

and

\(|p_j(q_j-\widehat d_j)|\leq\epsilon/16<\epsilon.\)

Thus the rational pair \((p,\widehat x)\) meets every stated requirement.

7. Complexity and relation to the cited results

All constructed rational parameters have polynomial binary length. Although \(\gamma\) can be numerically very small, \(\log(1/\gamma)\) is polynomially bounded in the input length and \(\log(1/\epsilon)\). The same holds for the utility lower bounds used when evaluating logarithms.

The optimization lemma uses polynomially many calls at polynomial binary precision and polynomial-length rational arguments. The common fixed polynomial bound on the utility evaluators therefore makes these calls polynomial-time. The nested oracle for \(D\) has fixed depth, so the complete algorithm remains polynomial-time. Its variable dimensions are \(m\tau\) and \(m\); no expansion of rational masses into individual buyers occurs.

The [ordinary CCH equilibrium characterization](https://arxiv.org/pdf/2107.08153) and the [convergence results for influence Fisher markets](https://arxiv.org/pdf/2303.06307) provide relevant context. The argument above independently supplies the evaluator-model and simultaneous absolute-error guarantees required here.

⟨structured verdict parsed — rendered above⟩

The prover’s polynomial-time claim is supported. The oracle reduction, parameter choices, buyer-regret bounds, and both market-error estimates are valid. I found no major or minor issue requiring repair.

• Value-oracle optimization lemma

The cited weak membership-to-weak optimization result applies to a convex body with a known interior center and radius and a known outer radius, with complexity measured in their binary encoding lengths. This is the content of [Grötschel–Lovász–Schrijver, Corollary 4.3.12](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1988.pdf).

The constructed epigraph body \(E\) satisfies these hypotheses. Convexity follows from convexity of \(f\), and compactness follows from the box restriction, the upper bound on the last coordinate, and continuity supplied by the Lipschitz assumption. The proposed interior ball is valid: its first coordinates stay within the box, while its last coordinate remains above \(M\) and below \(M+1\).

The weak membership oracle is correct in both branches. When \(s\geq A\), any violation of \(f(z)\leq s\) is at most \(\delta/4\), so vertical correction establishes the claimed proximity to \(E\). This correction respects the upper cap because \(f(z)\leq M\). When \(s<A\), the point with last coordinate \(s-\delta/4\) lies strictly below \(f(z)\), so the original point cannot have its entire \(\delta\)-ball inside \(E\). Rejection outside the box or above the cap is also valid.

The interpolation defining \(w_\delta\) correctly produces an interior comparison point for weak optimization. Its objective bound has the stated constant. Projection onto the rational box gives exact feasibility, and the subsequent Lipschitz estimate correctly bounds the objective loss. The required precision has polynomial binary length.

Finding: The lemma establishes exactly feasible rational approximate optimizers under the stated oracle assumptions.

• Monotonicity, utility bounds, and parameter encoding

The displayed superadditivity inequality follows from concavity and degree-one homogeneity. Nonnegativity of utility then yields coordinatewise monotonicity. Consequently, the bound \(u_t(y)\leq U\max_j y_j\) is valid, including at \(y=0\).

The evaluator’s fixed polynomial running-time bound controls the binary length of its output at \(\mathbf1\). Thus constructing a rational common upper bound \(U\) does not introduce an uncontrolled magnitude encoding.

All extrema and sums used in the parameter definitions are over nonempty finite lists of positive rational quantities. Every parameter is therefore positive and has polynomial binary length. Small masses, budgets, supplies, or accuracy may make parameters numerically small, but their reciprocals still have polynomial binary encoding length.

The optimization boxes are nondegenerate. In particular, \(h\leq1/2<R_t\), and the definitions of \(\rho\) and \(P\), together with \(q_{\min}\leq q_{\max}\), ensure \(\rho<P\).

Finding: No sign, domain, or encoding problem occurs in the parameter construction.

• Saddle formulation and optimization oracles

The perturbation \(v_t\) retains concavity, homogeneity, continuity, and interior differentiability. Since \(\lambda>0\), it is positive on every nonzero bundle, so all logarithms used on \(X\) are defined.

The function \(H\) is continuous, concave in \(x\), and affine in \(p\). Both domains are compact and convex. The stated minimax equality therefore applies. Taking the infimum over prices preserves concavity of \(F\), and taking the supremum over allocations preserves convexity of \(D\).

The lower and upper bounds on \(v_t\) are valid and have polynomial binary length. They suffice for polynomial-time evaluation of \(\log v_t\) to arbitrary binary precision. The claimed logarithm computation needs no derivative oracle.

Monotonicity gives nonnegative partial derivatives, and differentiable homogeneity gives Euler’s identity. Hence the bound \(\partial_j\log v_t(x_t)\leq1/h\) is justified. The stated constants \(C_x\) and \(C_p\) are valid Euclidean Lipschitz bounds; their generous factors also account for the allocation dimension and the type weights. The bound \(M\) controls \(H\), \(F\), and \(D\).

The formula for \(F\) correctly minimizes each independent affine price term at the appropriate endpoint. The oracle for \(D\) uses the already established optimization lemma on \(H(\cdot,p)\). Approximate maximization followed by approximate evaluation provides arbitrary-precision values of \(D\), with only a fixed additional level of optimization.

Finally, the two optimization guarantees give \(\mathcal G\leq\gamma\) directly.

Finding: The small saddle gap is computable in polynomial time using the supplied evaluators.

• Unrestricted buyer optimization and box truncation

Positive prices make each budget set compact. Continuity gives attainment of \(w_t\), and positivity and homogeneity ensure that a maximizing bundle spends the entire budget.

The scaling argument for \(\ell_t\) is valid for every nonzero bundle. The scalar expression \(\log r-r\) has maximum \(-1\), so the unrestricted maximization identity is exact.

A budget-maximizing bundle has coordinates at most \(b_t/\rho\). Adding \(h\mathbf1\) places it within its allocation box. Monotonicity ensures that this addition does not decrease the logarithmic utility term, while its additional expenditure is at most \(mPh\).

The saddle-gap decomposition has two nonnegative terms. Its allocation component bounds each type’s weighted box-maximization gap. Together with the truncation estimate, this yields the stated bound on \(g_t\). Both contributions are controlled by the definitions of \(\gamma\) and \(h\).

Finding: The proof correctly controls individual buyer gaps, including types with very small positive mass.

• Exact budget normalization and original-utility regret

Since \(p_j>0\) and \(x_{tj}\geq h>0\), every \(s_t\) is positive. The normalization is therefore well defined, rational, and exactly budget feasible.

The identity expressing \(g_t/b_t\) in terms of \(a_t\) and \(r_t\) follows correctly from homogeneity. Budget optimality gives \(0<a_t\leq1\), and both terms in that identity are nonnegative. The resulting bounds on \(a_t\) and on perturbed-utility regret are valid.

The transfer to original utility uses the perturbation cost at the normalized bundle. Its coordinates are bounded by \(b_t/\rho\), giving exactly the stated perturbation allowance. The choices of \(\eta\) and \(\lambda\) then yield regret at most \(\epsilon/32\).

Finding: Every output bundle satisfies the required budget and absolute original-utility regret constraints.

• Expenditure change

Both displayed lower bounds for \(r-1-\log r\) are correct on their respective ranges. With \(\eta\leq1/16\), they imply \(|r_t-1|\leq2\sqrt\eta\).

Weighting the resulting expenditure deviations gives \(S\leq2B\sqrt\eta\). The definition of \(\eta\) supplies the stated accuracy bound on \(S\), and also gives \(S\leq B/2\).

Finding: The demand change caused by normalization is quantitatively controlled.

• Market-error requirements

The expression for \(\Delta\) correctly distinguishes shortage from excess-demand coordinates, and all its summands are nonnegative.

The expenditure bound implies \(p\cdot d<2B\). For a good with excess demand, this forces \(p_j<2B/q_j<P/2\). Its summand in \(\Delta\) then controls both unweighted excess demand and price-weighted excess demand, with the stated constants.

For a shortage coordinate, the remaining term \(\rho(q_j-d_j)\) is bounded by \(\rho q_{\max}\). Together with \(\gamma\), this gives the stated price-weighted shortage estimate.

The normalization estimate follows because each type’s bundle changes by one scalar and each coordinate’s expenditure is at most total expenditure. Dividing by \(p_j\geq\rho\) gives the unweighted demand-change bound.

The final constants check: excess demand is at most \(3\epsilon/64\), and absolute price-weighted imbalance is at most \(\epsilon/16\).

Finding: Both simultaneous market-error requirements hold.

• Complexity, scope, and repair requirements

The proof controls numerical magnitudes through binary lengths throughout. Required oracle precisions and rational query lengths remain polynomial in the input length and \(\log(1/\epsilon)\). The fixed-depth nesting of polynomial-time oracle computations preserves polynomial running time.

The dimensions are \(m\tau\) and \(m\), and the algorithm uses type masses directly. It does not expand the support into individual buyers.

The argument therefore establishes the stronger claimed dependence on \(\log(1/\epsilon)\), which implies the polynomial dependence requested in the task. It does not depend on interpreting either contextual market paper as covering the specified evaluator model.

Minimum additional clarification needed: None.

⟨structured verdict parsed — rendered above⟩