Simultaneous Best-Response Dynamics in Random Potential Games
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916739214737408 |
|---|---|
| author | Ashkenazi-Golan, Galit Cecchelli, Domenico Mergoni Plumb, Edward |
| author_facet | Ashkenazi-Golan, Galit Cecchelli, Domenico Mergoni Plumb, Edward |
| contents | This paper examines the convergence behaviour of simultaneous best-response dynamics in random potential games. We provide a theoretical result showing that, for two-player games with sufficiently many actions, the dynamics converge quickly to a cycle of length two. This cycle lies within the intersection of the neighbourhoods of two distinct Nash equilibria. For three players or more, simulations show that the dynamics converge quickly to a Nash equilibrium with high probability. Furthermore, we show that all these results are robust, in the sense that they hold in non-potential games, provided the players' payoffs are sufficiently correlated. We also compare these dynamics to gradient-based learning methods in near-potential games with three players or more, and observe that simultaneous best-response dynamics converge to a Nash equilibrium of comparable payoff substantially faster. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_10378 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Simultaneous Best-Response Dynamics in Random Potential Games Ashkenazi-Golan, Galit Cecchelli, Domenico Mergoni Plumb, Edward Computer Science and Game Theory This paper examines the convergence behaviour of simultaneous best-response dynamics in random potential games. We provide a theoretical result showing that, for two-player games with sufficiently many actions, the dynamics converge quickly to a cycle of length two. This cycle lies within the intersection of the neighbourhoods of two distinct Nash equilibria. For three players or more, simulations show that the dynamics converge quickly to a Nash equilibrium with high probability. Furthermore, we show that all these results are robust, in the sense that they hold in non-potential games, provided the players' payoffs are sufficiently correlated. We also compare these dynamics to gradient-based learning methods in near-potential games with three players or more, and observe that simultaneous best-response dynamics converge to a Nash equilibrium of comparable payoff substantially faster. |
| title | Simultaneous Best-Response Dynamics in Random Potential Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2505.10378 |