  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 inefficiencies 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/\sqrt{T}$, by
allowing for a dynamically increasing population size.
