Last-iterate Convergence for Symmetric, General-sum, $2 \times 2$ Games Under The Exponential Weights Dynamic
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_ | 1866909996191580160 |
|---|---|
| author | Wang, Guanghui Acharya, Krishna Lakshmikanthan, Lokranjan Ziani, Juba Muthukumar, Vidya |
| author_facet | Wang, Guanghui Acharya, Krishna Lakshmikanthan, Lokranjan Ziani, Juba Muthukumar, Vidya |
| contents | We conduct a comprehensive analysis of the discrete-time exponential-weights dynamic with a constant step size on all general-sum and symmetric $2 \times 2$ normal-form games, i.e. games with $2$ pure strategies per player, and where the ensuing payoff tuple is of the form $(A,A^\top)$ (where $A$ is the $2 \times 2$ payoff matrix corresponding to the first player). Such symmetric games commonly arise in real-world interactions between 'symmetric" agents who have identically defined utility functions -- such as Bertrand competition and multi-agent performative prediction, and display a rich multiplicity of equilibria despite the seemingly simple setting. Somewhat surprisingly, we show through a first-principles analysis that the exponential weights dynamic, which is popular in online learning, converges in the last iterate for such games regardless of initialization with an appropriately chosen step size. For certain games and/or initializations, we further show that the convergence rate is in fact exponential and holds for any step size.
We illustrate our theory with extensive simulations and applications to the aforementioned game-theoretic interactions. In the case of multi-agent performative prediction, we formulate a new "mortgage competition" game between lenders (i.e. banks) who interact with a population of customers, and show that it fits into our framework. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_08063 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Last-iterate Convergence for Symmetric, General-sum, $2 \times 2$ Games Under The Exponential Weights Dynamic Wang, Guanghui Acharya, Krishna Lakshmikanthan, Lokranjan Ziani, Juba Muthukumar, Vidya Computer Science and Game Theory Machine Learning We conduct a comprehensive analysis of the discrete-time exponential-weights dynamic with a constant step size on all general-sum and symmetric $2 \times 2$ normal-form games, i.e. games with $2$ pure strategies per player, and where the ensuing payoff tuple is of the form $(A,A^\top)$ (where $A$ is the $2 \times 2$ payoff matrix corresponding to the first player). Such symmetric games commonly arise in real-world interactions between 'symmetric" agents who have identically defined utility functions -- such as Bertrand competition and multi-agent performative prediction, and display a rich multiplicity of equilibria despite the seemingly simple setting. Somewhat surprisingly, we show through a first-principles analysis that the exponential weights dynamic, which is popular in online learning, converges in the last iterate for such games regardless of initialization with an appropriately chosen step size. For certain games and/or initializations, we further show that the convergence rate is in fact exponential and holds for any step size. We illustrate our theory with extensive simulations and applications to the aforementioned game-theoretic interactions. In the case of multi-agent performative prediction, we formulate a new "mortgage competition" game between lenders (i.e. banks) who interact with a population of customers, and show that it fits into our framework. |
| title | Last-iterate Convergence for Symmetric, General-sum, $2 \times 2$ Games Under The Exponential Weights Dynamic |
| topic | Computer Science and Game Theory Machine Learning |
| url | https://arxiv.org/abs/2502.08063 |