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. (Lean)
Manuscripts (4)
Turn-Based Stochastic Mean-Payoff Games in Deterministic Quasipolynomial Time
October 5, 2026 · source · cite as \cite{OAI:Turn-Based-Stochastic-Mean-Payoff-Games-in-Deterministic-Quasipolynomial-Time-October-5-2026}
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.
Mean-payoff parity games in quasipolynomial time
October 5, 2026 · source · cite as \cite{OAI:Mean-payoff-parity-games-in-quasipolynomial-time-October-5-2026}
We give a uniform deterministic quasipolynomial-time algorithm for mean-payoff parity games. It computes all vertices from which a player can enforce both nonnegative liminf mean payoff and the parity condition, with arbitrary signed binary rewards and unrestricted binary priorities. The running time is 2^{O((\log(L+2))^2)} bit operations, where L is the complete input length.
Deterministic quasipolynomial-time mean-payoff games
September 25, 2026 · source · cite as \cite{OAI:Deterministic-quasipolynomial-time-mean-payoff-games-September-25-2026}
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.
Randomized quasipolynomial-time mean-payoff games
September 25, 2026 · source · Lean formalization available · cite as \cite{OAI:Randomized-quasipolynomial-time-mean-payoff-games-September-25-2026}
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.
Result 104 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.
Source: https://github.com/openai/math/blob/main/CONTENTS.md