Turn-Based Stochastic Mean-Payoff Games in Deterministic Quasipolynomial Time

We give a uniform deterministic quasipolynomial-time algorithm for finite turn-based stochastic mean-payoff games with signed integer rewards and rational chance-transition probabilities encoded in binary. It computes exactly the vertices of nonnegative value, including value zero, for the expectation of the pathwise liminf mean payoff. The algorithm uses exact rational arithmetic and $2^{O((\log (L+2){)}^2)}$ bit operations, where L is the complete binary input length.