• 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. 2018. Vol. 80. No. 11. P. 3132-3157.
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.