A Potential Reduction Algorithm for Two-Person Zero-Sum Mean Payoff Stochastic Games

We suggest a new algorithm for two-person zero-sum undiscounted stochastic games focusing on stationary strategies. Given a positive real $$\varepsilon $$ ε , let us call a stochastic game $$\varepsilon $$ ε -ergodic, if its values from any two initial positions differ by at most $$\varepsilon $$ ε . The proposed new algorithm outputs for every $$\varepsilon >0$$ ε > 0 in finite time either a pair of stationary strategies for the two players guaranteeing that the values from any initial positions are within an $$\varepsilon $$ ε -range, or identifies two initial positions u and v and corresponding stationary strategies for the players proving that the game values starting from u and v are at least $$\varepsilon /24$$ ε / 24 apart. In particular, the above result shows that if a stochastic game is $$\varepsilon $$ ε -ergodic, then there are stationary strategies for the players proving $$24\varepsilon $$ 24 ε -ergodicity. This result strengthens and provides a constructive version of an existential result by Vrieze (Stochastic games with finite state and action spaces. PhD thesis, Centrum voor Wiskunde en Informatica, Amsterdam, 1980) claiming that if a stochastic game is 0-ergodic, then there are $$\varepsilon $$ ε -optimal stationary strategies for every $$\varepsilon > 0$$ ε > 0 . The suggested algorithm is based on a potential transformation technique that changes the range of local values at all positions without changing the normal form of the game.