On canonical forms for two-person zero-sum limit average payoff stochastic games

Abstract

We consider two-person zero-sum mean payoff undiscounted stochastic games. We give a sufficient condition for the existence of a saddle point in uniformly optimal stationary strategies. Namely, we obtain sufficient conditions that enable us to to bring the game, by applying potential transformations 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 can be obtained by playing the local game at each state. We show that this condition is satisfied by the class of additive transition games, that is, the special case when the transitions at each state can be decomposed into two parts, each controlled completely by one of the two players. An important special case of additive games is the so-called BWR-games which are played by two players on a directed graph with positions of three types: Black, White and Random. We given an independent proof for the existence of canonical form in such games, and use this to derive the existence of canonical form (and hence of a saddle point in uniformly optimal stationary strategies) in a wide class of games, which includes stochastic games with perfect information, switching controller games and additive rewards, additive transition games.