Approachability in population games

This paper reframes approachability theory within the context of population games. Thus, whilst a player still aims at driving her average payoff to a predefined set, her opponent is no longer malevolent but instead is extracted randomly at each instant of time from a population of individuals choosing actions in a similar manner. First, we define the notion of 1st-moment approachability, a weakening of Blackwell's approachability. Second, since the endogenous evolution of the population's play is then important, we develop a model of two coupled partial differential equations (PDEs) in the spirit of mean-field game theory: one describing the best-response of every player given the population distribution, the other capturing the macroscopic evolution of average payoffs if every player plays her best response. Third, we provide a detailed analysis of existence, nonuniqueness, and stability of equilibria (fixed points of the two PDEs). Fourth, we apply the model to regret-based dynamics, and use it to establish convergence to Bayesian equilibrium under incomplete information.