The problem and the result

An instance consists of a finite directed multigraph \(G=(V,E)\) with \(V=\{1,\ldots,n\}\), \(n\ge1\), and at least one outgoing edge at every vertex. The vertex set is partitioned as \[V=V_{\max}\sqcup V_{\min}\sqcup V_{\mathrm{ch}}.\] Each edge \(e\) has an integer reward \(w(e)\). At a vertex of \(V_{\max}\), Max chooses the next edge; at a vertex of \(V_{\min}\), Min chooses it; at a vertex \(i\in V_{\mathrm{ch}}\), the next edge is drawn from a prescribed rational probability distribution \(p_i\) on the outgoing edges. Rewards and the numerators and positive denominators of the probabilities are encoded in binary. The graph and all edge data are listed explicitly. Loops, parallel edges, zero probabilities, and unreduced fractions are permitted.

Both players observe the complete finite history, including traversed edges, and may use arbitrary behavioral strategies with private randomness. Chance draws have the prescribed conditional law at the current vertex. A pure positional strategy chooses one outgoing edge at each vertex of its player, independently of the preceding history. For a play \(\pi=(X_0,e_0,X_1,e_1,\ldots)\) define \[\operatorname{MP}_w(\pi)=\liminf_{T\to\infty}\frac1T\sum_{t=0}^{T-1}w(e_t), \qquad \operatorname{val}(i)=\sup_\sigma\inf_\tau \mathbb E_{i,\sigma,\tau}[\operatorname{MP}_w].\] Here \(\sigma\) and \(\tau\) range over Max’s and Min’s behavioral strategies, respectively. The expectation is taken after the pathwise lower limit. If \(L\) is the complete binary input length, the decision problem is to output the set \[U=\{i\in V:\operatorname{val}(i)\ge0\}.\]

Historical context

Shapley introduced stochastic games with positive stopping probabilities and characterized their values by a contraction operator (Shapley 1953). Gillette considered the undiscounted, long-run average objective (Gillette 1957); Liggett and Lippman supplied the classical stationary-strategy theorem for perfect-information time-average games (Liggett and Lippman 1969). The relation between discounting and long-run optimization is also classical. Blackwell showed in finite dynamic programming that one stationary policy is optimal for every discount factor sufficiently close to one (Blackwell 1962). Rational discounted values provide the corresponding stabilization mechanism for perfect-information stochastic games; see, for example, Gimbert and Zielonka (Gimbert and Zielonka 2010, Theorem 3).

The computational problem connects several familiar classes of games. A simple stochastic game is a finite turn-based reachability game in which chance chooses fairly between two successors. Condon placed its threshold problem in \(\mathrm{NP}\cap\mathrm{coNP}\) (Condon 1992), and Ludwig gave a randomized subexponential algorithm (Ludwig 1995). Zwick and Paterson developed pseudopolynomial algorithms for deterministic mean-payoff games and a reduction to simple stochastic games (Zwick and Paterson 1996). Andersson and Miltersen later proved polynomial-time Turing equivalences among computing values and optimal strategies in simple stochastic, stochastic mean-payoff, and stochastic discounted-payoff games, with numerical parameters—including the discount factor—given in binary (Andersson and Miltersen 2009, Theorem 1). Randomized strategy-improvement algorithms have subexponential expected bounds (Zwick 2026). A different line obtains pseudopolynomial bounds when the number of random positions is fixed (Boros et al. 2019; Allamigeon et al. 2025). Numerical reward and denominator parameters in such bounds distinguish them from a bound in the complete binary input length. Deterministic quasipolynomial algorithms have also been obtained for simple stochastic games of bounded treewidth (Chatterjee et al. 2023).

Theorem 1 also gives a deterministic quasipolynomial algorithm for deciding whether the reachability value of a simple stochastic game is at least \(1/2\). Make the target absorbing, with reward \(+1\) on its self-loop, and give every other edge reward \(-1\); any other terminal vertex receives a self-loop of reward \(-1\). For every strategy pair the pathwise mean payoff is \(2\mathbf 1_{\{\text{target is reached}\}}-1\). Its expectation is twice the reachability probability minus one, so taking the strategy extrema proves the reduction. The transformation increases the input length by at most a constant factor.

