Abstract
When the transition probabilities of a two-person stochastic game do not depend on the actions of a fixed player at all states, the value exists in stationary strategies. Further, the data of the stochastic game, the values at each state, and the components of a pair of optimal stationary strategies all lie in the same Archimedean ordered field. This orderfield property holds also for the nonzero sum case in Nash equilibrium stationary strategies. A finite-step algorithm for the discounted case is given via linear programming.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Shapley, L. S.,Stochastic Games, Proceedings of the National Academy of Sciences, Vol. 39, pp. 1095–1100, 1953.
Gillette, D.,Stochastic Games with Zero-Stop Probabilities, Annals of Mathematical Studies, No. 39, Princeton University Press, Princeton, New Jersey, 1957.
Weyl, H.,Elementary Proof of a Minimax Theorem Due to Von Neumann, Annals of Mathematical Studies, Vol. 24, pp. 19–25, 1950.
Stern, M. A.,On Stochastic Games with Limiting Average Payoff, University of Illinois at Chicago Circle, Chicago, Illinois, PhD Thesis, 1975.
Bewley, T., andKohlberg, E.,The Asymptotic Theory of Stochastic Games, Mathematics of Operations Research, Vol. 1, pp. 197–208, 1976.
Charnes, A.,Constrained Games and Linear Programming, Proceedings of the National Academy of Sciences, Vol. 38, pp. 639–641, 1953.
Wolfe, P.,Determinateness of Polyhedral Games, Annals of Mathematics Studies, No. 38, Princeton University Press, Princeton, New Jersey, 1956.
Hoffman, A. J., andKarp, R. M.,On Nonterminating Stochastic Games, Management Science, Vol. 12, pp. 359–370, 1966.
Shapley, L. S., andSnow, R. N.,Basic Solutions of Discrete Games, Annals of Mathematics Studies, Vol. 24, Princeton University Press, Princeton, New Jersey, 1950.
Blackwell, D.,Discrete Dynamic Programming, Annals of Mathematical Statistics, Vol. 33, pp. 719–726, 1962.
Sobel, M. J.,Noncooperative Stochastic Games, Annals of Mathematical Statistics, Vol. 42, pp. 1930–1935, 1971.
Kuhn, H. W.,An Algorithm for Equilibrium Points in Bimatrix Games, Proceedings of the National Academy of Sciences, Vol. 47, pp. 1657–1662, 1961.
Parthasarathy, T., andRaghavan, T. E. S.,Some Topics in Two-Person Games, American Elsevier Publishing Company, New York, New York, 1971.
Goldman, A. J., andTucker, A. W.,Theory of Linear Programming, Annals of Mathematics Studies, No. 39, Princeton University Press, Princeton, New Jersey, 1956.
Bewley, T., andKohlberg, E.,The Theory of Stochastic Games with Zero-Stop Probabilities, Harvard University, Cambridge, Massachusetts, Project in Efficiency of Decision Making in Economic Systems, Technical Report No. 21, 1976.
Chandrasekharan, R., Nair, K. P. K., andRao, S. S.,Algorithms for Discounted Stochastic Games, Journal of Optimization Theory and Applications, Vol. 11, pp. 627–637, 1973.
Pollatschek, M. A., andAvi-itzhak, B.,Algorithm for Stochastic Games with Geometrical Interpretation, Management Science, Vol. 15, pp. 399–415, 1969.
Author information
Authors and Affiliations
Additional information
Communicated by G. Leitmann
This research was partially supported by the Air Force Office of Scientific Research, Grant No. 78-3495. The authors are indebted to Mr. J. Filar for some helpful suggestions in redrafting an earlier version of the paper, especially toward clarifying some obscurities in the proofs of Theorems 3.1 and 4.2 that existed in the earlier versions. This paper is dedicated to Professor C. R. Rao on his 60th birthday.
Rights and permissions
About this article
Cite this article
Parthasarathy, T., Raghavan, T.E.S. An orderfield property for stochastic games when one player controls transition probabilities. J Optim Theory Appl 33, 375–392 (1981). https://doi.org/10.1007/BF00935250
Issue Date:
DOI: https://doi.org/10.1007/BF00935250