Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos
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 arbitrary admissible constants as learning rates and prove convergence to 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.
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. An elaborate analysis on the upper bounds would be nicer, since for any $i$, this paper requires that
$$\frac{1}{\epsilon_i} >  \sup_{i,\mathbf{p}\in \Delta,\gamma\in S_i} \{c_{i\gamma}\}\geq \max_{e} c_e(|N|),$$ which can be huge when the number of agents is large enough.
Although Theorem 3.7 holds, the proof presented by the authors is flawed. To prove any point $\mathbf{y} \in \Omega$ is a fixed point of $\zeta$, one could guess from the argument in the paper that the authors intend to show that $\Phi(\mathbf{y}) = \Phi(\zeta(\mathbf{y}))$, thus by monotonicity of $\Phi$, $\zeta(\mathbf{y})=\mathbf{y}$. However, they applied the notation $\mathbf{y}(t)$, even though $\mathbf{y}$ is, according to their definition, the limit point of an orbit $\mathbf{p}(t)$ as $t$ goes to infinity. The subsequent argument is also hard to follow. 
A easy way to prove theorem 3.7 is by contradiction. Suppose that $\mathbf{y}$ is not a fixed point, then by definition (line221), there exists some $i,\gamma$ s.t., $y_{i\gamma} > 0$ and $c_{i\gamma}\neq \hat{c}_i$.  If $c_{i\gamma} > \hat{c}_i$, then by convergence and continuity of the mapping, $\exists t_0$ and $\epsilon_0 > 0$, s.t., $\forall t > t_0$, $p_{i\gamma}(t) \geq \epsilon_0 > 0$, and $c_{i\gamma}(t) \geq  \hat{c}_i(t)+ \epsilon_0.$ Then it's not hard to see that
$$p_{i\gamma}(t+1) = p_{i\gamma}(t) \frac{\frac{1}{\epsilon_i} - c_{i\gamma}(t) }{\frac{1}{\epsilon_i} - \hat{c}_{i}(t)} \leq  p_{i\gamma}(t) (1- \epsilon_0 \epsilon_i),$$ which yields $\lim_{t\to \infty} p_{i\gamma}(t) = y_{i\gamma}=0$, contradicting with $y_{i\gamma} > 0$.
If $c_{i\gamma} < \hat{c}_i$, then by convergence and continuity of the mapping, $\exists t_0$ and $\epsilon_0 > 0$, s.t., $\forall t > t_0$, $p_{i\gamma}(t) \geq \epsilon_0 > 0$, and $c_{i\gamma}(t) + \epsilon_0 <  \hat{c}_i(t).$ Then it's not hard to see that $$p_{i\gamma}(t+1) = p_{i\gamma}(t) \frac{\frac{1}{\epsilon_i} - c_{i\gamma}(t) }{\frac{1}{\epsilon_i} - \hat{c}_{i}(t)} \geq  p_{i\gamma}(t) (1+ \epsilon_0)$$. Then $\lim_{t\to \infty} p_{i\gamma}(t)$ doesn't lie in the simplex. 
In Remark 3.5, the authors claim that Lemma 3.3 and thus Theorem 3.4 and 3.1 hold in the extension of weighted potential games. However, a underlying step in the proof of Lemma 3.3 might not hold without adding extra conditions: the non-negativity of coefficients in $Q(p)$ in a weighted potential game. Similar to the proof of Lemma 3.3, in the weighted case, $\frac{\partial Q}{\partial p_{i\gamma}} = \frac{1}{\epsilon_i} - \frac{c_{i\gamma}}{w_i}$. Whether the RHS is non-negative is unknown simply by the definition of $\epsilon_i$ nor the fact that $w_i \in [0,1]$.
On Line 236, the constant in $Q(p)$ should rather be $Q(p)=const -\Phi$ and $const = \sum_{i\in N} 1/{\epsilon_i} + (|N|-1) 1/\beta$.