Quasipolynomial algorithms for mean-payoff games

Source and verification

This article explains family 104 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Infinite plays on a finite graph

A mean-payoff game has a finite directed graph with at least one outgoing edge at every vertex. Each vertex belongs to Max or Min, and its owner chooses the next edge. Edges have signed integer weights $w(e)$. An infinite play $\pi =e_0{e}_1\cdots$ has payoff

$${\mathrm{MP}}_w(\pi )=\underset{T\to \infty }{\mathrm{liminf}}\frac{1}{T}\sum _{t=0}^{T-1}w(e_t).$$

Max wins the zero-threshold game when this payoff is nonnegative. A strategy may depend on the entire finite history; a positional strategy depends only on the current vertex. The winning set consists of starts from which one Max strategy succeeds against every Min strategy. The order of these quantifiers matters.

Let $L$ be the complete binary input length, including endpoints, ownership, and weights. A weight $2^b$ uses only $b+1$ binary digits. A bound polynomial in the largest absolute weight can therefore be exponential in $L$; this is the difference between a pseudopolynomial bound and a bound in encoded input length.

Two companion claims

The deterministic manuscript returns the entire winning set in

$$2^{C({\log }_2(L+2){)}^2}$$

bit operations, for an absolute constant $C$. The randomized manuscript has the same form of time bound on every random tape and returns the entire set correctly with probability at least $7/8$. Both allow self-loops, parallel edges, and arbitrary history-dependent strategies. (OpenAI, 2026) (OpenAI, 2026b)

This is quasipolynomial time, of the form $L^{O(\log L)}$, rather than polynomial time. The probability concerns the whole output, not an individual vertex. The deterministic paper also reduces exact rational values and globally optimal positional strategies to winning-set queries. The randomized paper gives a checkable potential and a version that either returns a verified answer or reports failure; repetition yields an always-correct algorithm with an expected quasipolynomial bound.

🏷️ Cycle signs and bounded potentials

For $n$ vertices, replace each weight by

$$\hat{w}(e)=(n+1)w(e)+1.$$

A simple directed cycle of length $1\le \ell \le n$ and original sum $c$ now has sum $(n+1)c+\ell$. If $c\ge 0$, this is positive. If $c\le -1$, it is at most $-(n+1)+n=-1$. Thus original zero cycles join the nonnegative side, and no transformed simple cycle has sum zero. The integer and simple-cycle hypotheses are exactly what make this separation work.

For a potential $z\in {\mathbb{Z}}^V$, define at a Max vertex

$$F_i(z)=\underset{e:i\to j}{\max }(\hat{w}(e)+z_j).$$

At a Min vertex, replace the maximum by a minimum. The resulting operator preserves coordinatewise order and obeys $F(z+c1)=F(z)+c1$. In an integer box $[A,u]$, a subsolution satisfies $x_i\le F_i(x)$ wherever $x_i>A_i$. A supersolution satisfies $y_i\ge F_i(y)$ wherever $y_i<u_i$. No inequality is imposed on the corresponding excluded face.

The finite-box comparison lemma imported from the randomized companion gives a unique clipped fixed point

$$h=\min \{u,\max \{A,F(h)\}\},$$

and $x\le h\le y$ for every subsolution and supersolution. This conclusion uses the transformed cycle condition; it is not a property of arbitrary monotone maps. In a sufficiently wide box $[0,D{]}^V$, each coordinate of $h$ lies near one boundary. The upper band identifies Max’s winners and the lower band Min’s winners.

For a one-vertex game with an original zero-weight self-loop, the transformed operator is $F(z)=z+1$. Clipped iteration from zero takes $D$ steps to reach $h=D$. It is correct but slow in the binary encoding of $D$. The new recursions aim to determine the relevant boundary information without walking through all these integers.

🏷️ Simultaneous witnesses in the deterministic recursion

