Mean Payoff Games: OpenAI Proof Breaks the Binary-Weight Bottleneck in Quasipolynomial Time

A weight with a hundred binary digits can derail an algorithm that looks efficient on small numbers. Mean payoff games have carried that trap for decades: compact inputs can encode enormous numerical work. OpenAI’s September 25, 2026 manuscript presents a deterministic algorithm that computes every zero-threshold winner in quasipolynomial time measured against the complete binary input length. Reductions also recover exact values and optimal memoryless strategies.

The advance concerns a worst-case mathematical guarantee. Polynomial time remains open, and the manuscript supplies no practical speed benchmark. Its central trick is to classify potential-function boundaries without climbing through an enormous numerical range, using stationary pivots and carefully reweighted proof witnesses.

1. What Are Mean-Payoff Games? The Infinite Game Behind the Proof

A finite directed graph has $n$ vertices, each owned by Max or Min, and every vertex has an outgoing edge. Its owner chooses the next move. Each edge carries a signed integer weight. Max wants a large long-run average; Min wants a small one. For the infinite edge sequence $\pi$, the payoff is:

Here $T$ counts moves. The limit inferior captures the lowest asymptotic average when ordinary averages fail to converge. The zero-threshold question asks whether Max can guarantee a nonnegative payoff against every opposing strategy, including strategies using the entire history.

For a mean payoff games example, let Max’s vertex A offer a weight-zero edge to B or C. At Min’s vertex B, self-loops have weights +2 and −1. Vertex C has only a +1 self-loop. Min makes B worth −1, so Max chooses C and obtains value +1 from A. The single initial zero disappears from the long-run average.

2. Why Mean-Payoff Games Resisted Faster Algorithms for Decades

Classical positional determinacy says both players have optimal strategies depending only on the current vertex. This places the threshold decision problem in $\mathrm{NP}\cap\mathrm{coNP}$: each side has a polynomially checkable strategy certificate. It does not give a fast method for finding those certificates.

Earlier pseudopolynomial methods could depend polynomially on the largest absolute weight. A weight such as $2^{100}$ takes only 101 binary digits, while work proportional to its magnitude is astronomical. That mismatch is the binary-weight bottleneck in mean payoff games complexity.

Quasipolynomial parity-game algorithms did not automatically fix it. Parity games reduce to mean-payoff games with large but succinctly encoded weights. That reduction points toward the harder numerical problem, so reversing its algorithmic implication is invalid.

The challenge persists despite the graph being finite. Strategies generate infinite plays, and the algorithm must classify all possible opposition without listing those plays. Positional certificates compress the answer, but searching the space of possible policies can still be expensive.

Computational measures need the same care elsewhere: space simulation bounds measure memory, while quantum query complexity counts input accesses. Here the accounting covers deterministic bit operations, including arithmetic.

3. What OpenAI’s Deterministic Quasipolynomial-Time Proof Establishes

Theorem 1.1 in the deterministic mean-payoff games manuscript returns the complete winning set, rather than answering for one selected start. Let $L$ denote the full explicit binary encoding of vertices, ownership, edge endpoints, and weights. The bound is:

Quasipolynomial growth lies beyond a fixed polynomial bound, yet below familiar exponential growth in input length. The theorem includes preprocessing, recursion, exact arithmetic, and the entire output. Random success is unnecessary.

OpenAI describes the broader release as results produced by an internal frontier model in its mathematics release announcement. That attribution does not establish independent validation of every theorem. The published Lean scope documentation covers the related randomized algorithm and a finite counterexample to an older optimization step. It does not document complete formal verification of this deterministic theorem. As with proof formalization in Lean, the checked statement and its scope matter.

4. The First Proof Step: Perturbing Weights to Eliminate Zero Cycles

Zero-weight cycles obstruct the comparison machinery. The proof transforms each original edge weight using:

A simple cycle has length $\ell$ between 1 and $n$. If its original integer sum is $c$, its transformed sum is $(n+1)c+\ell$. For $c\geq0$, this is positive. For $c\leq-1$, it is negative. No simple cycle now has zero sum.

The transformation deliberately makes originally zero cycles positive. It preserves the distinction needed for the nonnegative threshold, rather than preserving every cycle’s original sign literally. For $n=3$, a two-edge cycle totaling −1 becomes −2; one totaling zero becomes +2. The numerical weights grow, but their binary descriptions grow modestly. Positional determinacy and cycle arguments carry the resulting threshold partition back to the original game.

