论文标题
完全分布的NASH平衡，以线性收敛速度寻求超时的通信网络
Fully distributed Nash equilibrium seeking over time-varying communication networks with linear convergence rate
论文作者
论文摘要
我们设计了一种分布式算法，用于在部分决策信息方案中学习NASH平衡，这是在随着时变的通信网络上，每个代理都可以访问其自身的成本功能和本地可行的集合，但只能观察某些邻居的行动。我们的算法基于预计的伪梯度动力学，并以共识的术语增强。在强大的单调性和游戏映射的Lipschitz连续性下，我们根据迭代的合同性属性提供了非常简单的线性收敛证明。与文献中提出的类似解决方案相比，我们还允许随时间变化的通信，并在确保收敛的步骤大小上得出更紧密的界限。实际上，在我们的数值模拟中，当将步骤大小设置为其理论上限时，我们的算法优于现有的基于梯度的方法。最后，为了放大网络结构的假设，我们提出了一种不同的伪级算法，该算法可以保证会在随着时变平衡的有向图上收敛。
We design a distributed algorithm for learning Nash equilibria over time-varying communication networks in a partial-decision information scenario, where each agent can access its own cost function and local feasible set, but can only observe the actions of some neighbors. Our algorithm is based on projected pseudo-gradient dynamics, augmented with consensual terms. Under strong monotonicity and Lipschitz continuity of the game mapping, we provide a very simple proof of linear convergence, based on a contractivity property of the iterates. Compared to similar solutions proposed in literature, we also allow for a time-varying communication and derive tighter bounds on the step sizes that ensure convergence. In fact, in our numerical simulations, our algorithm outperforms the existing gradient-based methods, when the step sizes are set to their theoretical upper bounds. Finally, to relax the assumptions on the network structure, we propose a different pseudo-gradient algorithm, which is guaranteed to converge on time-varying balanced directed graphs.
