OctoInform Beta

OpenAI preprint, September 2026 · §1. Introduction · §1

Theorem 1.1 [Main theorem]: One random-tape machine halts within 2C(log⁡2(L+2))22^{C(\log_2(L+2))^2} steps on games coded in LL bits, writing the winning set on at least 7/87/8 of tapes

Mean-payoff winning sets in randomized quasipolynomial time.

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

A mean-payoff game GG is played by Max and Min on a finite directed graph with vertex set VV of size nn, each vertex owned by one of the two players, and with integer weights w(e)w(e) on its edges, the owner of the current vertex choosing the next edge. The zero-threshold winning set U(G)U(G) of a mean-payoff game GG is the set of vertices of GG from which Max can force the long-run average weight of the play to be nonnegative. The main theorem gives a randomized algorithm that computes all of U(G)U(G) in time quasipolynomial in the length of the game’s code.

The library states it about one fixed Turing machine with three tapes that reads one random bit at each step. Running time becomes a number of steps, and the probability of success becomes the share of random tapes on which the machine writes U(G)U(G).

Machines with a Random Tape

Every game GG has a fixed input code dGd_G, a bit string whose length is denoted LL.

A three-tape machine with a random tape is a Turing machine MM with three tapes that, at each step, also reads the next bit of a random tape ρ\rho. Such a machine halts within TT steps on an input dd and a random tape ρ∈{0,1}T\rho\in\{0,1\}^T when its configuration after TT steps, started on dd and ρ\rho, is a halting one. The good tapes of MM on a game GG at step TT are the random tapes on which MM writes U(G)U(G) on its tape 2: GoodM(G,T)={ρ∈{0,1}T:after T steps on dG and ρ, tape 2 of M holds exactly U(G)}.\mathrm{Good}_M(G,T)=\bigl\{\rho\in\{0,1\}^T:\ \text{after $T$ steps on $d_G$ and $\rho$, tape 2 of $M$ holds exactly } U(G)\bigr\}.(1)

The Randomized Solver

A register program PP is a program on finitely many registers, each a stack of bits, whose steps may also flip a fair coin. Run on an input dd for λ\lambda steps, PP unfolds into its coin tree TreeP(d,λ)\mathrm{Tree}_P(d,\lambda), the binary tree that branches at each coin flip and whose leaves are the configurations after λ\lambda steps, a leaf behind jj flips having probability 2−j2^{-j}; for a property of leaves, Pr⁡TreeP(d,λ)[⋅]\Pr_{\mathrm{Tree}_P(d,\lambda)}[\,\cdot\,] is the total probability of the leaves that have it. Compiling PP gives a three-tape machine MPM_P with a random tape, and to an input dd and a step limit λ\lambda the compilation attaches a step count TP(d,λ)T_P(d,\lambda) of MPM_P.

The randomized solver P*P_* is the register program with five registers that runs on an input dd of length LL in three stages: preprocessing, drawing of coins, and postprocessing.✦ The preprocessing stage reads from dd a game on nn vertices with weights ww and computes its top width B*=8nWB_*=8nW, where t(e)=(n+1)w(e)+1t(e)=(n+1)w(e)+1 are the transformed weights, W=max⁡{1,max⁡e|t(e)|}W=\max\{1,\max_e|t(e)|\}, and ℓ(B*)\ell(B_*) is the number of binary digits of B*B_*; it also computes the numbers g=ℓ(B*)+1,s=2⌈log⁡2(217(g+1))⌉,J=2(s(n+1))6+1,N=225000⌈log⁡2(L+2)⌉2,g=\ell(B_*)+1,\qquad s=2^{\lceil\log_2(2^{17}(g+1))\rceil},\qquad J=2\bigl(s(n+1)\bigr)^6+1, \qquad N=2^{25000\lceil\log_2(L+2)\rceil^2},(2) and the auxiliary data x(d)x(d) collects the game, B*B_*, ss, JJ, NN and the initial job, the single solve job with which the recursion starts, on the box [0,B*]V[0,B_*]^V with reference width B*B_*. The second stage draws a(d)=Nlog⁡2sa(d)=N\log_2 s fair coins one at a time and records them. The postprocessing stage cuts the coins into NN blocks of log⁡2s\log_2 s bits, each read as a uniform index in {0,…,s−1}\{0,\dots,s-1\}, and runs the recursive solver as a stack of jobs for NN steps, one index per step, starting from the initial job. The output of P*P_* is the set of vertices vv whose coordinate qvq_v in the vector qq returned by the first solve job exceeds B*/2B_*/2.

