American Institute of Mathematical Sciences

Advanced
January  2022, 9(1): 117-122. doi: 10.3934/jdg.2021028

A note on the Nash equilibria of some multi-player reachability/safety games

Athanasios Kehagias

Department of Electrical and Computer Engineering, Aristotle University of Thessaloniki, Thessaloniki, Greece

Received  November 2020 Published  January 2022 Early access  November 2021

In this short note we study a class of multi-player, turn-based games with deterministic state transitions and reachability / safety objectives (this class contains as special cases "classic" two-player reachability and safety games as well as multi-player and ""stay–in-a-set" and "reach-a-set" games). Quantitative and qualitative versions of the objectives are presented and for both cases we prove the existence of a deterministic and memoryless Nash equilibrium; the proof is short and simple, using only Fink's classic result about the existence of Nash equilibria for multi-player discounted stochastic games

Keywords: Stochastic Games, N-player Games, Reachability, Nash Equilibrium, Graph Games.
Mathematics Subject Classification: Primary: 91A06, 91A15; Secondary: 68R10.
Citation: Athanasios Kehagias. A note on the Nash equilibria of some multi-player reachability/safety games. Journal of Dynamics and Games, 2022, 9 (1) : 117-122. doi: 10.3934/jdg.2021028
References:
[1]

K. Chatterjee, R. Majumdar and M. Jurdziński, On Nash Equilibria in Stochastic Games, Report No.UCB/CSD-3-1281, 2003, Computer Science Division (EECS), Univ. of California at Berkeley.

[2]

K. Chatterjee, R. Majumdar and M. Jurdziński, On Nash Equilibria in Stochastic Games, International Workshop on Computer Science Logic, Springer, Berlin, Heidelberg, 2004.

[3]

K. Chatterjee and T. A. Henzinger, A survey of stochastic $\omega$-regular games, Journal of Computer and System Sciences, 78 (2012), 394-413.  doi: 10.1016/j.jcss.2011.05.002.

[4]

J. Filar and K. Vrieze, Competitive Markov Decision Processes: Heory, Algorithms, and Applications, Springer-Verlag, New York, 1997.

[5]

A. M. Fink, Equilibrium in a stochastic $n$-person game, Journal of science of the Hiroshima University, Series Ai (Mathematics), 28 (1964), 89-93. 

[6]

A. Maitra and W. D. Sudderth, Borel stay-in-a-set games, International Journal of Game Theory, 32 (2003), 97-108.  doi: 10.1007/s001820300148.

[7]

R. Mazala, Infinite games, in Automata Logics, and Infinite Games, Springer, 2500 (2002), 23–38. doi: 10.1007/3-540-36387-4_2.

[8]

P. Secchi and W. D. Sudderth, Stay-in-a-set games, International Journal of Game Theory, 30 (2002), 479-490.  doi: 10.1007/s001820200092.

[9] M. Ummels, Stochastic Multiplayer Games: Theory and Algorithms, Amsterdam University Press, 2010. 

show all references

References:
[1]

K. Chatterjee, R. Majumdar and M. Jurdziński, On Nash Equilibria in Stochastic Games, Report No.UCB/CSD-3-1281, 2003, Computer Science Division (EECS), Univ. of California at Berkeley.

[2]

K. Chatterjee, R. Majumdar and M. Jurdziński, On Nash Equilibria in Stochastic Games, International Workshop on Computer Science Logic, Springer, Berlin, Heidelberg, 2004.

[3]

K. Chatterjee and T. A. Henzinger, A survey of stochastic $\omega$-regular games, Journal of Computer and System Sciences, 78 (2012), 394-413.  doi: 10.1016/j.jcss.2011.05.002.

[4]

J. Filar and K. Vrieze, Competitive Markov Decision Processes: Heory, Algorithms, and Applications, Springer-Verlag, New York, 1997.

[5]

A. M. Fink, Equilibrium in a stochastic $n$-person game, Journal of science of the Hiroshima University, Series Ai (Mathematics), 28 (1964), 89-93. 

[6]

A. Maitra and W. D. Sudderth, Borel stay-in-a-set games, International Journal of Game Theory, 32 (2003), 97-108.  doi: 10.1007/s001820300148.

[7]

R. Mazala, Infinite games, in Automata Logics, and Infinite Games, Springer, 2500 (2002), 23–38. doi: 10.1007/3-540-36387-4_2.

[8]

P. Secchi and W. D. Sudderth, Stay-in-a-set games, International Journal of Game Theory, 30 (2002), 479-490.  doi: 10.1007/s001820200092.

[9] M. Ummels, Stochastic Multiplayer Games: Theory and Algorithms, Amsterdam University Press, 2010. 
[1]

Getachew K. Befekadu, Panos J. Antsaklis. On noncooperative $n$-player principal eigenvalue games. Journal of Dynamics and Games, 2015, 2 (1) : 51-63. doi: 10.3934/jdg.2015.2.51
[2]

Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics and Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006
[3]

Rui Mu, Zhen Wu. Nash equilibrium points of recursive nonzero-sum stochastic differential games with unbounded coefficients and related multiple\\ dimensional BSDEs. Mathematical Control and Related Fields, 2017, 7 (2) : 289-304. doi: 10.3934/mcrf.2017010
[4]

Dean A. Carlson. Finding open-loop Nash equilibrium for variational games. Conference Publications, 2005, 2005 (Special) : 153-163. doi: 10.3934/proc.2005.2005.153
[5]

Lasse Kliemann, Elmira Shirazi Sheykhdarabadi, Anand Srivastav. Price of anarchy for graph coloring games with concave payoff. Journal of Dynamics and Games, 2017, 4 (1) : 41-58. doi: 10.3934/jdg.2017003
[6]

Alejandra Fonseca-Morales, Onésimo Hernández-Lerma. A note on differential games with Pareto-optimal NASH equilibria: Deterministic and stochastic models†. Journal of Dynamics and Games, 2017, 4 (3) : 195-203. doi: 10.3934/jdg.2017012
[7]

Borun Shi, Robert A. Van Gorder. Nonlinear dynamics from discrete time two-player status-seeking games. Journal of Dynamics and Games, 2017, 4 (4) : 335-359. doi: 10.3934/jdg.2017018
[8]

Xiangxiang Huang, Xianping Guo, Jianping Peng. A probability criterion for zero-sum stochastic games. Journal of Dynamics and Games, 2017, 4 (4) : 369-383. doi: 10.3934/jdg.2017020
[9]

Jingzhen Liu, Ka-Fai Cedric Yiu. Optimal stochastic differential games with VaR constraints. Discrete and Continuous Dynamical Systems - B, 2013, 18 (7) : 1889-1907. doi: 10.3934/dcdsb.2013.18.1889
[10]

Alain Bensoussan, Jens Frehse, Christine Grün. Stochastic differential games with a varying number of players. Communications on Pure and Applied Analysis, 2014, 13 (5) : 1719-1736. doi: 10.3934/cpaa.2014.13.1719
[11]

Mathias Staudigl, Srinivas Arigapudi, William H. Sandholm. Large deviations and Stochastic stability in Population Games. Journal of Dynamics and Games, 2021  doi: 10.3934/jdg.2021021
[12]

Samuel Drapeau, Peng Luo, Alexander Schied, Dewen Xiong. An FBSDE approach to market impact games with stochastic parameters. Probability, Uncertainty and Quantitative Risk, 2021, 6 (3) : 237-260. doi: 10.3934/puqr.2021012
[13]

Jiequn Han, Ruimeng Hu, Jihao Long. Convergence of deep fictitious play for stochastic differential games. Frontiers of Mathematical Finance, , () : -. doi: 10.3934/fmf.2021011
[14]

Yu Chen. Delegation principle for multi-agency games under ex post equilibrium. Journal of Dynamics and Games, 2018, 5 (4) : 311-329. doi: 10.3934/jdg.2018019
[15]

Alan Beggs. Learning in monotone bayesian games. Journal of Dynamics and Games, 2015, 2 (2) : 117-140. doi: 10.3934/jdg.2015.2.117
[16]

Konstantin Avrachenkov, Giovanni Neglia, Vikas Vikram Singh. Network formation games with teams. Journal of Dynamics and Games, 2016, 3 (4) : 303-318. doi: 10.3934/jdg.2016016
[17]

Carlos Hervés-Beloso, Emma Moreno-García. Market games and walrasian equilibria. Journal of Dynamics and Games, 2020, 7 (1) : 65-77. doi: 10.3934/jdg.2020004
[18]

Hassan Najafi Alishah, Pedro Duarte. Hamiltonian evolutionary games. Journal of Dynamics and Games, 2015, 2 (1) : 33-49. doi: 10.3934/jdg.2015.2.33
[19]

Dario Bauso, Thomas W. L. Norman. Approachability in population games. Journal of Dynamics and Games, 2020, 7 (4) : 269-289. doi: 10.3934/jdg.2020019
[20]

Yonghui Zhou, Jian Yu, Long Wang. Topological essentiality in infinite games. Journal of Industrial and Management Optimization, 2012, 8 (1) : 179-187. doi: 10.3934/jimo.2012.8.179

 Impact Factor: 

Tools

Article outline

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy