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

• Published in: Dynamic games and applications 2018-03, Vol.8 (1), p.22-41
• Main Authors: Boros, Endre, Elbassioni, Khaled, Gurvich, Vladimir, Makino, Kazuhisa
• Format: Article
• Language: English
• Subjects: Algorithms; Communications Engineering; Computer Systems Organization and Communication Networks; Economic Theory/Quantitative Economics/Mathematical Methods; Economics; Ergodic processes; Game Theory; Games; Lasers; Management Science; Mathematics; Mathematics and Statistics; Networks; Operations Research; Players; Social and Behav. Sciences
• ISSN: 2153-0785; 2153-0793
• DOI: 10.1007/s13235-016-0199-x

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 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 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 (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 ε -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.