Distributed Nash Equilibrium Learning for Average Aggregative Games: Harnessing Smoothness to Accelerate the Algorithm

Convergence speed is one of the most important features of an equilibrium-seeking algorithm. In this article, we address the problem of algorithm acceleration for distributed Nash equilibrium (NE) learning in networked average aggregative games with partial decision information. Harnessing the smoothness of cost functions, we propose a novel accelerated NE learning algorithm by integrating a momentum term into a gradient descent step. We prove that the distributed algorithm converges to the exact Nash equilibrium with constant stepsize by bounding four key consensus error terms. When cost functions are strongly convex and interaction graph is undirected and connected, the proposed algorithm enjoys a linear convergence rate $\mathcal {O}(\rho (\bm {M}(\theta))^{k})$, $\rho (\bm {M}(\theta))$ is the spectral radius of a parameterized matrix $\bm {M}(\theta)$ ($\theta$ is stepsize, $k$ is iterations). Simulation results under two different communication graphs show the momentum term does accelerate the algorithm, the iteration numbers of convergence to specific relative error are significantly reduced, up to 80% when the stepsize is small and the graph connectivity is high.

I. Introduction

Game theory deals with multiagent decision-making problems where agents' decisions are coupled in cost functions. Much more attention has been drawn to NE learning problems in multiagent networked games in recent years because of their various applications in the market economy [1], [2], automated driving [3], [4], [5], unmanned surface vessel formation [6], [7], [8], [9], wired and wireless sensor networks [10], [11], artificial intelligence [12], [13], and so on.