–
November 25, 2021
Abstract:
Recently long-term behavior of the discrete counterpart of replicator dynamics - Multiplicative Weights Update (MWU) and its natural generalization - Follow the Regularized Leader (FTRL) were thoroughly studied. It turned out that in many game theoretic contexts the dynamics introduced by these algorithms can become very complex and hard to predict.
In this talk I will describe how chaotic behavior of agents may emerge in a simple congestion game where agents use one of these algorithms. To test the robustness of chaos I will introduce discounting of the past by agents. This results in a dynamics closely related to penalty-regulated dynamics [1] and EWA dynamics [2,3]. I will discuss how interplay between discounting the past and characteristics of the game (costs of different paths) affects chaotic behavior.
[1] P. Coucheney, B. Gaujal, P. Mertikopoulos. "Penalty-regulated dynamics and robust learning procedures in games." Mathematics of Operations Research 40.3 (2015): 611-633.
[2] T. Galla, J. D. Farmer. "Complex dynamics in learning complicated games." Proceedings of the National Academy of Sciences 110.4 (2013): 1232-1236.
[3] M. Pangallo, T. Heinrich, J. D. Farmer. "Best reply structure and equilibrium convergence in generic games." Science Advances 5.2 (2019): eaat1328.
