@article{42609fe67d8341c795f827d555fa41d2,
title = "Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions",
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.",
keywords = "Approximation algorithms, Approximation schemes, Nash equilibrium, Stochastic mean payoff games",
author = "Endre Boros and Khaled Elbassioni and Mahmoud Fouz and Vladimir Gurvich and Kazuhisa Makino and Bodo Manthey",
note = "Funding Information: A preliminary version appeared in the proceedings of ICALP 2011 [2]. The first author is grateful for the partial support of the National Science Foundation (CMMI-0856663, “Discrete Moment Problems and Applications”), and the first, second, fourth and fifth authors are grateful to the Mathematisches Forschungsinstitut Oberwolfach for providing a stimulating research environment with an RIP award in March 2010. The forth author gratefully acknowledges the partial support of the Russian Academic Excellence Project {\textquoteleft}5-100{\textquoteright}. Funding Information: A preliminary version appeared in the proceedings of ICALP 2011 [2]. The first author is grateful for the partial support of the National Science Foundation (CMMI-0856663, ?Discrete Moment Problems and Applications?), and the first, second, fourth and fifth authors are grateful to the Mathematisches Forschungsinstitut Oberwolfach for providing a stimulating research environment with an RIP award in March 2010. The forth author gratefully acknowledges the partial support of the Russian Academic Excellence Project ?5-100?. Publisher Copyright: {\textcopyright} 2017, The Author(s).",
year = "2018",
month = nov,
day = "1",
doi = "10.1007/s00453-017-0372-7",
language = "British English",
volume = "80",
pages = "3132--3157",
journal = "Algorithmica (New York)",
issn = "0178-4617",
publisher = "Springer New York",
number = "11",
}