Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos

Abstract

The Multiplicative Weights Update (MWU) method is a ubiquitous meta-algorithm that works as follows: A distribution is maintained on a certain set, and at each step the probability assigned to element $\gamma$ is multiplied by $(1-\epsilon C(\gamma ))>0$ where $C(\gamma )$ is the "cost" of element $\gamma$ and then rescaled to ensure that the new values form a distribution. We analyze MWU in congestion games where agents use \textit{arbitrary admissible constants} as learning rates $\epsilon$ and prove convergence to \textit{exact Nash equilibria}. Our proof leverages a novel connection between MWU and the Baum-Welch algorithm, the standard instantiation of the Expectation-Maximization (EM) algorithm for hidden Markov models (HMM). Interestingly, this convergence result does not carry over to the nearly homologous MWU variant where at each step the probability assigned to element $\gamma$ is multiplied by $(1-\epsilon {)}^{C(\gamma )}$ even for the most innocuous case of two-agent, two-strategy load balancing games, where such dynamics can provably lead to limit cycles or even chaotic behavior.

17 pages, 9 figures

Cited by in corpus (10)

• Scaling up Mean Field Games with Online Mirror Descent
• Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games
• Smooth markets: A basic mechanism for organizing gradient-based learners
• Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes
• Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games
• Chaos of Learning Beyond Zero-sum and Coordination via Game Decompositions
• Learning in Matrix Games can be Arbitrarily Complex
• Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information
• Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamics
• Catastrophe by Design in Population Games: Destabilizing Wasteful Locked-in Technologies