An explicit small discount is only one part of the present algorithm. Andersson and Miltersen already bounded a sufficient discount using determinant coefficients and polynomial sign stabilization (Andersson and Miltersen 2009, Lemma 1); Gaubert, Grand-Clément, and Katz give sharper bounds on Blackwell optimality thresholds (Gaubert et al. 2025). Hansen, Miltersen, and Zwick proved that strategy iteration is strongly polynomial when the discount factor is fixed (Hansen et al. 2013). The dependence of their bound on the inverse distance of that factor from one does not yield a polynomial bound in its binary encoding. Here the discount has polynomial bit length, and a recursive comparison algorithm controls the cost of locating its fixed point.

For games without chance vertices, a deterministic quasipolynomial algorithm in the complete binary input length is given in OpenAI (2026, Theorem 1.1). Its simultaneous labeling construction is the direct predecessor of the method used here. We extend that construction to discounted operators, so that chance transitions enter through the same order and translation properties as player choices.

The proof and its main ideas

The first part of the proof replaces the mean-payoff problem by one discounted fixed point. For \(0<u<1\), the discounted map takes the maximum, minimum, or chance average of \(u w(e)+(1-u)t_j\) over edges \(e:i\to j\). It is a contraction and has a unique fixed point \(v(u)\). An explicit integer \(H\), of polynomial binary length, gives a nonzero-value gap of at least \(1/H\) and a discount \(\lambda\) for which \(\|v(\lambda)-\operatorname{val}\|_\infty\le1/(16H)\). Section 2 proves these estimates by elementary bounds on the rational functions of a fixed positional pair. Its gain and bias then give pathwise guarantees against every behavioral opponent. This establishes the payoff convention used here directly.

Finding the discounted fixed point by ordinary contraction iteration would take a number of steps depending on \(1/\lambda\), which can be exponential in the input length. The second part of the proof treats any monotone map \(F:\mathbb R^n\to\mathbb R^n\) satisfying \[F(t+c\mathbf 1)=F(t)+\gamma c\mathbf 1, \qquad 0<\gamma<1.\] In an integer box, a subsolution is an integer vector \(y\) satisfying \(F_i(y)\ge y_i\) at coordinates above the lower face; a supersolution satisfies the reverse inequality at coordinates below the upper face. A subsolution close to an upper face requires a plus label there, while a supersolution close to a lower face requires a minus label. The procedure assigns each coordinate a positive mass for each sign. Its guarantee holds simultaneously for all comparison vectors whose coordinates away from the opposite face have total mass at most one.

Section 3 adapts the two-pass pivot and mass-reweighting method of OpenAI (2026, secs. 4–5). The crucial translations have a fixed sign: subsolutions move downward and supersolutions upward. The discounted translation identity preserves their required inequalities, allowing comparison vectors in a large box to be used in smaller recursive boxes. Two pivot passes then arrange a redistribution of the masses that keeps the required comparisons valid. At each recursive call, at most one child leaves both mass vectors unchanged. Every other child increases each product of a coordinate’s two masses by a fixed factor. Starting from uniform masses, only \(O(\log(n+1))\) such choices are possible along a path, even when the coordinate range is exponentially large.

The final part explains why these boundary labels suffice to find the fixed point. After scaling, we place an integer subsolution \(Y\) and an integer supersolution \(Z\) on opposite sides of it, with \(Z-Y\) uniformly small. Neither vector is computed. A label excluding one comparison vector from a boundary strip permits that boundary to move inward while retaining both. Section 4 shrinks the enclosing box in this way, and the value gap converts the final approximation into the exact nonnegative-value set.

The reusable part of the argument is the labeling procedure: its correctness uses monotonicity and the scalar translation identity, and does not inspect the graph or the transition probabilities. The two-sided integer comparison vectors provide the link from that procedure to a discounted game. Quantitative discounting supplies the required accuracy, while the recursion determines the deterministic quasipolynomial running time.

Throughout, vector inequalities, extrema, and integer rounding are coordinatewise, and \(\mathbf 1\) denotes the all-ones vector. The proof uses only exact arithmetic.

A positional pair valid for all small discounts

Temporarily fix a pure positional pair: one outgoing edge at each Max and Min vertex. Let \(P\) be its row-stochastic transition matrix and let \(r_i\) be its expected one-step reward at \(i\). At a chance vertex the transition probabilities of parallel edges are added in \(P\), whereas their possibly different rewards are averaged in \(r\). The pair’s discounted equations are \[ x(u)=u r+(1-u)P x(u). \tag{7}\] The matrix \(I-(1-u)P\) is invertible for \(0<u<1\): a vector in its kernel would satisfy \(\|x\|_\infty\le(1-u)\|x\|_\infty\). The corresponding affine contraction preserves \([-W,W]^V\), so its solution satisfies \(\|x(u)\|_\infty\le W\).

