The route to chaos in routing games: When is Price of Anarchy too
optimistic?
Thiparat Chotibut, Fryderyk Falniowski, Michał Misiurewicz
and Georgios Piliouras
Abstract
Routing games are amongst the most studied classes of games. Their two
most well-known properties are that learning dynamics converge to
equilibria and that all equilibria are approximately optimal. In this
work, we perform a stress test for these classic results by studying
the ubiquitous dynamics, Multiplicative Weights Update, in different
classes of congestion games, uncovering intricate non-equilibrium
phenomena. As the system demand increases, the learning dynamics go
through period-doubling bifurcations, leading to instabilities, chaos
and large ineficiencies even in the simplest case of non-atomic
routing games with two paths of linear cost where the Price of Anarchy
is equal to one. Starting with this simple class, we show that every
system has a carrying capacity, above which it becomes unstable. If
the equilibrium flow is a symmetric 50-50% split, the system exhibits
one period-doubling bifurcation. A single periodic attractor of period
two replaces the attracting fixed point. Although the Price of Anarchy
is equal to one, in the large population limit the time-average 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 Li-Yorke chaos with
positive topological entropy and periodic orbits of all possible
periods. Remarkably, in all non-equilibrating regimes, the
time-average flows on the paths converge exactly to the equilibrium
flows, a property akin to no-regret learning in zero-sum games. These
results are robust. We extend them to routing games with arbitrarily
many strategies, polynomial cost functions, non-atomic as well as
atomic routing games and heteregenous users. Our results are also
applicable to any sequence of shrinking learning rates, e.g.,
1/√T, by allowing for a dynamically increasing population size.