{"id":"openai-math/Deterministic-quasipolynomial-time-mean-payoff-games","pdf":"https://github.com/openai/math/blob/main/preprints/Deterministic-quasipolynomial-time-mean-payoff-games-September-25-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/Deterministic-quasipolynomial-time-mean-payoff-games-September-25-2026","tags":["game-theory","algorithms","complexity"],"score":0,"title":"Deterministic quasipolynomial-time mean-payoff games","domain":"Theoretical computer science","family":"104","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{},"formalized":false,"family_title":"Quasipolynomial algorithms for mean-payoff, stochastic and parity games"}