  Log-linear learning has been extensively studied in both the game theoretic
and distributed control literature. It is appealing for many applications
because it often guarantees that the agents' collective behavior will converge
in probability to the optimal system configuration. However, the worst case
convergence time can be prohibitively long, i.e., exponential in the number of
players. We formalize a modified log-linear learning algorithm whose worst case
convergence time is roughly linear in the number of players. We prove this
characterization for a class of potential games where agents' utility functions
can be expressed as a function of aggregate behavior within a finite collection
of populations. Finally, we show that the convergence time remains roughly
linear in the number of players even when the players are permitted to enter
and exit the game over time.
