oai-math-revised beta

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

Deterministic 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 deterministic 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. A reduction also computes the exact rational value at every vertex and globally optimal positional strategies for both players within the same quasipolynomial 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.

Follow-up works

Formalization

  • OpenAI math release, Lean scope notes for family 104 (lean/docs/104.md, release of 6 Oct 2026). The notes list this paper as an accompanying paper, but the formalized statements are the randomized companion's zero-threshold algorithm and a finite counterexample to Truffet's elimination step; the deterministic main theorem 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:Deterministic-quasipolynomial-time-mean-payoff-games-September-25-2026,
  author = {{OpenAI}},
  title = {{Deterministic quasipolynomial-time mean-payoff games}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Deterministic-quasipolynomial-time-mean-payoff-games-September-25-2026/paper.pdf}{OAI:Deterministic-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: