Nash equilibria conditions for stochastic positional games

Dmitrii Lozovanu ; Stefan Pickl

Contributions to game theory and management, Tome 7 (2014), pp. 201-213.

Résumé

We formulate and study a class of stochastic positional games using a game-theoretical concept to finite state space Markov decision processes with an average and expected total discounted costs optimization criteria. Nash equilibria conditions for the considered class of games are proven and some approaches for determining the optimal strategies of the players are analyzed. The obtained results extend Nash equilibria conditions for deterministic positional games and can be used for studying Shapley stochastic games with average payoffs.

Détail

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

Bibliographie

[1] Condon A., “The complexity of stochastic games”, Informations and Computation, 96:2 (1992), 203–224 | DOI | MR | Zbl

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

[3] Filar J. A., Vrieze K., Competitive Markov Decision Processes, Springer, 1997 | MR | Zbl

[4] Gillette D., “Stochastic games with zero stop probabilities”, Contribution to the Theory of Games, v. III, Princeton, 1957, 179–187 | MR | Zbl

[5] Gurvich V. A., Karzanov A. V., Khachian L. G., “Cyclic games and an algorithm to find minimax cycle means in directed graphs”, USSR, Computational Mathematics and Mathematical Physics, 28 (1988), 85–91 | DOI | MR | Zbl

[6] Howard R. A., Dynamic Programming and Markov Processes, Wiley, 1960 | MR | Zbl

[7] Lal A. K., Sinha S., “Zero-sum two person semi-Markov games”, J. Appl. Prob., 29 (1992), 56–72 | DOI | MR | Zbl

[8] Lozovanu D., “The game-theoretical approach to Markov decision problems and determining Nash equilibria for stochastic positional games”, Int. J. Mathematical Modelling and Numerical Optimization, 2:2 (2011), 162–164

[9] Lozovanu D., Pickl S., “Nash equilibria conditions for Cyclic Games with $p$ players”, Electronic Notes in Discrete Mathematics, 25 (2006), 117–124 | DOI | MR

[10] Lozovanu D., Pickl S., Optimization and Multiobjective Control of Time-Discrete Systems, Springer, 2009 | MR

[11] Lozovanu D., Pickl S., Kropat E., “Markov decision processes and determining Nash equilibria for stochastic positional games”, Proceedings of 18th World Congress IFAC-2011, 2011, 13398–13493

[12] Lozovanu D., Pickl S., “Antagonistic Positional Games in Markov Decision Processes and Algorithms for Determining the Saddle Points”, Discrete Applied Mathematics, 2014 (to appear)

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

[14] Moulin H., Prolongement des jeux a deux joueurs de somme nulle, Bull. Soc. Math. France., Mem., 45, 1976 | Zbl

[15] Nash J. F., “Non cooperative games”, Annals of Mathematics, 2 (1951), 286–295 | DOI | MR | Zbl

[16] Neyman A., Sorin S., Stochastic games and applications, NATO ASI series, Kluwer Academic press, 2003 | MR

[17] Puterman M., Markov Decision Processes: Stochastic Dynamic Programming, John Wiley, New Jersey, 2005 | Zbl

[18] Shapley L., “Stochastic games”, Proc. Natl. Acad. Sci. U.S.A., 39 (1953), 1095–1100 | DOI | MR | Zbl