Title
On Canonical Forms for Zero-Sum Stochastic Mean Payoff Games
Abstract
We consider two-person zero-sum mean payoff undiscounted stochastic games and obtain sufficient conditions for the existence of a saddle point in uniformly optimal stationary strategies. Namely, these conditions enable us 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 these conditions hold for the class of additive transition (AT) 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 AT-games form 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 give an independent proof for the existence of a canonical form in such games, and use this result to derive the existence of a 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 (PI), switching controller (SC) games and additive rewards, additive transition (ARAT) games. Unlike the proof for AT-games, our proof for the BWR-case does not rely on the existence of a saddle point in stationary strategies. We also derive some algorithmic consequences from these our reductions to BWR-games, in terms of solving PI-, and ARAT-games in sub-exponential time.
Year
DOI
Venue
2013
10.1007/s13235-013-0075-x
Dynamic Games and Applications
Keywords
Field
DocType
equilibrium,saddle point,zero sum
Combinatorial game theory,Control theory,Mathematical optimization,Mathematical economics,Saddle point,Directed graph,Canonical form,Perfect information,Mathematics,Special case,Stochastic game
Journal
Volume
Issue
ISSN
3
2
2153-0793
Citations 
PageRank 
References 
7
0.51
13
Authors
4
Name
Order
Citations
PageRank
Endre Boros11779155.63
khaled elbassioni247335.78
Vladimir Gurvich368868.89
Kazuhisa Makino41088102.74