Abstract
We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph
$$G = (V, E)$$
G
=
(
V
,
E
)
, with local rewards
$$r{:}\,E \rightarrow \mathbb {Z}$$
r
:
E
→
Z
, and three types of positions: black
$$V_B$$
V
B
, white
$$V_W$$
V
W
, and random
$$V_R$$
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$$
|
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.