5. Potential Functions, Finite Boxes and the Comparison Theorem

Assign each vertex an integer potential $z_i$. The operator $F$ evaluates the best or worst transformed edge-plus-successor potential according to ownership:

A finite box restricts each coordinate between a lower endpoint $A_i$ and an upper endpoint $u_i$. Clipping means replacing any proposed coordinate outside that interval by the nearest endpoint.

A subsolution $x$ satisfies $x_i\leq F_i(x)$ wherever $x_i>A_i$. A supersolution $y$ satisfies $y_i\geq F_i(y)$ wherever $y_i<u_i$. The excluded boundaries are essential: neither condition is imposed everywhere.

Two operator properties make translations useful. Increasing every input coordinate cannot decrease any output coordinate. Adding the same integer to every coordinate adds that integer to every output as well. This common-shift invariance lets the proof relocate a witness without changing the local inequality it must satisfy before clipping.

Lemma 2.1 imports the companion paper’s finite-box comparison theorem and basic iteration. For this perturbed operator, there is a unique clipped fixed point $h$, and every such pair satisfies $x\leq h\leq y$. Monotonicity alone would not establish uniqueness. The cycle hypothesis matters. Basic iteration finds $h$, but on a wide box it can require work proportional to numerical width. The new algorithm avoids that cost.

6. How a Wide Potential Box Separates Winners From Losers

Let $W$ be the largest absolute transformed weight. Choose $D_0$ as the smallest power of two at least $64(n+1)(W+1)$. Proposition 2.2 places every coordinate of the solution in one of two disjoint bands:

Why can nothing remain in the middle? At an interior coordinate, an edge attains the exact potential equality. Following such edges must reach a boundary within $n$ moves. Repeating a vertex first would create a tight simple cycle with transformed sum zero, which the perturbation forbids. Each edge changes potential by at most $W$, giving the distance bound.

The cycle argument also controls arbitrary nonperiodic opposition. Remove simple cycles from any finite play prefix. What remains has fewer than n edges, so its possible negative contribution stays bounded independently of the prefix length. Dividing by a growing length makes that transient contribution vanish.

In the upper band, Max selects edges satisfying the subsolution inequality. At Min vertices every edge satisfies it. These choices remain in the band, and potential differences telescope around cycles. Original cycle sums are nonnegative. The lower band gives Min the dual guarantee, with original upper limiting average at most $-1/n$. Thus the bands identify winners without requiring an explicit wide-box solution.

7. Witnesses, Boundary Labels and Translation Into Narrower Boxes

The recursion asks for plus and minus labels that satisfy many potential certificates simultaneously. In a width-$D$ box, a Max witness is a subsolution whose support, the coordinates above their lower boundaries, has total positive rational mass at most one. Min uses supersolutions, coordinates below their upper boundaries, and separate masses.

A witness claims coordinates within $D/32$ of its favorable boundary. Opposing claims cannot coincide because comparison orders every subsolution below every supersolution. Initially each coordinate receives mass $1/n$ on both sides, so every support qualifies and the box solution’s claims settle every winner.

Support mass is an accounting constraint, not a probability of winning. There is no random sampling here. Nor does restricting a witness support delete vertices or edges from the game. Each recursive call retains the original graph and changes the box and mass parameters.

For recursion, a pivot $k$ sits near the box center. A Max witness’s peak is $\max_i(x_i-k_i)$; its gap at a coordinate measures distance below that peak. Translate the whole vector by one common amount, then clip at the narrower box’s bottom. Its surviving support is exactly the coordinates with gap below the child width. Near-peak coordinates become upper-boundary claims. Min uses the dual construction. Supports only shrink, preserving eligibility under unchanged masses. Witnesses are proof objects, never enumerated by the executable algorithm.

8. Inside OpenAI’s Deterministic Recursion: Downward and Upward Pivot Passes

For $D\geq4096$, set center $c=A+D/2$, movement cap $M=D/8$, narrow width $q=D/128$, and step $p=q/32$. Each update uses one child’s entire label vector simultaneously.

The protected peak explains safety. In the downward pass, every Max gap at most $p$ becomes a child claim and receives plus, so that coordinate stays still. Coordinates farther away move by at most $p$ and cannot overtake the peak. Min receives the symmetric protection upward.

The algorithm records downward marks where the stopped pivot lies more than $D/32$ below the center, and upward marks where the final pivot lies more than that distance above it. Peak protection proves that these marks cannot overwrite a claim belonging to the opposing witness type.