Give each vertex positive rational masses $a_i,b_i$. A qualifying Max witness is a subsolution whose support $\{i:x_i>A_i\}$ has total $a$-mass at most one. A qualifying Min witness has support $\{i:y_i<u_i\}$ of total $b$-mass at most one. Each witness requires the appropriate labels near its favored boundary.

The algorithm’s contract covers all qualifying witnesses simultaneously. Initially $a_i=b_i=1/n$, so the genuine box solution qualifies on both sides. The contract will therefore determine its boundary bands without computing it.

Translations near a witness’s largest deviation from an integer pivot move the comparison into a narrower box; clipping retains only coordinates near that extremum. The proof checks that the subsolution or supersolution inequalities survive, with support contained in the original support.

Two passes move the pivot first downward and then upward. At a stationary call, any still-unsettled witness must put more than $3/4$ of its relevant mass near the appropriate extremum. Otherwise the recursive labels would have forced another movement. A half-width call labels these large-mass regions. Its labels tell the algorithm which masses to decrease and which to increase, preserving every unsettled witness while increasing each product $a_i{b}_i$ by a fixed factor.

Starting from $1/n^2$, only $O(\log (n+1))$ such product increases can occur before every coordinate is excluded from at least one type of support. At most one child retains both mass vectors; that child decreases the box width. Counting where the limited number of mass increases can occur along width-reduction paths produces the quasipolynomial bound. Exact rational arithmetic and its operand lengths are part of that count. (OpenAI, 2026a)

🏷️ Fixed comparisons in the randomized recursion

The randomized companion has a different contract: for each fixed admissible comparison vector, a high-probability event controls all its coordinates. It does not assert one event that works for every vector simultaneously. (OpenAI, 2026b)

A sampled orientation procedure either protects the threatened boundary or finds a small-measure set carrying much of that particular witness’s support. Reweighting then permits a recursive call with lower support complexity. The sampled comparison is fixed before the child’s fresh randomness is drawn, so the child’s pointwise guarantee applies after conditioning.

At the top box, the deterministic vector $h$ is a qualifying comparison on both sides. Combining its two success events sandwiches the returned potential between $h$ and itself, giving exact recovery of all coordinates. The proof analyzes the one unchanged-parameter continuation chain together; repeatedly amplifying every call indiscriminately would spoil the cost estimate. Termination and time hold even on unsuccessful tapes.

🏷️ Chance transitions and discounted comparison

The stochastic companion adds chance vertices with explicit rational transition probabilities. Players observe the history and may randomize their strategies. Its value convention is

$$\mathrm{val}(i)=\underset{\sigma }{\sup }\underset{\tau }{\inf }{\mathbb{E}}_{i,\sigma ,\tau }[{\mathrm{MP}}_w].$$

The expectation is outside the pathwise lower limit. It is not an almost-sure winning condition. The manuscript claims the same deterministic quasipolynomial bit bound for the exact set $\{i:\mathrm{val}(i)\ge 0\}$, including zero values. The binary lengths of rewards and probability numerators and denominators all count toward $L$. (OpenAI, 2026c)

For a discount parameter $0<u<1$, take the maximum, minimum, or chance average of

$$uw(e)+(1-u)t_j$$

over outgoing edges. This defines a contraction $F$ with

$$F(t+c1)=F(t)+(1-u)c1.$$

Rational bounds for fixed positional strategy pairs give a nonzero-value gap at least $1/H$, where $H$ has polynomial binary length. A sufficiently small discount makes its fixed point uniformly close to the undiscounted values. Direct contraction iteration can still require time proportional to $1/u$, so the source extends the simultaneous boundary-labeling procedure instead. Subsolutions translate downward and supersolutions upward; these signs preserve the discounted inequalities. The value gap then turns sufficient numerical accuracy into an exact threshold decision.

As a concrete consequence, make a reachability target absorbing with self-loop reward $+1$ and give every other edge reward $-1$. For every play,

$$\mathrm{MP}=21_{\{\text{target reached}\}}-1.$$

