OctoInform Beta

OpenAI preprint, September 2026 · §8. The complete algorithm and certified outputs · §8

§8 (proof of Theorem 1.1): the root call, the threshold and the output law: The random program computing Solve(0,B*;B*,1,1,n,n)\mathrm{Solve}(0,B_*;B_*,1,1,n,n) and thresholding at B*/2B_*/2 marks the zero-threshold winning set with probability at least 7/87/8

Run long enough, the register program has the solver’s law.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Let GG be a mean-payoff game on a set VV of nn vertices with integer edge weights w(e)w(e), written for a machine as its input code ⟨G⟩\langle G\rangle, a binary string of length LL. The task is to output the zero-threshold winning set 𝒲0(G)\mathcal{W}_0(G) with a machine that reads its random choices off a tape of fair bits. A list of nn bits is correct for GG when it marks exactly the vertices of 𝒲0(G)\mathcal{W}_0(G).

The algorithm works with the transformed weights t(e)=(n+1)w(e)+1t(e)=(n+1)w(e)+1, the weight bound W=max⁡{1,max⁡e|t(e)|}W=\max\{1,\max_e|t(e)|\} and the top width B*=8nWB_*=8nW. Its solver Solve(a,b;B,α,β,k,m)\mathrm{Solve}(a,b;B,\alpha,\beta,k,m) takes a box with corners a≤ba\le b in ℤV\mathbb{Z}^V and reference width B≥b−aB\ge b-a, positive rational support weights α\alpha, β\beta and budgets kk, mm, and returns a random vector pp of the box. The thresholded solver 𝒮(G)\mathcal{S}(G) is the random list of nn bits whose ii-th bit says whether pi>B*/2p_i>B_*/2, for pp the output of the root call Solve(0,B*;B*,1,1,n,n)\mathrm{Solve}(0,B_*;B_*,1,1,n,n).

The library builds this algorithm as a register program on ⟨G⟩\langle G\rangle and a tape of fair bits, and reaches it from the solver through two machines: the solver as a control machine whose random choices are uniform sample indices, and a raw control machine on bit strings and unary counters, in which a counter stands for its length.

The Solver as a Control Machine

Fix a bound BB, with sample count ss, a power of two, and trial count JJ, the global parameters at BB; log⁡2s\log_2 s fair bits give a uniform index in {0,…,s−1}\{0,\dots,s-1\}. A state σ\sigma of the solver for GG at bound BB is a call call(ϕ,κ)\mathrm{call}(\phi,\kappa) of a job ϕ\phi under a continuation κ\kappa, or a return ret(κ,v)\mathrm{ret}(\kappa,v) of a value vv to κ\kappa, where a continuation is a stack of pending frames, each a job waiting for the value of the call above it, over the empty continuation ⌀\varnothing. The jobs are solve, ask, trials, update, centers, orient, orientation trials, orientation plus, tighten and reweight; a solve job on budgets PP and a box II is the call of Solve\mathrm{Solve} on them.

