• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

A Potential Reduction Algorithm for Ergodic Two-Person Zero-Sum Limiting Average Payoff Stochastic Games

P. 694-709.
Gurvich V., Boros E., Elbassioni K. M., Makino K.

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 differ by at most ϵϵ. The proposed new algorithm outputs for every ϵ>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 ϵϵ-range, or identifies two initial positions uu and vv and corresponding stationary strategies for the players proving that the game values starting from uu andvv are at least ϵ/24ϵ/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ϵ24ϵ-ergodicity. This result strengthens and provides a constructive version of an existential result by Vrieze (1980) claiming that if a stochastic game is 00-ergodic, then there are ϵϵ-optimal stationary strategies for every ϵ>0ϵ>0. The suggested algorithm extends the approach recently introduced for stochastic games with perfect information, and is based on the classical potential transformation technique that changes the range of local values at all positions without changing the normal form of the game.