{"ID":2856435,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.11550","arxiv_id":"2510.11550","title":"On the Complexity of Stationary Nash Equilibria in Discounted Perfect Information Stochastic Games","abstract":"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.","short_abstract":"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....","url_abs":"https://arxiv.org/abs/2510.11550","url_pdf":"https://arxiv.org/pdf/2510.11550v1","authors":"[\"Kristoffer Arnsfelt Hansen\",\"Xinhao Nie\"]","published":"2025-10-13T15:52:44Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"cs.CC\"]","methods":"[]","has_code":false}