- Previous Article
- JDG Home
- This Issue
-
Next Article
Crisis risk prediction with concavity from Polymodel
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 |
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
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]