The final stationary call is decisive. Suppose a Min witness still claims an unmarked coordinate after the downward pass. Its maximizing pivot deviation lies above the lower movement cap. If its near-peak support had original Min mass at most $3/4$, multiplying by $4/3$ would leave it eligible. The child would force minus at a maximizer, requiring movement. Stationarity contradicts that possibility.

Consequently the unresolved near-peak mass exceeds $3/4$. This Min certificate survives the upward pass because its near-peak set can only grow. The upward stopping call supplies the matching Max certificate. These inequalities turn stopped motion into usable evidence.

9. Mass Reweighting: Why Every Unresolved Witness Eventually Disappears

A child of width $D/2$ now labels the certified near-peak sets. They fall within its claim margin, so every unresolved witness gets its favorable label on mass greater than $3/4$. These provisional labels guide reweighting, rather than directly settling the parent’s claims.

At a plus label, multiply Max mass by $4/5$ and Min mass by $8/5$. At minus, reverse those multipliers. For an unresolved Max support $S$, write $Q_+$ for the provisional plus coordinates. Its new mass obeys:

The Min calculation is symmetric. Unresolved witnesses therefore remain eligible in the continuation on the original box. Meanwhile every coordinate’s mass product grows by $(4/5)(8/5)=32/25$, independently of its label.

Starting from product $1/n^2$, only logarithmically many such increases fit before every product exceeds one. At that base case each coordinate is too heavy for at least one witness type, allowing a direct safe label. Witnesses need not literally disappear together: the precise progress measure is growing mass products alongside shrinking widths.

10. Why the Recursion Is Correct and Its Running Time Is Quasipolynomial

Correctness uses induction on a rank combining logarithmic width with the remaining mass-growth budget. Pivot-pass children increase products by $4/3$; the continuation increases them by $32/25$. The provisional child alone preserves masses, but halves width. Every child decreases the rank.

Marked coordinates receive safe overrides: downward marks cannot contain Max claims, and upward marks cannot contain Min claims. Every remaining claim belongs to a witness preserved by reweighting, so induction makes the continuation respect it. The guarantee holds simultaneously for all witnesses.

At small width, below 4096, direct iteration becomes safe: it needs at most one plus $nD$ operator evaluations. Each evaluation scans the explicit edges. This is where the executable procedure actually evaluates the game operator. The large-width recursion manipulates labels and exact mass parameters instead of searching for witness vectors.

Each pass uses only linearly many child calls in $n$. A branch has polynomial depth in $L$, but only $O(\log(n+1))$ mass-budget decreases. Crucially, only one child preserves that budget. Counting where the other branches occur gives the quasipolynomial bound. Integer coordinates and rational masses retain polynomial bit length; floating-point approximations are unnecessary.

This is exact worst-case complexity, not an approximation ratio like the factor-two superstring guarantee, or a competitive ratio like the randomized k-server bound. Those guarantees answer different algorithmic questions.

11. Exact Game Values, Optimal Positional Strategies and the Remaining Open Problem

Fixing both optimal positional strategies eventually repeats a simple cycle. Hence each exact value is rational with denominator at most $n$. To test threshold $p/q$, replace weights by $qw(e)-p$. Polynomially many threshold queries narrow each value to an interval containing only one eligible rational.

Strategies require additional care. An edge between equal-value vertices can still be a losing choice if it traps play in an inferior cycle. The paper tests edge restrictions while preserving the entire value vector. Max and Min are recovered separately from fresh copies of the original game, yielding strategies optimal from every vertex against history-dependent opposition.

Direct corollaries decide prescribed-credit one-resource energy games and compute minimum winning credits, including infinity when no finite credit works. Other classical reductions give tropical feasibility and tropical-rank tests at fixed corank. These are precisely scoped consequences, not a general polynomial-time tropical optimization result.

Finite minimum energy credits are bounded by $(n-1)W_0$, where $W_0$ is the largest absolute original weight. That bound supports binary search over credit values, rather than an array whose size depends on their numerical magnitude.

For developers, implementation and benchmarking remain work to do: the proof establishes no production speedup. The difference between a complexity theorem and a usable solver also matters in exact three-machine scheduling and maximum cardinality matching. Mean payoff games now have a deterministic quasipolynomial construction in this manuscript; polynomial time remains the next question. Follow Binary Verse AI for research explainers that trace the argument from its original bottleneck to its actual guarantee.