Pointwise Convergence in Games with Conflicting Interest
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_ | 1866910959544565760 |
|---|---|
| author | Zhou, Nanxiang Dong, Jing Wang, Baoxiang |
| author_facet | Zhou, Nanxiang Dong, Jing Wang, Baoxiang |
| contents | In this work, we introduce the concept of non-negative weighted regret, an extension of non-negative regret \cite{anagnostides2022last} in games. Investigating games with non-negative weighted regret helps us to understand games with conflicting interests, including harmonic games and important classes of zero-sum games.We show that optimistic variants of classical no-regret learning algorithms, namely optimistic mirror descent (OMD) and optimistic follow the regularized leader (OFTRL), converge to an $ε$-approximate Nash equilibrium at a rate of $O(1/ε^2)$.Consequently, they guarantee pointwise convergence to a Nash equilibrium if there are only finitely many Nash equilibria in the game. These algorithms are robust in the sense the convergence holds even if the players deviate Our theoretical findings are supported by empirical evaluations of OMD and OFTRL on the game of matching pennies and harmonic game instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_15454 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Pointwise Convergence in Games with Conflicting Interest Zhou, Nanxiang Dong, Jing Wang, Baoxiang Computer Science and Game Theory In this work, we introduce the concept of non-negative weighted regret, an extension of non-negative regret \cite{anagnostides2022last} in games. Investigating games with non-negative weighted regret helps us to understand games with conflicting interests, including harmonic games and important classes of zero-sum games.We show that optimistic variants of classical no-regret learning algorithms, namely optimistic mirror descent (OMD) and optimistic follow the regularized leader (OFTRL), converge to an $ε$-approximate Nash equilibrium at a rate of $O(1/ε^2)$.Consequently, they guarantee pointwise convergence to a Nash equilibrium if there are only finitely many Nash equilibria in the game. These algorithms are robust in the sense the convergence holds even if the players deviate Our theoretical findings are supported by empirical evaluations of OMD and OFTRL on the game of matching pennies and harmonic game instances. |
| title | Pointwise Convergence in Games with Conflicting Interest |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2505.15454 |