The completely mixed single-controller stochastic game

Filar, Jerzy A.

doi:10.1090/S0002-9939-1985-0810169-4

The completely mixed single-controller stochastic game
HTML articles powered by AMS MathViewer

by Jerzy A. Filar PDF

Proc. Amer. Math. Soc. 95 (1985), 585-594 Request permission

Abstract:

We consider a zero-sum stochastic game with finitely many states and actions. Further we assume that the transition probabilities depend on the actions of only one player (player II, in our case), and that the game is completely mixed. That is, every optimal stationary strategy for either player assigns a positive probability to every action in every state. For these games, properties analogous to those derived by Kaplansky [4] for the completely mixed matrix games, are established in this paper. These properties lead to the counterintuitive conclusion that the controller need not know the law of motion in order to play optimally, but his opponent does not have this luxury.

References

Jerzy A. Filar and T. E. S. Raghavan, A matrix game solution of the single-controller stochastic game, Math. Oper. Res. 9 (1984), no. 3, 356–362. MR 757310, DOI 10.1287/moor.9.3.356
A. Hordijk and L. C. M. Kallenberg, Linear programming and Markov decision chains, Management Sci. 25 (1979/80), no. 4, 352–362. MR 543386, DOI 10.1287/mnsc.25.4.352

Linear programming and Markov games

Irving Kaplansky, A contribution to von Neumann’s theory of games, Ann. of Math. (2) 46 (1945), 474–479. MR 13890, DOI 10.2307/1969164
T. Parthasarathy and T. E. S. Raghavan, An orderfield property for stochastic games when one player controls transition probabilities, J. Optim. Theory Appl. 33 (1981), no. 3, 375–392. MR 619631, DOI 10.1007/BF00935250
T. E. S. Raghavan, Completely mixed strategies in bimatrix games, J. London Math. Soc. (2) 2 (1970), 709–712. MR 270761, DOI 10.1112/jlms/2.Part_{4}.709
L. S. Shapley, Stochastic games, Proc. Nat. Acad. Sci. U.S.A. 39 (1953), 1095–1100. MR 61807, DOI 10.1073/pnas.39.10.1953

On stochastic games with limiting average payoff

John von Neumann and Oskar Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, Princeton, N.J., 1944. MR 0011937

Linear programming and undiscounted stochastic games in which one player controls transitions

3