The determinant argument follows the rational-function sign method of Andersson and Miltersen (Andersson and Miltersen 2009, Lemma 1); we derive all coefficient bounds in the input parameters above. For a polynomial \(a\), write \(\|a\|_{\mathrm{coef}}\) for the sum of the absolute values of its coefficients. This norm is subadditive and submultiplicative. Every entry of \(QP\) and \(Qr\) is an integer. Cramer’s rule therefore gives integer polynomials \(N_i,D\) with \[ x_i(u)=\frac{N_i(u)}{D(u)}, \qquad D(u)=\det\bigl(Q(I-(1-u)P)\bigr). \tag{8}\] Each entry of the matrix defining \(D\) has coefficient norm at most \(3Q\). The replacing column defining \(N_i\) is \(Qu r\), whose entries have coefficient norm at most \(QW\). Expanding each determinant over its \(n!\) permutations gives \[ \|D\|_{\mathrm{coef}}\le A_0, \qquad \|N_i\|_{\mathrm{coef}}\le A_0. \tag{9}\]

Whether this pair’s chosen edge is optimal at a player vertex \(i\) is determined by comparisons with every outgoing edge \(e:i\to j\). Each comparison is the sign of \[ x_i(u)-u w(e)-(1-u)x_j(u) =\frac{N_i(u)-u w(e)D(u)-(1-u)N_j(u)}{D(u)}. \tag{10}\] The numerator has coefficient norm at most \((3+W)A_0\le H\).

To control these signs, let \(a\) be any nonzero integer polynomial with \(\|a\|_{\mathrm{coef}}\le H\). Factoring its lowest power of \(u\) gives \(a(u)=u^\ell(c+u q(u))\), where \(c\) is a nonzero integer. For \(0<u\le1/(2H)\), \[|u q(u)|\le Hu\le\tfrac12<|c|.\] Thus the sign of \(a(u)\) throughout this interval is the sign of its lowest nonzero coefficient. This observation applies to both the numerator and denominator in (10); the denominator is nonzero there by invertibility. Every edge comparison therefore has a constant sign or vanishes identically on the interval.

Now choose attaining edges in the maximum and minimum defining \(f_{\lambda_0}(v(\lambda_0))\). They give a pure positional pair \((\sigma^*,\tau^*)\), and its linear solution at \(\lambda_0\) equals \(v(\lambda_0)\). Since \(\lambda_0\le1/(2H)\), all edge inequalities that hold at \(\lambda_0\) continue to hold for every \(0<u\le1/(2H)\). For each such \(u\), the pair’s linear solution is consequently a fixed point of \(f_u\), hence equals \(v(u)\). The pair is needed for the proof; the algorithm need not compute it.

The rational gain and its approximation error

Use the polynomials of the pair just selected. Let \(\ell\) be the lowest nonzero degree of \(D\). Boundedness of \(N_i(u)/D(u)\) as \(u\downarrow0\) implies that \(u^\ell\) also divides each \(N_i\). Define \(\widehat D=D/u^\ell\) and \(\widehat N_i=N_i/u^\ell\). Their coefficient norms satisfy (9), and \(\widehat D(0)\) is a nonzero integer. The quotient is analytic at zero, so it has the expansion (4), with \[ G_i=\frac{\widehat N_i(0)}{\widehat D(0)}. \tag{11}\] The bound (3) gives \(|G_i|\le W\). The displayed denominator has magnitude at most \(A_0\), and its numerator is an integer. Thus \(G_i\ne0\) implies \(|G_i|\ge1/A_0\ge1/H\).

The same coefficient bounds also control the approximation error. The polynomial \(\widehat N_i-G_i\widehat D\) has constant coefficient zero and coefficient norm at most \((1+W)A_0\). For \(0<u\le1/(2H)\), the tail of \(\widehat D\) has magnitude at most \(A_0u\le1/2\), so \(|\widehat D(u)|\ge1/2\). It follows that \[ |v_i(u)-G_i| \le 2(1+W)A_0u \le 2Hu. \tag{12}\] At \(u=\lambda_0\), this is the error claimed in (6).

