A Matrix Game Solution of the Single-Controller Stochastic Game

Source abstract

We consider a stochastic game on finitely many states with limiting average payoff. Further we assume that the law of motion depends on the actions of one player only, say the minimizer. We show that these games have the following properties: (a) The value of the stochastic game for each state s is the same as the value of the matrix game whose rows and columns are the pure stationary strategies of the players and whose entries are the corresponding payoffs, (b) These matrix games have a common optimal strategy for the maximizer which in turn yields his optimal stationary strategy in the stochastic game, (c) If the value of a stochastic subgame obtained by deleting a column or a row in a particular state coincides with the value of the original game at that state, then it coincides at all states, (d) If all actions of the minimizer at each state are essential for optimal play, then in the transient states (under optimal play) the minimizer has only one action. In such a case the original game can be solved by solving a number of simpler subgames independently of each other.