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.
- Approximation schemes
- Approximation algorithms
- Nash equilibrium
- Stochastic mean payoff games
Boros, E., Elbassioni, K., Fouz, M., Gurvich, V., Makino, K., & Manthey, B. (2018). Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions. Algorithmica, 80(11), 3132-3157. https://doi.org/10.1007/s00453-017-0372-7