d4-conf-wine-2024-0004 (d4-conf-wine-2024-0004)

Given sellers \(K\), items \(J\) partitioned among them, \(\tau\) types with rational masses \(\mu_t>0\) summing to \(1\), per-capita budgets \(b_t\), values \(v_{tj}\), per-capita supplies \(s_j\), and positive initial budget splits \(\beta^0_{tk}\), run the paper’s pacing-equilibrium process with mass-weighted feasibility \(\sum_t\mu_t x^r_{tj}=s_j\) and update \(\beta^{r+1}_{tk}=b_t u^r_{tk}/u^r_t\), where \(u^r_{tk}=\sum_{j\in J_k}v_{tj}x^r_{tj}\) and \(u^r_t=\sum_k u^r_{tk}\). Does this process converge to a continuum competitive equilibrium, and what bit-sensitive round and per-round computation bounds suffice to output a feasible average allocation \(\hat{x}\) with \(G^*-G(\hat{x})\le\epsilon\), where \(G(x)=\frac{\sum_t\mu_t b_t\log(\sum_jv_{tj}x_{tj})}{\sum_t\mu_t b_t}\) and \(G^*\) is its maximum over feasible allocations?

A society is given by its support: \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. There are \(m\ge1\) divisible items, partitioned into nonempty sets \(J_k\) owned by sellers \(k\in K\).
All numerical inputs are binary rationals: per-capita budgets \(b_t>0\), supplies \(s_j>0\), and values \(v_{tj}\ge0\). Each item has a positive value for some type, and each type values some item of every seller positively. Initial per-capita splits satisfy \(\beta^0_{tk}>0\) and \(\sum_k\beta^0_{tk}=b_t\). Let \(L\) be the total input bit length, including the requested rational accuracy \(0<\epsilon<1\).
An allocation specifies per-capita quantities \(x_{tj}\ge0\), with feasibility \(\sum_t\mu_t x_{tj}=s_j\). At round \(r\), seller \(k\) chooses an uncapped value-maximizing pacing equilibrium: multipliers \(\alpha^r_{tk}>0\), prices \(p^r_j=\max_t\alpha^r_{tk}v_{tj}\), feasible quantities, and per-capita payments \(\sum_{j\in J_k}p^r_jx^r_{tj}=\beta^r_{tk}\); positive allocations require \(\alpha^r_{tk}v_{tj}=p^r_j\). Ties may be divided fractionally in any equilibrium-consistent way.
Set \(u^r_{tk}=\sum_{j\in J_k}v_{tj}x^r_{tj}\), \(u^r_t=\sum_k u^r_{tk}\), and \(\beta^{r+1}_{tk}=b_tu^r_{tk}/u^r_t\). A continuum competitive equilibrium is a linear Fisher competitive equilibrium with per-capita budgets \(b_t\) and the mass-weighted clearing constraints above. Convergence means that splits, prices, and total utilities have equilibrium limits, and every allocation accumulation point is an equilibrium allocation.
Define \(B=\sum_t\mu_tb_t\), \(G(x)=B^{-1}\sum_t\mu_tb_t\log(\sum_jv_{tj}x_{tj})\), with \(\log0=-\infty\), and \(G^*=\max_{x\text{ feasible}}G(x)\). The round average is \(\hat x=T^{-1}\sum_{r=0}^{T-1}x^r\).

Is obtaining a feasible round average with \(G^*-G(\hat x)\le\epsilon\) polynomial-time in \(m,\tau,|K|,L,1/\epsilon\), or NP-hard at inverse-polynomial accuracy?
Does the prescribed process converge to a continuum competitive equilibrium, and what round and per-round bit-operation bounds suffice for that accuracy?

