Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



The completely mixed single-controller stochastic game

Author: Jerzy A. Filar
Journal: Proc. Amer. Math. Soc. 95 (1985), 585-594
MSC: Primary 90D15
MathSciNet review: 810169
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] J. A. Filar and T. E. S. Raghavan, A matrix game solution to a single-controller stochastic game, Math. Oper. Res. 9 (1984), 356-362. MR 757310 (85g:93049)
  • [2] A. Hordijk and L. C. M. Kallenberg, Linear programming and Markov decision chains, Management Sci. 25 (1979), 352-362. MR 543386 (80h:90149)
  • [3] -, Linear programming and Markov games. II, Game Theory and Mathematical Economics (O. Moeschlin and D. Pallaschke, eds.), North-Holland, Amsterdam, 1981, pp. 307-319.
  • [4] I. Kaplansky, A contribution to von Neumann's theory of games, Ann. of Math. (2) 46 (1945), 474-479. MR 0013890 (7:214c)
  • [5] T. Parthasarathy and T. E. S. Raghavan, An orderfield property for stochastic games, when one player controls the transition probabilities, J. Optim. Theory Appl. 33 (1981), 375-392. MR 619631 (83a:93058)
  • [6] T. E. S. Raghavan, Completely mixed strategies in bimatrix games, J. London Math. Soc. (2) 2 (1970), 709-712. MR 0270761 (42:5649)
  • [7] L. S. Shapley, Stochastic games, Proc. Nat. Acad. Sci. U.S.A. 39 (1953), 1095-1100. MR 0061807 (15:887g)
  • [8] M. A. Stern, On stochastic games with limiting average payoff, Ph.D. Thesis, Univ. of Illinois at Chicago Circle, Chicago, Ill. 1975.
  • [9] J. von Neumann and O. Morgenstern, Theory of games and economic behaviour, Princeton Univ. Press, Princeton, N. J., 1944. MR 0011937 (6:235k)
  • [10] O. J. Vrieze, Linear programming and undiscounted stochastic games in which one player controls transitions, OR Spektrum 3 (1981), 29-35.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 90D15

Retrieve articles in all journals with MSC: 90D15

Additional Information

Keywords: Stochastic games, single-controller, completely mixed property, stationary strategies
Article copyright: © Copyright 1985 American Mathematical Society

American Mathematical Society