Nash Equilibria Conditions for Stochastic Positional Games

Authors

  • Dmitrii Lozovanu Academy of Sciences of Moldova
  • Stefan Pickl Universität der Bundeswehr

Abstract

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.

Keywords:

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

Downloads

Download data is not yet available.

References

Condon, A. (1992). The complexity of stochastic games. Informations and Computation. 96(2), 203–224.

Ehrenfeucht, A., Mycielski, J. (1979). Positional strategies for mean payoff games. International Journal of Game Theory, 8, 109–113. 8–113.

Filar, J.A., Vrieze, K. (1997). Competitive Markov Decision Processes. Springer, 1997.

Gillette, D. (1957). Stochastic games with zero stop probabilities. Contribution to the Theory of Games, vol. III, Princeton, 179–187.

Gurvich, V.A., Karzanov, A.V., Khachian, L.G. (1988). Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR, Computational Mathematics and Mathematical Physics, 28, 85–91.

Howard, R.A. (1960). Dynamic Programming and Markov Processes. Wiley.

Lal, A.K., Sinha S. (1992). Zero-sum two person semi-Markov games, J. Appl. Prob., 29, 56–72.

Lozovanu, D. (2011). 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), 162–164.

Lozovanu, D., Pickl, S. (2006). Nash equilibria conditions for Cyclic Games with p players. Eletronic Notes in Discrete Mathematics, 25, 117–124.

Lozovanu, D., Pickl, S. (2009). Optimization and Multiobjective Control of Time-Discrete Systems. Springer

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

Lozovanu, D., Pickl, S. (2014) Antagonistic Positional Games in Markov Decision Processes and Algorithms for Determining the Saddle Points. Discrete Applied Mathematics, 2014 (Accepted for publication).

Mertens, J.F., Neyman, A. (1981) Stochastic games. International Journal of Game Theory, 10, 53–66.

Moulin, H. (1976) Prolongement des jeux a deux joueurs de somme nulle. Bull. Soc. Math. France., Mem 45.

Nash, J.F. (1951) Non cooperative games. Annals of Mathematics, 2, 286–295.

Neyman, A., Sorin, S. (2003). Stochastic games and applications. NATO ASI series, Kluver Academic press.

Puterman, M. (2005). Markov Decision Processes: Stochastic Dynamic Programming. John Wiley, New Jersey.

Shapley L. (1953). Stochastic games. Proc. Natl. Acad. Sci. U.S.A. 39, 1095–1100.

Downloads

Published

2022-08-09

How to Cite

Lozovanu, D., & Pickl, . S. (2022). Nash Equilibria Conditions for Stochastic Positional Games. Contributions to Game Theory and Management, 7. Retrieved from https://gametheory.spbu.ru/article/view/13603

Issue

Section

Articles