  How can a social planner adaptively incentivize selfish agents who are
learning in a strategic environment to induce a socially optimal outcome in the
long run? We propose a two-timescale learning dynamics to answer this question
in both atomic and non-atomic games. In our learning dynamics, players adopt a
class of learning rules to update their strategies at a faster timescale, while
a social planner updates the incentive mechanism at a slower timescale. In
particular, the update of the incentive mechanism is based on each player's
externality, which is evaluated as the difference between the player's marginal
cost and the society's marginal cost in each time step. We show that any fixed
point of our learning dynamics corresponds to the optimal incentive mechanism
such that the corresponding Nash equilibrium also achieves social optimality.
We also provide sufficient conditions for the learning dynamics to converge to
a fixed point so that the adaptive incentive mechanism eventually induces a
socially optimal outcome. Finally, we demonstrate that the sufficient
conditions for convergence are satisfied in a variety of games, including (i)
atomic networked quadratic aggregative games, (ii) atomic Cournot competition,
and (iii) non-atomic network routing games.
