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

Research output: Contribution to journalArticlepeer-review

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 languageBritish English
Pages (from-to)3132-3157
Number of pages26
JournalAlgorithmica (New York)
Volume80
Issue number11
DOIs
StatePublished - 1 Nov 2018

Keywords

  • Approximation algorithms
  • Approximation schemes
  • Nash equilibrium
  • Stochastic mean payoff games

Fingerprint

Dive into the research topics of 'Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions'. Together they form a unique fingerprint.

Cite this