Skip to yearly menu bar Skip to main content


Poster

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

Gerasimos Palaiopanos · Ioannis Panageas · Georgios Piliouras

Pacific Ballroom #224

Keywords: [ Dynamical Systems ] [ Game Theory and Computational Economics ]


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 action γ is multiplied by (1ϵC(γ))>0 where C(γ) is the cost" of action γ 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 ϵ and prove convergence to \textit{exact Nash equilibria}. Interestingly, this convergence result does not carry over to the nearly homologous MWU variant where at each step the probability assigned to action γ is multiplied by (1ϵ)C(γ) even for the simplest case of two-agent, two-strategy load balancing games, where such dynamics can provably lead to limit cycles or even chaotic behavior.

Live content is unavailable. Log in and register to view live content