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 $\gamma$ is multiplied by $(1 -\epsilon C(\gamma))> 0$ where $C(\gamma)$ is the ``cost of action $\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}. Interestingly, this convergence result does not carry over to the nearly homologous MWU variant where at each step the probability assigned to action $\gamma$ is multiplied by $(1 -\epsilon)^{C(\gamma)}$ 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.

The paper revisits the convergence result of multiplicative weighted update (MWU) in a congestion game, due to Kleinberg, Piliouras, and Tardos (STOC 2009), and establishes a connection between MWU and Baum-Welch algorithm in a neat and elegant style. By showing the monotonicity of the potential function in a congestion game, the authors prove that any MWU with linear updating rule converges to the set of fixed points, which is a superset of all the Nash equilibria of the congestion game. The Baum-Eagon inequality offers a new interpretation of the dynamics of the linear updating rule in MWU and their results in congestion games are quite general, and so are the conditions on initialization and isolated Nash equilibrium in a congestion game with finite set of agents and pure strategies. The results in this paper hold for any congestion game irrespective of the topology of the strategy sets by the nature of their game, however, one should emphasize the assumption that, individual earning rates \epsilon_i are bounded above, in order for Baum-Eagon inequality to work in their context.

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 $\gamma$ is multiplied by $(1 -\epsilon C(\gamma)) 0$ where $C(\gamma)$ is the cost" of action $\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}. Interestingly, this convergence result does not carry over to the nearly homologous MWU variant where at each step the probability assigned to action $\gamma$ is multiplied by $(1 -\epsilon) {C(\gamma)}$ 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. Papers published at the Neural Information Processing Systems Conference.