Answer: Polynomial-time solvable in \(m,\tau,L\), with exact market clearing and binary-rational output.
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven any positive starting point $\bbb^\circ$, the algorithm PR-QLIN converges to the set of market equilibrium spending vectors of the quasi-linear Fisher market.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) goods, a finite type set \(T\) with \(|T|=\tau\), binary-rational masses \(\mu_t>0\) summing to \(1\), positive rational valuations \(v_{tj}\), positive rational per-unit-mass budgets \(\kappa_t\), and an accuracy parameter \(\varepsilon>0\), compute prices \(p_j>0\) and per-unit-mass spending vectors \(z_t\) such that \(p_j=\sum_{t\in T}\mu_t z_{tj}\), \(\sum_j z_{tj}\leq\kappa_t\), and each type’s spending utility is within \(\varepsilon\) of its maximum at prices \(p\).
A society is given by its support: a list \(T\) of the \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\), with \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) divisible goods, each with supply one, positive binary-rational valuations \(v_{tj}\), positive binary-rational budgets per unit mass \(\kappa_t\), and a positive binary-rational accuracy parameter \(\varepsilon\). Let \(L\) be the total input bit length, including \(\varepsilon\).
At fixed prices \(p\in\mathbb{R}_{>0}^m\), a type's feasible spending vectors form \(Z_t=\{a\in\mathbb{R}_{\geq0}^m:\sum_j a_j\leq\kappa_t\}\), and its utility per unit mass is \(u_t(a\mid p)=\sum_j v_{tj}a_j/p_j-\sum_j a_j\). Unspent budget is allowed; ties may be resolved by any feasible split.
The computational problem is to find binary-rational prices \(p_j>0\) and spending vectors \(z_t\in Z_t\) satisfying \(p_j=\sum_t\mu_t z_{tj}\) for every good and \(u_t(z_t\mid p)\geq\max_{a\in Z_t}u_t(a\mid p)-\varepsilon\) for every type.
Is this computational problem solvable in time polynomial in \(m,\tau,L\), or is it \(\mathsf{NP}\)-hard?
For finite-agent quasi-linear Fisher markets, proportional response converges from every positive feasible starting portfolio to the equilibrium spending set ([Cheung, Leonardos, and Piliouras](https://www.ijcai.org/proceedings/2021/0016.pdf)); this convergence statement supplies no polynomial bit-complexity bound.
A strongly polynomial equilibrium algorithm is also claimed for finite quasi-linear markets formulated as Arctic Auctions ([Garg, Taherijam, and Vazirani](https://arxiv.org/html/2604.24756v1)). No result explicitly addressing the precise support-input mass problem above was located.
The problem is solvable in time polynomial in \(m,\tau,L\). This includes the required exact market-clearing equalities and binary-rational output.
The proof uses convex optimization with controlled precision. It does not require a polynomial convergence rate for proportional response or the recent strongly polynomial algorithm.
Define the aggregate budget and spending of type \(t\) by
\(B_t=\mu_t\kappa_t,\qquad b_{tj}=\mu_t z_{tj}.\)
Let
\(K=\left\{b\in\mathbb R_{\geq0}^{\tau\times m}:\sum_j b_{tj}\leq B_t\text{ for every }t\right\},\qquad p_j(b)=\sum_t b_{tj}.\)
At positive prices, define aggregate utility by
\(U_t(b_t\mid p)=\sum_j\left(\frac{v_{tj}}{p_j}-1\right)b_{tj}.\)
The substitution \(b_t=\mu_t z_t\) is a bijection between the corresponding spending simplices, and
\(U_t(\mu_t z_t\mid p)=\mu_t u_t(z_t\mid p).\)
Consequently, aggregate utility regret at most \(\mu_t\varepsilon\) implies the required per-unit-mass regret at most \(\varepsilon\).
This transformation creates exactly \(\tau\) buyers. It requires no replication of agents and increases the encoding length only polynomially.
Throughout, logarithms are natural. Put
\(F(b)=\sum_j\bigl(p_j(b)\log p_j(b)-p_j(b)\bigr)-\sum_{t,j}b_{tj}\log v_{tj},\)
using the continuous convention \(0\log0=0\).
This is the quasi-linear Shmyrev objective; it also appears in [Gao and Kroer, Section 4](https://proceedings.neurips.cc/paper_files/paper/2020/file/f75526659f31040afeb61cb7133e4e6d-Paper.pdf). The properties needed here are proved below.
Since \(x\mapsto x\log x-x\) is convex and continuous on the nonnegative real line, \(F\) is convex and continuous on \(K\). The set \(K\) is nonempty and compact, so a minimizer \(b^*\) exists.
Suppose \(p_j(b^*)=0\). Choose any type \(t\).
If its budget constraint has positive slack, add an amount \(\eta>0\) to \(b^*_{tj}\). If its constraint is tight, then \(B_t>0\) guarantees some \(b^*_{tk}>0\); transfer \(\eta\) from that coordinate to \(b^*_{tj}\).
For sufficiently small \(\eta\), either modification is feasible. The newly positive column contributes \(\eta\log\eta+O(\eta)\) to the objective change. Every other changed term contributes \(O(\eta)\), because the column from which money is transferred has positive price. Thus the total change is negative for sufficiently small \(\eta\), contradicting minimality.
Therefore \(p_j^*=p_j(b^*)>0\) for every good.
At a point with positive prices,
\(\displaystyle \frac{\partial F}{\partial b_{tj}}=\log\frac{p_j(b)}{v_{tj}}.\)
Optimality of \(b^*\) implies
\(\langle\nabla F(b^*),a-b^*\rangle\geq0\qquad\text{for every }a\in K.\)
Because \(K\) is a product of row simplices, each \(b_t^*\) maximizes
\(\displaystyle \sum_j a_j\log\frac{v_{tj}}{p_j^*}\)
over nonnegative \(a\) with \(\sum_j a_j\leq B_t\).
For a linear objective on this simplex, an optimum spends only on coordinates with maximal positive coefficient; it spends the entire budget if that maximum is positive. If the maximum is zero, it may retain money or split spending among zero-coefficient coordinates.
The coefficients \(\log(v_{tj}/p_j^*)\) and \(v_{tj}/p_j^*-1\) have identical signs, orderings, and ties. They therefore have identical maximizing spending sets. Hence every \(b_t^*\) maximizes aggregate utility at \(p^*\). By definition,
\(p_j^*=\sum_t b_{tj}^*.\)
Thus \((b^*,p^*)\) is an exact equilibrium.
Define
\(B_{\min}=\min_t B_t,\qquad S=\sum_t B_t,\qquad v_{\min}=\min_{t,j}v_{tj},\qquad V=\max_{t,j}v_{tj},\)
and
\(A=\max\left\{1,\frac{mV}{B_{\min}}\right\},\qquad q=\frac{v_{\min}}{2A}.\)
All these quantities are positive rationals of polynomial encoding length.
For a minimizing equilibrium, let
\(\alpha_t=\max\left\{1,\max_j\frac{v_{tj}}{p_j^*}\right\}.\)
If \(\alpha_t>1\), buyer optimality implies that type \(t\) spends its entire budget and spends only on goods satisfying \(v_{tj}/p_j^*=\alpha_t\). Set \(x_{tj}=b_{tj}^*/p_j^*\). Market clearing gives \(\sum_t x_{tj}=1\), so \(x_{tj}\leq1\). Consequently,
\(\displaystyle \alpha_t B_t=\sum_j v_{tj}x_{tj}\leq\sum_j v_{tj}\leq mV.\)
If \(\alpha_t=1\), its bound is immediate. Thus \(\alpha_t\leq A\) for every type.
Every good has some positive spender. For such a spender, optimality gives \(v_{tj}/p_j^*=\alpha_t\), including the case \(\alpha_t=1\). Therefore
\(\displaystyle p_j^*=\frac{v_{tj}}{\alpha_t}\geq\frac{v_{\min}}A=2q.\)
We also have \(p_j^*\leq S\).
Now restrict optimization to the rational polytope
\(P=\{b\in K:p_j(b)\geq q\text{ for every }j\}.\)
It contains every minimizer of \(F\) over \(K\). In particular,
\(\min_{b\in P}F(b)=\min_{b\in K}F(b)=F(b^*).\)
We use the standard finite-precision ellipsoid theorem in the following form:
A convex differentiable function can be minimized to additive accuracy \(\delta>0\) over an explicitly given bounded rational polytope in polynomial bit time, provided that the polytope has a known interior ball, a known outer ball, a Lipschitz bound, and polynomial-time rational approximations to function values and gradients. The dependence on the accuracy and geometric bounds is logarithmic. The returned point is rational and satisfies the polytope’s linear constraints exactly.
The rational implementation and its complexity are standard ellipsoid results; see [Grötschel, Lovász, and Schrijver, Chapters 3–4](https://link.springer.com/book/10.1007/978-3-642-78240-4).
Here are the required hypothesis checks.
First, \(q\leq B_{\min}/(2m)\). Indeed, if \(A=mV/B_{\min}\), this follows from \(v_{\min}\leq V\); if \(A=1\), then \(B_{\min}\geq mV\geq mv_{\min}\).
Consider the rational point
\(b^0_{tj}=\frac{3B_t}{4m}.\)
Its row budget slack is \(B_t/4\), and its column sums are \(3S/(4m)\). Since \(q\leq S/(2m)\), its column slack is at least \(S/(4m)\).
The Euclidean ball centered at \(b^0\) with radius
\(r=\frac{B_{\min}}{8m\tau}\)
lies inside \(P\). To check this, each coordinate changes by at most \(r\), each row sum by at most \(mr\), and each column sum by at most \(\tau r\). These bounds are smaller than the respective nonnegativity, row, and column slacks.
For every \(b\in P\),
\(\|b\|_2\leq\sum_{t,j}b_{tj}\leq S.\)
Thus \(R=1+S\) is a valid outer radius. Both \(r\) and \(R\), and hence the logarithm of \(R/r\), have polynomial encoding bounds.
On \(P\), every price lies in \([q,S]\). Hence
\(\left|\frac{\partial F}{\partial b_{tj}}\right|=\left|\log\frac{p_j(b)}{v_{tj}}\right|\)
has a polynomially bounded magnitude. An explicit rational bound on the gradient norm, and therefore on the Lipschitz constant, follows by bounding the ratios between \(q/V\) and \(S/v_{\min}\).
Function values and gradients can be approximated to any requested binary precision in polynomial time. For completeness, a positive rational \(x\) can be written \(x=2^k y\), with \(1\leq y<2\), and then evaluated using
\(\displaystyle \log x=k\log2+2\sum_{\ell=0}^{\infty}\frac{w^{2\ell+1}}{2\ell+1},\qquad w=\frac{y-1}{y+1}.\)
Here \(0\leq w<1/3\), so the series has a geometrically decreasing tail. The same series computes \(\log2\). Polynomially many terms suffice for polynomially many accuracy bits, and the rational arithmetic has polynomial bit complexity.
Approximate gradients suffice: if \(F(x)>F^*+\delta/2\) and \(F(y)\leq F^*+\delta/4\), convexity gives
\(\langle\nabla F(x),y-x\rangle<-\delta/4.\)
A gradient approximation with Euclidean error at most \(\delta/(16R)\) changes this inner product by at most \(\delta/8\). Its central cut therefore retains that lower sublevel set.
That sublevel set has a known interior-ball bound. If \(M\geq1\) is a Lipschitz bound and \(x^*\) is a minimizer in \(P\), the ball obtained by mixing \(x^*\) with the ball around \(b^0\), with mixing weight
\(\theta=\min\{1,\delta/(8MR)\},\)
has radius \(\theta r\), lies in \(P\), and has objective value at most \(F^*+\delta/4\). This follows from convexity and the bound \(2MR\) on objective variation across \(P\).
Thus finite-precision cuts and ellipsoid volume reduction apply with polynomially many accuracy bits. We can obtain, in polynomial time, a rational \(b\in P\) satisfying
\(F(b)-F(b^*)\leq\delta.\)
The remaining task is to choose \(\delta\) so this objective guarantee implies the required utility guarantees.
For \(b\in P\), define its first-order gap over the original spending set \(K\) by
\(g(b)=\max_{a\in K}\langle\nabla F(b),b-a\rangle.\)
Let \(a\in K\) attain this maximum, and put \(b_s=(1-s)b+sa\). For \(0\leq s\leq1/2\),
\(p_j(b_s)\geq(1-s)p_j(b)\geq q/2.\)
Differentiating along this segment gives
\(\displaystyle \frac{d^2}{ds^2}F(b_s)=\sum_j\frac{(p_j(a)-p_j(b))^2}{p_j(b_s)}.\)
Both nonnegative price vectors have total sum at most \(S\), so their difference has sum of absolute coordinates at most \(2S\). Therefore
\(\displaystyle \frac{d^2}{ds^2}F(b_s)\leq\frac{8S^2}{q}.\)
Set \(C=4S^2/q\). Taylor’s inequality yields
\(F(b_s)\leq F(b)-s g(b)+Cs^2.\)
Since \(b_s\in K\), its objective is at least \(F(b^*)\). Hence, whenever \(F(b)-F(b^*)\leq\delta\),
\(\displaystyle g(b)\leq\frac{\delta}{s}+Cs\qquad(0<s\leq1/2).\)
Write
\(c_{tj}=\log(v_{tj}/p_j(b)),\qquad c_t=\max\{0,\max_j c_{tj}\},\)
and define
\(h_t=B_t c_t-\sum_j b_{tj}c_{tj}.\)
The rowwise linear maximization defining \(g\) gives
\(g(b)=\sum_t h_t,\qquad h_t\geq0.\)
Let \(s_t=\sum_j b_{tj}\), \(\alpha_t=e^{c_t}\), and
\(H=\max\{1,V/q\}.\)
The aggregate best-response utility is \(B_t(\alpha_t-1)\). Its regret at \(b_t\) equals
\(\displaystyle \mathcal R_t=(B_t-s_t)(\alpha_t-1)+\sum_j b_{tj}(\alpha_t-e^{c_{tj}}).\)
Because \(c_t\geq0\), \(c_{tj}\leq c_t\), and \(e^{c_t}\leq H\), integration of the exponential derivative gives
\(\alpha_t-1\leq Hc_t,\qquad \alpha_t-e^{c_{tj}}\leq H(c_t-c_{tj}).\)
Consequently,
\(\mathcal R_t\leq Hh_t\leq Hg(b).\)
This controls every type separately.
Put
\(e=\min\{\varepsilon,1\},\qquad \mu_{\min}=\min_t\mu_t,\qquad \gamma=\frac{\mu_{\min}e}{2H},\)
and choose
\(s_0=\min\left\{\frac12,\frac{\gamma}{2C}\right\},\qquad \delta=\frac{s_0\gamma}{2}.\)
All these are positive rationals of polynomial encoding length.
Apply Section 4 to obtain rational \(b\in P\) with objective error at most \(\delta\). Section 5 gives
\(\displaystyle g(b)\leq\frac{\delta}{s_0}+Cs_0\leq\gamma.\)
Thus every aggregate regret satisfies
\(\mathcal R_t\leq H\gamma=\mu_{\min}e/2\leq\mu_t e/2.\)
Define
\(z_{tj}=b_{tj}/\mu_t,\qquad p_j=\sum_t\mu_t z_{tj}.\)
These vectors are feasible, satisfy \(p_j\geq q\), and have per-unit-mass regret at most \(e/2\).
We now round them while preserving exact clearing. This step even ensures dyadic output if “binary-rational” is interpreted as a finite binary expansion.
Let \(D\) be a positive integer such that \(D\mu_t\) is integral for every type. The product of the input mass denominators is one such choice, and its bit length is polynomial.
Define
\(K_0=2V\left(\frac{\kappa_{\max}}{q^2}+\frac{m}{q}\right),\qquad \kappa_{\max}=\max_t\kappa_t.\)
Choose an integer \(N\) such that the dyadic grid spacing \(h=D2^{-N}\) satisfies
\(\displaystyle h\leq\min\left\{\frac q2,\frac{e}{2K_0}\right\}.\)
Finally output
\(\widehat z_{tj}=h\left\lfloor z_{tj}/h\right\rfloor,\qquad \widehat p_j=\sum_t\mu_t\widehat z_{tj}.\)
Rounding down preserves nonnegativity and every budget constraint. Since \(\sum_t\mu_t=1\),
\(0\leq p_j-\widehat p_j\leq h,\qquad \widehat p_j\geq q-h\geq q/2>0.\)
Market clearing holds exactly by the definition of \(\widehat p\).
Both outputs are dyadic: \(\widehat z_{tj}\) is an integer multiple of \(D2^{-N}\), and \(\mu_t\widehat z_{tj}\) is an integer multiple of \(2^{-N}\).
For any feasible spending vector \(a\) of type \(t\),
\(\displaystyle u_t(a\mid\widehat p)-u_t(a\mid p)=\sum_j v_{tj}a_j\frac{p_j-\widehat p_j}{p_j\widehat p_j}\leq\frac{2\kappa_{\max}Vh}{q^2}.\)
Therefore best-response utility increases by at most this amount.
Lower prices weakly increase the utility of the old portfolio \(z_t\). Removing less than \(h\) from each coordinate at prices \(\widehat p\) decreases utility by at most \(2mVh/q\). Hence
\(\displaystyle \operatorname{Regret}_t(\widehat z_t,\widehat p)\leq\frac e2+\frac{2\kappa_{\max}Vh}{q^2}+\frac{2mVh}{q}=\frac e2+K_0h\leq e\leq\varepsilon.\)
Thus the final output satisfies every requirement.
There are \(m\tau\) optimization variables and polynomially many explicit rational linear constraints.
Every positive input number has logarithmic magnitude bounded by its encoding length. Products, sums, divisions, and extrema defining \(B_{\min},S,q,H,C,\gamma,\delta,K_0\) therefore have polynomial encoding length. In particular, the required logarithmic precision in \(\delta\) and the grid exponent \(N\) are polynomially bounded.
The convex optimization uses polynomially many bit operations, and the final divisions and rounding do likewise. Small support masses affect the requested precision through the logarithm of \(1/\mu_{\min}\), which is already controlled by \(L\).
The construction is therefore a polynomial-time algorithm for the stated support-input problem.
⟨structured verdict parsed — rendered above⟩
Assessment: proved with minor gaps. The argument establishes polynomial-time solvability of the stated support-input problem in substance. The mass reduction, equilibrium characterization, price bounds, conversion from objective error to individual regret, and final rounding are correct. The only issue identified is an omitted routine specification of the Lipschitz bound used by the optimization procedure.
No central statement is false, and no additional mathematical lemma is needed.
Correct.
Because every mass is positive, the substitution \(b_{tj}=\mu_t z_{tj}\) is invertible. It maps the original spending constraint exactly to \(\sum_j b_{tj}\leq B_t\), where \(B_t=\mu_t\kappa_t\).
The utility identity \(U_t(\mu_t z_t\mid p)=\mu_t u_t(z_t\mid p)\) also applies to the corresponding best-response maxima. Thus aggregate regret divided by \(\mu_t\) is exactly per-unit-mass regret.
The transformation introduces one buyer per supported type. Multiplying the input rationals increases their encoding lengths only polynomially. There is no hidden dependence on the number of possible types or any replication proportional to mass denominators.
Correct.
The objective is continuous and convex on the compact, nonempty set \(K\), so a minimizer exists.
The perturbation argument excluding a zero-price column is valid:
Since \(\eta\log\eta\) dominates the remaining linear-order terms negatively as \(\eta\) tends to zero, the contradiction follows.
This argument covers \(m=1\) and \(\tau=1\). In particular, when the sole column has zero spending, no row with positive budget can be tight.
Correct.
At positive column sums, the derivative is indeed
\(\frac{\partial F}{\partial b_{tj}}=\log(p_j/v_{tj})\).
The first-order optimality inequality is applicable even when some individual spending coordinates vanish: the objective remains differentiable in a neighborhood of the point where all column sums are positive.
The product structure of \(K\) permits independent rowwise linear optimization. The two coefficient families, \(\log(v_{tj}/p_j)\) and \(v_{tj}/p_j-1\), have the same signs, ordering, and ties. Consequently they produce the same maximizing spending sets, including:
Exact market clearing follows from the definition of the column sums.
The objective also matches the quasi-linear Shmyrev program in [Gao and Kroer, Section 4](https://proceedings.neurips.cc/paper_files/paper/2020/file/f75526659f31040afeb61cb7133e4e6d-Paper.pdf), after eliminating leftover-budget variables. The proof supplies its own equilibrium characterization, so it does not depend on importing that paper’s equilibrium theorem.
Correct.
When \(\alpha_t>1\), buyer optimality ensures full expenditure and equality \(v_{tj}/p_j^*=\alpha_t\) on every positively purchased good. Hence the displayed identity
\(\alpha_t B_t=\sum_j v_{tj}x_{tj}\)
is justified.
Market clearing gives \(\sum_t x_{tj}=1\), and nonnegativity therefore gives \(x_{tj}\leq1\). The bound \(\alpha_t B_t\leq mV\), and consequently \(\alpha_t\leq A\), follows with the stated constants.
Every good has a positive spender because its price is positive. Such a spender must purchase a maximizing good with nonnegative utility coefficient. This also justifies the claimed equality when \(\alpha_t=1\). Therefore \(p_j^*\geq v_{\min}/A=2q\).
The upper bound \(p_j^*\leq S\) follows from total feasible spending. Thus every minimizer lies in \(P\), and restricting the optimization to \(P\) preserves the minimum.
Correct.
Both branches in the proof of \(q\leq B_{\min}/(2m)\) are valid.
At \(b^0\), the coordinate, row-budget, and column-price slacks have the stated lower bounds. For the proposed radius \(r\), the respective perturbation bounds \(r\), \(mr\), and \(\tau r\) fit within those slacks. Thus the claimed Euclidean ball lies in \(P\).
The outer-ball estimate is also valid: nonnegativity gives \(\|b\|_2\leq\sum_{t,j}b_{tj}\leq S\). The quantities controlling the geometry have polynomial encoding length.
Correct.
The logarithm series has geometric convergence after normalization. Its use to compute \(\log 2\) involves the endpoint \(w=1/3\), which still gives geometric convergence; the strict inequality for normalized \(y<2\) causes no failure.
The inner-product error bound checks out. Since feasible points are at distance at most \(2R\), gradient error at most \(\delta/(16R)\) causes inner-product error at most \(\delta/8\). Therefore the proposed approximate central cut retains the stated lower sublevel set.
The mixed-ball argument is also valid. Its radius is \(\theta r\), and the bound \(2MR\theta\leq\delta/4\) holds in both branches defining \(\theta\). The ball’s center need not be known for the ellipsoid volume argument; its guaranteed radius is what matters.
The stated ellipsoid theorem requires rational, exactly feasible output. The proof’s explicit rational constraints and exact constraint checks support that formulation; mere approximate feasibility would not suffice for the subsequent construction.
Where: Section 4, “Objective and oracle bounds.”
What: The proof establishes polynomial bounds on all gradient coordinates, but does not give the explicit rational Lipschitz bound subsequently denoted by \(M\). It says that such a bound “follows” from the ratio bounds.
This is a routine omitted calculation. The necessary interval and gradient formula are already present, so supplying the bound requires no new mathematical argument.
Minimum clarification: State an explicit rational \(M\geq1\), specify that it bounds the Euclidean gradient norm on \(P\), and record its encoding-length bound. Use that same \(M\) in the optimization parameters.
Correct.
The maximum defining \(g(b)\) is attained because \(K\) is compact. Along the chosen segment, prices remain at least \(q/2\) for \(0\leq s\leq1/2\), so the second derivative is well defined.
The two price vectors each have total spending at most \(S\), giving their difference an absolute-coordinate sum at most \(2S\). This verifies the second-derivative bound \(8S^2/q\).
Taylor’s bound therefore has quadratic coefficient \(C=4S^2/q\), exactly as stated.
The comparison with \(F(b^*)\) uses minimization over \(K\). It remains valid even if the segment leaves \(P\), because the segment stays in \(K\). Thus the displayed bound on \(g(b)\) is justified.
Correct.
Rowwise maximization gives \(g(b)=\sum_t h_t\), with each \(h_t\geq0\).
The best-response utility \(B_t(\alpha_t-1)\) includes the zero-spending option because \(\alpha_t\geq1\). Expanding the difference from achieved utility yields precisely the stated regret decomposition.
On each integration interval, the exponential derivative is bounded by \(H\). Both inequalities relating exponential differences to coefficient differences are therefore valid, even for very negative individual coefficients.
All factors multiplying those inequalities are nonnegative. Consequently \(\mathcal R_t\leq Hh_t\leq Hg(b)\) is correct and controls each type individually.
Correct.
Both branches defining \(s_0\) ensure \(Cs_0\leq\gamma/2\). Since \(\delta/s_0=\gamma/2\), the first-order gap is at most \(\gamma\).
The aggregate regret bound therefore gives per-unit-mass regret at most \(e/2\). The use of \(\mu_{\min}\) correctly accounts for every supported type.
The rounding argument verifies all required output properties:
The utility bounds also have the correct constants. Price changes increase best-response utility by at most \(2\kappa_{\max}Vh/q^2\). Removing spending decreases achieved utility by at most \(2mVh/q\). Negative spending coefficients do not invalidate this upper bound on utility loss.
Combining these estimates gives final regret at most \(e/2+K_0h\leq e\leq\varepsilon\).
Correct, subject to the minor specification above.
All derived rational quantities have polynomial encoding length. Their numerical magnitudes may be exponentially large or small; the algorithm uses their logarithmic sizes.
The denominator product \(D\) has polynomial bit length, and a sufficiently large grid exponent \(N\) also has polynomial size. The precision dependence on small masses is through their logarithmic inverse magnitude, already controlled by the input encoding.
The argument addresses exactly the requested support-input problem, including individual regret, positive binary-rational prices, feasible binary-rational spending, and exact market clearing.
⟨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.