Remember me

Register  |   Lost password?


 

arXiv logo for blog page


The route to chaos in routing games: Population increase drives period-doubling instability, chaos & inefficiency with Price of Anarchy equal to one. (arXiv:1906.02486v1 [cs.GT])

Thu, 06 Jun 2019 23:02:11 GMT

We study a learning dynamic model of routing (congestion) games to explore
how an increase in the total demand influences system performance. We focus on
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 equilibrium analysis suggests that system performance
is close to optimal in the large population limit, as seen by the Price of
Anarchy reduction. In this work, however, we reveal a rather undesirable
consequence of non-equilibrium phenomena driven by population increase. As the
total demand rises, we prove that the learning dynamics unavoidably become
non-equilibrating, typically chaotic. The Price of Anarchy predictions of
near-optimal performance no longer apply. To the contrary, the time-average
social cost may converge to its worst possible value in the large population
limit.

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. A single periodic attractor of
period two replaces the attracting fixed point when the demand exceeds the
carrying capacity. In general, 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. Remarkably, in any
non-equilibrating regime, the time-average flows on the edges converge {\it
exactly} to the equilibrium flows, a property akin to no-regret learning in
zero-sum games. Our results extend to any sequence of shrinking learning rates,
e.g., $1/\sqrt{T}$, by allowing for a dynamically increasing population size.