Fast and Interpretable Dynamics for Fisher Markets (aaai23-25723)

Given finitely many buyer types with rational masses, budgets, and valuation vectors, item supplies, and linear utilities, compute an \(\epsilon\)-Fisher equilibrium of the mass-weighted Eisenberg–Gale program using randomized item-block updates across types, with complexity measured in the number of types, items, input bits, and \(\log(1/\epsilon)\).

A society is given by its support: the list of the \(\tau\) types with positive binary-rational masses \(a_t\), with \(\sum_t a_t=1\); \(\tau\) is the support size, not the number of possible types. There are \(m\ge1\) divisible items. Per-person budgets \(B_t>0\), supplies \(s_j>0\), and valuations \(v_{tj}\ge0\) are binary rationals; every type values some item, and every item is valued by some type. Let \(L\) be the total input bit length.
An allocation \(x_t\in\mathbb R_+^m\) is a per-person bundle, with utility \(u_t=\langle v_t,x_t\rangle\) and feasibility \(\sum_t a_tx_{tj}\le s_j\). The mass-weighted Eisenberg–Gale program maximizes \(\sum_t a_tB_t\log u_t\) over feasible allocations. At exact equilibrium, each bundle maximizes utility under \(\langle p,x_t\rangle\le B_t\), and positive-price items clear.
Put \(W=\sum_t a_tB_t\). For rational \(0<\epsilon<1\), an \(\epsilon\)-Fisher equilibrium means a feasible allocation with positive utilities and dual certificates \(p\ge0\), \(\beta_t>0\), satisfying \(p_j\ge\beta_tv_{tj}\) and normalized primal–dual gap \(\sum_j s_jp_j-W+\sum_t a_tB_t\log\!\bigl(B_t/(\beta_tu_t)\bigr)\le\epsilon W\).
The required dynamics start at \(x^0_{tj}=s_jB_t/W\). Set \(c_t=\langle v_t,x_t^0\rangle\), and obtain \(\widetilde f\) from \(-\sum_t a_tB_t\log u_t\) by replacing each logarithmic term below \(c_t\) with its second-order Taylor continuation at \(c_t\).
Each iteration samples an item \(j\) independently and uniformly, and updates only its allocation column by \(x_{\cdot j}^{+}=\operatorname{Proj}_{K_j}(x_{\cdot j}-\eta_j\nabla_{\cdot j}\widetilde f(x))\), where \(K_j=\{z\ge0:\sum_t a_tz_t\le s_j\}\) and the projection is Euclidean. Positive stepsizes may be chosen adaptively; feasible finite-precision approximations are allowed, with all precision and auxiliary computation charged to runtime.

Does this mass-market problem admit randomized projected item-block computation in time polynomial in \(m,\tau,L,\log(1/\epsilon)\), with success probability at least \(2/3\), or is computing the specified approximate equilibrium NP-hard?

