TY - JOUR
T1 - A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions
AU - Boros, Endre
AU - Elbassioni, Khaled
AU - Gurvich, Vladimir
AU - Makino, Kazuhisa
N1 - Funding Information:
We thank the anonymous reviewer for the very careful reading and helpful remarks. We are also grateful for the support received from the Mathematisches Forschungsinstitut Oberwolfach, during a stay within the “Research in Pairs” Program from July 26, 2015-August 15, 2015. The research of the third author has been partially funded by the Russian Academic Excellence Project ‘5-100’.
Publisher Copyright:
© 2019 Elsevier Inc.
PY - 2019/8
Y1 - 2019/8
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→Z, and three types of positions: black V B , 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, even when |V R |=0. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this paper, 1 we show that BWR-games with a constant number of random positions can be solved in pseudo-polynomial time. More precisely, in any BWR-game with |V R |=O(1), a saddle point in uniformly optimal pure stationary strategies can be found in time polynomial in |V W |+|V B |, the maximum absolute local reward, 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→Z, and three types of positions: black V B , 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, even when |V R |=0. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this paper, 1 we show that BWR-games with a constant number of random positions can be solved in pseudo-polynomial time. More precisely, in any BWR-game with |V R |=O(1), a saddle point in uniformly optimal pure stationary strategies can be found in time polynomial in |V W |+|V B |, the maximum absolute local reward, and the common denominator of the transition probabilities.
KW - Equilibrium computation
KW - Perfect information
KW - Pseudo-polynomial algorithm
KW - Stochastic games
KW - Zero-sum games
UR - http://www.scopus.com/inward/record.url?scp=85063427481&partnerID=8YFLogxK
U2 - 10.1016/j.ic.2019.03.005
DO - 10.1016/j.ic.2019.03.005
M3 - Article
AN - SCOPUS:85063427481
SN - 0890-5401
VL - 267
SP - 74
EP - 95
JO - Information and Computation
JF - Information and Computation
ER -