The sampled step with sample index jj is the map σ↦stepj(σ)\sigma\mapsto\mathrm{step}_j(\sigma) on states that makes one move of the solver.✦ A return to ⌀\varnothing stays as it is, a return to a pushed frame resumes that frame with the value, and a call makes its job’s first move: a solve job returns the small vector when the parameter R=km∑i∈V1/(αiβi)R=k\,m\sum_{i\in V}1/(\alpha_i\beta_i) of P=(α,β,k,m)P=(\alpha,\beta,k,m) is below 11, the exact vector when II has width at most 128s128s, and otherwise tightens II; an ask runs JJ trials and returns their median box, and trials with JJ remaining run one solve at a time. An update asks the budgets reduced in kk on the box centered at its current center qq of width h/(32s)h/(32s), hh the width of II, and then, on the same box, the budgets reduced in mm; centers with tt remaining run tt updates; an orient job on a box of width at most 128s128s is the base orientation, and otherwise computes ss centers from the midpoint of the box; orientation trials repeat the orient job JJ times, and orientation plus combines these trials into the choice made by a strict majority, with all their exception sets listed one after another; a tighten job asks the budgets reduced in kk; a reweight job asks, for each exception set HH of the orientation in turn, the budgets reweighted at HH, in mm for the choice YY and in kk for the choice ZZ. An orientation is a choice between YY and ZZ together with a list of exception sets of vertices. The index jj is read in one place, the orientation loop: it takes the centers of the trial vectors, the positive and negative displacement sets of a center being the coordinates where it lies far above or far below the midpoint of the box, and when neither the positive nor the negative displacement set at the ss-th center has measure above 1/21/2, it orients the widened centered box at the jj-th center. A frame resumed with a value vv combines it: trial vectors and centers are collected into lists, the median box of the trial vectors in II is returned, and the clipped average of two centers is returned. When the positive displacement set at the ss-th center has measure above 1/21/2 for the budgets, the orientation loop returns the choice YY with the complement of that set as its exception set, and when the negative displacement set has, the choice ZZ with the complement of that set. An orientation computed on the widened centered box keeps its choice and has the two displacement sets appended to its exception sets. A tightening moves the floor of II to vv when some coordinate of vv lies at least the grid width δ\delta from the lower corner, and after a second ask the ceiling of II to vv when some coordinate lies at least δ\delta from the upper corner; otherwise the box is returned unchanged. A solve job on a box of width above 128s128s calls the orientation plus job on the tightened box and then reweights by the choice between YY and ZZ and the exception sets of the orientation returned; it then calls the solve job on the budgets and the tightened box capped high, for the choice YY, or capped low, for ZZ, by its width minus its grid width δ\delta, and returns the coordinatewise minimum, respectively maximum, of the vector of that call and the vectors returned by the reweighting. The base orientation of a box II with lower corner aa and width ww, for the budgets PP and the exact vector vv of II, is given by the set MM of coordinates ii with w≤2(vi−ai)w\le 2(v_i-a_i): if MM has measure above 1/21/2 for PP, it chooses YY with the complement of MM as its exception set, and otherwise it chooses ZZ with MM as its exception set.✦

Each state σ\sigma has a rank rkσ\mathrm{rk}\,\sigma, a number of steps after which the solver started at σ\sigma has halted, and an output law [[σ]][\![\sigma]\!], the law of the value it returns. The solver’s step semantics, its one-step transition law on states, run for ℓ\ell steps from σ\sigma, gives a random state Runℓ(σ)\mathrm{Run}_\ell(\sigma). The sampled run Runˆℓ(σ)\widehat{\mathrm{Run}}_\ell(\sigma) is the random state reached from σ\sigma by ℓ\ell sampled steps, each with a fresh uniform index: Runˆ0(σ)=σ,Runˆℓ+1(σ)=Runˆℓ(stepj(σ)),j uniform in {0,…,s−1}.\widehat{\mathrm{Run}}_0(\sigma)=\sigma,\qquad \widehat{\mathrm{Run}}_{\ell+1}(\sigma)=\widehat{\mathrm{Run}}_\ell\bigl(\mathrm{step}_j(\sigma)\bigr), \quad j\text{ uniform in }\{0,\dots,s-1\}.(1)✦

The Raw Control Machine

A register pack π\pi is a record of eight registers: budgets, a box, a unary counter, a first vector q(π)q(\pi) and a second vector of binary words, a list of vectors, an orientation and a list of orientations, where an orientation is a bit, true for YY, with a list of vertex masks.✦ A stack cell is a tag, a unary counter whose length names a job or a frame, with a register pack holding its data.✦ A raw control state zz is a current cell, holding the job called or, under tag 1010, the value returned, over a stack of cells holding the pending frames; π(z)\pi(z) is the pack of its current cell.✦

An environment η\eta is a raw arena, a bit string that can code a graph, together with four counters.✦ An environment η\eta represents GG at bound BB, written η⊩(G,B)\eta\Vdash(G,B), when its arena codes the graph of GG with the transformed weight t(e)t(e) on each edge and its counters have lengths log⁡2s\log_2 s, ss, JJ and at least 128ns128ns, the last bounding the steps of the basic solver, the solver that returns the exact vector on a box of width at most 128s128s.✦

