Approximation theorems for zero-sum nonstationary stochastic games

Nowak, Andrzej S.

doi:10.1090/S0002-9939-1984-0759667-1

Approximation theorems for zero-sum nonstationary stochastic games
HTML articles powered by AMS MathViewer

by Andrzej S. Nowak PDF

Proc. Amer. Math. Soc. 92 (1984), 418-424 Request permission

Abstract:

This paper deals with zero-sum nonstationary stochastic games with countable state and action spaces which include both Shapley’s stochastic games [11] and infinite games with imperfect information studied by Orkin in [7]. It is shown that any nonstationary stochastic game with a bounded below lower semicontinuous payoff defined on the space of all histories has a value function and the minimizer has an optimal strategy. Moreover, two approximation theorems extending the main results of Orkin from [7] are established. Finally, counterexamples answering in the negative some open questions raised by Orkin [7] and Sengupta [10] are given.

References

H. A. M. Couwenbergh, Stochastic games with metric state space, Internat. J. Game Theory 9 (1980), no. 1, 25–36. MR 571962, DOI 10.1007/BF01784794
Ky Fan, Minimax theorems, Proc. Nat. Acad. Sci. U.S.A. 39 (1953), 42–47. MR 55678, DOI 10.1073/pnas.39.1.42
K. Hinderer, Foundations of non-stationary dynamic programming with discrete time parameter, Lecture Notes in Operations Research and Mathematical Systems, Vol. 33, Springer-Verlag, Berlin-New York, 1970. MR 0267890
J.-F. Mertens and A. Neyman, Stochastic games, Internat. J. Game Theory 10 (1981), no. 2, 53–66. MR 637403, DOI 10.1007/BF01769259
Jacques Neveu, Mathematical foundations of the calculus of probability, Holden-Day, Inc., San Francisco, Calif.-London-Amsterdam, 1965. Translated by Amiel Feinstein. MR 0198505
Andrzej S. Nowak, Universally measurable strategies in zero-sum stochastic games, Ann. Probab. 13 (1985), no. 1, 269–287. MR 770642
Michael Orkin, An approximation theorem for infinite games, Proc. Amer. Math. Soc. 36 (1972), 212–216. MR 319583, DOI 10.1090/S0002-9939-1972-0319583-8
T. Parthasarathy and M. Stern, Markov games—a survey, Differential games and control theory, II (Proc. 2nd Conf., Univ. Rhode Island, Kingston, R.I., 1976) Lecture Notes in Pure and Appl. Math., vol. 30, Dekker, New York, 1977, pp. 1–46. MR 0681335
M. Schäl, Stochastic nonstationary two person zero sum games, Z. Angew. Math. Mech. 61 (1981), no. 5, T352–T353. MR 648255
Sailes K. Sengupta, Lower semicontinuous stochastic games with imperfect information, Ann. Statist. 3 (1975), 554–558. MR 475919
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