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

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

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

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, 2022, 1 (2) : 287-319. 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: 

Metrics

  • PDF downloads (136)
  • HTML views (196)
  • Cited by (0)

Other articles
by authors

[Back to Top]