A raw control state zz represents a solver state σ\sigma, written z⊩σz\Vdash\sigma, when its current cell carries the tag of the job σ\sigma calls, or tag 1010 when σ\sigma returns, with a pack holding the job’s budgets, box, counts and vectors or the returned value, and its stack represents the continuation of σ\sigma cell by cell, each cell carrying the tag and the data of its frame.✦ A pack π\pi represents a value vv, written π⊩v\pi\Vdash v, when the register of the value’s kind holds it: a vector in q(π)q(\pi), a list of vectors, an orientation or a list of orientations in its own register, an inner box in the box register.✦

The advance step with environment η\eta and a sample index, given as a counter, moves zz by the tag of its current cell: tags 00 to 99 make the first move of the jobs in the order listed above, and any other tag resumes the frame on top of the stack, or leaves zz as it is when the stack is empty.✦ Its moves compute the solver’s operations on raw data: coordinatewise medians of trial vectors, strict majorities of orientations, and the basic solver on boxes of width at most 128s128s. For a box of midpoint μ\mu and width hh and a center vv, they build the masks of the displacement sets {i:s(vi−μi)>2h}\{i: s(v_i-\mu_i)>2h\} and {i:s(vi−μi)<−2h}\{i: s(v_i-\mu_i)<-2h\}, the centered boxes of widths h/(32s)h/(32s) and h/8h/8, and the grid width δ=h/(4s)\delta=h/(4s).

The control loop Loopη(z;c1,…,cℓ)\mathrm{Loop}_\eta(z;c_1,\dots,c_\ell) is the raw control state reached from zz by the advance step with η\eta and the indices c1,…,cℓc_1,\dots,c_\ell in turn.✦ Drawn samples at bound BB are independent counters c1,…,cℓc_1,\dots,c_\ell, each uniform in {0,…,s−1}\{0,\dots,s-1\}.✦

The Root Call and the Register Program

The root environment ηG\eta_G holds the arena of GG and the counters log⁡2s\log_2 s, ss, JJ and 128ns128ns at bound B*B_*, computed as g=|B*|+1,log⁡2s=⌈log⁡2(217(g+1))⌉,J=2(s(n+1))6+1,g=|B_*|+1,\qquad \log_2 s=\bigl\lceil\log_2(2^{17}(g+1))\bigr\rceil,\qquad J=2\bigl(s(n+1)\bigr)^6+1,(2)✦ with |B*||B_*| the binary length of B*B_*. In the root call the budgets are (α,β,k,m)=(1,1,n,n),(\alpha,\beta,k,m)=(1,1,n,n),(3)✦ and its initial box is the box [0,B*]V[0,B_*]^V of reference width B*B_*: a=(0,…,0),b=(B*,…,B*),B=B*.a=(0,\dots,0),\qquad b=(B_*,\dots,B_*),\qquad B=B_*.(4)✦ The initial control state zGz_G calls job 00, the solve job, on a pack holding these budgets and this box, over the empty stack.✦ The root call has a bound NGN_G on its number of steps, its root control bound NG=A(n,B*)KGN_G=A(n,B_*)\,K_G, where A(n,B*)A(n,B_*) is the number of control steps the library allows for one solver invocation on a game with nn vertices and top width B*B_* (controlAllowance) and KGK_G is its bound on the number of solver invocations of the root call (rootInvocationBound); NGN_G is rootControlBound, defined in the imported library MeanPayoff (MeanPayoff/ArithmeticBounds.lean).

The classification by half of a binary word xx and a vector v=(v1,…,vn)v=(v_1,\dots,v_n) of binary words is the list of bits cl(x;v)=([⌊x/2⌋<v1],…,[⌊x/2⌋<vn]),\mathrm{cl}(x;v)=\bigl([\lfloor x/2\rfloor<v_1],\dots,[\lfloor x/2\rfloor<v_n]\bigr),(5)✦ where [⋅][\,\cdot\,] is 11 on a true condition and 00 on a false one.

