Stochastic Limit-Average Games are in EXPTIME

Krishnendu Chatterjee, Rupak Majumdar, Thomas A. Henzinger

The value of a finite-state two-player zero-sum stochastic game with limit-average payoff can be approximated to within $\epsilon$ in time exponential in a polynomial in the size of the g…