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

arXiv: https://arxiv.org/abs/1703.01138 · HTML: https://mlsanity.com/paper/1703.01138/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2017.

## Built on by (most cited first, 29 of 29)

- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence](https://mlsanity.com/paper/2202.04129/) (2022)
- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [Independent Natural Policy Gradient Always Converges in Markov Potential Games](https://mlsanity.com/paper/2110.10614/) (2021)
- [Multi-agent Performative Prediction: From Global Stability and Optimality to Chaos](https://mlsanity.com/paper/2201.10483/) (2022)
- [Scaling up Mean Field Games with Online Mirror Descent](https://mlsanity.com/paper/2103.00623/) (2021)
- [Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information](https://mlsanity.com/paper/2101.04667/) (2021)
- [Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update](https://mlsanity.com/paper/2111.14737/) (2021)
- [Learning in Matrix Games can be Arbitrarily Complex](https://mlsanity.com/paper/2103.03405/) (2021)
- [Follow-the-Regularized-Leader Routes to Chaos in Routing Games](https://mlsanity.com/paper/2102.07974/) (2021)
- [Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization](https://mlsanity.com/paper/2204.05466/) (2022)
- [The Group Loss++: A deeper look into group loss for deep metric learning](https://mlsanity.com/paper/2204.01509/) (2022)
- [Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics](https://mlsanity.com/paper/2203.14129/) (2022)
- [Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games](https://mlsanity.com/paper/2207.08426/) (2022)
- [The equivalence of dynamic and strategic stability under regularized learning in games](https://mlsanity.com/paper/2311.02407/) (2023)
- [Optimistic Games for Combinatorial Bayesian Optimization with Application to Protein Design](https://mlsanity.com/paper/2409.18582/) (2024)
- [Evolutionary Dynamics and Phi-Regret Minimization in Games](https://mlsanity.com/paper/2106.14668/) (2021)
- [Expressivity of Neural Networks via Chaotic Itineraries beyond Sharkovsky's Theorem](https://mlsanity.com/paper/2110.10295/) (2021)
- [Taming the Exponential Action Set: Sublinear Regret and Fast Convergence to Nash Equilibrium in Online Congestion Games](https://mlsanity.com/paper/2306.13673/) (2023)
- [Convergence of Regret Matching in Potential Games and Constrained Optimization](https://mlsanity.com/paper/2510.17067/) (2025)
- [Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Games](https://mlsanity.com/paper/2404.06516/) (2024)
- [Swim till You Sink: Computing the Limit of a Game](https://mlsanity.com/paper/2408.11146/) (2024)
- [Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamics](https://mlsanity.com/paper/2109.03974/) (2021)
- [Chaos persists in large-scale multi-agent learning despite adaptive learning rates](https://mlsanity.com/paper/2306.01032/) (2023)
- [Games played by Exponential Weights Algorithms](https://mlsanity.com/paper/2407.06676/) (2024)
- [On the Decomposition of Differential Game](https://mlsanity.com/paper/2411.03802/) (2024)
- [Last-iterate Convergence for Symmetric, General-sum, 2 × 2 Games Under The Exponential Weights Dynamic](https://mlsanity.com/paper/2502.08063/) (2025)
- [Langevin Multiplicative Weights Update with Applications in Polynomial Portfolio Management](https://mlsanity.com/paper/2502.19210/) (2025)
- [Natural Invariant Measures for Chaotic Game Dynamics: Finding Order in Chaos](https://mlsanity.com/paper/2607.21805/) (2026)

## Abstract (arXiv)

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 γ is multiplied by (1 -ε C(γ))>0 where C(γ) is the "cost" of element γ and then rescaled to ensure that the new values form a distribution. We analyze MWU in congestion games where agents use textitarbitrary admissible constants as learning rates ε and prove convergence to textitexact 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 γ is multiplied by (1 -ε)C(γ) 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.