A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions

摘要

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 → R, and three types of vertices: black V_B, white Vw, 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 |V_R| = O(1), a saddle point in pure stationary strategies can be found in time polynomial in |V_W| + |V_B|, the maximum absolute local reward R, and the common denominator of the transition probabilities.