Asynchronous Networked Aggregative Games

We propose a fully asynchronous networked aggregative game (Asy-NAG) where each player minimizes a local cost function that depends on its own action and the aggregate of all players' actions. In sharp contrast to the existing NAGs, each player in our Asy-NAG can compute an estimate of the aggregate action at any wall-clock time by only using (possibly stale) information from neighboring players of a directed network. Such an asynchronous update does not require any coordination among players. Moreover, we design a novel distributed algorithm with an aggressive mechanism for each player to adaptively adjust its optimization stepsize per update. Particularly, the slow players in terms of updating their estimates smartly increase their stepsizes to catch up with the fast ones. Then, we adopt an augmented network approach to address the asynchronicity and the information delays between players, and rigorously show the convergence to a Nash equilibrium of the Asy-NAG via a perturbed coordinate algorithm which is also of independent interest. Finally, we evaluate the performance of the distributed algorithm through numerical simulations. (C) 2021 Elsevier Ltd. All rights reserved.

Automated summary

We propose a fully asynchronous networked aggregative game (Asy-NAG) where each player minimizes a local cost function that depends on its own action and the aggregate of all players' actions. In contrast to existing NAGs, our Asy-NAG allows each player to compute an estimate of the aggregate action at any wall-clock time using potentially outdated information from neighboring players. The game does not require coordination among players and incorporates a novel distributed algorithm that adjusts optimization stepsize adaptively per update. We address asynchronicity and information delays between players using an augmented network approach and rigorously prove convergence to a Nash equilibrium of the Asy-NAG via a perturbed coordinate algorithm.