Follow-the-Regularized-Leader Routes to Chaos in Routing Games

Jakub Bielawski, Thiparat Chotibut, Fryderyk Falniowski, Grzegorz Kosiorowski, Michał Misiurewicz, Georgios Piliouras
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:925-935, 2021.

Abstract

We study the emergence of chaotic behavior of Follow-the-Regularized Leader (FoReL) dynamics in games. We focus on the effects of increasing the population size or the scale of costs in congestion games, and generalize recent results on unstable, chaotic behaviors in the Multiplicative Weights Update dynamics to a much larger class of FoReL dynamics. We establish that, even in simple linear non-atomic congestion games with two parallel links and \emph{any} fixed learning rate, unless the game is fully symmetric, increasing the population size or the scale of costs causes learning dynamics to becomes unstable and eventually chaotic, in the sense of Li-Yorke and positive topological entropy. Furthermore, we prove the existence of novel non-standard phenomena such as the coexistence of stable Nash equilibria and chaos in the same game. We also observe the simultaneous creation of a chaotic attractor as another chaotic attractor gets destroyed. Lastly, although FoReL dynamics can be strange and non-equilibrating, we prove that the time average still converges to an \emph{exact} equilibrium for any choice of learning rate and any scale of costs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-bielawski21a, title = {Follow-the-Regularized-Leader Routes to Chaos in Routing Games}, author = {Bielawski, Jakub and Chotibut, Thiparat and Falniowski, Fryderyk and Kosiorowski, Grzegorz and Misiurewicz, Micha{\l} and Piliouras, Georgios}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {925--935}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/bielawski21a/bielawski21a.pdf}, url = {https://proceedings.mlr.press/v139/bielawski21a.html}, abstract = {We study the emergence of chaotic behavior of Follow-the-Regularized Leader (FoReL) dynamics in games. We focus on the effects of increasing the population size or the scale of costs in congestion games, and generalize recent results on unstable, chaotic behaviors in the Multiplicative Weights Update dynamics to a much larger class of FoReL dynamics. We establish that, even in simple linear non-atomic congestion games with two parallel links and \emph{any} fixed learning rate, unless the game is fully symmetric, increasing the population size or the scale of costs causes learning dynamics to becomes unstable and eventually chaotic, in the sense of Li-Yorke and positive topological entropy. Furthermore, we prove the existence of novel non-standard phenomena such as the coexistence of stable Nash equilibria and chaos in the same game. We also observe the simultaneous creation of a chaotic attractor as another chaotic attractor gets destroyed. Lastly, although FoReL dynamics can be strange and non-equilibrating, we prove that the time average still converges to an \emph{exact} equilibrium for any choice of learning rate and any scale of costs.} }
Endnote
%0 Conference Paper %T Follow-the-Regularized-Leader Routes to Chaos in Routing Games %A Jakub Bielawski %A Thiparat Chotibut %A Fryderyk Falniowski %A Grzegorz Kosiorowski %A Michał Misiurewicz %A Georgios Piliouras %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-bielawski21a %I PMLR %P 925--935 %U https://proceedings.mlr.press/v139/bielawski21a.html %V 139 %X We study the emergence of chaotic behavior of Follow-the-Regularized Leader (FoReL) dynamics in games. We focus on the effects of increasing the population size or the scale of costs in congestion games, and generalize recent results on unstable, chaotic behaviors in the Multiplicative Weights Update dynamics to a much larger class of FoReL dynamics. We establish that, even in simple linear non-atomic congestion games with two parallel links and \emph{any} fixed learning rate, unless the game is fully symmetric, increasing the population size or the scale of costs causes learning dynamics to becomes unstable and eventually chaotic, in the sense of Li-Yorke and positive topological entropy. Furthermore, we prove the existence of novel non-standard phenomena such as the coexistence of stable Nash equilibria and chaos in the same game. We also observe the simultaneous creation of a chaotic attractor as another chaotic attractor gets destroyed. Lastly, although FoReL dynamics can be strange and non-equilibrating, we prove that the time average still converges to an \emph{exact} equilibrium for any choice of learning rate and any scale of costs.
APA
Bielawski, J., Chotibut, T., Falniowski, F., Kosiorowski, G., Misiurewicz, M. & Piliouras, G.. (2021). Follow-the-Regularized-Leader Routes to Chaos in Routing Games. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:925-935 Available from https://proceedings.mlr.press/v139/bielawski21a.html.

Related Material