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: |
[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.
![]() |