For finitely many buyers, proportional seller-budget dynamics has competitive equilibria as fixed points, converges to equilibrium, and has an ergodic Eisenberg–Gale objective gap of \(O(T^{-1})\). [Li–Tang](https://arxiv.org/html/2407.11872v1)
Continuous-item Fisher markets have equilibrium existence and convex-program characterizations; this concerns a continuum of items, rather than this buyer-mass dynamics. [Gao–Kroer](https://ojs.aaai.org/index.php/AAAI/article/view/16684) No result settling this precise dynamics and its bit complexity was located.

Proven results and remaining classification

The prescribed process converges in the sense requested, and
$$ T=\left\lceil\frac{2L}{\epsilon}\right\rceil $$
exact rounds suffice for the objective guarantee.

There is also a stronger computational obstruction than the one in NOTES: the exact round average itself can require exponentially many output bits, even with four types and two singleton sellers. Thus, under the standard representation of the output by explicit binary rationals, obtaining the exact prescribed average is not polynomial-time in the stated parameters. This conclusion applies to arbitrary algorithms, rather than only to algorithms explicitly storing every split.

This is an output-size lower bound, not an NP-hardness proof. Consequently, the proposed polynomial-time-versus-NP-hard dichotomy is not established.

For the numerical interpretation, I additionally prove that a polynomial-bit rounded implementation produces an exactly feasible allocation whose average utilities approximate those of the prescribed trajectory and whose objective gap is at most $\epsilon$. Its output need not equal an exact prescribed round average.

All logarithms below are natural unless explicitly written as $\log_2$.

1. Reduction using the support, without expanding the population

Define
$$ w_t=\frac{\mu_tb_t}{B},\qquad q_{tk}^r=\frac{\mu_t\beta_{tk}^r}{B},\qquad y_{tj}^r=\frac{\mu_tx_{tj}^r}{s_j},\qquad a_{tj}=\frac{s_jv_{tj}}{\mu_t}. $$
Then
$$ \sum_t w_t=1,\qquad \sum_kq_{tk}^r=w_t,\qquad \sum_ty_{tj}^r=1. $$
The utility transformation is exact:
$$ U_{tk}(y):=\sum_{j\in J_k}a_{tj}y_{tj} =\sum_{j\in J_k}v_{tj}x_{tj}=u_{tk}. $$
Write $U_t=\sum_kU_{tk}$. The objective becomes
$$ F(y):=\sum_tw_t\log U_t(y)=G(x). $$

For prices and multipliers, define
$$ \pi_j^r=\frac{s_jp_j^r}{B}, \qquad A_{tk}^r=\frac{\mu_t\alpha_{tk}^r}{B}. $$
For $j\in J_k$, the seller conditions become
$$ \pi_j^r=\max_tA_{tk}^ra_{tj},\qquad y_{tj}^r>0\Longrightarrow A_{tk}^ra_{tj}=\pi_j^r, $$
and
$$ \sum_{j\in J_k}\pi_j^ry_{tj}^r=q_{tk}^r. $$
These are precisely the equilibrium conditions of a unit-supply linear Fisher market with seller-specific budgets $q_{tk}^r$. Summing payments gives
$$ \sum_j\pi_j^r=\sum_{t,k}q_{tk}^r=1. $$

Every item has positive price. Every type has positive spending at every seller, so its seller utility is positive. The tight-edge condition therefore gives
$$ A_{tk}^r=\frac{q_{tk}^r}{U_{tk}^r}, \qquad q_{tk}^{r+1}=w_t\frac{U_{tk}^r}{U_t^r}. $$
In particular, all finite-round splits remain positive.

The transformed market has exactly $\tau$ buyers. Its rational input length is polynomial in the original input length. The finite-market convergence results of [Li–Tang](https://arxiv.org/html/2407.11872v1) are therefore relevant, but the required convergence and rate statements are proved below.

2. Equilibrium characterization

Let
$$ \mathcal Y=\left\{y\geq0:\sum_ty_{tj}=1\text{ for every }j\right\}. $$
This set is compact and convex. The allocation $y_{tj}=1/\tau$ gives every type positive utility. The extended objective $F$, with $\log0=-\infty$, is upper semicontinuous and bounded above, so it attains its maximum. Every maximizer has positive total utilities.

The maximizing total utility vector $U^*$ is unique. Indeed, the feasible utility vectors form a convex set, and
$$ U\longmapsto\sum_tw_t\log U_t $$
is strictly concave on positive utility vectors.

Fix a maximizing allocation $y^*$. Define
$$ \lambda_t^*=\frac{w_t}{U_t^*}, \qquad \pi_j^*=\max_t\lambda_t^*a_{tj}. $$
For every feasible $z$, the directional derivative at $y^*$ gives
$$ \sum_{t,j}\lambda_t^*a_{tj}(z_{tj}-y_{tj}^*)\leq0. $$
Hence $y^*$ maximizes this linear functional over $\mathcal Y$. Since the allocation of each item can be varied independently,
$$ y_{tj}^*>0\Longrightarrow\lambda_t^*a_{tj}=\pi_j^*. $$
Consequently,
$$ \sum_j\pi_j^*y_{tj}^* =\lambda_t^*U_t^*=w_t, \qquad \sum_j\pi_j^*=1. $$
For any bundle $z_t$ costing at most $w_t$,
$$ \lambda_t^*\sum_ja_{tj}z_{tj} \leq\sum_j\pi_j^*z_{tj}\leq w_t. $$
Thus $y_t^*$ is utility maximizing at prices $\pi^*$.

Conversely, consider an arbitrary Fisher equilibrium $(\widetilde y,\widetilde\pi)$, and write its utilities as $\widetilde U_t$. Every price is positive: a zero-priced item valued positively by some buyer would make that buyer's utility-maximization problem unbounded. Every buyer spends its budget because it values some item positively.

Set
$$ \widetilde\lambda_t=\frac{w_t}{\widetilde U_t}. $$
Individual optimality and full spending imply
$$ \widetilde\lambda_ta_{tj}\leq\widetilde\pi_j, \qquad \widetilde y_{tj}>0 \Longrightarrow \widetilde\lambda_ta_{tj}=\widetilde\pi_j. $$
Therefore, for any feasible $y$ with positive utilities,
$$ \begin{aligned} F(y)-F(\widetilde y) &\leq\sum_t\widetilde\lambda_t \bigl(U_t(y)-\widetilde U_t\bigr)\\ &\leq\sum_j\widetilde\pi_j \left(\sum_ty_{tj}-\sum_t\widetilde y_{tj}\right) =0. \end{aligned} $$
An allocation with a zero utility has objective $-\infty$, so the same optimality conclusion holds for all feasible allocations.

Thus equilibrium allocations are exactly the maximizers of $F$. Their total utilities are $U^*$, and their prices are uniquely
$$ \pi_j^*=\max_t\frac{w_t}{U_t^*}a_{tj}. $$

Define the split associated with $y^*$ by
$$ q_{tk}^* =\sum_{j\in J_k}\pi_j^*y_{tj}^* =\lambda_t^*U_{tk}^*. $$
These reference splits may have zero coordinates, and their row sums are $w_t$.

3. A telescoping identity and the exact-round bound

For the fixed equilibrium split $q^*$, define
$$ D_r=\sum_{t,k}q_{tk}^*\log\frac{q_{tk}^*}{q_{tk}^r}, $$
interpreting zero-weight terms as zero. Both arrays have total mass one, so $D_r\geq0$.

Set
$$ M_{tk}^r=A_{tk}^rU_{tk}^*, \qquad h_r=\sum_{t,k}M_{tk}^r. $$
The maximum-bid condition implies
$$ h_r =\sum_{t,j}A_{tk(j)}^ra_{tj}y_{tj}^* \leq\sum_j\pi_j^r=1. $$
Moreover, $h_r>0$, and $q_{tk}^*>0$ implies $M_{tk}^r>0$.

Define
$$ H_r=\sum_{t,k}q_{tk}^* \log\frac{q_{tk}^*}{M_{tk}^r}. $$
Writing $D(p\|z)=\sum_i p_i\log(p_i/z_i)$ for probability vectors,
$$ H_r=D(q^*\|M^r/h_r)-\log h_r\geq0. $$

Using the update and $q_{tk}^r=A_{tk}^rU_{tk}^r$,
$$ \begin{aligned} D_r-D_{r+1} &=\sum_{t,k}q_{tk}^* \log\frac{q_{tk}^{r+1}}{q_{tk}^r}\\ &=\sum_{t,k}q_{tk}^* \log\frac{w_t/U_t^r}{A_{tk}^r}\\ &=\sum_tw_t\log\frac{U_t^*}{U_t^r} +\sum_{t,k}q_{tk}^* \log\frac{\lambda_t^*}{A_{tk}^r}\\ &=F^*-F(y^r)+H_r. \end{aligned} $$
The last equality uses $q_{tk}^*=\lambda_t^*U_{tk}^*$ on every positive reference coordinate. Therefore
$$ D_r-D_{r+1}\geq F^*-F(y^r)\geq0. $$

Summing over the first $T$ rounds,
$$ \frac1T\sum_{r=0}^{T-1}\bigl(F^*-F(y^r)\bigr) \leq\frac{D_0}{T}. $$
The average allocation $\hat y$ is feasible. By concavity,
$$ G^*-G(\hat x)=F^*-F(\hat y)\leq\frac{D_0}{T}. $$

Since $q_{tk}^*\leq w_t$,
$$ D_0 \leq\sum_{t,k}q_{tk}^*\log\frac{w_t}{q_{tk}^0} \leq\max_{t,k}\log\frac{b_t}{\beta_{tk}^0}. $$
Every positive rational in an input of total length $L$ lies between $2^{-L}$ and $2^L$. Hence
$$ D_0\leq2L\log2<2L. $$
This proves the sufficient round bound
$$ \boxed{ T=\left\lceil\frac{2L}{\epsilon}\right\rceil \Longrightarrow G^*-G(\hat x)\leq\epsilon. } $$
The bound holds for every equilibrium-consistent choice of ties.

4. Convergence of the prescribed process

4.1 Utilities and allocation accumulation points

The telescoping inequality gives
$$ \sum_{r=0}^{\infty}\bigl(F^*-F(y^r)\bigr)<\infty, $$
so $F(y^r)\to F^*$.

Every allocation subsequence has a convergent further subsequence because $\mathcal Y$ is compact. An accumulation point cannot have a zero total utility: that logarithmic term would tend to $-\infty$, while the remaining terms have fixed finite upper bounds.

At a positive-utility accumulation point, $F$ is continuous. Every such point consequently maximizes $F$, and is an equilibrium allocation. Uniqueness of $U^*$ then gives
$$ U_t^r\longrightarrow U_t^* \quad\text{for every }t. $$

4.2 Prices

Since $D_r$ decreases to a finite limit, $D_r-D_{r+1}\to0$. The identity in Section 3 implies $H_r\to0$. Its decomposition therefore yields
$$ h_r\to1,\qquad D(q^*\|M^r/h_r)\to0. $$

We use the probability-vector form of Pinsker's inequality, with natural logarithms:
$$ D(p\|z)\geq\frac12\|p-z\|_1^2. $$
Here both vectors are normalized, and every positive reference coordinate has positive denominator. Thus
$$ M^r/h_r\to q^*, \qquad M^r\to q^*. $$
Whenever $U_{tk}^*>0$,
$$ A_{tk}^r =\frac{M_{tk}^r}{U_{tk}^*} \longrightarrow\lambda_t^*. $$

For each item $j$, choose a type $t$ with $y_{tj}^*>0$. Its reference seller utility is positive, so
$$ \liminf_r\pi_j^r \geq\lim_rA_{tk(j)}^ra_{tj} =\pi_j^*. $$
All current and limiting price vectors sum to one. For any fixed item $j$,
$$ \limsup_r\pi_j^r \leq1-\sum_{\ell\ne j}\liminf_r\pi_\ell^r \leq\pi_j^*. $$
Hence $\pi^r\to\pi^*$.

4.3 Splits

Let
$$ a_{\min}=\min\{a_{tj}:a_{tj}>0\}. $$
Every type values some item of every seller positively. Since $\pi_j^r\leq1$, the maximum-bid condition gives
$$ 0<A_{tk}^r\leq\frac1{a_{\min}}. $$

Take a subsequence along which $(q^r,y^r)\to(\bar q,\bar y)$. Its allocation limit is an equilibrium allocation.

If $\bar U_{tk}=0$, the identity $q_{tk}^r=A_{tk}^rU_{tk}^r$ and the multiplier bound imply $\bar q_{tk}=0$.

If $\bar U_{tk}>0$, some item $j\in J_k$ has $a_{tj}>0$ and $\bar y_{tj}>0$. Eventually $y_{tj}^r>0$ along this subsequence, so
$$ A_{tk}^r=\frac{\pi_j^r}{a_{tj}} \longrightarrow\frac{\pi_j^*}{a_{tj}} =\lambda_t^*. $$
Thus in both cases
$$ \bar q_{tk}=\lambda_t^*\bar U_{tk}. $$
Every split accumulation point is therefore an equilibrium split.

Use $\bar q$ as the reference split in Section 3. The potential $D(\bar q\|q^r)$ is nonincreasing. Along the chosen subsequence it tends to zero, because every positive coordinate of $\bar q$ has a positive limiting denominator. Hence it tends to zero along the entire sequence. Pinsker's inequality gives $q^r\to\bar q$.

The inverse changes of variables are fixed. This proves convergence of the original splits, prices, and total utilities, with every allocation accumulation point a continuum competitive-equilibrium allocation.

5. Sufficient bounds for exact rational computation

An exact rational linear Fisher equilibrium is computable in polynomial bit complexity. One applicable result is Orlin's exact algorithm: with $N$ buyers plus goods and $E$ positive valuation incidences, its strongly polynomial arithmetic bound is
$$ O\!\left(N^2\log N\,(E+N\log N)\right). $$
The bit-operation consequence uses polynomially bounded intermediate encodings, not unit-cost arithmetic on arbitrary-length numbers. Rational inputs reduce to integral inputs by clearing budget denominators globally and valuation denominators separately for each buyer. The former scales prices; the latter scales each buyer's utility and preserves its preferences. Positive budgets and positive valuation incidence for every buyer and good hold here. See [Orlin, Theorem 4.1 and Section 1.1](https://drops.dagstuhl.de/storage/16dagstuhl-seminar-proceedings/dsp-vol10171/DagSemProc.10171.2/DagSemProc.10171.2.pdf).

The later-round budget lengths must nevertheless be bounded.

Consider a seller's tight-edge graph, with edges satisfying
$$ \pi_j=A_ta_{tj}. $$
Every buyer and item lies in this graph. Within a connected component, spanning-tree paths express
$$ A_t=c_t\ell,\qquad \pi_j=d_j\ell, $$
where the rational coefficients depend only on the fixed valuations. Their bit lengths are polynomial in the original input length and market dimensions. Summing spending within the component gives
$$ \ell= \frac{\sum_{t\text{ in the component}}q_t} {\sum_{j\text{ in the component}}d_j}. $$
Thus prices and multipliers have rational encodings whose lengths are linear in the current budget encoding length, up to polynomial factors.

Let $S_r$ bound the bit length of a common denominator and all numerators of the split array. Seller utilities are $q_{tk}^r/A_{tk}^r$. Summing these utilities and applying the proportional update uses polynomially many rational operations. Taking a common denominator for the resulting split array consequently gives
$$ S_{r+1}\leq P(S_r+1), $$
for some polynomial $P\geq2$ in $m,\tau,|K|,L$. Enlarging $P$ to cover the initial encoding yields
$$ S_r\leq P^{r+1}. $$

A rational equilibrium allocation can be selected by the exact algorithm. Equivalently, once prices and tight edges are known, rational payments satisfying the buyer and item totals can be found by a transportation-flow computation, and quantities are payments divided by prices.

Consequently, for a computably chosen rational tie division:

• Round $r$ requires at most $P^{O(r+1)}$ bit operations.
• Computing the first $T$ rounds and their exact average requires at most $P^{O(T)}$ bit operations.

Combined with Section 3, this is a sufficient singly exponential exact-computation bound. It does not bound the encoding of arbitrary externally supplied irrational tie divisions.

6. New result: the exact average has exponential output length

The following example strengthens the simulation obstruction in NOTES to an obstruction for every algorithm producing an explicit exact average.

6.1 Four types and two singleton sellers

Take
$$ \tau=4,\qquad \mu_t=\frac14,\qquad b_t=1,\qquad s_1=s_2=1,\qquad v_{t1}=v_{t2}=1. $$
Each seller owns one item. Let
$$ f_t(z)=\frac{tz}{1+tz},\qquad z_0=24, $$
and initialize
$$ \beta_{t1}^0=f_t(z_0),\qquad \beta_{t2}^0=1-f_t(z_0). $$
All task hypotheses hold.

Write $S(z)=\sum_{t=1}^4f_t(z)$. If the current splits have this form, seller prices and per-capita allocations are uniquely
$$ p_1=\frac{S(z)}4,\qquad p_2=\frac{4-S(z)}4, $$
$$ x_{t1}=\frac{4f_t(z)}{S(z)},\qquad x_{t2}=\frac{4(1-f_t(z))}{4-S(z)}. $$
Uniqueness follows directly from the single-item payment equations.

The update satisfies
$$ \frac{f_t^{\,\mathrm{next}}}{1-f_t^{\,\mathrm{next}}} =tz\,\frac{4-S(z)}{S(z)}. $$
Hence the form is preserved, with
$$ z_{r+1}=R(z_r):=z_r\frac{4-S(z_r)}{S(z_r)}. $$

Define
$$ P(z)=\prod_{t=1}^4(1+tz) =1+10z+35z^2+50z^3+24z^4. $$
Since $S(z)=zP'(z)/P(z)$,
$$ R(z)=\frac{4P(z)-zP'(z)}{P'(z)} =\frac{50z^3+70z^2+30z+4} {96z^3+150z^2+70z+10}. $$

6.2 Uniform bounds on cancellation

Write $z_r=a_r/b_r$ in lowest positive terms. Define the homogeneous polynomials
$$ \begin{aligned} N(a,b)&=50a^3+70a^2b+30ab^2+4b^3,\\ D(a,b)&=96a^3+150a^2b+70ab^2+10b^3,\\ C(a,b)&=4(b+2a)(b+3a)(b+4a). \end{aligned} $$
The next unreduced split parameter is $N(a_r,b_r)/D(a_r,b_r)$, and
$$ x_{11}^r=\frac{C(a_r,b_r)}{D(a_r,b_r)}. $$

The following polynomial identities are verified by expansion:
$$ \begin{aligned} &(-27120a^2-33255ab-8741b^2)N\\ &\quad +(14125a^2+15025ab+3500b^2)D=36b^5,\\ &(210a^2+225ab+50b^2)N\\ &\quad +(-109a^2-100ab-20b^2)D=36a^5, \end{aligned} $$
and
$$ \begin{aligned} &(-6000a^2-7407ab-1972b^2)C\\ &\quad +(6000a^2+4532ab+790b^2)D=12b^5,\\ &(285a^2+325ab+75b^2)C\\ &\quad +(-284a^2-190ab-30b^2)D=96a^5. \end{aligned} $$

Because $\gcd(a,b)=1$, the first pair implies
$$ \gcd(N(a,b),D(a,b))\mid36. $$
Indeed, a common divisor divides both $36a^5$ and $36b^5$, whose greatest common divisor is $36$.

The second pair similarly implies
$$ \gcd(C(a,b),D(a,b))\mid96. $$
For each prime, at least one of $a,b$ has zero valuation, and $12$ divides $96$.

Let $d_r$ be the reduced denominator of $x_{11}^r$. Reduction of the recurrence and of the allocation therefore gives
$$ \boxed{ \frac{b_{r+1}}{96}\leq d_r\leq36b_{r+1}. } $$

6.3 Denominator growth survives averaging

The coefficient ratios of the numerator and denominator of $R$ lie between $2/5$ and $25/48$. Since all coefficients are positive,
$$ \frac25\leq z_r\leq\frac{25}{48}<1 \quad\text{for every }r\geq1. $$
In particular,
$$ D(a_r,b_r)\geq10b_r^3. $$
The cancellation bound yields
$$ b_{r+1}\geq\frac5{18}b_r^3 \quad(r\geq1). $$

Set
$$ h_r=\log_2b_r,\qquad c=\log_2(18/5). $$
Then
$$ h_{r+1}\geq3h_r-c. $$
The first iterate is
$$ z_1=\frac{366122}{707597}, $$
so $h_1>c/2$. Induction gives
$$ h_r\geq3^{r-1}(h_1-c/2)+c/2. $$

We now bound the denominator of the sum, allowing arbitrary cancellation. Fix $r\geq1$, and let $H$ be the reduced denominator of
$$ \sum_{i=0}^r x_{11}^i. $$
Let $E$ be the reduced denominator of the preceding sum. Then
$$ E\leq\prod_{i=0}^{r-1}d_i. $$
Subtracting that preceding sum from the full sum shows that $d_r$ divides $HE$. Therefore
$$ H\geq\frac{d_r}{E} \geq\frac{d_r}{\prod_{i=0}^{r-1}d_i}. $$

The recurrence also implies, for $1\leq k\leq r$,
$$ h_k\leq3^{-(r-k)}h_r+c/2. $$
Consequently,
$$ \sum_{k=1}^rh_k\leq\frac32h_r+\frac{rc}{2}. $$
Using the bounds on $d_i$,
$$ \begin{aligned} \log_2H &\geq h_{r+1}-\log_2 96 -\sum_{k=1}^rh_k-r\log_2 36\\ &\geq\frac32h_r-c-\log_2 96 -r\bigl(c/2+\log_2 36\bigr). \end{aligned} $$
The right-hand side is $\Omega(3^r)$.

Dividing a reduced rational by a positive integer cannot decrease its reduced denominator: if the rational is $n/H$, the new denominator is
$$ \frac{HT}{\gcd(n,T)}\geq H. $$
Taking $r=T-1$, we conclude
$$ \boxed{ \text{The exact coordinate }\hat x_{11} \text{ requires }\Omega(3^T)\text{ binary bits.} } $$
This proof does not assume that an algorithm constructs the intermediate splits.

6.4 Accuracy forces many rounds

The function $S$ increases continuously from $0$ to $4$, so there is a unique $z_*>0$ with $S(z_*)=2$. Moreover,
$$ zS'(z)=\sum_tf_t(z)(1-f_t(z)). $$
Differentiating $R=z(4-S)/S$ gives
$$ R'(z) =\frac{4\sum_tf_t(z)^2-S(z)^2}{S(z)^2}>0. $$
The strict inequality follows because the four $f_t(z)$ are distinct for $z>0$.

Since $S(24)>2$, we have $z_0>z_*$. For $z>z_*$,
$$ R(z)<z,\qquad R(z)>R(z_*)=z_*. $$
Thus $z_*<z_{r+1}<z_r$ for every round.

The per-capita total utility is
$$ U_t(z)=\frac{4f_t(z)}{S(z)} +\frac{4(1-f_t(z))}{4-S(z)}, $$
and direct simplification gives
$$ U_t(z)-2 =\frac{(4-2S(z))(4f_t(z)-S(z))} {S(z)(4-S(z))}. $$
For type $1$, both numerator factors are negative when $z>z_*$, because $f_1(z)$ is strictly smaller than the average of the four coordinates. Hence
$$ U_1^r>2 \quad\text{for every }r. $$
Define the fixed positive constant
$$ d=U_1^0-2. $$
The average utility satisfies
$$ \hat U_1-2\geq\frac dT. $$

Every feasible allocation has
$$ \sum_{t=1}^4U_t=8,\qquad U_t\leq8. $$
The allocation $x_{t1}=x_{t2}=1$ is feasible and gives utilities $(2,2,2,2)$. Jensen's inequality shows that this vector maximizes
$$ F(U)=\frac14\sum_t\log U_t. $$
On positive utilities bounded by $8$,
$$ \nabla^2F(U)\preceq-\frac1{256}I. $$
Taylor's inequality from $(2,2,2,2)$ therefore gives
$$ F^*-F(\hat U) \geq\frac1{512}\sum_t(\hat U_t-2)^2. $$
The linear term vanishes because the total utility is fixed. Thus
$$ G^*-G(\hat x)\geq\frac{d^2}{512T^2}. $$
Achieving gap at most $\epsilon$ requires
$$ T\geq\frac d{\sqrt{512\epsilon}}. $$

Combining this with the exact-average encoding bound proves
$$ \boxed{ \text{Every accurate explicit exact average in this example needs } \exp\!\bigl(\Omega(\epsilon^{-1/2})\bigr) \text{ output bits.} } $$

6.5 The obstruction occurs at inverse-polynomial accuracy

For an integer $n\geq2$, replace every budget by
$$ b_t=1+2^{-n} $$
and multiply every initial split by the same factor. Uniformly scaling all budgets scales prices and preserves every round allocation and split proportion.

The resulting total input length is $L_n=\Theta(n)$. Choose
$$ \epsilon_n=\frac1{n^2}. $$
This is inverse-polynomial in $L_n$, and the required output length is
$$ \exp(\Omega(n))=\exp(\Omega(L_n)). $$
Therefore explicit exact-average computation is not polynomial-time even at inverse-polynomial objective accuracy.

7. Polynomial-bit numerical approximation of the trajectory

This section concerns a feasible numerical substitute for the exact average. It does not remove the output obstruction above.

7.1 Stability of seller utilities

Consider two equilibria of the same seller market, with positive budget vectors $q,q'$ and multipliers $A,A'$. Define
$$ e=\max_t\left|\log\frac{q'_t}{q_t}\right|. $$
I claim
$$ \max_t\left|\log\frac{A'_t}{A_t}\right|\leq e. $$

Let $h=\max_t A'_t/A_t$, and let $I$ be the buyers attaining this maximum. Consider every item allocated positively to some buyer in $I$ in the first equilibrium. Its second price is exactly $h$ times its first price: an old tight bidder in $I$ supplies the lower bound, while all multiplier ratios are at most $h$.

Every second-equilibrium winner of such an item belongs to $I$. A buyer with smaller multiplier ratio bids strictly below that new price. Therefore
$$ \sum_{t\in I}q'_t \geq h\sum_{t\in I}q_t. $$
On the other hand,
$$ \sum_{t\in I}q'_t \leq\left(\max_t\frac{q'_t}{q_t}\right) \sum_{t\in I}q_t. $$
Thus $h\leq\max_tq'_t/q_t$. Reversing the roles of the equilibria gives the lower multiplier-ratio bound.

Since seller utilities satisfy $U_t=q_t/A_t$,
$$ \left|\log\frac{U'_t}{U_t}\right|\leq2e. $$
In particular, equal budgets imply equal seller utilities, independently of tie divisions.

For full split arrays, define the same maximum logarithmic distance over all type–seller pairs. Local seller utilities and their sums differ multiplicatively by at most $\exp(2e)$. Consequently the proportional update map $\Phi$ satisfies
$$ \boxed{ \max_{t,k}\left| \log\frac{\Phi(q')_{tk}}{\Phi(q)_{tk}} \right|\leq4e. } $$

7.2 Rounding with polynomial precision

Write $f_{tk}=q_{tk}/w_t$, so every row sums to one. Set
$$ \rho_0=\min_{t,k}f_{tk}^0,\qquad a_{\max}=\max_{t,j}a_{tj},\qquad w_{\min}=\min_tw_t, $$
and
$$ c_0=\frac{w_{\min}a_{\min}}{ma_{\max}}\in(0,1]. $$
The multiplier bound gives
$$ U_{tk}\geq a_{\min}q_{tk}, \qquad U_t\leq ma_{\max}. $$
Thus every ideal next proportion satisfies
$$ f_{tk}^{\mathrm{ideal}} =\frac{U_{tk}}{U_t}\geq c_0f_{tk}. $$

Choose
$$ T=\left\lceil\frac{4L}{\epsilon}\right\rceil, \qquad \eta=\frac{\epsilon}{32\,4^T}. $$
Choose a dyadic grid spacing $\delta=2^{-H}$ satisfying
$$ |K|\delta \leq\eta\rho_0(c_0/2)^T. $$

At each round, compute an exact seller equilibrium at the current rounded budgets. Round the first $|K|-1$ ideal proportions in each row downward to the grid, and assign the residual to the last coordinate.

Each coordinate changes by at most $|K|\delta$. Induction gives
$$ f_{tk}^r\geq\rho_0(c_0/2)^r, $$
and the relative rounding error is at most $\eta$. Indeed, for $r<T$, the ideal proportion is at least $\rho_0(c_0/2)^T$, and multiplication by $1-\eta\geq1/2$ preserves the inductive lower bound.

The logarithmic rounding error is at most $2\eta$. Let $e_r$ be the logarithmic distance between the rounded and prescribed splits at round $r$. The stability lemma gives
$$ e_0=0,\qquad e_{r+1}\leq4e_r+2\eta. $$
Therefore
$$ e_r\leq\frac{2\eta(4^r-1)}3 \leq\frac{\epsilon}{48} \quad(r\leq T). $$
Their corresponding total utilities differ multiplicatively by at most $\exp(\epsilon/24)$. The same bound holds for averaged total utilities, because averaging preserves coordinatewise multiplicative inequalities.

Let $\hat y_{\mathrm{round}}$ be the average of the rounded-round allocations, and $\hat y_{\mathrm{exact}}$ the prescribed average. Then
$$ \left|F(\hat y_{\mathrm{round}}) -F(\hat y_{\mathrm{exact}})\right| \leq\frac{\epsilon}{24}. $$
Section 3 gives
$$ F^*-F(\hat y_{\mathrm{exact}}) \leq\frac{2L}{T}\leq\frac{\epsilon}{2}. $$
Consequently,
$$ F^*-F(\hat y_{\mathrm{round}}) \leq\frac{\epsilon}{2}+\frac{\epsilon}{24}<\epsilon. $$
Every rounded-round allocation, and hence its rational average, is exactly feasible.

The rational magnitude bounds imply
$$ H=O\!\left(T(L+1)+\log(|K|/\epsilon)\right). $$
The grid can be selected using rational comparisons with polynomial-length encodings. Each round's budgets have polynomial encoding length in $L+H$. Exact seller computation and rational averaging therefore take polynomially many bit operations in
$$ m,\tau,|K|,L,1/\epsilon. $$

8. Scope of the conclusions

The convergence question is settled affirmatively. The prescribed trajectory has the exact-round objective bound $2L/T$, and exact rational computation has a sufficient singly exponential bit-operation bound.

The new four-type example settles a stronger negative computational statement: an explicit exact average of the prescribed rounds cannot always be obtained in polynomial time, because the required output itself is too long. This remains true at inverse-polynomial accuracy.

The numerical substitute in Section 7 has polynomial bit complexity and closely tracks the prescribed average utilities. It is nevertheless an average of rounded-process allocations, so it does not satisfy the strict exact-average output requirement.

No NP-hardness reduction is established, and the complexity of producing succinct representations of exact prescribed averages remains open.

⟨structured verdict parsed — rendered above⟩

Verification report

The output establishes substantial correct results: convergence of the prescribed process, the exact-round objective bound, an explicit-output lower bound, and a polynomial-time rounded substitute. I found no false central mathematical step.

The requested polynomial-time-versus-NP-hard classification is not fully established. The output explicitly acknowledges this limitation. Its unconditional output-size obstruction must be distinguished from NP-hardness, and its rounded substitute must be distinguished from a prescribed round average.

1. Support reduction

Verified.

The changes of variables correctly preserve feasibility, utilities, payments, and tight-edge conditions. In particular,
$$ A_{tk}a_{tj} =\frac{s_j\alpha_{tk}v_{tj}}{B}, \qquad \pi_jy_{tj} =\frac{\mu_tp_jx_{tj}}{B}. $$
Thus the transformed seller markets have unit supplies and budgets $q_{tk}$, without expanding the population.

Each transformed item has a positive valuation incidence, so its maximum-bid price is positive. Positive spending at every seller then ensures positive seller utility. The identities
$$ A_{tk}^r=\frac{q_{tk}^r}{U_{tk}^r}, \qquad q_{tk}^{r+1}=w_t\frac{U_{tk}^r}{U_t^r} $$
follow, and preserve positivity at every finite round.

2. Equilibrium characterization

Verified.

The compact feasible set contains a strictly positive-utility allocation. Upper semicontinuity and boundedness above therefore yield a maximizing allocation with positive utilities.

Strict concavity in the total utility vector establishes uniqueness of that vector, without incorrectly asserting uniqueness of the allocation.

The directional-derivative argument yields precisely the itemwise maximizing conditions. The resulting allocation spends each budget and is individually optimal. Conversely, the equilibrium inequalities and the logarithmic tangent inequality establish objective optimality.

The claimed uniqueness of prices also follows: every item is allocated, and any positive allocation satisfies its tight-edge equality. Consequently, its price equals the maximum weighted valuation determined by the unique total utilities.

Reference splits with zero coordinates are admissible in the subsequent potential argument.

3. Telescoping identity and round bound

Verified, including signs and constants.

The maximum-bid inequalities give
$$ 0<h_r\leq1. $$
The normalized relative-entropy expression for $H_r$ is valid, including zero reference coordinates, and implies $H_r\geq0$.

The displayed telescoping identity is correct:
$$ D_r-D_{r+1}=F^*-F(y^r)+H_r. $$
The signs of both logarithmic terms agree with the update and the reference relation.

Telescoping and concavity establish the objective guarantee for the feasible arithmetic average. The input-length estimate also checks:
$$ D_0\leq\max_{t,k}\log\frac{b_t}{\beta_{tk}^0} \leq2L\log2<2L. $$
Therefore the stated sufficient bound
$$ T=\left\lceil\frac{2L}{\epsilon}\right\rceil $$
is valid for every equilibrium-consistent tie division.

4. Convergence

Verified.

The summable objective gaps tend to zero. Compactness supplies allocation accumulation points; the bounded upper utility coordinates exclude an accumulation point with zero total utility. Continuity then identifies every accumulation point as an equilibrium allocation, yielding convergence of total utilities.

The use of Pinsker’s inequality is properly normalized. From $H_r\to0$, both constituent nonnegative terms vanish, giving convergence of $M^r$ to the reference split. The reference allocation supplies a positive tight bidder for every item, establishing the price lower limits. The fixed total price sum then establishes convergence of every price coordinate.

For splits, the uniform multiplier bound is justified by the positive valuation incidence at every seller. At a joint accumulation point, the two cases of zero and positive seller utility correctly establish
$$ \bar q_{tk}=\lambda_t^*\bar U_{tk}. $$
Using this equilibrium split as a new reference makes its relative-entropy potential nonincreasing. Its subsequential limit is zero, and Pinsker then establishes convergence of the entire split sequence.

No uniqueness of equilibrium splits is assumed.

5. Exact rational computation

Verified in substance.

The cited exact Fisher algorithm applies after the stated rational-to-integral scaling. Its positive-incidence hypotheses hold separately for each seller. The arithmetic operation bound agrees with the cited source; the strongly polynomial algorithm supplies the asserted polynomial bit-complexity consequence. See [Orlin’s algorithm and model assumptions](https://drops.dagstuhl.de/storage/16dagstuhl-seminar-proceedings/dsp-vol10171/DagSemProc.10171.2/DagSemProc.10171.2.pdf).

The tight-edge component argument correctly expresses multipliers and prices through valuation-dependent rational ratios and a budget-dependent component scale. Positive budgets and prices ensure that all buyers and goods belong to the graph and that the component denominator is positive.

The rational-operation count supports a recurrence linear in the current encoding length, with a polynomial parameter-dependent coefficient. Thus the bounds
$$ S_r\leq P^{r+1}, \qquad P^{O(r+1)} $$
per round, and $P^{O(T)}$ overall, are justified for a computably chosen rational allocation.

Minor issue: “singly exponential” needs its parameter specified. The bound is exponential in $T\log P$. Since $1/\epsilon$ can be exponential in its binary encoding length, this is not necessarily singly exponential in $L$ alone.

Minimum clarification: state the exponential parameter explicitly.

6. Explicit exact-average output lower bound

Verified, including the critical computations.

Seller allocations and recurrence

The singleton payment equations uniquely determine the displayed prices and allocations. The odds-ratio update preserves the one-parameter form. The polynomial expansion and rational recurrence are correct.

Cancellation identities

I independently expanded all four identities; each is exact. I also checked the first iterate:
$$ z_1=\frac{366122}{707597}. $$
The identities imply the stated greatest-common-divisor bounds. Those bounds correctly yield
$$ \frac{b_{r+1}}{96}\leq d_r\leq36b_{r+1}. $$

Growth and averaging

The coefficient-ratio bounds correctly place every positive iterate after the initial round in the stated interval. The cubic denominator-growth inequality follows.

The averaging argument permits cancellation: the reduced denominator of the last summand divides the product of the reduced denominators of the full sum and preceding sum. The resulting logarithmic estimate correctly retains exponential growth.

Dividing the reduced sum by the number of rounds cannot decrease its denominator. Thus the explicit exact average requires $\Omega(3^T)$ bits asymptotically.

Accuracy requirement

The derivative formula for $R$ is correct and strictly positive for positive arguments. The monotonicity argument keeps all iterates above $z_*$.

The displayed utility deviation has the claimed positive sign for type $1$. Its average deviation is consequently bounded below by $d/T$.

The feasible total-utility sum, equilibrium utility vector, Hessian bound, and vanishing linear term are all correct. They establish
$$ G^*-G(\hat x)\geq\frac{d^2}{512T^2}. $$
Combining this with denominator growth gives the asserted output-size obstruction.

Uniform budget scaling preserves allocations. The padded family has input length $\Theta(n)$ and inverse-polynomial accuracy, so its explicit output-length lower bound follows.

This proves a lower bound for explicit binary rational exact averages. It establishes neither NP-hardness nor a lower bound for succinct representations.

7. Rounded numerical implementation

Verified as a separate result.

The multiplier-stability argument correctly handles fractional ties. Items allocated to maximum-ratio buyers in the first equilibrium have the asserted scaled second prices, and all second-equilibrium winners of those items belong to that buyer set. The spending comparison therefore proves the multiplier-ratio bound.

The seller-utility and update stability factors follow.

The positivity lower bound, grid-error bound, and logarithmic-error recurrence are consistent. The chosen precision yields the stated error bounds through the final round. Coordinatewise multiplicative utility comparisons survive averaging, so the objective comparison is valid.

The resulting allocation is exactly feasible, and its precision and computation costs are polynomial in the requested parameters.

However, it averages allocations from rounded budgets. As the prover acknowledges, it is not generally the average of the prescribed exact trajectory.

8. Issues and minimum feedback

• Major — incomplete requested complexity classification.

The explicit-output obstruction rules out polynomial-time explicit exact-average computation, but no NP-hardness result is established. The polynomial rounded substitute does not answer the prescribed-average requirement. This is an acknowledged scope limitation, not an error in the proved lower bound.

Minimum additional requirement: a classification argument for the remaining requested complexity claim, with its output representation stated. The existing results must remain separated by their output requirements.

• Minor — exponential-bound terminology.

Specify that the exact-computation bound is exponential in $T\log P$, rather than leaving “singly exponential” unqualified.

• Minor — undefined external context.

The references to NOTES have no supplied referent.

Minimum clarification: remove those comparisons or identify the referenced document. The proofs themselves do not depend on it.

The direction is promising. The convergence, rate, output-size obstruction, and rounded approximation are genuine progress; the remaining limitation concerns the requested classification.

⟨structured verdict parsed — rendered above⟩