2025/05/21 by Jing Dong, Zhou, Nanxiang, Dong, Jing +2 · 1 citation
Decision Sciences · Economics, Econometrics and Finance · Physics and Astronomy · #Computer Science and Game Theory (cs.GT) #Economic theories and models #FOS: Computer and information sciences #Game Theory and Applications #Opinion Dynamics and Social Influence
paper · pdf · doi:10.48550/arxiv.2505.15454
openalex publication_date 2025/05/21 · openalex created_date 2025/10/19 · openalex updated_date 2026/07/28
In this work, we introduce the concept of non-negative weighted regret, an extension of non-negative regret \citeanagnostides2022last 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.