We suggest a new algorithm for two-person zero-sum undiscounted stochastic games focusing on stationary strategies. Given a positive real @math , let us call a stochastic game @math -ergodic, if its values from any two initial positions differ by at most @math . The proposed new algorithm outputs for every @math in finite time either a pair of stationary strategies for the two players guaranteeing that the values from any initial positions are within an @math -range, or identifies two initial positions @math and @math and corresponding stationary strategies for the players proving that the game values starting from @math and @math are at least @math apart. In particular, the above result shows that if a stochastic game is @math -ergodic, then there are stationary strategies for the players proving @math -ergodicity. This result strengthens and provides a constructive version of an existential result by Vrieze (1980) claiming that if a stochastic game is @math -ergodic, then there are @math -optimal stationary strategies for every @math . 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.
This paper considers undiscounted two-person, zero-sum sequential games with finite state and action spaces. Under conditions that guarantee the existence of stationary optimal strategies, we present two successive approximation methods for finding the optimal gain rate, a solution to the optimality equation, and for any ϵ > 0, ϵ-optimal policies for both players. A stochastic game is played in a sequence of steps; at each step the play is said to be in some state i, chosen from a finite collection of states. If the play is in state i, the first player chooses move k and the second player chooses move l, then the first player receives a reward akli, and, with probability pklij, the next state is j. The concept of stochastic games was introduced by Shapley with the proviso that, with probability 1, play terminates. The authors consider the case when play never terminates, and show properties of such games and offer a convergent algorithm for their solution. In the special case when one of the players is a dummy, the nonterminating stochastic game reduces to a Markovian decision process, and the present work can be regarded as the extension to a game theoretic context of known results on Markovian decision processes.