oai-math-revised beta

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

Turn-Based Stochastic Mean-Payoff Games in Deterministic Quasipolynomial Time

OpenAI · October 5, 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 uniform deterministic quasipolynomial-time algorithm for finite turn-based stochastic mean-payoff games with signed integer rewards and rational chance-transition probabilities encoded in binary. It computes exactly the vertices of nonnegative value, including value zero, for the expectation of the pathwise liminf mean payoff. The algorithm uses exact rational arithmetic and $2^{O((\log(L+2))^2)}$ bit operations, where L is the complete binary input length.

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). The notes describe the randomized zero-threshold theorem and a finite counterexample to Truffet's elimination procedure, and list only the two September 25 mean-payoff papers; this paper's stochastic result is not formalized. [family-level]

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:Turn-Based-Stochastic-Mean-Payoff-Games-in-Deterministic-Quasipolynomial-Time-October-5-2026,
  author = {{OpenAI}},
  title = {{Turn-Based Stochastic Mean-Payoff Games in Deterministic Quasipolynomial Time}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Turn-Based-Stochastic-Mean-Payoff-Games-in-Deterministic-Quasipolynomial-Time-October-5-2026/stochastic-mean-payoff-games.pdf}{OAI:Turn-Based-Stochastic-Mean-Payoff-Games-in-Deterministic-Quasipolynomial-Time-October-5-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: