A convex programming-based algorithm for mean payoff stochastic games with perfect information

作者：Boros Endre; Elbassioni Khaled^*; Gurvich Vladimir; Makino Kazuhisa

来源：Optimization Letters, 2017, 11(8): 1499-1512.

DOI：10.1007/s11590-017-1140-y

• Stochastic games
• Perfect information
• Mean payoff
• Pseudo-polynomial algorithm
• Convex programming

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, even when |V-R| = 0. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this short note, we show that BWR-games can be solved via convex programming in pseudo-polynomial time if the number of random positions is a constant.

• 出版日期2017-12
• 单位rutgers