Generalized Mirror Descents in Congestion Games
  Different types of dynamics have been studied in repeated game play, and one
of them which has received much attention recently consists of those based on
"no-regret" algorithms from the area of machine learning. It is known that
dynamics based on generic no-regret algorithms may not converge to Nash
equilibria in general, but to a larger set of outcomes, namely coarse
correlated equilibria. Moreover, convergence results based on generic no-regret
algorithms typically use a weaker notion of convergence: the convergence of the
average plays instead of the actual plays. Some work has been done showing that
when using a specific no-regret algorithm, the well-known multiplicative
updates algorithm, convergence of actual plays to equilibria can be shown and
better quality of outcomes in terms of the price of anarchy can be reached for
atomic congestion games and load balancing games. Are there more cases of
natural no-regret dynamics that perform well in suitable classes of games in
terms of convergence and quality of outcomes that the dynamics converge to?
  We answer this question positively in the bulletin-board model by showing
that when employing the mirror-descent algorithm, a well-known generic
no-regret algorithm, the actual plays converge quickly to equilibria in
nonatomic congestion games. Furthermore, the bandit model considers a probably
more realistic and prevalent setting with only partial information, in which at
each time step each player only knows the cost of her own currently played
strategy, but not any costs of unplayed strategies. For the class of atomic
congestion games, we propose a family of bandit algorithms based on the
mirror-descent algorithms previously presented, and show that when each player
individually adopts such a bandit algorithm, their joint (mixed) strategy
profile quickly converges with implications.
