Stochastic games with perfect information: the existence of canonical form

The fact that a saddle point exists in pure positional strategies was proved by Gillette in 1957 and Liggett and Lippman in 1969
by considering the discounted version, in which the payoff of White is discounted by a factor $\gb^i$ at step $i$ and then proceeding to the limit as the discount factor $\gb\in[0,1)$ goes to $1$.

This class of games lies in the complexity class NP$\cap$CoNP and contains the well-known cyclic games (when $V_R$ is empty) and
Markov decision processes (when $V_B$ or $V_W$ is empty).

We show that every such game can be reduced by a potential transformation to a canonical form in which locally optimal strategies are globally optimal, and hence the value for every initial position and the optimal strategies of both players are obvious.

In the discounted case the transformed game values are also ergodic (i.e. do not depend on the initial position) and the corresponding potentials can be found in polynomial time.

Yet, this time tends to infinity, as $\gb \rightarrow 1^-$.


This is joint work with Endre Boros, Vladimir Gurvich and Kazuhisa Makino.