• Media type: E-Book
  • Title: A potential reduction algorithm for two-person zero-sum mean payoff stochastic games
  • Contributor: Boros, Endre [Author]; Elbassioni, Khaled [Author]; Gurvich, Vladimir [Author]; Makino, Kazuhisa [Author]
  • Published: Oberwolfach-Walke: Mathematisches Forschungsinstitut, 2015
  • Published in: Oberwolfach preprints ; 2015,19
  • Extent: Online-Ressource (22 Seiten)
  • Language: English
  • DOI: 10.14760/OWP-2015-19
  • Identifier:
  • Keywords: undiscounted stochastic games ; limiting average payoff ; mean payoff ; local reward ; potential transformation ; computational game theory
  • Origination:
  • University thesis:
  • Footnote:
  • Description: We suggest a new algorithm for two-person zero-sum undiscounted 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 identifes 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 0-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 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.
  • Access State: Open Access