On the computational complexity of solving stochastic mean-payoff games

Vladimir Gurvich, Peter Bro Miltersen

We consider some well-known families of two-player, zero-sum, perfect information games that can be viewed as special cases of Shapley's stochastic games. We show that the followin…