TY - GEN

T1 - A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and a few random positions

AU - Boros, Endre

AU - Elbassioni, Khaled

AU - Gurvich, Vladimir

AU - Makino, Kazuhisa

PY - 2013

Y1 - 2013

N2 - We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph G = (V, E), with local rewards r: E → ℝ, and three types of vertices: black VB , white V W , and random V R forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, or not. In fact, a pseudo-polynomial algorithm for these games would already imply their polynomial solvability. In this paper, we show that BWR-games with a constant number of random nodes can be solved in pseudo-polynomial time. That is, for any such game with a few random nodes |VR| = O(1), a saddle point in pure stationary strategies can be found in time polynomial in |VW| + |VB|, the maximum absolute local reward R, and the common denominator of the transition probabilities.

AB - We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph G = (V, E), with local rewards r: E → ℝ, and three types of vertices: black VB , white V W , and random V R forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, or not. In fact, a pseudo-polynomial algorithm for these games would already imply their polynomial solvability. In this paper, we show that BWR-games with a constant number of random nodes can be solved in pseudo-polynomial time. That is, for any such game with a few random nodes |VR| = O(1), a saddle point in pure stationary strategies can be found in time polynomial in |VW| + |VB|, the maximum absolute local reward R, and the common denominator of the transition probabilities.

UR - http://www.scopus.com/inward/record.url?scp=84880257132&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-39206-1_19

DO - 10.1007/978-3-642-39206-1_19

M3 - Conference contribution

AN - SCOPUS:84880257132

SN - 9783642392054

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 220

EP - 231

BT - Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings

T2 - 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013

Y2 - 8 July 2013 through 12 July 2013

ER -