It remains to identify \(G_i\) with the mean-payoff value. The gain controls which transitions can persist, and the coefficient \(\psi\) then controls the rewards on those transitions. For a selected player edge \(e:i\to j\), substitution of (4) into the discounted equation gives \[ G_i=G_j, \qquad \psi_i=w(e)+\psi_j-G_j. \tag{13}\] At a chance vertex, the corresponding identities are \[ \begin{split} G_i&=\sum_{e:i\to j}p_i(e)G_j,\\ \psi_i&=\sum_{e:i\to j}p_i(e)\bigl(w(e)+\psi_j-G_j\bigr). \end{split} \tag{14}\] At a Min vertex, the inequality \(v_i(u)\le u w(e)+(1-u)v_j(u)\) for an arbitrary outgoing edge first gives \(G_i\le G_j\). If \(G_i=G_j\), subtracting this common constant, dividing by \(u\), and letting \(u\downarrow0\) gives \[ \psi_i\le w(e)+\psi_j-G_j. \tag{15}\] At a Max vertex, the gain inequality and, when the gains agree, the bias inequality both reverse.

From one-step inequalities to pathwise payoffs

We use two elementary facts about adapted processes. Fixing a selected strategy will give the gain along a play one-sided conditional drift. The first lemma shows that the gain then becomes constant, so only gain-preserving player moves can persist and the bias inequalities apply. The second lemma shows that the centered contributions at chance vertices have vanishing averages.

Witnesses and the labeling guarantee

An input consists of \(A\in\mathbb Z^n\), a width \[ D=h2^d,\qquad 128\le h\le255,\quad h,d\in\mathbb Z,\quad d\ge0, \tag{19}\] and positive rational mass vectors \(a,b\in\mathbb Q_{>0}^n\). Write \(u=A+D\mathbf 1\), \(P=D/32\), and \(a(S)=\sum_{i\in S}a_i\), \(b(S)=\sum_{i\in S}b_i\) for \(S\subseteq\{1,\ldots,n\}\). The representation in Equation (19) is unique. Its short range of mantissas will later allow small relative decreases in the width.

Every claim belongs to its witness’s support, since \(0<P<D\). The output must respect all these claims simultaneously, although the algorithm is not given any witness and does not search for one.

The existence of a labeling will already follow from the finite box iteration below. The purpose of the recursive construction is to obtain such labels with the controlled branching and decreasing rank of Lemma 9, replacing dependence on the numerical width by dependence on its exponent.

The recursive procedure

A centered call of even width \(r\) at an integer pivot \(k\) means the call \(\mathcal L(k-(r/2)\mathbf 1,r,a',b')\) with the indicated masses. All calls use the same map \(F\). In a nonbase call set \[ c=A+\frac D2\mathbf 1,\qquad M=\frac D8,\qquad q=\frac D{128},\qquad p=\frac q{32}=\frac D{4096}. \tag{21}\] The pivot will stay between \(c-M\mathbf 1\) and \(c+M\mathbf 1\). The two passes use narrow centered boxes to identify some labels directly and arrange the remaining witnesses so that the later mass change preserves their admissibility. The downward pass preserves the plus masses, and the upward pass preserves the minus masses. A final wider centered call supplies the signs used to change both mass vectors.

Procedure \(\mathcal L(A,D,a,b)\). Execute the first applicable base case. If neither applies, execute Steps 3–6 in order.

1. Mass base case. If \(a_i b_i>1\) for every \(i\), return \(+\) at \(i\) when \(b_i>1\), and return \(-\) otherwise.

2. Width base case. If \(d<12\), compute \(t^*\) by Equation (20). Return \(+\) at \(i\) when \(t_i^*>A_i+D/2\), and return \(-\) otherwise.

3. Downward pass. Initialize \(k=c\). Make a centered width-\(q\) call at \(k\) with masses \((a,\frac43 b)\), and use its labels to update all coordinates simultaneously by \[ k_i^{\mathrm{new}}= \begin{cases} \max\{c_i-M,k_i-p\},&\text{if the child labels }i\text{ by }-,\\ k_i,&\text{if the child labels }i\text{ by }+. \end{cases} \tag{22}\] Replace \(k\) by \(k^{\mathrm{new}}\) and repeat until an update leaves the pivot unchanged. Denote this last pivot by \(k^{\downarrow}\) and set \[ I_- =\{i:k_i^{\downarrow}<c_i-P\}. \tag{23}\]

