Name
Abstract | ||
|---|---|---|
We suggest a new algorithm for two-person zero-sum undiscounted stochastic games focusing on stationary strategies. Given a positive real \(\varepsilon \), let us call a stochastic game \(\varepsilon \)-ergodic, if its values from any two initial positions differ by at most \(\varepsilon \). The proposed new algorithm outputs for every \(\varepsilon >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 \(\varepsilon \)-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 \(\varepsilon /24\) apart. In particular, the above result shows that if a stochastic game is \(\varepsilon \)-ergodic, then there are stationary strategies for the players proving \(24\varepsilon \)-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 \(\varepsilon \)-optimal stationary strategies for every \(\varepsilon > 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s13235-016-0199-x | Dynamic Games and Applications |
Keywords | Field | DocType |
Undiscounted stochastic games, Limiting average payoff, Mean payoff, Local reward, Potential transformation, Computational game theory | Ergodicity,Mathematical economics,Combinatorics,Computational game theory,Constructive,Algorithm,Finite state,Mathematics,Finite time,Stochastic game | Journal |
Volume | Issue | ISSN |
abs/1508.03455 | 1 | 2153-0793 |
Citations | PageRank | References |
0 | 0.34 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Endre Boros | 1 | 1779 | 155.63 |
| khaled elbassioni | 2 | 473 | 35.78 |
| Vladimir Gurvich | 3 | 688 | 68.89 |
| Kazuhisa Makino | 4 | 1088 | 102.74 |