We consider the Nash equilibrium problem in a partial-decision information scenario. Specifically, each agent can only receive information from some neighbors via a communication network, while its cost function depends on the strategies of possibly all agents. In particular, while the existing methods assume undirected or balanced communication, in this paper we allow for non-balanced, directed graphs. We propose a fully-distributed pseudo-gradient scheme, which is guaranteed to converge with linear rate to a Nash equilibrium, under strong monotonicity and Lipschitz continuity of the game mapping. Our algorithm requires global knowledge of the communication structure, namely of the Perron-Frobenius eigenvector of the adjacency matrix and of a certain constant related to the graph connectivity. Therefore, we adapt the procedure to setups where the network is not known in advance, by computing the eigenvector online and by means of vanishing step sizes.
翻译:具体地说,每个代理商只能通过通信网络接收来自某些邻居的信息,而其成本功能则取决于所有代理商的战略。特别是,现有方法假设了无方向或平衡的通信,我们在本文件中允许使用不平衡的定向图形。我们提议了一个完全分布的假渐变计划,该计划保证与线性率一致到纳什均衡,在游戏绘图的强烈单调和利普西茨连续性下。我们的算法要求全球了解通信结构,即相邻矩阵的Perron-Frobenius精子和与图形连接有关的某个常数。因此,我们调整程序,在网络事先不为人所知的情况下,通过在线计算树叶素,并通过消亡步骤大小的方式,设置网络。