Complexity of deterministic mean-payoff games
Follow the latest progress by email.
Can ordinary mean-payoff games with arbitrary signed binary edge weights be solved deterministically in quasipolynomial bit time? The target computes the exact winning set, values and optimal positional strategies in 2^O((log(L+2))²) operations, where L is the complete binary input length.
Why it matters and what counts as progress
Why it matters: Quasipolynomial bit complexity must account for binary weight size; bounds polynomial in weight magnitude do not settle that target.
What counts as progress: Obtain this weight-sensitive bit bound or a polynomial one without assuming small integer weights.
How the problem developed
- 1979 · Game formulation [1]
Andrzej Ehrenfeucht and Jan Mycielski Studied positional strategies in mean-payoff games, establishing a foundational model for later algorithmic work.
- 20 May 1996 · Algorithmic result [2]
Uri Zwick and Mike Paterson Placed mean-payoff game solving in NP∩coNP and gave a pseudopolynomial-time algorithm.
- 25 Sept 2026 · Reported algorithm [3]
OpenAI Reported a deterministic quasipolynomial bit-complexity algorithm for the exact winning set, game values and optimal positional strategies with signed binary weights.
AI contribution
Deterministic quasipolynomial-time mean-payoff games
For an ordinary mean-payoff game of complete binary input length L with arbitrary signed binary edge weights, the September 25 deterministic manuscript reports a 2^O((log(L+2))²)-bit-operation algorithm for the exact winning set, values and optimal positional strategies.
Sources
Website timeline
Publication dates and editorial changes.
AI reports a deterministic quasipolynomial algorithm for mean-payoff games