Quasipolynomial algorithms for mean-payoff, stochastic and parity games

What OpenAI claims

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)

Papers (4)

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

   5 October 2026 · Preprint, not peer reviewed · PDF

   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.

2. Mean-payoff parity games in quasipolynomial time

   5 October 2026 · Preprint, not peer reviewed · PDF

   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.

3. Deterministic quasipolynomial-time mean-payoff games

   25 September 2026 · Preprint, not peer reviewed · PDF

   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.

4. Randomized quasipolynomial-time mean-payoff games

   25 September 2026 · Preprint, not peer reviewed · PDF

   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.

Status

Preprint. The papers have not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.