Tracking equilibria with Markovian evolution

Can sophisticated global behavior be achieved by individual players locally optimizing their payoff functions and sharing information with neighbors? We present a novel regret-based stochastic approximation algorithm that is employed by individual players to achieve such a goal in a noncooperative game with neighborhood structure. Within neighborhoods, players receive local payoffs and observe the action profile of neighbors. Players also acquire global payoffs due to global interaction with players outside neighborhood, however, are oblivious to their action profile. Motivated by engineering applications such as cognitive radio and smart sensor systems, the parameters of the game model (e.g. payoff functions, neighborhood structure) may evolve with time according to a Markov process. It is proved that the global behavior emergent by all players following the adaptive algorithm properly tracks the time-evolving set of correlated ε-equilibrium of the game.