Abstract
Stationary equilibria in discounted and limiting average finite state/action space stochastic games are shown to be equivalent to global optima of certain nonlinear programs. For zero sum limiting average games, this formulation reduces to a linear objective, nonlinear constraints program, which finds the “best” stationary strategies, even whenε-optimal stationary strategies do not exist, for arbitrarily smallε.
Similar content being viewed by others
References
T. Bewley and E. Kohlberg, “On stochastic games with stationary optimal strategies,”Mathematics of Operations Research 1 (1978) 104–125.
M. Breton, A. Haurie, J.A. Filar and T. Schultz, “On the computation of equilibria in discounted stochastic dynamic games,” in: T. Basar, M. Beckmann and W. Krelle, eds.,Lecture notes in Economics and Mathematical Systems No. 265 (Springer, Berlin, 1986) pp. 64–87.
D. Blackwell, “Discrete dynamic programming,”Annals of Mathematical Statistics 33 (1962) 719–726.
D. Blackwell and T.S. Ferguson, “The big match,”Annals of Mathematical Statistics 39 (1968) 159–163.
C. Derman,Finite State Markovian Decision Processes (Academic Press, New York, 1970).
J.A. Filar and T. Schultz, “Nonlinear programming and stationary strategies in stochastic games,”Mathematical Programming 35 (1986) 243–247.
A.M. Fink, “Equilibrium in a stochastic n-person game,”Journal of Science of Hiroshima University, Series A-I 28 (1964) 89–93.
D. Gillete, “Stochastic games with zero stop probabilities,” in: M. Dresher, A.W. Tucker and P. Wolfe, eds.,Contributions to the Theory of Games III (Princeton University Press, Princeton, NJ, 1957) pp. 179–187.
A. Hordijk and L.C.M. Kallenberg, “Linear programming and Markov decision chains,”Management Science 25 (1979) 352–362.
A. Hordijk, O.J. Vrieze and G.L. Wanrooy, “Semi-Markov strategies in stochastic games,”International Journal of Game Theory 12 (1983) 81–89.
C.E. Lemke and J. Howson, “Equilibrium points of bimatrix games,”Journal of the Society of Industrial and Applied Mathematics 12 (1964) 413–423.
O.L. Mangasarian and H. Stone, “Two-person nonzero-sum games and quadratic programming,”Journal of Mathematical Analysis and Applications 9 (1964) 348–355.
P.D. Rogers, “Non-zero-sum stochastic games,” PhD Thesis, Report ORC 69-8 Operations Research Center, University of California (Berkeley, CA, 1969).
J. Rosenmuller, “On a generalization of the Lemke-Howson algorithm to noncooperativen-person games,”SIAM Journal of Applied Mathematics 21 (1971) 73–79.
U.G. Rothblum, “Solving stopping stochastic games by maximizing a linear function subject to quadratic constraints,” in: O. Moeschlin and D. Pallashke, eds.,Game Theory and Related Topics (North-Holland, Amsterdam, 1979) pp. 103–105.
T. Schultz, “Mathematical programming and stochastic games,” PhD Thesis, Johns Hopkins University (Baltimore, MD, 1987).
M. Sobel, “Noncooperative stochastic games,”The Annals of Mathematical Statistics 42 (1971) 1930–1935.
M. Takahashi, “Equilibrium points of stochastic, noncooperative n-person games,”Journal of Science of Hiroshima University Series A-I 28 (1964) 95–99.
O.J. Vrieze,Stochastic Games with Finite State and Action Spaces, CWI-tract No. 33, (Centre for Mathematics and Computer Science, Amsterdam, 1987).
R. Wilson, “Computing Equilibria ofn-person games,”SIAM Journal of Applied Mathematics 21 (1971) 80–87.
Author information
Authors and Affiliations
Additional information
The work of the first author was supported in part by the Air Force Office of Scientific Research, and by the National Science Foundation under Grant No ECS-8704954.
The work of the third author was supported by The Netherlands Organization for Scientific Research NWO, project 10-64-10.
Rights and permissions
About this article
Cite this article
Filar, J.A., Schultz, T.A., Thuijsman, F. et al. Nonlinear programming and stationary equilibria in stochastic games. Mathematical Programming 50, 227–237 (1991). https://doi.org/10.1007/BF01594936
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01594936