On Nonterminating Stochastic Games

A stochastic game is played in a sequence of steps; at each step the play is said to be in some state i, chosen from a finite collection of states. If the play is in state i, the first player chooses move k and the second player chooses move l, then the first player receives a reward a kl i , and, with probability p kl ij , the next state is j. The concept of stochastic games was introduced by Shapley with the proviso that, with probability 1, play terminates. The authors consider the case when play never terminates, and show properties of such games and offer a convergent algorithm for their solution. In the special case when one of the players is a dummy, the nonterminating stochastic game reduces to a Markovian decision process, and the present work can be regarded as the extension to a game theoretic context of known results on Markovian decision processes.

• 저널Management Science · 12(5) · 359–370
• 토픽Game Theory and Applications · Management Science and Operations Research
• DOI10.1287/mnsc.12.5.359
• 저자Alan J. Hoffman, Richard M. Karp