∃R-completeness of stationary nash equilibria in perfect information stochastic games

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

DOI

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.

OriginalsprogEngelsk
Titel45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020
RedaktørerJavier Esparza, Daniel Král
Antal sider15
ForlagSchloss Dagstuhl--Leibniz-Zentrum für Informatik
Udgivelsesår2020
Sider45:1-45:15
ISBN (Elektronisk)9783959771597
DOI
StatusUdgivet - 2020
Begivenhed45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020 - Prague, Tjekkiet
Varighed: 24 aug. 202028 aug. 2020

Konference

Konference45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020
LandTjekkiet
ByPrague
Periode24/08/202028/08/2020
SerietitelLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind170
ISSN1868-8969

Se relationer på Aarhus Universitet Citationsformater

ID: 196913615