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

Athanasios Kehagias

doi:10.3934/jdg.2021028

Article Contents

2022, Volume 9, Issue 1: 117-122. Doi: 10.3934/jdg.2021028

This issue Previous Article Crisis risk prediction with concavity from Polymodel Next Article

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: October 31, 2020

Early access: November 2021

Published: January 2022

Abstract Full Text(HTML) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 91A06, 91A15; Secondary: 68R10.

Citation:

Full Text(HTML)

Related Papers

Cited by

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.