Known results: [Nan, Gao, and Kroer](https://arxiv.org/pdf/2303.00506) establish geometric convergence in expected objective gap for discrete projected item-block dynamics, with a rate depending on smoothness and a Hoffman constant, without a polynomial input-bit bound. [Orlin](https://drops.dagstuhl.de/storage/16dagstuhl-seminar-proceedings/dsp-vol10171/DagSemProc.10171.2/DagSemProc.10171.2.pdf) gives a strongly polynomial algorithm for ordinary linear Fisher equilibrium computation; it does not establish the requested bound for these randomized projected item-block dynamics.

Partial progress: adaptive steps for overlapping valuations

The general question remains unresolved here. I prove two new positive results for the prescribed dynamics, including their arithmetic and sampling bounds:

• For at most two support types, arbitrary overlapping valuations are allowed.
• For any number of support types, the dynamics succeed when every item has a unique winner under the equilibrium dual certificates.

Both constructions use the permitted feasible finite-precision approximations. They return an allocation with zero primal–dual gap with probability at least $2/3$ in polynomial time. The unresolved cases have at least three types and ties among equilibrium winners.

1. Computing an equilibrium target

Write
$$ w_t=a_tB_t, \qquad W=\sum_t w_t. $$

First, an exact equilibrium can be computed in polynomial bit time without the dynamics restriction.

Introduce
$$ z_{tj}=\frac{a_tx_{tj}}{s_j}. $$
Consider an ordinary linear Fisher market with unit supplies, buyer budgets $w_t$, and valuations
$$ d_{tj}=s_jv_{tj}. $$
Its feasibility conditions are precisely
$$ z_{tj}\ge0, \qquad \sum_t z_{tj}\le1. $$
Its buyer utility is
$$ U_t=\sum_jd_{tj}z_{tj}=a_tu_t. $$
Thus its Eisenberg–Gale objective differs from the mass-market objective by the constant
$$ \sum_t w_t\log a_t. $$

If $P_j$ denotes a transformed-market price, set $p_j=P_j/s_j$. Then
$$ \sum_jP_jz_{tj} = a_t\sum_jp_jx_{tj}. $$
Consequently, budget constraints and utility maximizers correspond.

Orlin’s theorem supplies a strongly polynomial algorithm computing exact prices and allocations for an ordinary linear Fisher market with positive integer budgets, nonnegative integer valuations, and a positive valuation incident to every buyer and good. These incidence hypotheses hold here. Clearing budget denominators jointly and valuation denominators separately for each buyer satisfies the integrality hypotheses with polynomial encoding length. Buyer-specific valuation scaling preserves demands; common budget scaling scales prices. Hence the theorem applies after these scalings, and its output can be transformed back in polynomial bit time. [Orlin, Theorem 4.1](https://drops.dagstuhl.de/storage/16dagstuhl-seminar-proceedings/dsp-vol10171/DagSemProc.10171.2/DagSemProc.10171.2.pdf).

Fix the resulting rational equilibrium $(x^\star,p^\star)$, and put
$$ u_t^\star=\langle v_t,x_t^\star\rangle, \qquad \beta_t^\star=\frac{B_t}{u_t^\star}. $$
These numbers have polynomial encoding length.

Every equilibrium price is positive: otherwise a type valuing a zero-price item would have unbounded budget-constrained utility. Every type spends its budget, since it values some item positively. Therefore all items clear, and
$$ \sum_j s_jp_j^\star=W. $$
Utility maximization also gives
$$ p_j^\star\ge\beta_t^\star v_{tj}, $$
with equality whenever $x_{tj}^\star>0$.

This establishes polynomial-time solvability of unrestricted equilibrium output. A hardness result for that output problem would therefore imply $\mathrm P=\mathrm{NP}$ under standard reductions. It does not settle the prescribed-trajectory question.

2. Properties of the continued objective

Define
$$ V_t=\sum_j s_jv_{tj}>0. $$
The specified initialization satisfies
$$ c_t=\langle v_t,x_t^0\rangle=\frac{B_tV_t}{W}>0. $$

Let
$$ h_t(u)= \begin{cases} -w_t\log u,&u\ge c_t,\\ -w_t\log c_t-\dfrac{w_t}{c_t}(u-c_t) +\dfrac{w_t}{2c_t^2}(u-c_t)^2,&0\le u<c_t. \end{cases} $$
Then
$$ F(x)=\widetilde f(x)=\sum_t h_t(u_t). $$
Each $h_t$ is differentiable and strictly convex on $[0,\infty)$: its second derivative is $w_t/c_t^2$ below $c_t$ and $w_t/u^2$ above $c_t$, with matching derivatives at the junction.

The equilibrium target minimizes the continuation

Summing the equilibrium dual inequalities against supplies gives
$$ \beta_t^\star V_t\le W. $$
Hence
$$ u_t^\star=\frac{B_t}{\beta_t^\star}\ge c_t. $$

For every feasible $x$,
$$ \sum_t a_t\beta_t^\star u_t \le \sum_j p_j^\star\sum_t a_tx_{tj} \le W. $$
Since $h_t'(u_t^\star)=-a_t\beta_t^\star$, it follows that
$$ \sum_t h_t'(u_t^\star)(u_t-u_t^\star) = W-\sum_t a_t\beta_t^\star u_t \ge0. $$
Convexity therefore implies $F(x)\ge F(x^\star)$.

Moreover, every minimizer has utility vector $u^\star$. Otherwise, strict convexity in utilities would make its midpoint with $x^\star$ have smaller objective. Thus
$$ u\ne u^\star \quad\Longrightarrow\quad F(x)>F(x^\star). $$

Rational marginal utilities

Define
$$ \alpha_t(u)=-\frac{h_t'(u)}{a_t} = \begin{cases} B_t/u,&u\ge c_t,\\ B_t(2c_t-u)/c_t^2,&0\le u<c_t. \end{cases} $$
This function is positive and strictly decreasing, and
$$ \alpha_t(u_t^\star)=\beta_t^\star. $$
The column gradient is
$$ g_{tj}:=\nabla_{tj}F(x) = -a_t\alpha_t(u_t)v_{tj}. $$
For rational allocations, all these derivatives are rational; evaluating them requires no logarithms.

Finally, if $u\ne u^\star$, the convexity inequality gives
$$ \sum_j \left\langle g_{\cdot j}, x_{\cdot j}^\star-x_{\cdot j}\right\rangle \le F(x^\star)-F(x)<0. $$
Thus at least one column points strictly downhill toward its target.

3. Positive steps that implement waiting

Both algorithms below permanently settle columns. Their allocations always consist of columns drawn from the two rational allocations $x^0$ and $x^\star$.

Here is a finite-precision implementation that preserves a settled column when it is sampled.

Let $D$ be the product of the denominators of all coordinates of $x^0$ and $x^\star$. Given an integer precision parameter $P\ge1$, set
$$ Q=2^PD. $$
Every coordinate of either allocation belongs to the grid $Q^{-1}\mathbb Z$.

For a column $z$ that should remain unchanged, compute its gradient $g$ and choose the positive rational step
$$ \eta=\frac{1}{4Q(1+\|g\|_1)}. $$
If
$$ r=\operatorname{Proj}_{K_j}(z-\eta g), $$
the Euclidean projection inequality, using $z\in K_j$, yields
$$ \|r-z\|_2 \le\eta\|g\|_2 < \frac{1}{4Q}. $$
For example, this follows directly from the projection variational inequality:
$$ \|r-z\|_2^2 \le \langle-\eta g,r-z\rangle. $$

Coordinatewise nearest-grid rounding of $r$ therefore returns exactly $z$. The returned allocation is feasible, and its error relative to the exact projected update is less than
$$ \frac{1}{4Q}\le2^{-P-2}. $$
The bound certifies the rounded answer without explicitly computing $r$.

This implements an actual positive stepsize followed by a feasible finite-precision approximation. Taking
$$ P=1+\left\lceil\log_2(1/\epsilon)\right\rceil $$
gives polynomial precision cost. The resulting allocation is exactly unchanged, so these rounding errors do not accumulate in the stored state.

Sampling bound

Suppose a phase designates one unsettled item and succeeds when that item is sampled. Waiting updates leave the state unchanged, so the designated successful update remains valid throughout the phase.

Allow
$$ T=m\left\lceil\log_2(3m)\right\rceil $$
independent uniform samples per phase. Conditionally on any preceding history, the probability of missing its designated item is at most
$$ (1-1/m)^T \le e^{-T/m} \le\frac{1}{3m}. $$
For at most $m$ phases, a union bound gives success probability at least $2/3$, with at most
$$ m^2\left\lceil\log_2(3m)\right\rceil $$
samples.

4. Proven result: arbitrary valuations with two types

Theorem. If $\tau\le2$, the permitted finite-precision projected item-block dynamics compute an allocation with zero requested gap with probability at least $2/3$ in time polynomial in $m,L,\log(1/\epsilon)$.

For $\tau=1$, the initialization already gives the only type every item, so assume $\tau=2$.

One projected step can reach a downhill target column

Fix a current clearing column $z$ and its target $z^\star$. Write
$$ a=(a_1,a_2), \qquad d=(a_2,-a_1). $$
Both columns satisfy $a\cdot z=a\cdot z^\star=s_j$, so
$$ z^\star-z=\kappa d $$
for some rational $\kappa$.

Suppose
$$ \langle g,z^\star-z\rangle<0. $$
Put $q=g\cdot d$. Then $\kappa q<0$, and the rational stepsize
$$ \eta=-\frac{\kappa(a_1^2+a_2^2)}{q} $$
is positive.

For $y=z-\eta g$, define
$$ \lambda=-\frac{\eta\,a\cdot g}{a_1^2+a_2^2}\ge0. $$
The inequality follows because every gradient coordinate is nonpositive. Orthogonal decomposition along $a$ and $d$ gives
$$ y-\lambda a = z-\eta\frac{q}{a_1^2+a_2^2}d = z+\kappa d = z^\star. $$
Since $z^\star\ge0$ and $a\cdot z^\star=s_j$, these equations satisfy the projection KKT conditions, with zero multipliers for nonnegativity. Strict convexity of squared distance therefore proves
$$ \operatorname{Proj}_{K_j}(z-\eta g)=z^\star. $$
The calculation also applies when the target is an endpoint.

Algorithm and termination

Start at $x^0$. In each phase:

• If $u=u^\star$, stop.
• Otherwise, select a column satisfying

$$ \left\langle g_{\cdot j}, x_{\cdot j}^\star-x_{\cdot j}\right\rangle<0. $$

• Wait for that item using Section 3, then apply the displayed stepsize to set its column exactly to its target.

Section 2 guarantees a selectable column. Already-settled columns contribute zero to the sum, so every successful phase settles a new column. After at most $m$ phases, either the algorithm has stopped or $x=x^\star$.

At stopping, output $p^\star,\beta^\star$. Since $u=u^\star$,
$$ \sum_j s_jp_j^\star-W + \sum_t w_t\log\frac{B_t}{\beta_t^\star u_t} =0. $$

Every intermediate utility is positive. Indeed, for each type some coordinate of $x_t^\star$ has positive utility contribution. In its column, either the target has already been installed, or the strictly positive initial coordinate remains.

Arithmetic cost

Every stored column is initial or target, so its encoding length remains polynomial. Utilities, gradients, eligibility tests, stepsizes, grid denominators, and certificates use rational arithmetic on numbers of polynomial encoding length.

A nonzero rational denominator such as $q$ can be numerically tiny, but taking its reciprocal increases encoding length only polynomially. Combined with Section 3’s sample bound and the charged equilibrium preprocessing, this proves the theorem.

5. Proven result: unique equilibrium winners with any number of types

Assume that each item $j$ has a unique type $o(j)$ satisfying
$$ \beta_{o(j)}^\star v_{o(j)j} > \beta_r^\star v_{rj} \qquad \text{for every }r\ne o(j). $$
This condition is checkable by rational comparisons after computing the target.

Complementarity forces the target allocation to be
$$ x_{tj}^\star= \begin{cases} s_j/a_t,&t=o(j),\\ 0,&t\ne o(j). \end{cases} $$

Theorem. Under this unique-winner hypothesis, the permitted dynamics compute an allocation with zero requested gap with probability at least $2/3$ in time polynomial in $m,\tau,L,\log(1/\epsilon)$.

A suitable unsettled item always exists

At the current allocation, define
$$ R_t=\frac{\alpha_t(u_t)}{\beta_t^\star}. $$
If $u\ne u^\star$, some type satisfies $u_t<u_t^\star$. Otherwise all utilities would be at least their equilibrium values, contradicting
$$ \sum_t a_t\beta_t^\star u_t \le W = \sum_t a_t\beta_t^\star u_t^\star $$
unless every utility were equal.

Choose a type $t$ maximizing $R_t$. Strict decrease of $\alpha_t$ implies
$$ R_t>1, \qquad u_t<u_t^\star. $$
Some item owned by $t$ must remain unsettled: if all its owned items had been installed, their utility contribution alone would equal $u_t^\star$, and all other contributions are nonnegative.

Choose such an item $j$. For every $r\ne t$,
$$ \alpha_t(u_t)v_{tj} = R_t\beta_t^\star v_{tj} > R_t\beta_r^\star v_{rj} \ge R_r\beta_r^\star v_{rj} = \alpha_r(u_r)v_{rj}. $$
Thus $t$ is the unique current winner as well.

A rational step reaches the owner endpoint

For this column, write
$$ \gamma_r=\alpha_r(u_r)v_{rj}. $$
Then $\gamma_t>\gamma_r$ for $r\ne t$, and $\gamma_t>0$. The gradient is $g_r=-a_r\gamma_r$.

Given the current clearing column $z$, choose
$$ \eta= 1+\max\left( \left\{0,\frac{s_j/a_t-z_t}{a_t\gamma_t}\right\} \cup \left\{ \frac{z_r/a_r-z_t/a_t+s_j/a_t^2} {\gamma_t-\gamma_r}:r\ne t \right\} \right). $$
All denominators are positive. Put
$$ y_r=z_r+\eta a_r\gamma_r, \qquad \lambda=\frac{z_t+\eta a_t\gamma_t-s_j/a_t}{a_t}. $$
The first bound in the maximum ensures $\lambda\ge0$. Also,
$$ y_t-\lambda a_t=s_j/a_t, $$
while, for $r\ne t$,
$$ y_r-\lambda a_r = a_r\left( \frac{z_r}{a_r}-\frac{z_t}{a_t} +\frac{s_j}{a_t^2} -\eta(\gamma_t-\gamma_r) \right) \le0. $$
Therefore
$$ z_r^+=\max\{0,y_r-\lambda a_r\} $$
is exactly the target owner endpoint. It clears supply and satisfies the projection KKT conditions, proving that it is the Euclidean projection.

Completion and bit complexity

Designate this unsettled item, use rounded waiting updates until it is sampled, and install its target endpoint. Each successful phase settles one new column. Hence at most $m$ phases are needed, and Section 3 gives the required success probability.

All stored columns remain initial or target. The strict differences $\gamma_t-\gamma_r$ are nonzero rationals with polynomial encoding length; their reciprocals likewise have polynomial encoding length. Thus even extremely small winner separations do not invalidate the polynomial arithmetic bound.

At termination, $u=u^\star$, and $p^\star,\beta^\star$ give zero requested gap.

6. Why the two-type argument does not directly extend

For three types, a strictly downhill direction toward an equilibrium column need not be reachable by one scalar projected step.

Consider
$$ a_1=a_2=a_3=\frac13, \qquad B_t=s_j=1, $$
with two items and valuations
$$ v_1=(3,1), \qquad v_2=v_3=(1,1). $$
The initialization has every coordinate equal to $1$. An equilibrium is
$$ x_1^\star=(2,0), \qquad x_2^\star=(1,1), \qquad x_3^\star=(0,2). $$
Indeed, its utilities are $(6,2,2)$, and
$$ p^\star=(1/2,1/2), \qquad \beta^\star=(1/6,1/2,1/2). $$
Every type spends its budget on items attaining its maximum utility per unit price, and both supplies clear.

At initialization, the first-column gradient is
$$ g=(-1/4,-1/6,-1/6). $$
Its target displacement is $(1,0,-1)$, so
$$ \langle g,(1,0,-1)\rangle=-1/12<0. $$
Nevertheless, the second and third coordinates of $z-\eta g$ are equal for every $\eta>0$. The feasible set and Euclidean projection are invariant under exchanging these coordinates. Uniqueness of projection therefore makes the projected coordinates equal too. They cannot equal the target coordinates $1$ and $0$.

This example identifies a failure of the one-step target argument. It gives no general update lower bound: another equilibrium allocates the two columns as $(2,1/2,1/2)$ and $(0,3/2,3/2)$.

7. Remaining question

The proved classes permit overlapping valuations and adaptive steps far beyond reciprocal global smoothness bounds. Their proofs also explicitly account for precision, preprocessing, and uniform sampling.

For general markets with at least three types and tied equilibrium winners, I have neither a polynomial trajectory construction nor an obstruction covering every permitted adaptive rule.

⟨structured verdict parsed — rendered above⟩

Verification report

Overall assessment: partial progress. The two restricted dynamics results are sound as written, apart from a minor omission concerning timeout handling. They do not resolve the general question in USER_TASK. No central false step or counterexample to either restricted theorem was found.

The distinction matters: polynomial-time equilibrium preprocessing is established for every input, but the prescribed projected item-block trajectory is established only for the two stated classes.

1. Equilibrium preprocessing

Verified.

The substitution
$$ z_{tj}=\frac{a_tx_{tj}}{s_j} $$
correctly transforms feasibility into unit-supply feasibility. With budgets $w_t=a_tB_t$ and valuations $d_{tj}=s_jv_{tj}$, the transformed utility is indeed
$$ U_t=a_tu_t. $$
Consequently, the two Eisenberg–Gale objectives differ by the stated allocation-independent constant.

The price transformation $p_j=P_j/s_j$ also gives the stated spending identity. Both utility maximization and budget feasibility therefore correspond under the transformation.

The cited result applies to integral budgets and utilities, assuming every buyer and every good has a positive valuation incident to it. The prover checks these hypotheses and correctly explains denominator clearing: common budget scaling and buyer-specific valuation scaling preserve the relevant demands. The source establishes exact equilibrium computation with a strongly polynomial algorithm; its rational reconstruction is consistent with the claimed polynomial encoding bound. [Orlin, Sections 1.1, 2, and 4](https://drops.dagstuhl.de/storage/16dagstuhl-seminar-proceedings/dsp-vol10171/DagSemProc.10171.2/DagSemProc.10171.2.pdf).

The subsequent equilibrium properties also check out:

• Every price is positive because a positively valued, zero-price good would make a buyer’s utility maximization unbounded.
• Every buyer spends its budget.
• Every item clears, and total revenue equals $W$.
• The certificates $\beta_t^\star=B_t/u_t^\star$ satisfy the stated dual inequalities and complementary equalities.

This establishes unrestricted equilibrium computation. It does not establish the prescribed trajectory bound, and the prover correctly maintains that distinction.

2. Continued objective and its minimizers

Verified.

The formula for $c_t$ follows directly from initialization. Its positivity follows from the valuation incidence assumptions.

The Taylor continuation has the correct coefficients. Its first and second derivatives match at $c_t$, and the stated second derivatives are positive throughout the domain. Thus the differentiability and strict convexity assertions are valid.

Summing the equilibrium dual inequalities against supplies correctly gives
$$ \beta_t^\star V_t\le W, $$
and hence $u_t^\star\ge c_t$. This justifies evaluating the derivative at the equilibrium utility using the logarithmic branch.

The inequality
$$ \sum_t a_t\beta_t^\star u_t\le W $$
holds for every feasible allocation. The resulting first-order convexity calculation proves that $x^\star$ minimizes the continuation.

Strict convexity in the utility vector, together with feasibility of the midpoint, correctly proves that every minimizer has utility vector $u^\star$. It does not require uniqueness of the allocation.

The formulas for $\alpha_t$ and the column gradient are correct, including their signs and behavior at $c_t$. The final convexity inequality correctly guarantees a column with strictly negative target directional derivative whenever $u\ne u^\star$.

3. Waiting updates, precision, and sampling

Verified, with one minor implementation omission.

The denominator product $D$ puts all stored coordinates on the proposed grid. Its bit length is polynomial because it is the product of polynomially many denominators of polynomial encoding length.

The projection variational inequality gives the stated displacement bound. Since each coordinate moves by less than $1/(4Q)$, nearest-grid rounding returns the original column exactly. That returned column is feasible, and its Euclidean error relative to the exact projected update satisfies the stated bound.

This is a permitted finite-precision approximation under USER_TASK. In particular, the write-up supplies an error certificate for returning the unchanged column without explicitly computing the projection. The stored state has no accumulated rounding error.

The sampling calculation is also correct. Conditional on previous phases, the designated item remains fixed while waiting, and independent uniform sampling gives the stated miss probability. The choice
$$ T=m\left\lceil\log_2(3m)\right\rceil $$
is sufficient for the claimed union bound, including $m=1$.

Minor issue: The algorithms say to wait until the designated item is sampled, while the polynomial runtime argument caps waiting at $T$ samples per phase. The behavior when those samples all miss is implicit.

Minimum clarification: Explicitly state that a phase timeout terminates the algorithm with failure, or with a specified fallback output. This makes the bounded runtime implementation unambiguous; it does not change the success-probability argument.

4. The result for at most two types

Verified.

For two types, clearing columns lie on the same affine line, so the displacement representation
$$ z^\star-z=\kappa(a_2,-a_1) $$
is correct.

The strict downhill condition implies $\kappa q<0$, making the displayed stepsize positive. The orthogonal decomposition has the correct signs and coefficients. Because the gradient coordinates are nonpositive, the supply multiplier $\lambda$ is nonnegative.

The resulting equations satisfy the Euclidean projection optimality conditions. Zero nonnegativity multipliers are valid even when the target is an endpoint. Thus the projected step reaches the target exactly.

The phase-selection argument is valid: settled columns contribute zero, so a strictly downhill column must be unsettled. Each successful phase therefore settles a new column.

Positive intermediate utilities follow from the stated initial-or-target column invariant. At stopping, equality of the utility vectors gives zero requested primal–dual gap, whether or not the allocation itself equals $x^\star$.

The rational arithmetic argument is sufficient. Exact tests, stepsizes, and reciprocal operations involve numbers of polynomial encoding length; small nonzero rational values do not themselves cause superpolynomial bit length.

The single-type case is correctly handled by initialization.

5. The unique-winner result

Verified.

The strict winner condition, complementarity, and supply clearing force each target column to be the stated owner endpoint.

The argument establishing an under-served type when $u\ne u^\star$ is valid. Maximizing $R_t$ then yields $R_t>1$ and $u_t<u_t^\star$. Such a type must own an unsettled item, as argued.

The inequality chain proving that this owner is also the unique current winner is correct. It remains valid when a competing valuation is zero.

The endpoint stepsize formula also checks out. Its denominators are positive, its first bound makes $\lambda\ge0$, and the remaining bounds make every competing projected coordinate zero. The resulting allocation clears supply and satisfies the Euclidean projection conditions.

Termination, zero-gap certification, and arithmetic bounds follow from the same stored-column invariant and sampling argument. The intermediate-utility positivity argument from the two-type section applies unchanged here.

The result depends on the strict winner hypothesis. It provides no guarantee when equilibrium winners tie.

6. The three-type example

Verified, with the stated limited interpretation.

The displayed target allocation is feasible and clearing. Its utilities, prices, and certificates are correct; each buyer spends its budget on maximizing goods.

At initialization, the first-column gradient and directional derivative are correctly computed:
$$ g=(-1/4,-1/6,-1/6), \qquad \langle g,(1,0,-1)\rangle=-1/12. $$

The symmetry argument is valid. The second and third coordinates of the pre-projection point agree, and the feasible set is invariant under exchanging them. Uniqueness of Euclidean projection therefore prevents reaching the displayed asymmetric target column in one step.

This refutes only the proposed generalization of that one-step target argument. The prover correctly states that it supplies no lower bound covering all adaptive rules or all equilibrium targets.

7. Unresolved target and actionable feedback

Major issue relative to USER_TASK: the general dynamics question remains unsettled.

Neither restricted theorem covers general inputs with at least three support types and tied equilibrium winners. The example does not establish a trajectory obstruction, and unrestricted equilibrium preprocessing does not establish that a permitted trajectory reaches an equilibrium in polynomial time.

This is an acknowledged limitation, not an internal contradiction or a false claim of completeness.

Minimum requirement for completion: Provide an argument covering the remaining inputs that establishes either the requested polynomial runtime for the prescribed dynamics or the requested hardness conclusion. The existing restricted proofs do not imply either outcome.

The direction is promising because both restricted trajectory constructions survive verification. The appropriate adjudication remains partial, and the continuous problem’s requested complexity classification remains unresolved.

⟨structured verdict parsed — rendered above⟩