Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

08.07.2016 | Ausgabe 1/2018

Dynamic Games and Applications 1/2018

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

Zeitschrift:
Dynamic Games and Applications > Ausgabe 1/2018
Autoren:
Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino
Wichtige Hinweise
This research was partially supported by DIMACS, Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, and by the Scientific Grant-in-Aid from Ministry of Education, Science, Sports and Culture of Japan. Part of this research was done at the Mathematisches Forschungsinstitut Oberwolfach during stays within the Research in Pairs Program. The first author also acknowledges the partial support of NSF Grant IIS-1161476. The third author was partially funded by the Russian Academic Excellence Project ‘5-100’.
An extended abstract of this paper was published in the proceedings of the Combinatorial Optimization and Applications, 2014 [8].

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.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe​​​​​​​​​​​​​​

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb

Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 1/2018

Dynamic Games and Applications 1/2018 Zur Ausgabe

Premium Partner

    Bildnachweise