  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.