On ⟨G⟩\langle G\rangle the preparation computes the number of samples and of random bits, N=225000⌈log⁡2(L+2)⌉2,A(G)=Nlog⁡2s,N=2^{25000\lceil\log_2(L+2)\rceil^2},\qquad A(G)=N\log_2 s,(6)✦ and the auxiliary data auxG\mathrm{aux}_G: the numbers log⁡2s\log_2 s, ss and NN, the width B*B_*, the root environment ηG\eta_G and the initial control state zGz_G. The answer ansG(u)\mathrm{ans}_G(u) on random bits u∈{0,1}A(G)u\in\{0,1\}^{A(G)} is the list of bits obtained by cutting uu into NN chunks of log⁡2s\log_2 s bits, reading the ii-th chunk as a binary number ci<sc_i<s, running the control loop on c1,…,cNc_1,\dots,c_N and classifying the first vector of the final pack by B*B_*: ansG(u)=cl(B*;q(π(LoopηG(zG;c1,…,cN)))).\mathrm{ans}_G(u)=\mathrm{cl}\Bigl(B_*;\,q\bigl(\pi(\mathrm{Loop}_{\eta_G}(z_G;c_1,\dots,c_N))\bigr)\Bigr).(7)✦

The register program ℳ\mathcal{M} is a program on five registers. It runs the preprocessing, which reads ⟨G⟩\langle G\rangle and computes the preparation, then draws a fresh fair bit for each of the A(G)A(G) units of the counter left by the preparation, then runs the postprocessing, which computes the answer on these bits and auxG\mathrm{aux}_G and writes it out. The postprocessing cost cpost(y)c_{\mathrm{post}}(y) of an input yy of the postprocessing, random bits with auxiliary data, is the step bound for computing its answer plus the cost of writing it out, plus 22; |y||y| is the encoded size of yy.✦ For constants KK and DD, the step limit on ⟨G⟩\langle G\rangle is TK,D(⟨G⟩)=cpre(⟨G⟩)+36A(G)+K(4A(G)+|auxG|+3)D+20,T_{K,D}(\langle G\rangle)=c_{\mathrm{pre}}(\langle G\rangle)+36A(G) +K\bigl(4A(G)+|\mathrm{aux}_G|+3\bigr)^D+20,(8)✦ where cprec_{\mathrm{pre}} is the preprocessing cost, the steps of reading the input and of the preparation. Run for TT steps from its initial configuration on ⟨G⟩\langle G\rangle, ℳ\mathcal{M} ends in a random configuration whose output is the list ℳT(⟨G⟩)\mathcal{M}_T(\langle G\rangle).

The Claim

Theorem 1. Let GG be a mean-payoff game on nn vertices.

(a) The initial control state represents the root call over the empty continuation: zG⊩call(Solve(0,B*;B*,1,1,n,n),⌀).z_G\Vdash\mathrm{call}\bigl(\mathrm{Solve}(0,B_*;B_*,1,1,n,n),\varnothing\bigr).(9)✦

(b) If vv is a vector of the box [0,B*]V[0,B_*]^V, a pack π\pi represents vv, and xx is a binary word of value B*B_*, then the classification (5) gives cl(x;q(π))=([v1>B*/2],…,[vn>B*/2]).\mathrm{cl}\bigl(x;q(\pi)\bigr)=\bigl([v_1>B_*/2],\dots,[v_n>B_*/2]\bigr).(10)✦

Let further σ\sigma be a state of the solver for GG at a bound BB, with sample count ss.

(c) If an environment η\eta and a raw control state zz satisfy η⊩(G,B)\eta\Vdash(G,B) and z⊩σz\Vdash\sigma, then for all indices c1,…,cℓc_1,\dots,c_\ell Loopη(z;c1,…,cℓ)⊩stepcℓ∘…∘stepc1(σ).\mathrm{Loop}_\eta(z;c_1,\dots,c_\ell)\Vdash \mathrm{step}_{c_\ell}\circ\dots\circ\mathrm{step}_{c_1}(\sigma).(11)✦

(d) For every ℓ\ell and every function QQ from states to the rationals, 𝔼Q(Runˆℓ(σ))=𝔼Q(Runℓ(σ)).\mathbb{E}\,Q\bigl(\widehat{\mathrm{Run}}_\ell(\sigma)\bigr) =\mathbb{E}\,Q\bigl(\mathrm{Run}_\ell(\sigma)\bigr).(12)✦

(e) If c1,…,cℓc_1,\dots,c_\ell are drawn samples at bound BB, then for every such QQ 𝔼Q(stepcℓ∘…∘stepc1(σ))=𝔼Q(Runˆℓ(σ)).\mathbb{E}\,Q\bigl(\mathrm{step}_{c_\ell}\circ\dots\circ\mathrm{step}_{c_1}(\sigma)\bigr) =\mathbb{E}\,Q\bigl(\widehat{\mathrm{Run}}_\ell(\sigma)\bigr).(13)✦