If the target is reached, the finite preceding costs vanish in the average; otherwise every reward is $-1$. Taking expectation and strategy extrema shows that a reachability probability threshold of $1/2$ becomes mean-payoff threshold zero. This also illustrates why the stochastic statement uses expected payoff.

🏷️ Parity and the cost of restarting

The fourth setting places a nonnegative integer priority and an integer reward at every vertex. Max must achieve both nonnegative liminf average reward and an even least priority among vertices visited infinitely often. The parity companion claims the same deterministic quasipolynomial bit bound, with no fixed bound on the number of priorities. It uses the deterministic ordinary mean-payoff solver as an explicit input. (OpenAI, 2026b)

Infinite memory can matter for the conjunction

Let Max control two vertices. Vertex $a$ has reward zero, odd priority one, and choices to stay at $a$ or visit $b$. Vertex $b$ has reward $-1$, even priority zero, and returns to $a$.

Staying forever at $a$ satisfies mean payoff but fails parity. Repeating a fixed finite waiting pattern visits $b$ with positive frequency and gives negative mean payoff. Waiting $1,2,3,\dots$ rounds at $a$ between visits to $b$ visits the even priority infinitely often while making the density of negative rewards tend to zero. A deterministic finite-memory strategy produces an eventually periodic play here and cannot satisfy both conditions.

A dominion is a set in which one player can keep play and win. The recursion protects all dominions below two size bounds, one per player. At most one child retains both bounds; other children halve one, while recursive calls remove the least priority. This gives a quasipolynomial number of mean-payoff queries of polynomially bounded encoded size.

Combining the strategies requires more than a limiting statement for each uninterrupted play. Writing $R_{\pi }(t)$ for the total reward of a length-$t$ prefix, the source proves uniform estimates of the form

$$R_{\pi }(t)\ge -ϵt-C_{ϵ}.$$

Playing a mean-payoff policy for increasingly long rounds between priority visits makes the number of restarts by time $T$ only $O(\sqrt{T})$. Bounded overhead per restart then contributes $O(T^{-1/2})$ to the average. This is the quantitative fact that lets the recursive parity strategies preserve mean payoff.

🏷️ Key steps and proof outlines

A comparison principle extracted from cycle signs

The transformed weights make every simple cycle strictly positive or strictly negative. The finite-box comparison proof supposes that a subsolution $y$ exceeds a supersolution $z$ somewhere and puts $d={\max }_i(y_i-z_i)>0$. At a coordinate achieving this maximum, $y_i>A_i$ and $z_i<u_i$: positivity of the difference prevents either excluded boundary face. Both witness inequalities therefore apply, and monotonicity and translation invariance give

$$d\le F_i(y)-F_i(z)\le d.$$

Every inequality is an equality. At a Max vertex choose an edge attaining $F_i(y)$; at a Min vertex choose one attaining $F_i(z)$. The equalities force its endpoint also to achieve difference $d$, with the potential inequalities tight along the chosen edge. Repeating on a finite graph gives a directed cycle, and summing the tight potential equalities around it gives weight zero, contradicting the transformed cycle condition.

Thus the boundary exclusions are harmless exactly where the maximum-difference argument is used. The comparison then gives uniqueness of the clipped solution and supports the boundary-band characterization. The deterministic and randomized manuscripts consume this interface rather than carrying out one-unit value iteration. (OpenAI, 2026a) (OpenAI, 2026c)

Why the mass recursion has few expensive events

At a recursive call, let $S$ be the support of a particular witness, and let $a(S)={\sum }_{i\in S}{a}_i$. Qualifying witnesses satisfy $a(S)\le 1$. In a pass where a child’s masses are multiplied by $4/3$, any portion of $S$ with parent mass at most $3/4$ still qualifies for that child. The contrapositive is useful: if a witness’s claim survives the pass unresolved, its relevant near-extremal portion must have mass greater than $3/4$.