4. Upward pass. Start at \(k=k^{\downarrow}\). Make a centered width-\(q\) call at \(k\) with masses \((\frac43 a,b)\), and update simultaneously by \[ k_i^{\mathrm{new}}= \begin{cases} \min\{c_i+M,k_i+p\},&\text{if the child labels }i\text{ by }+,\\ k_i,&\text{if the child labels }i\text{ by }-. \end{cases} \tag{24}\] Replace \(k\) by \(k^{\mathrm{new}}\) and repeat until an unchanged update. Denote the last pivot by \(k^f\) and set \[ I_+ =\{i:k_i^f>c_i+P\}. \tag{25}\]

5. Provisional labels and new masses. Make a centered width-\(D/2\) call at \(k^f\) with masses \((a,b)\). For its output \(\ell^0\), define \[ (\bar a_i,\bar b_i)= \begin{cases} (\frac45 a_i,\frac85 b_i),&\ell_i^0=+,\\[1mm] (\frac85 a_i,\frac45 b_i),&\ell_i^0=-. \end{cases} \tag{26}\]

6. Continuation and overrides. Call \(\mathcal L(A,D,\bar a,\bar b)\). In its output replace the signs on \(I_-\) by \(-\) and those on \(I_+\setminus I_-\) by \(+\). Return this label vector.

Each pass includes the final child call whose update changes nothing. That call will certify a mass inequality at the stopped pivot. All coordinates in one update use the same old pivot and the same child output; there is no order-dependent coordinate update.

The purpose of the passes is the following mass property. For every witness with a claim outside its own override set—\(I_+\) for a plus witness and \(I_-\) for a minus witness—the coordinates in its support whose provisional labels match its sign will have total mass greater than \(3/4\). Here mass means \(a\)-mass for a plus witness and \(b\)-mass for a minus witness. Its original total mass is at most one, so Step 5 will leave its new total mass below \[\frac85-\frac45\cdot\frac34=1.\] It will therefore remain a witness for the continuation in the unchanged box. At the same time, every product \(a_i b_i\) is multiplied by \(32/25\). We first use this product growth to prove termination; the subsequent witness analysis proves the stated mass property and hence correctness.

The continuation preserves the width, so width reduction alone does not prove termination. The mass products provide the missing measure. Define \[ \mu(a,b)=\min_i a_i b_i,\qquad \rho=\frac{32}{25},\qquad B(\mu)=\min\{j\in\mathbb Z_{\ge0}:\rho^j\mu>1\}. \tag{27}\] This integer is used only in the proof, not computed by the procedure.

Translating a witness into a centered box

To analyze the labels, we follow an arbitrary parent witness through the centered calls. Translation places its largest deviation from the pivot at one boundary of the child box; clipping removes coordinates far below that largest deviation. The surviving support will identify the mass forced near the largest deviation when a pivot pass stops.

Fix a nonbase input and a pivot \(k\in[c-M\mathbf 1,c+M\mathbf 1]\). For a relevant plus witness \(y\), define its peak and gaps by \[ s_y(k)=\max_i(y_i-k_i),\qquad g_i^y(k)=s_y(k)-(y_i-k_i). \tag{28}\] For a relevant minus witness \(z\), put \[ s_z(k)=\max_i(k_i-z_i),\qquad g_i^z(k)=s_z(k)-(k_i-z_i). \tag{29}\] The gaps are nonnegative integers and at least one gap is zero. The following lemma handles both signs, including the inequalities introduced by the discount factor.

What the two pivot passes enforce

We prove correctness by induction on the rank from Lemma 9. For the remainder of this subsection, fix a nonbase call and assume that all its children satisfy Theorem 6. Witnesses, supports, and claims refer to the parent input unless stated otherwise.

In each pass, the sign whose masses are unchanged protects its own peak: coordinates close enough to that peak must receive its sign and remain stationary. The opposite sign has its masses multiplied by \(4/3\). At the final unchanged update, any witness of that sign with a claim outside its override set must consequently have mass greater than \(3/4\) near its peak. The next two lemmas make these statements precise.

The two passes have now separated the claims into those that can safely receive an override and those whose witnesses have substantial mass near a peak at \(k^f\). The wider provisional call labels all that mass with the witness’s sign. Reducing the masses of that sign then keeps each remaining witness admissible for the continuation. Figure 1 summarizes how the two passes supply the information used in this final step.

