On the existence of stationary Nash equilibria in average stochastic games with finite state and action spaces

Dmitrii Lozovanu ; Stefan Pickl

Contributions to game theory and management, Tome 13 (2020), pp. 304-323.

Résumé

We consider infinite $n$-person stochastic games with limiting average payoffs criteria for the players. The main results of the paper are concerned with the existence of stationary Nash equilibria and determining the optimal strategies of the players in the games with finite state and action spaces. We present conditions for the existence of stationary Nash equilibria in the considered games and propose an approach for determining the optimal stationary strategies of the players if such strategies exist.

Détail

Keywords: Markov decision processes, average stochastic games, stationary Nash equilibria, optimal stationary strategies.

Bibliographie

[1] Boyd S., Vandenberghe L., Convex optimization, Cambridge university press, 2004 | MR | Zbl

[2] Dasgupta P., Maskin E., “The existence of equilibrium in discontinuous economic games, I: Theory”, The Review of economic studies, 53 (1986), 1–26 | DOI | MR | Zbl

[3] Debreu G., “A social equilibrium existence theorem”, Proceedings of the National Academy of Sciences, 38 (1952), 886–893 | DOI | MR | Zbl

[4] Ehrenfeucht A., Mycielski J., “Positional strategies for mean payoff games”, Int. J. of Game Theory, 8 (1979), 109–113 | DOI | MR | Zbl

[5] Filar J., Vrieze K., Competitive Markov Decision Processes, Springer, New York, NY, 1997 | MR | Zbl

[6] Filar J. A., Schultz T. A., Thuijsman F., Vrieze O., “Nonlinear programming and stationary equilibria in stochastic games”, Mathematical Programming, 50 (1991), 227–237 | DOI | MR | Zbl

[7] Fink A. M., “Equilibrium in a stochastic $n$-person game”, Journal of Science of the Hiroshima University, ser. math., 28 (1964), 89–93 | DOI | MR | Zbl

[8] Flesch J., Thuijsman F., Vrieze K., “Cyclic Markov equilibria in stochastic games”, International Journal of Game Theory, 26 (1997), 303–314 | DOI | MR | Zbl

[9] Gillette D., “Stochastic games with zero stop probabilities”, Contributions to the Theory of Games, 3 (1957), 179–187 | MR

[10] Glicksberg I. L., “A further generalization of the Kakutani fixed point theorem wih application to Nash equilibrium points”, Proceedings of the American Mathematical Society, 38 (1952), 170–174 | MR

[11] Kallenberg L., Markov decision processes, University of Leiden, Netherland, 2016

[12] Lozovanu D., “The game-theoretical approach to Markov decision problems and determining Nash equilibria for stochastic positional games”, International Journal of Mathematical Modelling and Numerical Optimisation, 2 (2011), 162–174 | DOI | Zbl

[13] Lozovanu D., “Stationary Nash equilibria for average stochastic positional games”, Frontiers of Dynamic Games, Static and Dynamic Game Theory: Fondation and Application, Chapter 9, eds. L. Petrosyan et al., Springer, 2018, 139–163 | DOI | MR

[14] Lozovanu D., “Pure and Mixed Stationary Nash equilibria for average stochastic positional games”, Frontiers of Dynamic Games, Static and Dynamic Game Theory: Fondation and Application, Chapter 8, eds. L. Petrosyan et al., Springer, 2019, 131–174 | DOI | MR

[15] Lozovanu D., Pickl S., Optimization of stochastic discrete systems and control on complex networks, Springer, 2015 | MR | Zbl

[16] Mertens J.-F., Neyman A., “Stochastic games”, International Journal of Game Theory, 10 (1981), 53–66 | DOI | MR | Zbl

[17] Neyman A., Sorin S., Stochastic games and applications, NATO science series, C, Mathematical and physical sciences, 569, Kluwer Academic Publishers, 2003 | MR

[18] Puterman M. L., Markov decision processes: Discrete stochastic dynamic programming, Wiley, New Jersey, 2005 | MR | Zbl

[19] Reny P. J., “On the existence of pure and mixed strategy Nash equilibria in discontinuous games”, Econometrica, 67 (1999), 1029–1056 | DOI | MR | Zbl

[20] Rogers P. D., Nonzero-sum stochastic games, Technical Report, DTIC Document, 1969 | MR

[21] Schultz T. A., Mathematical programming and stochastic games, Ph. D. Thesis, The John Hopkins University, Baltimore, Maryland, 1986

[22] Shapley L. S., “Stochastic games”, Proceedings of the National Academy of Sciences, 39 (1953), 1095–1100 | DOI | MR | Zbl

[23] Simon L. K., “Games with discontinuous payoffs”, The Review of Economic Studies, 54 (1987), 569–597 | DOI | MR | Zbl

[24] Sobel M. J., “Noncooperative stochastic games”, The Annals of Mathematical Statistics, 42 (1971), 1930–1935 | DOI | MR | Zbl

[25] Solan E., “Stochastic games”, Encyclopedia of Complexity and Systems Science, Springer, 2009, 8698–8708 | DOI

[26] Solan E., Vieille N., “Computing uniformly optimal strategies in two-player stochastic games”, Economic Theory, 42 (2010), 237–253 | DOI | MR | Zbl

[27] Takahashi M., “Equilibrium points of stochastic non-cooperative $ n $-person games”, Journal of Science of the Hiroshima University, Series AI, Math., 28 (1964), 95–99 | DOI | MR | Zbl

[28] Tijs S., Vrieze O., “On the existence of easy initial states for undiscounted stochastic games”, Mathematics of Operations Research, 11 (1986), 506–513 | DOI | MR | Zbl

[29] Vieille N., “Stochastic games: Recent results”, Handbook of Game Theory with Economic Applications, v. 3, 2002, 1833–1850 | DOI

[30] Vieille N., “Equilibrium in 2-person stochastic games I, II”, Israel Journal of Mathematics, 2009, 8698–8708

[31] Vrieze O. J., “Stochastic games with finite state and action spaces”, CWI Tracts, 33, 1987, 1–221 | MR