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

Endre Boros (), Khaled Elbassioni (), Vladimir Gurvich () and Kazuhisa Makino ()
Additional contact information
Endre Boros: Rutgers University
Khaled Elbassioni: Masdar Institute of Science and Technology
Vladimir Gurvich: Rutgers University
Kazuhisa Makino: Kyoto University

Dynamic Games and Applications, 2018, vol. 8, issue 1, No 2, 22-41

Abstract: 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$$ ε > 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$$ ε / 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 $$ 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 $$\varepsilon $$ ε -optimal stationary strategies for every $$\varepsilon > 0$$ ε > 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.

Keywords: Undiscounted stochastic games; Limiting average payoff; Mean payoff; Local reward; Potential transformation; Computational game theory (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13235-016-0199-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:dyngam:v:8:y:2018:i:1:d:10.1007_s13235-016-0199-x

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/13235

DOI: 10.1007/s13235-016-0199-x

Access Statistics for this article

Dynamic Games and Applications is currently edited by Georges Zaccour

More articles in Dynamic Games and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().