A sample-path approach to stochastic games

Two-person zero-sum stochastic games with finite state and action spaces are considered. The expected average payoff criterion is used for multichain structures. In the special case in which only one player controls the transitions, it is shown that the optimal stationary policies and the value of the game can be obtained from the optimal solutions to a pair of dual linear programs. A decomposition algorithm which produces such optimal stationary policies for both players is given. In the case in which both players control the transitions, a generalized game is obtained, the solution of which gives the optimal policies