0887f1a5b9970ad13f46b8c1485f7900-Paper.pdf

Routing games are amongst the most studied classes of games in game theory. Their most well-known property is that learning dynamics typically converge to equilibria implying approximately optimal performance (low Price of Anarchy). We perform a stress test for these classic results by studying the ubiquitous learning dynamics, Multiplicative Weights Update (MWU), in different classes of congestion games, uncovering intricate non-equilibrium phenomena. We study MWU using the actual game costs without applying cost normalization to [0, 1]. Although this non-standard assumption leads to large regret, it captures realistic agents' behaviors.