A solve job carries a solver input (a,b;B,α,β,k,m)(a,b;B,\alpha,\beta,k,m): a box with corners a≤ba\le b in ℤV\mathbb{Z}^V, a reference width B≥b−aB\ge b-a, positive rational support weights α,β\alpha,\beta and budgets k,mk,m; it returns a vector. An orientation is a choice between YY and ZZ together with a list of masks, each mask a list of truth values indexed by the vertices.✦ Among the jobs, an ask job returns the coordinatewise median of the vectors returned by JJ solve jobs, and an orientation job returns the majority choice of JJ orientation trials. The majority is strict, and the returned orientation carries the masks of all the trials.✦ A solve job whose budgets are small returns the small vector of the budgets and the box; otherwise a solve job on a box of width at most 128s128s is answered by the basic solver, the procedure for small boxes, which is run on the game and the box for 128ns128ns steps and returns a vector. The initial solve job carries the support weights α\alpha and β\beta, each the vector with every entry equal to 11, and the budgets k=m=nk=m=n, two rational numbers. On a wider box, a solve job first tightens the box. A tighten job asks with the kk-reduced budgets on the box; if some coordinate of the returned vector lies at least the grid width δ\delta, the box’s width divided by 4s4s, above the lower corner, it raises the floor of the box to that vector and tightens again. Otherwise it asks with the mm-reduced budgets and, if some coordinate of the returned vector lies at least δ\delta below the upper corner, it lowers the ceiling to that vector and tightens again; if neither happens the box is tight.

On the tight box, a solve job obtains an orientation from an orientation job and, for each mask of the orientation, asks on the box with the budgets reweighted by that mask, on the mm side if the orientation chooses YY and on the kk side if it chooses ZZ. It then calls itself on the box with its high cap at the cap width, the box’s width minus δ\delta, for YY, and with its low cap for ZZ, and returns the coordinatewise minimum for YY, the coordinatewise maximum for ZZ, of the vector this call returns and the vectors returned by the asks.

A single orientation trial on a box of width at most 128s128s marks the coordinates ii with w≤2(vi−ai)w\le 2(v_i-a_i), where vv is the vector returned by the basic solver, aa the lower corner and ww the width of the box; if the marked set has measure above one half for the budgets it returns YY with the complement of the set as its exception, and otherwise ZZ with the set as its exception.✦ On a wider box it computes ss centers, starting from the midpoint of the box, each next center being the clipped average of the answers of two ask jobs, with the kk-reduced and the mm-reduced budgets, on the box of width divided by 32s32s centered at the current center. For the last center vv and the midpoint mm of the box it marks the coordinates with s(vi−mi)>2ws(v_i-m_i)>2w and those with s(vi−mi)<−2ws(v_i-m_i)<-2w; if the first set has measure above one half it returns YY with its complement as exception, and if the second does it returns ZZ with its complement as exception. If neither does, it runs an orientation trial on the box of width divided by 88 centered at a center chosen by a random index, and extends the orientation returned by the two masks.

The compilation M*=MP*M_*=M_{P_*} of the solver is the machine of the main theorem. For constants KK and rr, the step limit of P*P_* on dd is λK,r(d)=cpre(d)+36a(d)+K(4a(d)+∥x(d)∥+3)r+20,\lambda_{K,r}(d)=c_{\mathrm{pre}}(d)+36\,a(d)+K\bigl(4a(d)+\|x(d)\|+3\bigr)^{r}+20,(3)✦ where cpre(d)c_{\mathrm{pre}}(d) is the step budget of the preprocessing stage and ∥x∥\|x\| is the size of the code of a datum xx; the third term is the step budget of the postprocessing stage. The total running time of P*P_* on dd is τK,r(d)=TP*(d,λK,r(d))\tau_{K,r}(d)=T_{P_*}(d,\lambda_{K,r}(d)), a step count of M*M_*.✦ The postprocessing cost cpost(z)c_{\mathrm{post}}(z) of an input zz of the postprocessing stage, recorded coins with auxiliary data, is the number of steps that stage is allowed on zz, the writing of its output included.✦

The Claim

