Learning Nash Equilibria in Congestion Games
  We study the repeated congestion game, in which multiple populations of
players share resources, and make, at each iteration, a decentralized decision
on which resources to utilize. We investigate the following question: given a
model of how individual players update their strategies, does the resulting
dynamics of strategy profiles converge to the set of Nash equilibria of the
one-shot game? We consider in particular a model in which players update their
strategies using algorithms with sublinear discounted regret. We show that the
resulting sequence of strategy profiles converges to the set of Nash equilibria
in the sense of Ces\`aro means. However, strong convergence is not guaranteed
in general. We show that strong convergence can be guaranteed for a class of
algorithms with a vanishing upper bound on discounted regret, and which satisfy
an additional condition. We call such algorithms AREP algorithms, for
Approximate REPlicator, as they can be interpreted as a discrete-time
approximation of the replicator equation, which models the continuous-time
evolution of population strategies, and which is known to converge for the
class of congestion games. In particular, we show that the discounted Hedge
algorithm belongs to the AREP class, which guarantees its strong convergence.
