On the Complexity of Stationary Nash Equilibria in Discounted Perfect Information Stochastic Games
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914090439409664 |
|---|---|
| author | Hansen, Kristoffer Arnsfelt Nie, Xinhao |
| author_facet | Hansen, Kristoffer Arnsfelt Nie, Xinhao |
| contents | We study the problem of computing stationary Nash equilibria in discounted perfect information stochastic games from the viewpoint of computational complexity. For two-player games we prove the problem to be in PPAD, which together with a previous PPAD-hardness result precisely classifies the problem as PPAD-complete. In addition to this we give an improved and simpler PPAD-hardness proof for computing a stationary epsilon-Nash equilibrium. For 3-player games we construct games showing that rational-valued stationary Nash equilibria are not guaranteed to exist, and we use these to prove SqrtSum-hardness of computing a stationary Nash equilibrium in 4-player games. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_11550 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Complexity of Stationary Nash Equilibria in Discounted Perfect Information Stochastic Games Hansen, Kristoffer Arnsfelt Nie, Xinhao Computer Science and Game Theory Computational Complexity We study the problem of computing stationary Nash equilibria in discounted perfect information stochastic games from the viewpoint of computational complexity. For two-player games we prove the problem to be in PPAD, which together with a previous PPAD-hardness result precisely classifies the problem as PPAD-complete. In addition to this we give an improved and simpler PPAD-hardness proof for computing a stationary epsilon-Nash equilibrium. For 3-player games we construct games showing that rational-valued stationary Nash equilibria are not guaranteed to exist, and we use these to prove SqrtSum-hardness of computing a stationary Nash equilibrium in 4-player games. |
| title | On the Complexity of Stationary Nash Equilibria in Discounted Perfect Information Stochastic Games |
| topic | Computer Science and Game Theory Computational Complexity |
| url | https://arxiv.org/abs/2510.11550 |