Efficient Algorithm for Approximating Nash Equilibrium of Distributed Aggregative Games
针对分布式聚合博弈中投影计算困难的问题，提出用内接多面体近似局部约束，设计分布式算法求解近似博弈的ϵ-纳什均衡，并证明收敛性与近似精度。
In this article, we aim to design a distributed approximate algorithm for seeking Nash equilibria (NE) of an aggregative game. Due to the local set constraints of each player, projection-based algorithms have been widely employed for solving such problems actually. Since it may be quite hard to get the exact projection in practice, we utilize inscribed polyhedrons to approximate local set constraints, which yields a related approximate game model. We first prove that the NE of the approximate game is the ϵ -NE of the original game and then propose a distributed algorithm to seek the ϵ -NE, where the projection is then of a standard form in quadratic optimization with linear constraints. With the help of the existing developed methods for solving quadratic optimization, we show the convergence of the proposed algorithm and also discuss the computational cost issue related to the approximation. Furthermore, based on the exponential convergence of the algorithm, we estimate the approximation accuracy related to ϵ . In addition, we investigate the computational cost saved by approximation in numerical simulation.