<![CDATA[MoneyScience: Quantitative Finance at arXiv's blog: 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])]]>
http://www.moneyscience.com/pg/blog/arXiv/read/853799/the-route-to-chaos-in-routing-games-population-increase-drives-perioddoubling-instability-chaos-inefficiency-with-price-of-anarchy-equal-to-one-arxiv190602486v1-csgt?view=rss
http://www.moneyscience.com/pg/blog/arXiv/read/853799/the-route-to-chaos-in-routing-games-population-increase-drives-perioddoubling-instability-chaos-inefficiency-with-price-of-anarchy-equal-to-one-arxiv190602486v1-csgtThu, 06 Jun 2019 23:02:11 -0500
http://www.moneyscience.com/pg/blog/arXiv/read/853799/the-route-to-chaos-in-routing-games-population-increase-drives-perioddoubling-instability-chaos-inefficiency-with-price-of-anarchy-equal-to-one-arxiv190602486v1-csgt
<![CDATA[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])]]>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.
read more...