A potential reduction algorithm for two-person zero-sum mean payoff stochastic games

Abstract

We suggest a new algorithm for two-person zero-sum undiscounted stochastic games focusing on stationary strategies. Given a positive real , let us call a stochastic game -ergodic, if its values from any two initial positions dier by at most . The proposed new algorithm outputs for every > 0 in nite time either a pair of stationary strategies for the two players guaranteeing that the values from any initial positions are within an -range, or identies 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 =24 apart. In particular, the above result shows that if a stochastic game is -ergodic, then there are stationary strategies for the players proving 24-ergodicity. This result strengthens and provides a constructive version of an existential result by Vrieze (1980) claiming that if a stochastic game is 0-ergodic, then there are -optimal stationary strategies for every > 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.