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

Optimization Letters. 2017. Vol. 11. No. 8. P. 1499–1512.

Boros E., Elbassioni K., Гурвич В. А., Makino K.

We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph (Formula presented.), with local rewards (Formula presented.), and three types of positions: black (Formula presented.), white (Formula presented.), and random (Formula presented.) forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, even when (Formula presented.). 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. 

Ключевые слова: Stochastic games, mean payoff, Convex programming, Perfect information, Pseudo-polynomial algorithm

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА: Теоретическая информатика (2017)