1 Search Results for "Sølvsten, Steffan Christ"

Document
DOI: 10.4230/LIPIcs.MFCS.2020.45
∃ℝ-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games

Authors: Kristoffer Arnsfelt Hansen and Steffan Christ Sølvsten

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

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.
Cite as

Kristoffer Arnsfelt Hansen and Steffan Christ Sølvsten. ∃ℝ-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hansen_et_al:LIPIcs.MFCS.2020.45,
  author =	{Hansen, Kristoffer Arnsfelt and S{\o}lvsten, Steffan Christ},
  title =	{{\exists\mathbb{R}-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 =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.45},
  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}
}
  • Refine by Author
  • 1 Hansen, Kristoffer Arnsfelt
  • 1 Sølvsten, Steffan Christ

  • Refine by Classification
  • 1 Theory of computation → Exact and approximate computation of equilibria
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Existential Theory of the Reals
  • 1 Perfect Information Stochastic Games
  • 1 Stationary Nash Equilibrium

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact