VibeMathedMath problems solved with AI
Sign in

Quasipolynomial-time solution of mean-payoff games with binary weights

In a finite two-player mean-payoff game on a directed graph with integer edge weights ww given in binary, Max wins from a vertex if she can force lim inf⁡T→∞1T∑t<Tw(et)≥0\liminf_{T\to\infty}\frac1T\sum_{t<T}w(e_t)\ge0. Ehrenfeucht and Mycielski proved positional determinacy, which puts the threshold problem in NP∩coNP\mathrm{NP}\cap\mathrm{coNP}, and Zwick and Paterson (1996) gave pseudopolynomial algorithms, polynomial in the largest weight but exponential in its bit length; the best general bounds were randomized subexponential. The quasipolynomial algorithm for parity games (Calude, Jain, Khoussainov, Li and Stephan) does not transfer, since the reduction runs from parity to mean payoff. Can the winning regions of mean-payoff games be computed in polynomial time, or at least in quasipolynomial time, in the binary input length?

Result
Proved(see note)
Status
Partial result
AI contribution
AI-discovered
Method
Argument
Field
Algorithmic game theory; games on graphs; complexity of NP and coNP problems
Posed by
Uri Zwick and Mike Paterson, The complexity of mean payoff games on graphs (1996), as cited by the manuscript; the question is the polynomial-time status of a problem in NP and coNP
Year posed
1996
Years open
30y
Solved
2026-09-25
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Unreviewed
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
42 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Claims a deterministic algorithm computing the exact set of vertices from which Max can force nonnegative liminf mean payoff, for arbitrary signed binary weights, self-loops and parallel edges, in 2O((log⁡(L+2))2)2^{O((\log(L+2))^2)} bit operations; a reduction gives exact rational values and optimal positional strategies for both players, energy-game minimum credits, and tropical feasibility tests within the same bound. A randomized companion of the same date gives a Las Vegas algorithm with a polynomial-time certificate check. It does NOT give a polynomial-time algorithm, which the paper names as a further improvement. Priority note: Truffet (arXiv:2603.26423, and a 2025 HAL note) claims a strongly polynomial algorithm via tropical optimization; the randomized companion gives a small example on which the printed rule of version 4 loses the optimum, and makes no claim about the 2025 note.

What the AI did

The release README says all results were produced by an unreleased internal OpenAI model, the vast majority by one fixed procedure using on average about three hours of ChatGPT Pro thinking compute per result. Its named exceptions (the Hodge conjecture for CM abelian varieties, and the Re(s) > 11/12 zero-free region, whose write-up was human edited for readability) do not concern this family. The manuscripts are credited to OpenAI with no human author named. The family has four manuscripts. The deterministic algorithm (25 September 2026) imports only the finite-box comparison facts from the randomized companion of the same date; the two October 5 manuscripts extend the method to turn-based stochastic games and to mean-payoff parity games. The randomized companion's main theorem has a Lean formalization in the release.

Verification

No independent mathematician has checked this yet. Theorem 1.1 of the principal manuscript was read against the question: a uniform deterministic algorithm outputs the full zero-threshold winning set with 2C(log⁡2(L+2))22^{C(\log_2(L+2))^2} bit operations, LL the complete binary input length; Section 7 adds exact values and optimal positional strategies. The release formalizes only the randomized companion: ComparatorChallenges/RandomizedMeanPayoff.lean (declaration OAI.randomized_quasipolynomial_mean_payoff, file OAI/Computability/RandomMean/Main.lean, listed in formalization.yaml) states that one Turing machine with random bits halts within quasipolynomially many steps on every tape and outputs the exact winning set on at least 7/8 of tapes. That is a randomized form of the result, not the deterministic headline, so under the strict tier rule this entry stays Unreviewed. Not rebuilt here. A second Lean challenge, TruffetCounterexample, concerns an appendix about another author's proposed algorithm and is not in formalization.yaml.

Sources

Changelog1 change

Discussion