2026-07-22T11:00:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25089 2026-02-09T08:06:03Z ddc:004 open_access

ε-Stationary Nash Equilibria in Multi-Player Stochastic Graph Games Asadi, Ali Brice, Léonard Chatterjee, Krishnendu Thejaswini, K. S. Nash Equilibria ε-Nash equilibria Approximation Existential Theory of Reals A strategy profile in a multi-player game is a Nash equilibrium if no player can unilaterally deviate to achieve a strictly better payoff. A profile is an ε-Nash equilibrium if no player can gain more than ε by unilaterally deviating from their strategy. In this work, we use ε-Nash equilibria to approximate the computation of Nash equilibria. Specifically, we focus on turn-based, multiplayer stochastic games played on graphs, where players are restricted to stationary strategies - strategies that use randomness but not memory. The problem of deciding the constrained existence of stationary Nash equilibria - where each player’s payoff must lie within a given interval - is known to be ∃ℝ-complete in such a setting (Hansen and Sølvsten, 2020). We extend this line of work to stationary ε-Nash equilibria and present an algorithm that solves the following promise problem: given a game with a Nash equilibrium satisfying the constraints, compute an ε-Nash equilibrium that ε-satisfies those same constraints - satisfies the constraints up to an ε additive error. Our algorithm runs in FNP^NP time. To achieve this, we first show that if a constrained Nash equilibrium exists, then one exists where the non-zero probabilities are at least an inverse of a double-exponential in the input. We further prove that such a strategy can be encoded using floating-point representations, as in the work of Frederiksen and Miltersen (2013), which finally gives us our FNP^NP algorithm. We further show that the decision version of the promise problem is NP-hard. Finally, we show a partial tightness result by proving a lower bound for such techniques: if a constrained Nash equilibrium exists, then there must be one where the probabilities in the strategies are double-exponentially small. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ali Asadi and Léonard Brice and Krishnendu Chatterjee and K. S. Thejaswini 2025 Is Part Of LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2025.9 urn:nbn:de:0030-drops-250897 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.9 eng https://creativecommons.org/licenses/by/4.0/legalcode