IEEE Trans Cybern. 2023 Jul;53(7):4375-4387. doi: 10.1109/TCYB.2022.3175831. Epub 2023 Jun 15.
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.
本文旨在设计一种分布式近似算法，用于寻找聚合博弈的纳什均衡（NE）。由于每个玩家的局部集合约束，实际上已经广泛采用基于投影的算法来解决此类问题。由于在实践中很难获得精确的投影，我们利用内接多面体来近似局部集合约束，从而得到一个相关的近似博弈模型。我们首先证明近似博弈的 NE 是原始博弈的 ϵ-NE，然后提出一种分布式算法来寻找 ϵ-NE，其中投影随后是二次优化问题中的标准形式，具有线性约束。借助于现有的用于求解二次优化问题的方法，我们展示了所提出算法的收敛性，并讨论了与逼近相关的计算成本问题。此外，基于算法的指数收敛性，我们估计了与 ϵ 相关的逼近精度。此外，我们还在数值模拟中研究了逼近所节省的计算成本。