The subsequent half-width call identifies these heavy portions. Reweighting is designed so that each unresolved witness retains total allowed mass while every coordinate product $a_i{b}_i$ grows by a fixed factor. Starting with products $n^{-2}$ permits only $O(\log n)$ such growth events before a coordinate cannot participate on both sides. This is a resource count on the recursion tree, not a bound on numerical potential size.

To see the resulting complexity shape, write $d$ for a logarithmic width parameter and $r=O(\log n)$ for the remaining mass-growth allowance. There is at most one branch that spends width without reducing this allowance. Other branches spend one of the $r$ exceptional events. Counting the placements of these events among $O(d)$ width levels gives a bound of the shape $(d+r{)}^{O(r)}$, up to the source’s fixed branching factors. Since encoded widths have polynomially bounded logarithms, this produces quasipolynomial rather than pseudopolynomial dependence. Exact arithmetic must still be charged separately.

The sign of a discounted translation

For the stochastic companion, $F(x+c1)=F(x)+\gamma c1$ with $0<\gamma <1$. If $y\le F(y)$ and $t\ge 0$, then

$$y-t1\le F(y)-t1\le F(y)-\gamma t1=F(y-t1).$$

Thus a downward translation preserves a subsolution. An upward translation preserves a supersolution by the reverse calculation. Clipping to a narrower box then uses monotonicity and equality on the surviving support. These inequalities are the bridge allowing the deterministic witness recursion to handle chance averages. They also show why translating in the opposite directions would not follow from the same argument. (OpenAI, 2026d)

Restarting without losing a liminf guarantee

In the parity companion, concatenate rounds whose $j$th round includes at least $j$ steps. After $m$ completed rounds the total length is at least of order $m^2$, so at most $O(\sqrt{T})$ rounds can have completed by time $T$. A round may be much longer, or continue indefinitely in a winning component. Suppose each excursion and restart costs at most a fixed $C$, and each round satisfies its uniform prefix estimate with tolerance $ϵ$. At time $T$ the accumulated lower bound has the form

$$R(T)\ge -ϵT-O_{ϵ}(\sqrt{T}).$$

Dividing by $T$ and taking the lower limit gives at least $-ϵ$; the same fixed strategy satisfies this bound for every $ϵ>0$, so its liminf is at least zero. Uniform control of every prefix is needed because $T$ may stop midway through a round. If infinitely many rounds finish, the designated even-priority region is visited infinitely often. If only finitely many finish, the remaining tail stays in its winning component strategy, which supplies the parity condition. This is the quantitative composition argument behind the example requiring infinite memory. (OpenAI, 2026b)

See Also

• Logarithmic-space derandomization studies a different recursive numerical algorithm where memory, termination, and precision also require separate accounting.
• Approximation hardness concerns finite constraint optimization; the finite games here generate infinite plays with long-run objectives.

🏷️ Manuscripts and verification scope

• Turn-Based Stochastic Mean-Payoff Games in Deterministic Quasipolynomial Time — pinned manuscript and companion source.
• Mean-payoff parity games in quasipolynomial time — pinned manuscript and companion source.
• Deterministic quasipolynomial-time mean-payoff games — pinned manuscript and companion source.
• Randomized quasipolynomial-time mean-payoff games — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. Its coverage is narrower than this four-manuscript article: it lists a finite counterexample to a particular optimization procedure and a randomized mean-payoff winning-set algorithm. The listed finite counterexample is not a formalization of the deterministic solver. The deterministic, stochastic, and mean-payoff-parity headline algorithms are not listed as comparator results on this page. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. Deterministic quasipolynomial-time mean-payoff games.

🐻  OpenAI 2026b. Mean-payoff parity games in quasipolynomial time.

🐻  OpenAI 2026c. Randomized quasipolynomial-time mean-payoff games.

🐻  OpenAI 2026d. Turn-Based Stochastic Mean-Payoff Games in Deterministic Quasipolynomial Time.