(f) If η\eta and zz are as in (c) and rkσ≤ℓ\mathrm{rk}\,\sigma\le\ell, if c1,…,cℓc_1,\dots,c_\ell are drawn samples at bound BB, and if functions FF on packs and ff on the values σ\sigma can return, both to the rationals, satisfy F(π)=f(v)F(\pi)=f(v) whenever π⊩v\pi\Vdash v, then 𝔼F(π(Loopη(z;c1,…,cℓ)))=𝔼v∼[[σ]]f(v).\mathbb{E}\,F\bigl(\pi(\mathrm{Loop}_\eta(z;c_1,\dots,c_\ell))\bigr) =\mathbb{E}_{v\sim[\![\sigma]\!]}\,f(v).(14)✦

(g) If ℓ≥NG\ell\ge N_G, c1,…,cℓc_1,\dots,c_\ell are drawn samples at bound B*B_*, and ff maps lists of bits to the rationals, then 𝔼f(cl(B*;q(π(LoopηG(zG;c1,…,cℓ)))))=𝔼f(𝒮(G)).\mathbb{E}\,f\Bigl(\mathrm{cl}\bigl(B_*;\,q(\pi(\mathrm{Loop}_{\eta_G}(z_G;c_1,\dots,c_\ell)))\bigr)\Bigr) =\mathbb{E}\,f\bigl(\mathcal{S}(G)\bigr).(15)✦

(h) If uu is uniform in {0,1}A(G)\{0,1\}^{A(G)}, then for every such ff the answer (7) satisfies 𝔼f(ansG(u))=𝔼f(𝒮(G)).\mathbb{E}\,f\bigl(\mathrm{ans}_G(u)\bigr)=\mathbb{E}\,f\bigl(\mathcal{S}(G)\bigr).(16)✦

(i) If constants KK and DD bound the postprocessing cost, cpost(y)≤K(|y|+1)Dc_{\mathrm{post}}(y)\le K(|y|+1)^D for every input yy of the postprocessing, and T=TK,D(⟨G⟩)T=T_{K,D}(\langle G\rangle), then for every such ff 𝔼f(ℳT(⟨G⟩))=𝔼f(𝒮(G)).\mathbb{E}\,f\bigl(\mathcal{M}_T(\langle G\rangle)\bigr)=\mathbb{E}\,f\bigl(\mathcal{S}(G)\bigr).(17)✦

(j) Under the same bound on the postprocessing cost, Pr⁡[ℳT(⟨G⟩) is correct for G]≥7/8.\Pr\bigl[\mathcal{M}_T(\langle G\rangle)\text{ is correct for }G\bigr]\ge 7/8.(18)✦

In the paper, the result reads: compute tt, WW, B*B_* and the global parameters, run p=Solve(0,B*;B*,1,1,n,n)p=\mathrm{Solve}(0,B_*;B_*,1,1,n,n) and return Up={i∈V:pi>B*/2}U_p=\{i\in V: p_i>B_*/2\}; by Corollary 6.4 the single event p=xp=x, for xx the box solution of [0,B*][0,B_*], has probability at least 7/87/8, and on it Proposition 2.5 identifies UpU_p with the entire zero-threshold winning set.

What Is Checked

The claim is stated over mean-payoff games and their input codes; the solver’s states at a bound with the sampled step, the sampled run (1), the step semantics, ranks and output laws; the raw control machine with its environments, packs, control loop and representations; the root environment (2), budgets (3), box (4) and initial control state; the classification (5); the preparation (6) and the answer; and the register program run for the step limit (8) under a polynomial bound on the postprocessing cost.

The library also bounds the sizes of the raw computations. Every pair of environment and control state that the control loop passes through, from a start xx on a list cc of indices, has encoded size at most 240(|(x,c)|+1)122^{40}(|(x,c)|+1)^{12}.✦ Cutting random bits into samples keeps every intermediate state of encoded size at most 5(|y|+1)25(|y|+1)^2✦, and every partial coordinatewise maximum or minimum of vectors has encoded size at most 20(|y|+1)220(|y|+1)^2, for yy the input in each case.