Answer: Polynomial-time solvable under the standard precision-parameter encoding.
Proposition 2 — class: algorithmic
Given \(n\) goods, a finite support of \(\tau\) CES buyer types \(\theta=(b_\theta,\rho_\theta,(a_{\theta j})_{j=1}^n)\), and rational masses \(\mu_\theta^r\) summing to \(1\) and per-capita supplies \(w_j^r>0\) for rounds \(r=0,\ldots,T\), compute an \(\epsilon\)-approximation to the final price vector. Define aggregate demand by \(D_j^r(p)=\sum_\theta \mu_\theta^r b_\theta (a_{\theta j})^{1-c_\theta}p_j^{c_\theta-1}/\sum_k(a_{\theta k})^{1-c_\theta}p_k^{c_\theta}\), where \(c_\theta=\rho_\theta/(\rho_\theta-1)\), and update \(p_j^{r+1}=p_j^r[1+\lambda\min\{(D_j^r(p^r)-w_j^r)/w_j^r,1\}]\). For fixed \(\rho_\theta=1/2\), rational type data and an assumed price bound \(P\) and contraction parameter \(\delta>0\), return a certified bound on \(\Phi^T=\sum_jp_j^T|D_j^T(p^T)-w_j^T|\), in particular whether \(\Phi^T\le(1-\delta)^T\Phi^0+\sum_{r=1}^T(1-\delta)^{T-r}[\sum_\theta b_\theta|\mu_\theta^r-\mu_\theta^{r-1}|+P\|w^r-w^{r-1}\|_1]\) can be certified with running time polynomial in \(n,\tau,T\), the input bit length, and \(\log(1/\epsilon)\).
There are \(m\ge1\) divisible goods and rounds \(r=0,\ldots,T\), supplied explicitly. Each round's society is given by its support: types with positive mass, each mass a binary rational; \(\tau\) is the size of the union of these supports, not the number of possible types. Missing types have mass zero, and \(\sum_\theta\mu_\theta^r=1\).
Types have fixed binary-rational budgets \(b_\theta>0\), coefficients \(a_{\theta j}\ge0\) with \(\sum_j a_{\theta j}>0\), and CES exponent \(\rho_\theta=1/2\). Supplies \(w_j^r>0\), initial prices \(p_j^0>0\), and parameters \(0<\lambda<1\), \(P>0\), \(0<\delta\le1\), \(0<\epsilon<1\) are binary rationals.
Define \(D_j^r(p)=\sum_\theta\mu_\theta^r b_\theta a_{\theta j}^2p_j^{-2}/\bigl(\sum_{k=1}^m a_{\theta k}^2p_k^{-1}\bigr)\) and \(\Phi_r(p)=\sum_{j=1}^m p_j|D_j^r(p)-w_j^r|\).
For \(r=0,\ldots,T-1\), update \(p_j^{r+1}=p_j^r[1+\lambda\min\{(D_j^r(p^r)-w_j^r)/w_j^r,1\}]\); the market changes after this update.
Inputs promise \(p_j^r\le P\) throughout and \(\Phi_r(p^{r+1})\le(1-\delta)\Phi_r(p^r)\) for every update; these promises need not be checked.
Set \(U=(1-\delta)^T\Phi_0(p^0)+\sum_{r=1}^T(1-\delta)^{T-r}[\sum_\theta b_\theta|\mu_\theta^r-\mu_\theta^{r-1}|+P\|w^r-w^{r-1}\|_1]\).
The computational problem is to approximate \(p^T\) with absolute \(\ell_\infty\) error at most \(\epsilon\), compute rational enclosing intervals of width at most \(\epsilon\) for \(\Phi_T(p^T)\) and \(U\), and certify \(\Phi_T(p^T)\le U\) under the promises. Let \(L\) be the total bit length of the market data and parameters other than \(\epsilon\).
Is this promised computation solvable in time polynomial in \(m,\tau,T,L,\log(1/\epsilon)\), or is it NP-hard?
For finitely many buyers, dynamic supply admits a misspending tracking bound with geometrically weighted recent perturbations and a geometric tail, conditional on bounded prices and static contraction; budget perturbations admit analogous bounds. The general tracking inequality includes perturbations through the final round. [Verified source](https://www.ifaamas.org/Proceedings/aamas2019/pdfs/p1225.pdf)
No result settling this precise finite-support approximation and certification problem in the bit model was located.
The promised computation is polynomial-time solvable. The key is to round prices after every update, using polynomially many bits of precision, rather than propagate exact rational prices through all rounds.
I use the usual accuracy-parameter interpretation: an accuracy request can be replaced by \(2^{-k}\), where \(k=\lceil\log_2(1/\epsilon)\rceil\). Binary fractional notation permits finding this tolerance from the first nonzero bit. If \(\epsilon\) is instead encoded as an unrestricted numerator–denominator pair, its input-reading cost must also be counted; the algorithm below is polynomial in that encoding length as well. This encoding qualification does not affect the substantive computation.
Index the union of the supplied supports by \(\theta=1,\ldots,\tau\), inserting zero masses where necessary. Define, for positive prices \(p\),
\[ c_{\theta j}=a_{\theta j}^2,\qquad S_\theta(p)=\sum_k\frac{c_{\theta k}}{p_k},\qquad s_{\theta j}(p)=\frac{c_{\theta j}/p_j}{S_\theta(p)}. \]
Here and below, these formulas use only rational operations. Each \(S_\theta(p)\) is positive because at least one coefficient of type \(\theta\) is positive. Moreover,
\[ s_{\theta j}(p)\ge0,\qquad \sum_j s_{\theta j}(p)=1. \]
Define aggregate expenditure on good \(j\) by
\[ E_j^r(p)=p_jD_j^r(p) =\sum_\theta\mu_\theta^r b_\theta s_{\theta j}(p). \]
Thus
\[ \Phi_r(p)=\sum_j\left|E_j^r(p)-p_jw_j^r\right|. \]
For consecutive markets at the same price vector, the reverse triangle inequality gives
\[ \left|\Phi_r(p)-\Phi_{r-1}(p)\right| \le \sum_j\left|E_j^r(p)-E_j^{r-1}(p)\right| +\sum_jp_j|w_j^r-w_j^{r-1}|. \]
The first term satisfies
\[ \sum_j\left|E_j^r(p)-E_j^{r-1}(p)\right| \le \sum_\theta b_\theta|\mu_\theta^r-\mu_\theta^{r-1}| \sum_js_{\theta j}(p) = \sum_\theta b_\theta|\mu_\theta^r-\mu_\theta^{r-1}|. \]
Consequently, whenever all prices are at most \(P\),
\[ \Phi_r(p)\le\Phi_{r-1}(p)+\Delta_r, \]
where
\[ \Delta_r= \sum_\theta b_\theta|\mu_\theta^r-\mu_\theta^{r-1}| +P\|w^r-w^{r-1}\|_1. \]
Apply this at \(p=p^r\). The promised contraction for update \(r-1\) yields
\[ \Phi_r(p^r) \le (1-\delta)\Phi_{r-1}(p^{r-1})+\Delta_r. \]
Induction therefore proves
\[ \Phi_T(p^T) \le (1-\delta)^T\Phi_0(p^0) +\sum_{r=1}^T(1-\delta)^{T-r}\Delta_r =U. \]
In particular, the perturbation at round \(T\) has coefficient \(1\). For \(\delta=1\), exponent-zero powers are interpreted as \(1\).
This proves the required certificate directly. It is the contraction-plus-perturbation mechanism studied for dynamic supply and budgets in the [supplied paper](https://www.ifaamas.org/Proceedings/aamas2019/pdfs/p1225.pdf).
For any positive price vector, demand is nonnegative. Hence every update multiplier lies between \(1-\lambda\) and \(1+\lambda\). It follows inductively that
\[ p_j^r\ge p_j^0(1-\lambda)^r. \]
Set
\[ \alpha=\left(\min_jp_j^0\right)(1-\lambda)^T, \qquad \mathcal C=[\alpha,P]^m. \]
The exact trajectory lies in \(\mathcal C\): the lower bound follows from the preceding inequality, and the upper bound is promised.
The rational number \(\alpha\) has bit length \(O((T+1)L)\). Although its numerical value may be exponentially small, its description is polynomially long.
Also define
\[ B=\max_\theta b_\theta, \qquad \underline w=\min_{r,j}w_j^r>0. \]
Normalization of the masses implies, in every round,
\[ \sum_\theta\mu_\theta^r b_\theta\le B. \]
For a single type, write
\[ x_{\theta j}(p)=\frac{b_\theta s_{\theta j}(p)}{p_j}. \]
Differentiating on the positive orthant gives
\[ \frac{\partial s_{\theta j}}{\partial p_k} = \frac{s_{\theta j}}{p_k} \left(s_{\theta k}-\mathbf1_{\{j=k\}}\right), \]
and therefore
\[ \frac{\partial x_{\theta j}}{\partial p_k} = \frac{x_{\theta j}}{p_k} \left(s_{\theta k}-2\mathbf1_{\{j=k\}}\right). \]
On \(\mathcal C\), the absolute row sum is bounded by
\[ \sum_k\left|\frac{\partial x_{\theta j}}{\partial p_k}\right| = x_{\theta j} \left( \frac{2-s_{\theta j}}{p_j} +\sum_{k\ne j}\frac{s_{\theta k}}{p_k} \right) \le\frac{3x_{\theta j}}{\alpha}. \]
Furthermore,
\[ D_j^r(p) =\sum_\theta\mu_\theta^r x_{\theta j}(p) \le\frac{B}{\alpha}. \]
Thus every row of the Jacobian of \(D^r\) has absolute sum at most \(3B/\alpha^2\). Integrating along the line segment between two points of the convex set \(\mathcal C\) proves
\[ \|D^r(p)-D^r(q)\|_\infty \le\frac{3B}{\alpha^2}\|p-q\|_\infty. \]
Let \(F_r\) denote the update map. The scalar function \(z\mapsto\min\{z,1\}\) is \(1\)-Lipschitz, including at its breakpoint. The update multiplier has absolute value at most \(1+\lambda\), so
\[ |F_{r,j}(p)-F_{r,j}(q)| \le (1+\lambda)|p_j-q_j| +\frac{\lambda P}{w_j^r}|D_j^r(p)-D_j^r(q)|. \]
Consequently, a common Lipschitz constant for all update maps on \(\mathcal C\) is
\[ K=2+\frac{3PB}{\underline w\,\alpha^2}\ge2. \]
This bound does not require deciding which side of a cap breakpoint the exact trajectory occupies.
The share derivative also gives
\[ \sum_{j,k} \left| \frac{\partial(b_\theta s_{\theta j})}{\partial p_k} \right| \le \frac{b_\theta}{\alpha} \sum_j s_{\theta j}\sum_k |s_{\theta k}-\mathbf1_{\{j=k\}}|. \]
For fixed \(j\), the inner sum equals \(2(1-s_{\theta j})\). Therefore the displayed expression is at most \(2b_\theta/\alpha\). Aggregating with the nonnegative masses and integrating along a line segment yields
\[ \|E^T(p)-E^T(q)\|_1 \le\frac{2B}{\alpha}\|p-q\|_\infty. \]
Using the reverse triangle inequality in the expression for \(\Phi_T\), we obtain
\[ |\Phi_T(p)-\Phi_T(q)| \le H\|p-q\|_\infty, \qquad H=\frac{2B}{\alpha}+\sum_jw_j^T. \]
All constants introduced so far are rational and have polynomial bit length.
The case \(T=0\) is handled by computing \(p^0\), \(\Phi_0(p^0)\), and \(U=\Phi_0(p^0)\) exactly. Assume henceforth that \(T\ge1\).
Choose a dyadic tolerance \(\epsilon_*=2^{-k}\le\epsilon\), with
\[ k=\lceil\log_2(1/\epsilon)\rceil. \]
Let
\[ M=\max\{1,H\},\qquad c=\lceil\log_2K\rceil,\qquad d=\lceil\log_2M\rceil, \]
and choose
\[ N=k+1+d+Tc,\qquad h=2^{-N}. \]
The integers \(c,d\) can be obtained by exact comparisons of rational numbers with powers of two.
Let \(\Pi\) be coordinatewise projection onto \(\mathcal C\), and let
\[ R_h(z)=h\lfloor z/h\rfloor \]
act coordinatewise. Initialize \(\widetilde p^0=p^0\), and perform
\[ \widetilde p^{r+1} = \Pi\!\left(R_h(F_r(\widetilde p^r))\right). \]
Each update is evaluated exactly at the stored rational prices; only its output is rounded.
Projection is nonexpansive in the infinity norm. Since \(p^{r+1}=F_r(p^r)\) lies in \(\mathcal C\), the errors
\[ e_r=\|\widetilde p^r-p^r\|_\infty \]
satisfy
\[ e_{r+1}\le h+Ke_r,\qquad e_0=0. \]
Hence, because \(K\ge2\),
\[ e_T\le h\sum_{i=0}^{T-1}K^i\le hK^T. \]
Using \(K\le2^c\), define the convenient dyadic bound
\[ \eta=2^{-(k+1+d)}. \]
Then
\[ e_T\le hK^T\le\eta \le\frac{\epsilon_*}{2M} \le\frac{\epsilon}{2M}. \]
Thus the output \(\widetilde p^T\) has the required price accuracy. Moreover,
\[ |\Phi_T(\widetilde p^T)-\Phi_T(p^T)| \le H\eta\le\frac{\epsilon}{2}. \]
Compute exactly
\[ \widehat\Phi=\Phi_T(\widetilde p^T), \qquad R=H\eta, \]
and compute \(U\) exactly from its defining formula. Output the rational intervals
\[ I_\Phi= \left[ \max\{0,\widehat\Phi-R\}, \ \min\{U,\widehat\Phi+R\} \right], \qquad I_U=[U,U]. \]
The error bound proves that \(\Phi_T(p^T)\) belongs to
\([\widehat\Phi-R,\widehat\Phi+R]\). Section 1 proves that it also belongs to \([0,U]\). Therefore \(I_\Phi\) is nonempty and encloses the true value.
Its width is at most \(2R\le\epsilon\), and \(I_U\) has width zero. Its upper endpoint is at most the exactly computed \(U\), furnishing the requested certification under the promises.
This remains valid when \(\Phi_T(p^T)=U\); numerical separation is unnecessary.
For standard binary encodings, every positive input rational lies between \(2^{-L}\) and \(2^L\). In particular,
\[ \alpha\ge2^{-(T+1)L}, \qquad \underline w\ge2^{-L}, \qquad P,B\le2^L. \]
The formulas for \(K\) and \(H\) consequently imply
\[ c=O((T+1)L+1), \qquad d=O((T+1)L+\log(m+1)+1). \]
Therefore
\[ N= O\!\left( (T+1)^2L+\log(m+1)+\log(1/\epsilon) \right). \]
After rounding and projection, each stored price is either a dyadic grid point or one of the rational endpoints \(\alpha,P\). Its bit length is thus polynomially bounded uniformly across all rounds.
At such prices, one exact update has polynomial bit complexity:
For clarity, summing \(n\) rational numbers whose numerators and denominators have at most \(\ell\) bits produces a rational representation with \(O(n\ell+\log n)\) bits using a common denominator. Applying this bound to the explicitly described sums shows that all intermediate representations within one update have polynomial size. Rounding prevents those representations from being carried into the next round.
Finally, \(U\) uses only the initial rational prices, explicit market differences, and powers of \(1-\delta\) with exponents at most \(T\). These powers have polynomial bit length, and the subsequent sums and products also have polynomial bit complexity.
There are \(T\) updates. Thus the entire promised computation runs in time polynomial in \(m,\tau,T,L,\log(1/\epsilon)\), under the precision convention stated above.
⟨structured verdict parsed — rendered above⟩
The mathematical argument is sound. It proves the tracking certificate and gives a simulation whose required precision and arithmetic cost are polynomially bounded. The only qualification is the representation of the accuracy parameter: the claimed dependence on \(\log(1/\epsilon)\) uses the stated accuracy-parameter convention. I treat this as a minor encoding clarification under the task’s evidently intended precision-parameter reading.
The definitions are well-defined for every positive price vector. Each type has at least one positive coefficient, so \(S_\theta(p)>0\). Zero coefficients cause no difficulty, and inserting zero masses for absent types preserves all sums.
The expenditure identity \(E_j^r(p)=p_jD_j^r(p)\) follows directly from the demand formula. Consequently, the expression for \(\Phi_r\) in terms of expenditures is exact.
The reverse triangle inequality correctly bounds the change in misspending at a fixed price vector. The expenditure perturbation bound follows from nonnegative shares and \(\sum_j s_{\theta j}(p)=1\). The supply perturbation bound uses precisely the hypothesis \(p_j\le P\).
Applying this comparison at \(p^r\), followed by the promised contraction for update \(r-1\), gives the displayed recurrence. Its iteration produces exactly the stated \(U\), including the perturbation through round \(T\).
The convention for exponent-zero powers correctly handles \(\delta=1\). The separate treatment of \(T=0\) also handles this case.
Finding: The tracking certificate is proved. No result from the linked paper is needed for this derivation.
Nonnegative demand implies that the update multiplier belongs to \([1-\lambda,1+\lambda]\). Since \(1-\lambda>0\), induction gives the claimed positive lower bound.
For every \(r\le T\), that bound is at least \(\alpha\). Together with the promised upper bound, this places the exact trajectory in \(\mathcal C\). In particular, the promises ensure that this box is nonempty.
The bit-length claim for \(\alpha\) is valid: taking the \(T\)-th power of a rational multiplies its numerator and denominator bit lengths by at most \(T\), up to routine overhead.
Normalization of the masses correctly gives aggregate budget at most \(B\).
Finding: The domain and its size estimates are justified.
Both derivative identities are correct, including when an individual coefficient vanishes.
For the demand derivative, the diagonal contribution has magnitude \(x_{\theta j}(2-s_{\theta j})/p_j\), and the off-diagonal contributions have magnitudes \(x_{\theta j}s_{\theta k}/p_k\). Their sum is bounded by \(3x_{\theta j}/\alpha\), as claimed.
Aggregating with the nonnegative masses and using \(D_j^r(p)\le B/\alpha\) gives the stated Jacobian bound. Integration along a segment is valid because \(\mathcal C\) is convex and lies entirely in the positive orthant.
The update-map estimate correctly uses the Lipschitz property of the cap, the multiplier bound, and \(q_j\le P\). The proposed \(K\) dominates the resulting constant because \(0<\lambda<1\).
For final expenditures, the identity \(\sum_k|s_{\theta k}-\mathbf1_{\{j=k\}}|=2(1-s_{\theta j})\) is correct. It yields the asserted bound after aggregation and integration. The supply term then gives the claimed \(H\).
Finding: Both Lipschitz constants are valid. No differentiability across the cap breakpoint is assumed.
The initialization belongs to \(\mathcal C\), and projection keeps every subsequent stored price there. Thus every application of the Lipschitz estimates is within their stated domain.
Coordinatewise downward rounding changes a coordinate by less than \(h\). Projection is nonexpansive and fixes the exact next price. These facts justify \(e_{r+1}\le h+Ke_r\).
The geometric-sum estimate \(e_T\le hK^T\) is valid for \(K\ge2\). The definitions of \(N\), \(c\), and \(\eta\) then give \(e_T\le\eta\).
Because \(M\ge1\) and \(M\ge H\), the resulting bounds imply both the required price accuracy and misspending error at most \(\epsilon/2\).
Finding: The simulation error analysis is correct, including near cap breakpoints and box boundaries.
The untrimmed misspending interval encloses the exact value by the preceding error bound. Independently, Section 1 places that value in \([0,U]\).
Their intersection is therefore nonempty and has exactly the stated endpoints. Its width cannot exceed \(2H\eta\le\epsilon\). Computing \(U\) exactly gives a valid interval of width zero.
The certificate remains valid at equality \(\Phi_T(p^T)=U\). It relies on the promised contraction and bounded prices, which the task explicitly permits the algorithm to assume.
Finding: The output intervals and conditional certificate meet the mathematical requirements.
The bounds on positive input rationals are valid for standard binary representations. The lower bound on \(1-\lambda\) follows because its positive numerator is at least one and its denominator has at most the input bit length.
The resulting estimates for \(c\), \(d\), and \(N\) are polynomial in the specified parameters.
A stored grid price has polynomial numerator and denominator size; either projection endpoint also has polynomial size. Within one update, the rational expressions consist of explicitly bounded sums, products, and quotients. Their intermediate bit lengths are polynomial. Crucially, these intermediate denominators are discarded when the next stored price is rounded.
The exact computation of \(\Phi_T(\widetilde p^T)\), the interval endpoints, and \(U\) likewise involves polynomially many operations on polynomial-size rationals.
Finding: The arithmetic complexity argument is sufficient; it does not mistakenly assume that the exact trajectory has polynomial bit length.
Minor — accuracy encoding. The initial precision convention is necessary for the final runtime statement. An unrestricted numerator–denominator representation of \(\epsilon\) can have encoding length much larger than \(\log(1/\epsilon)\). The prover acknowledges this, but polynomial dependence on that encoding length is a different bound from the one requested.
Under the task’s intended accuracy-parameter interpretation, this is an encoding clarification rather than a mathematical gap. The minimum clarification is to specify that the accuracy input is supplied as a precision integer, or in a binary representation from which a suitable dyadic tolerance can be obtained in time polynomial in \(\log(1/\epsilon)\). If unrestricted rational encoding is intended instead, the write-up has not established the literal runtime bound excluding its encoding length.
No additional mathematical lemma or repair is needed for the tracking, simulation, or certification arguments.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.