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