2017/03/03 by Gerasimos Palaiopanos, Ioannis Panageas, Palaiopanos, Gerasimos +3 · 5 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #cs.GT
paper · pdf · doi:10.48550/arxiv.1703.01138
17 pages, 9 figures
arxiv created 2017/03/03 · openalex publication_date 2017/03/03 · arxiv updated 2017/03/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 arbitrary admissible constants as learning rates ε and prove convergence to 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 γ 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.