Distributed convergence to Nash equilibria in network and average aggregative games

Abstract

We consider network aggregative games where each player minimizes a cost function that depends on its own strategy and on a convex combination of the strategies of its neighbors. As a first contribution, we propose a class of distributed algorithms that can be used to steer the strategies of the rational agents to a Nash equilibrium configuration, with guaranteed convergence under different sufficient conditions depending on the cost functions and on the network. A distinctive feature of the proposed class of algorithms is that agents use optimal responses instead of gradient type of strategy updates. As a second contribution, we show that the algorithm suggested for network aggregative games can also be used to recover a Nash equilibrium of average aggregative games (i.e., games where each agent is affected by the average of the strategies of the whole population) in a distributed fashion, that is, without requiring a central coordinator. We apply our theoretical results to multi-dimensional, convex-constrained opinion dynamics and to demand-response schemes for energy management.