oai-math-revised beta

Browse › Theoretical computer science › 104 Quasipolynomial algorithms for mean-payoff, stochastic and parity games

Randomized quasipolynomial-time mean-payoff games

OpenAI · September 25, 2026

Lean

Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion

Edit NOTES.md · Existing issues · Source on GitHub

Abstract

We give a randomized algorithm that computes the complete zero-threshold winning set of a finite mean-payoff game with arbitrary signed integer edge weights encoded in binary. For total explicit input length L, it uses $2^{O((\log(L+2))^2)}$ bit operations on every random tape and is correct with probability at least 7/8. A polynomial-time check certifies the winning regions and positional strategies for both players or reports failure. Independent repetition therefore gives an always-correct algorithm with the same expected quasipolynomial bit bound.

If the PDF does not display here, open it directly: Open PDF.

Notes

No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.

Automatically collected notes (unreviewed)

work in progress

Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.

Formalization

  • OpenAI math release, Lean scope notes for family 104 (lean/docs/104.md, release of 6 Oct 2026). Describes two formalized statements: this paper's randomized algorithm, which outputs the complete zero-threshold winning set with probability at least 7/8 in quasipolynomial bit time on every tape, and a finite counterexample to one step of Truffet's elimination procedure (the subject of this paper's appendix). [family-level]
  • OpenAI math release, RandomizedMeanPayoff.lean (comparator statement) (lean/ComparatorChallenges, release of 6 Oct 2026). States OAI.randomized_quasipolynomial_mean_payoff: a fixed randomized machine halts on every random tape within $2^{C(\log_2(L+2))^2}$ steps and is correct on at least 7/8 of tapes; the proof is not in this comparator file.

Possibly relevant literature (found by the agent, not checked)

Digests and expositions

  • Latent Seminar, Quasipolynomial algorithms for mean-payoff games (7 October 2026). Explains the four manuscripts' potential comparisons, recursive methods, stochastic discounting, and parity strategy composition, explicitly without independently verifying the complete proofs. [family-level]
  • AI Proved What?, Who wins in the long run? (Episode 104, October 2026; status updated 19 October 2026). Provides an animated exposition and transcript covering all four claims, the binary-weight complexity distinction, and the reported limits of Lean coverage. [AI-generated per source] [family-level]

News and blogs

Elsewhere

Independent sites; their content is not reviewed here.

Cite

@misc{OAI:Randomized-quasipolynomial-time-mean-payoff-games-September-25-2026,
  author = {{OpenAI}},
  title = {{Randomized quasipolynomial-time mean-payoff games}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Randomized-quasipolynomial-time-mean-payoff-games-September-25-2026/paper.pdf}{OAI:Randomized-quasipolynomial-time-mean-payoff-games-September-25-2026}},
  year = {2026}
}

Lean formalization

OpenAI provides Lean files for this family: lean/docs/104.md. The Lean statements have not been checked by people against the paper's claims.

Family 104: Quasipolynomial algorithms for mean-payoff, stochastic and parity games

Gives deterministic algorithms using $2^{O((\log(L+2))^2)}$ bit operations, for complete binary input length L, for ordinary mean-payoff games and two separate extensions. They compute exact values and optimal positional strategies in ordinary games, the nonnegative expectation-of-liminf value set in turn-based stochastic games, and the winning set for nonnegative liminf mean payoff conjoined with parity. Signed rewards, rational chance probabilities, and parity priorities are unrestricted and binary-encoded.

Other papers in this family: