Sign in
Back
Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions
Journal article   Open access  Peer reviewed

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

Endre Boros, Khaled Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino and Bodo Manthey
Algorithmica, Vol.80(11), pp.3132-3157
11/2018
DOI: https://doi.org/10.1007/s00453-017-0372-7

Abstract

Algorithm Analysis and Problem Complexity Algorithms Approximation algorithms Approximation schemes Computer Science Computer Systems Organization and Communication Networks Data Structures, Cryptology and Information Theory Mathematics of Computing Nash equilibrium Stochastic mean payoff games Theory of Computation
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.
url
https://doi.org/10.1007/s00453-017-0372-7View
Version of Record (VoR) Open

Metrics

11 Record Views

Details