Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions

Endre Boros, Khaled Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino, Bodo Manthey (Corresponding Author)

Research output: Contribution to journalArticleAcademicpeer-review

48 Downloads (Pure)

Abstract

We consider two-player zero-sum stochastic mean payoff games with perfect information. We show that any such game, with a constant number of random positions and polynomially bounded positive transition probabilities, admits a polynomial time approximation scheme, both in the relative and absolute sense.
Original languageEnglish
Pages (from-to)3132-3157
Number of pages26
JournalAlgorithmica
Volume80
Issue number11
DOIs
Publication statusPublished - 1 Nov 2018

Keywords

  • UT-Hybrid-D
  • Approximation schemes
  • Approximation algorithms
  • Nash equilibrium
  • Stochastic mean payoff games

Cite this