Skip to Main content Skip to Navigation
Conference papers

No-regret learning and mixed Nash equilibria: They do not mix

Abstract : Understanding the behavior of no-regret dynamics in general N-player games is a fundamental question in online learning and game theory. A folk result in the field states that, in finite games, the empirical frequency of play under no-regret learning converges to the game's set of coarse correlated equilibria. By contrast, our understanding of how the day-today behavior of the dynamics correlates to the game's Nash equilibria is much more limited, and only partial results are known for certain classes of games (such as zero-sum or congestion games). In this paper, we study the dynamics of follow the regularized leader (FTRL), arguably the most well-studied class of no-regret dynamics, and we establish a sweeping negative result showing that the notion of mixed Nash equilibrium is antithetical to no-regret learning. Specifically, we show that any Nash equilibrium which is not strict (in that every player has a unique best response) cannot be stable and attracting under the dynamics of FTRL. This result has significant implications for predicting the outcome of a learning process as it shows unequivocally that only strict (and hence, pure) Nash equilibria can emerge as stable limit points thereof.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-03043763
Contributor : Panayotis Mertikopoulos <>
Submitted on : Monday, December 7, 2020 - 2:16:58 PM
Last modification on : Friday, December 18, 2020 - 6:46:06 PM

File

UnstableNash-NIPS.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03043763, version 1

Citation

Lampros Flokas, Emmanouil Vlatakis-Gkaragkounis, Thanasis Lianeas, Panayotis Mertikopoulos, Georgios Piliouras. No-regret learning and mixed Nash equilibria: They do not mix. NeurIPS '20: The 34th International Conference on Neural Information Processing Systems, 2020, Vancouver, Canada. ⟨hal-03043763⟩

Share

Metrics

Record views

9

Files downloads

61