Timezone: »
Poster
The route to chaos in routing games: When is price of anarchy too optimistic?
Thiparat Chotibut · Fryderyk Falniowski · Michał Misiurewicz · Georgios Piliouras
Routing games are amongst the most studied classes of games in game theory. Their most wellknown property is that learning dynamics typically converge to equilibria implying approximately optimal performance (low Price of Anarchy). We perform a stress test for these classic results by studying the ubiquitous learning dynamics, Multiplicative Weights Update (MWU), in different classes of congestion games, uncovering intricate nonequilibrium phenomena. We study MWU using the actual game costs without applying cost normalization to $[0,1]$. Although this nonstandard assumption leads to large regret, it captures realistic agents' behaviors. Namely, as the total demand increases, agents respond more aggressively to unbearably large costs.
We start with the illustrative case of nonatomic routing games with two paths of linear cost, and show that every system has a carrying capacity, above which it becomes unstable. If the equilibrium flow is a symmetric $5050\%$ split, the system exhibits one perioddoubling bifurcation. Although the Price of Anarchy is equal to one, in the large population limit the timeaverage social cost for all but a zero measure set of initial conditions converges to its worst possible value. For asymmetric equilibrium flows, increasing the demand eventually forces the system into LiYorke chaos with positive topological entropy and periodic orbits of all possible periods. Remarkably, in all nonequilibrating regimes, the timeaverage flows on the paths converge {\it exactly} to the equilibrium flows, a property akin to noregret learning in zerosum games. We extend our results to games with arbitrarily many strategies, polynomial cost functions, nonatomic as well as atomic routing games, and heterogenous users.
Author Information
Thiparat Chotibut (Chulalongkorn university)
A Theoretical and Computational Physicist at Chulalongkorn University, Bangkok, Thailand. I work on the problems at the interface among computer science, physics, and biology.
Fryderyk Falniowski (Cracow University of Economics)
Michał Misiurewicz (Indiana UniversityPurdue University Indianapolis)
Georgios Piliouras (Singapore University of Technology and Design)
More from the Same Authors

2020 Poster: NoRegret Learning and Mixed Nash Equilibria: They Do Not Mix »
EmmanouilVasileios VlatakisGkaragkounis · Lampros Flokas · Thanasis Lianeas · Panayotis Mertikopoulos · Georgios Piliouras 
2020 Poster: Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent »
Dimitris Fotakis · Thanasis Lianeas · Georgios Piliouras · Stratis Skoulakis 
2020 Spotlight: NoRegret Learning and Mixed Nash Equilibria: They Do Not Mix »
EmmanouilVasileios VlatakisGkaragkounis · Lampros Flokas · Thanasis Lianeas · Panayotis Mertikopoulos · Georgios Piliouras 
2020 Poster: Chaos, Extremism and Optimism: Volume Analysis of Learning in Games »
Yun Kuen Cheung · Georgios Piliouras 
2019 Poster: Efficiently avoiding saddle points with zero order methods: No gradients required »
EmmanouilVasileios VlatakisGkaragkounis · Lampros Flokas · Georgios Piliouras 
2019 Poster: Poincaré Recurrence, Cycles and Spurious Equilibria in GradientDescentAscent for NonConvex NonConcave ZeroSum Games »
EmmanouilVasileios VlatakisGkaragkounis · Lampros Flokas · Georgios Piliouras 
2019 Spotlight: Poincaré Recurrence, Cycles and Spurious Equilibria in GradientDescentAscent for NonConvex NonConcave ZeroSum Games »
EmmanouilVasileios VlatakisGkaragkounis · Lampros Flokas · Georgios Piliouras 
2019 Poster: Fast and Furious Learning in ZeroSum Games: Vanishing Regret with NonVanishing Step Sizes »
James Bailey · Georgios Piliouras