{"id":"openai-math/Randomized-quasipolynomial-time-mean-payoff-games","pdf":"https://github.com/openai/math/blob/main/preprints/Randomized-quasipolynomial-time-mean-payoff-games-September-25-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/Randomized-quasipolynomial-time-mean-payoff-games-September-25-2026","tags":["algorithms","game-theory","complexity"],"score":0,"title":"Randomized 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 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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{},"formalized":true,"family_title":"Quasipolynomial algorithms for mean-payoff, stochastic and parity games"}