F. Falniowski: "Robust routes to chaos in congestion games: The effects of scale on learning dynamics"

We study the effects of increasing the population size/scale of costs in congestion games and generalize recent results for the well known Multiplicative Weights Update dynamic to a large class of Follow-the-Regularized Leader dynamics (FoReL). We prove that even in simple linear congestion games with two parallel links as the population/scale increases, learning becomes unstable and (unless the game is fully symmetric) eventually Li-Yorke chaotic. Despite their chaotic instability, the dynamics provably converge in a time-average sense to an exact equilibrium for any choice of learning rate and any scale of costs.