License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.45
URN: urn:nbn:de:0030-drops-127113
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12711/
Go to the corresponding LIPIcs Volume Portal

Hansen, Kristoffer Arnsfelt ; Sølvsten, Steffan Christ

∃ℝ-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games

pdf-format:
LIPIcs-MFCS-2020-45.pdf (0.5 MB)

Abstract

We show that the problem of deciding whether in a multi-player perfect information recursive game (i.e. a stochastic game with terminal rewards) there exists a stationary Nash equilibrium ensuring each player a certain payoff is ∃ℝ-complete. Our result holds for acyclic games, where a Nash equilibrium may be computed efficiently by backward induction, and even for deterministic acyclic games with non-negative terminal rewards. We further extend our results to the existence of Nash equilibria where a single player is surely winning. Combining our result with known gadget games without any stationary Nash equilibrium, we obtain that for cyclic games, just deciding existence of any stationary Nash equilibrium is ∃ℝ-complete. This holds for reach-a-set games, stay-in-a-set games, and for deterministic recursive games.

BibTeX - Entry

@InProceedings{hansen_et_al:LIPIcs:2020:12711,
  author =	{Kristoffer Arnsfelt Hansen and Steffan Christ S{\o}lvsten},
  title =	{{∃ℝ-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{45:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Javier Esparza and Daniel Kr{\'a}ľ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12711},
  URN =		{urn:nbn:de:0030-drops-127113},
  doi =		{10.4230/LIPIcs.MFCS.2020.45},
  annote =	{Keywords: Existential Theory of the Reals, Stationary Nash Equilibrium, Perfect Information Stochastic Games}
}

Keywords: Existential Theory of the Reals, Stationary Nash Equilibrium, Perfect Information Stochastic Games
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI