Title: A finite algorithm for the switching control stochastic game
Abstract: In this paper two-person zero-sum stochastic games are considered with the average payoff as criterion. It is assumed that in each state one of the players governs the transitions. We will establish an algorithm, which yields in a finite number of iterations the solution of the game i.e. the value of the game and optimal stationary strategies for both players. An essential part of our algorithm is formed by the linear programming problem which solves a one player control stochastic game. Furthermore, our algorithm provides a constructive proof of the existence of the value and of optimal stationary strategies for both players. In addition, the finiteness of our algorithm proves also the ordered field property of the switching control stochastic game.