ε-Stationary Nash Equilibria in Multi-player Stochastic Graph Games
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908787592396800 |
|---|---|
| author | Asadi, Ali Brice, Léonard Chatterjee, Krishnendu Thejaswini, K. S. |
| author_facet | Asadi, Ali Brice, Léonard Chatterjee, Krishnendu Thejaswini, K. S. |
| contents | 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 $\exists\mathbb{R}$-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 that where the probabilities in the strategies are double-exponentially small. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_15356 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | ε-Stationary Nash Equilibria in Multi-player Stochastic Graph Games Asadi, Ali Brice, Léonard Chatterjee, Krishnendu Thejaswini, K. S. Computer Science and Game Theory 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 $\exists\mathbb{R}$-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 that where the probabilities in the strategies are double-exponentially small. |
| title | ε-Stationary Nash Equilibria in Multi-player Stochastic Graph Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2508.15356 |