Mass reweighting and completion of the proof

Two nearby integer comparison vectors

Use the integers \(W,Q,A_0,H\) of Section 2, and set \[ \begin{gathered} N=32H^2,\qquad \lambda=1/N=\lambda_0,\qquad \gamma=1-1/N,\\ K=256(N+1),\qquad S=16HK,\qquad J=SW+N+1. \end{gathered} \tag{38}\] Let \[F(t)=S f_\lambda(t/S),\qquad x=S v(\lambda).\] Then \(F(x)=x\), the map \(F\) is monotone, and \[ F(t+c\mathbf 1)=F(t)+\gamma c\mathbf 1\qquad(t\in\mathbb R^n,\ c\in\mathbb R). \tag{39}\] Thus \(F\) has the properties used in Section 3. Define the integer vectors \[ Y=\lfloor x\rfloor-N\mathbf 1, \qquad Z=\lceil x\rceil+N\mathbf 1. \tag{40}\] Floors and ceilings are coordinatewise; in particular, a floor of a negative number is taken toward minus infinity. These vectors are used only in the proof. The algorithm will not compute them.

Shrinking the box

Recall that the permitted widths are \(D=h2^d\) with \(128\le h\le255\) and integers \(d\ge0\). Start with \[ A=-J\mathbf 1,\qquad D=D_0=128\cdot2^{d_0}, \tag{42}\] where \(d_0\) is the least nonnegative integer for which \(D_0\ge2J\). The box \([A,A+D\mathbf 1]\) contains \(Y\) and \(Z\).

While \(D>K\), call \(\mathcal L(A,D,a,b)\) with \(a_i=b_i=1/n\) for all \(i\). Put \(u=A+D\mathbf 1\) and \(P=D/32\). Within the current box, \(Y\) is a subsolution and \(Z\) is a supersolution, and their support masses are at most one. Consequently, the labeling guarantee has the following contrapositive form: \[ \begin{aligned} \text{label }+\text{ at }i&\quad\Longrightarrow\quad Z_i>A_i+P,\\ \text{label }-\text{ at }i&\quad\Longrightarrow\quad Y_i<u_i-P. \end{aligned} \tag{43}\] For example, \(Z_i\le A_i+P\) would be a minus claim and would require a minus label.

Let \(D'\) be the next smaller permitted width. More explicitly, \[ D'=\begin{cases} (h-1)2^d,&h>128,\\ 255\cdot2^{d-1},&h=128. \end{cases} \tag{44}\] The second case has \(d\ge1\), because the loop condition implies \(D>K>255\). Set \(\delta=D-D'\). In the first case \(\delta/D=1/h\le1/128\); in the second case this ratio is \(1/256\). Thus \[ 0<\delta\le D/128, \qquad Z_i-Y_i\le K/128<D/128. \tag{45}\] Define \[A'_i=\begin{cases} A_i+\delta,&\text{if the label is }+,\\ A_i,&\text{if the label is }-. \end{cases}\] Replace \((A,D)\) by \((A',D')\).

At termination, \(Y\le x\le Z\) and the invariant imply \(A_i\le x_i\le A_i+D\). Hence \[ \left|\frac{A_i}{S}-v_i(\lambda)\right| \le\frac KS=\frac1{16H}. \tag{46}\] Theorem 2 now gives \[ \left|\frac{A_i}{S}-\operatorname{val}(i)\right|\le\frac1{8H}. \tag{47}\] Output exactly the indices satisfying \[ \frac{A_i}{S}\ge-\frac1{2H}, \quad\text{equivalently}\quad A_i\ge-8K. \tag{48}\] If \(\operatorname{val}(i)=0\), (47) puts \(A_i/S\) at least \(-1/(8H)\), so the index is included. If \(\operatorname{val}(i)>0\), the same conclusion holds. If \(\operatorname{val}(i)<0\), the value gap in Theorem 2 gives \(A_i/S\le-1/H+1/(8H)=-7/(8H)\), so the index is excluded. This proves exact correctness, including equality at zero.

Bit complexity and uniformity

It remains to show that the potentially large integer widths do not produce a large recursion tree, and that every local computation has polynomial bit cost. The first point uses the mass-product rank of Section 3; the second uses the explicit binary encoding.