Theorem 1 (Main theorem). There are a three-tape machine MM that reads one random bit per step and a real C>0C>0 such that, for every game GG, with LL the length of its input code dGd_G, some step count TT satisfies T≤2C(log⁡2(L+2))2andM halts within T steps on dG and every ρ∈{0,1}T,T\le 2^{C(\log_2(L+2))^2}\quad\text{and}\quad M\text{ halts within $T$ steps on $d_G$ and every }\rho\in\{0,1\}^T,(4)✦ #GoodM(G,T)≥782T.\#\,\mathrm{Good}_M(G,T)\ge\tfrac{7}{8}\,2^T.(5)✦

In the paper, the result reads: for a game GG on a finite directed graph (V,E)(V,E) with V={1,…,n}V=\{1,\dots,n\}, n≥1n\ge1, an ownership partition V=VMax∪VMinV=V_{\mathrm{Max}}\cup V_{\mathrm{Min}} and signed integer weights w:E→ℤw\colon E\to\mathbb{Z}, every vertex having an outgoing edge and self-loops and parallel edges permitted, in which the owner of a vertex chooses the next edge, both players may use strategies depending on the entire finite history, and a play π=(e0,e1,…)\pi=(e_0,e_1,\dots) has mean payoff MPw(π)=liminf⁡h→∞1h∑j<hw(ej)\mathrm{MP}_w(\pi)=\liminf_{h\to\infty}\frac1h\sum_{j<h}w(e_j), and for LL the total length of an explicit binary encoding of the graph, ownership and signed weights (endpoints and ownership charged), there is a uniform randomized algorithm that returns the entire set U={v∈V:some Max strategy σ has MPw(πv,σ,τ)≥0 for every Min strategy τ}U=\{v\in V:\text{some Max strategy }\sigma\text{ has }\mathrm{MP}_w(\pi_{v,\sigma,\tau})\ge0 \text{ for every Min strategy }\tau\}, where πv,σ,τ\pi_{v,\sigma,\tau} is the play from vv in which Max follows σ\sigma and Min follows τ\tau, correctly with probability at least 7/87/8 and whose total cost on every random tape is at most 2C(log⁡2(L+2))22^{C(\log_2(L+2))^2} bit operations, for an absolute constant C>0C>0, in a standard model polynomially equivalent to a uniform probabilistic Turing machine, the bound including preprocessing, recursive calls, intermediate arithmetic and random-bit generation.

What Is Checked

The main theorem is stated over three-tape machines with a random tape and over games GG, through their input codes dGd_G and their winning sets U(G)U(G).

Take constants KK and rr with cpost(z)≤K(∥z∥+1)rc_{\mathrm{post}}(z)\le K(\|z\|+1)^r for every input zz of the postprocessing stage. The solver then satisfies, for every bit string dd and every game GG, every leaf of TreeP*(d,λK,r(d)) has halted,\text{every leaf of }\mathrm{Tree}_{P_*}\bigl(d,\lambda_{K,r}(d)\bigr)\text{ has halted},(6)✦ PrTreeP*(dG,λK,r(dG))[output=U(G)]≥78.\Pr_{\mathrm{Tree}_{P_*}(d_G,\,\lambda_{K,r}(d_G))}\bigl[\text{output}=U(G)\bigr] \ge\tfrac{7}{8}.(7)✦

For all constants KK and rr there is a real C>0C>0 such that, for every bit string dd of length LL, τK,r(d)≤2C(log⁡2(L+2))2.\tau_{K,r}(d)\le 2^{C(\log_2(L+2))^2}.(8)✦

Let PP be a register program, GG a game and λ\lambda a step limit, put T=TP(dG,λ)T=T_P(d_G,\lambda), and suppose that every leaf of TreeP(dG,λ)\mathrm{Tree}_P(d_G,\lambda) has halted. Then MP halts within T steps on dG and every ρ∈{0,1}T,M_P\text{ halts within $T$ steps on $d_G$ and every }\rho\in\{0,1\}^T,(9)✦ 2TPrTreeP(dG,λ)[output=U(G)]≤#GoodMP(G,T),2^T\Pr_{\mathrm{Tree}_P(d_G,\lambda)}\bigl[\text{output}=U(G)\bigr] \le\#\,\mathrm{Good}_{M_P}(G,T),(10)✦ and if the probability in (10) is at least 7/87/8, then 7⋅2T≤8#GoodMP(G,T).7\cdot2^T\le 8\,\#\,\mathrm{Good}_{M_P}(G,T).(11)✦