TY - JOUR

T1 - A potential reduction algorithm for ergodic two-person zero-sum limiting average payoff stochastic games

AU - Boros, Endre

AU - Elbassioni, Khaled

AU - Gurvich, Vladimir

AU - Makino, Kazuhisa

N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2014.

PY - 2014

Y1 - 2014

N2 - We suggest a new algorithm for two-person zero-sum undis-counted stochastic games focusing on stationary strategies. Given a positive real e, let us call a stochastic game e-ergodic, if its values from any two initial positions differ by at most e. The proposed new algorithm outputs for every e > 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 e-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 e/24 apart. In particular, the above result shows that if a stochastic game is e-ergodic, then there are stationary strategies for the players proving 24e-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 e-optimal stationary strategies for every e > 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.

AB - We suggest a new algorithm for two-person zero-sum undis-counted stochastic games focusing on stationary strategies. Given a positive real e, let us call a stochastic game e-ergodic, if its values from any two initial positions differ by at most e. The proposed new algorithm outputs for every e > 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 e-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 e/24 apart. In particular, the above result shows that if a stochastic game is e-ergodic, then there are stationary strategies for the players proving 24e-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 e-optimal stationary strategies for every e > 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.

UR - http://www.scopus.com/inward/record.url?scp=84921648517&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84921648517&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-12691-3_52

DO - 10.1007/978-3-319-12691-3_52

M3 - Article

AN - SCOPUS:84921648517

SN - 0302-9743

VL - 8881

SP - 694

EP - 709

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -