Deterministic quasipolynomial-time mean-payoff games
A uniform deterministic algorithm computes the exact zero-threshold winning set for any finite mean-payoff game with arbitrary signed integer edge weights encoded in binary, using at most bit operations for an absolute constant , where is the complete explicit input length.
The proof is complete and rigorous, combining the finite-box comparison interface (Lemma 2.1, imported from the companion paper), the wide-box game reduction (Proposition 2.2), the simultaneous labelling theorem (Theorem 2.4), and the bit-complexity accounting (Section 6).
“Theorem 1.1. A uniform deterministic algorithm returns exactly the set U = {v ∈ V : ∃ Max strategy σ ∀ Min strategies τ, MPw(πv,σ,τ ) ≥ 0} for every game specified above. For an absolute constant C > 0, the complete computation uses at most 2^{C(log_2(L+2))^2} bit operations in a standard model polynomially equivalent to a uniform deterministic Turing machine. The bound includes preprocessing, exact arithmetic, recursion, and output of the entire set U.” · Show in paper