• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

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

Algorithmica. 2017.
Gurvich V., Boros E., Manthey B., Elbassioni K., Fouz M., Makino K.

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.