2026-07-23T20:02:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12711 2024-03-06T10:50:39Z ddc:004 open_access

∃ℝ-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games Hansen, Kristoffer Arnsfelt Sølvsten, Steffan Christ Existential Theory of the Reals Stationary Nash Equilibrium Perfect Information Stochastic Games 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kristoffer Arnsfelt Hansen and Steffan Christ Sølvsten 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.45 urn:nbn:de:0030-drops-127113 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.45 eng https://creativecommons.org/licenses/by/3.0/legalcode