Reproduce “Pointwise Convergence in Games with Conflicting Interest” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Nanxiang Zhou, Jing Dong, Baoxiang Wang
Researchers at The Chinese University of Hong Kong introduce "non-negative weighted regret" as a framework to unify the analysis of harmonic games and zero-sum games. They demonstrate that optimistic learning algorithms, specifically Optimistic Mirror Descent and Optimistic Follow the Regularized Leader, achieve pointwise convergence to a Nash equilibrium in these games when the equilibrium set is discrete, even under finite strategic deviations.
Key insights
- The proposed "non-negative weighted regret" successfully unifies harmonic games and key classes of zero-sum games under a common theoretical framework, simplifying analysis of learning dynamics in conflicting interest scenarios.
- Optimistic learning algorithms (OMD and OFTRL) not only converge to approximate Nash equilibria at an $O(1/\epsilon^2)$ rate but also achieve asymptotic convergence to the set of Nash equilibria in these game classes.
- A significant finding is the establishment of pointwise convergence to a single Nash equilibrium when the set of equilibria is discrete, providing a stronger and more desirable theoretical guarantee than previous work.
- The algorithms demonstrate remarkable robustness, maintaining their convergence properties (approximate, asymptotic, and pointwise to discrete NE) even when players cumulatively deviate by a finite amount from prescribed strategies.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.