The route to chaos in routing games: Population increase drives period-doubling instability and chaos with Price of Anarchy equal to one

We study a simple learning dynamic model of routing (congestion) games to explore the effects of increasing the total demand on system performance. We focus on the most benign setting, non-atomic routing games with two parallel edges of linear cost, where all agents evolve using Multiplicative Weights Updates with a fixed learning rate. Previous game-theoretic analysis suggests that system performance is improved in the large population limit, as seen by the reduction in the Price of Anarchy. In this work, however, we show that Price of Anarchy reduction comes at the cost of destabilizing the system. By increasing the total demand, we prove that the system eventually becomes chaotic, invalidating the Price of Anarchy predictions of near-optimal system performance. 

Every system has a carrying capacity, above which the dynamics is non-equilibrating. If the equilibrium flow is a symmetric $50-50\%$ split, the system exhibits one period-doubling bifurcation, so that a single periodic attractor of period two replaces the attracting fixed point when the demand exceeds the carrying capacity. For asymmetric equilibrium flows, increasing the demand destabilizes the system, so that the system eventually becomes Li-Yorke chaotic with positive topological entropy. This demand-driven instability emerges from any pair of linear cost functions, provided the game is not trivial, i.e., dominance solvable (e.g. Pigou network).  Lastly, in any non-equilibrating regime, the time-average flows on the edges converge {\it exactly} to the equilibrium values, a property akin to no-regret learning in zero-sum games. However, the time-average convergence property does not guarantee small regret nor low social costs, even when the Price of Anarchy is 1. In fact, time-average regret and social costs increase with fluctuations from equilibrium flows, which can be large for non-equilibrating dynamics. These unusual phenomena are of an algorithmic, dynamic nature, and are invisible in standard game-theoretic equilibrium or Price of Anarchy analysis.

Dr. Piliouras is an assistant professor at the Singapore University of Technology and Design (SUTD).  He received his PhD in Computer Science from Cornell University in 2010. He has held postdoc positions at the Georgia Institute of Technology (GaTech, ECE Dept.) and California Institute of Technology (Caltech, Dept. of Computing and Mathematical Sciences). He has held visiting positions at UC Berkeley and DeepMind and is a collaborator of the Ethereum Foundation. He is the recipient of a Singapore NRF Fellowship (2018) and a Simons/UC Berkeley Fellowship (2015).