TY - GEN
T1 - ∃R-completeness of stationary nash equilibria in perfect information stochastic games
AU - Hansen, Kristoffer Arnsfelt
AU - Sølvsten, Steffan Christ
PY - 2020
Y1 - 2020
N2 - 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 ∃R-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 ∃R-complete. This holds for reach-a-set games, stay-in-a-set games, and for deterministic recursive games.
AB - 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 ∃R-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 ∃R-complete. This holds for reach-a-set games, stay-in-a-set games, and for deterministic recursive games.
KW - Existential Theory of the Reals
KW - Perfect Information Stochastic Games
KW - Stationary Nash Equilibrium
UR - https://www.scopus.com/pages/publications/85090507512
U2 - 10.4230/LIPIcs.MFCS.2020.45
DO - 10.4230/LIPIcs.MFCS.2020.45
M3 - Article in proceedings
AN - SCOPUS:85090507512
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 45:1-45:15
BT - 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020
A2 - Esparza, Javier
A2 - Král, Daniel
PB - Dagstuhl Publishing
T2 - 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020
Y2 - 24 August 2020 through 28 August 2020
ER -