Since every vertex has an outgoing edge and the input is explicit, \(n,|E|=O(L+1)\). The binary lengths of the probabilities and rewards give \[\log_2 Q=O(L+1),\qquad \log_2 W=O(L+1),\qquad \log_2 A_0=O((L+2)^2).\] In particular, all integers in (38) and (42) have \(O((L+2)^2)\) bits, and \(d_0=O((L+2)^2)\). Reading the input and forming these integers by ordinary exact arithmetic take polynomial time. Every recursive box lies in its parent, and every outer box lies in the initial box. Thus all box endpoints, pivot coordinates, and integer arguments to \(F\) have polynomial binary length.

For an integer vector \(t\), the quantities used to evaluate \(F_i(t)\) are \[ \frac{S w(e)+(N-1)t_j}{N},\qquad e:i\longrightarrow j. \tag{49}\] Max and Min take exact extrema. At a chance vertex write the encoded probability as \(p(e)=c_e/d_e\) with \(d_e>0\). Its weighted sum can be formed with the common denominator \(QN\) and integer numerator \[\sum_{e:i\to j}c_e\frac{Q}{d_e} \bigl(Sw(e)+(N-1)t_j\bigr).\] Every \(d_e\) divides \(Q\), even when input fractions are not reduced. This formula gives polynomial bit lengths and polynomial bit cost for an evaluation and its coordinatewise floors. Zero probabilities and parallel edges require no special handling.

Consider one outer call, whose initial masses are \(a_i=b_i=1/n\). For a recursive call put \[\mu=\min_i a_i b_i,\qquad \rho=\frac{32}{25},\qquad B(\mu)=\min\{j\in\mathbb Z_{\ge0}:\rho^j\mu>1\}.\] The initial value \(B_0=B(1/n^2)\) is \(O(\log(n+1))\); this includes \(n=1\), for which \(B_0=1\). Every recursive edge decreases \(d+B\). Only the provisional-label child can preserve \(B\), and it decreases \(d\) by one. Each other child decreases \(B\) by at least one and does not increase \(d\). Thus the depth is at most \[\Lambda=d_0+B_0,\] and any root-to-node path contains at most \(B_0\) edges decreasing \(B\). At each node there is at most one \(B\)-preserving child and at most \[s_*=2(1024n+1)+1=2048n+3\] other children: the two pivot passes account for the first term and the reweighted call for the final one.

A path of length \(\ell\) with \(j\) edges decreasing \(B\) is specified by their \(j\) positions and at most \(s_*\) choices at each such position; the other child, if present, is unique. The total number of nodes is therefore at most \[\begin{align*} \sum_{\ell=0}^{\Lambda}\sum_{j=0}^{\min(\ell,B_0)} \binom{\ell}{j}s_*^j &\le (\Lambda+1)(B_0+1)(1+\Lambda s_*)^{B_0} \tag{50}\\ &=2^{O((\log_2(L+2))^2)}. \tag{51}\end{align*}\] The distinction between these two kinds of children is essential: the depth may be polynomial in \(L\), but branching choices occur only \(O(\log(n+1))\) times on any path.

All masses can be stored as unreduced positive fractions. An edge that changes masses multiplies each by one of a fixed set of rational constants, and so increases its numerator and denominator lengths by at most a constant. The other edge leaves masses unchanged. Thus the mass lengths are polynomial (indeed \(O(\log(n+1))\)), and every comparison, update, and support-independent base test has polynomial bit cost. The algorithm does not compute \(B\); it is used only for this analysis.

Outside its children, a nonbase call performs \(O(n+1)\) pivot updates and associated vector operations, all of polynomial bit cost. In a width base case, \(d<12\) gives \(D\le255\cdot2^{11}\), an absolute constant, so the clipped-floor iteration uses at most \(1+nD\) polynomial-cost evaluations. The mass base case is also polynomial. Consequently (51) bounds the bit cost of one outer call up to a polynomial factor. Lemma 14 bounds the number of outer calls by a polynomial as well.

Finally, all loops, tie rules, integer operations, and recursive calls are specified by finite algorithms independent of the input. A depth-first implementation stores a stack of polynomial depth whose individual records have polynomial length. Scanning such a stack or copying a record on a deterministic Turing machine costs at most a polynomial factor per local operation. The final integer tests (48) and the output take polynomial time. Absorbing these factors into (51) proves the bound \(2^{C(\log_2(L+2))^2}\) for one absolute constant \(C\). This completes the proof of Theorem 1.