We study distributed algorithms for finding a Nash equilibrium (NE) in a class of non-cooperative convex games under partial information. Specifically, each agent has access only to its own smooth local cost function and can receive information from its neighbors in a time-varying directed communication network. To this end, we propose a distributed gradient play algorithm to compute a NE by utilizing local information exchange among the players. In this algorithm, every agent performs a gradient step to minimize its own cost function while sharing and retrieving information locally among its neighbors. The existing methods impose strong assumptions such as balancedness of the mixing matrices and global knowledge of the network communication structure, including Perron-Frobenius eigenvector of the adjacency matrix and other graph connectivity constants. In contrast, our approach relies only on a reasonable and widely-used assumption of row-stochasticity of the mixing matrices. We analyze the algorithm for time-varying directed graphs and prove its convergence to the NE, when the agents' cost functions are strongly convex and have Lipschitz continuous gradients. Numerical simulations are performed for a Nash-Cournot game to illustrate the efficacy of the proposed algorithm.
翻译:在部分信息下,我们研究在一组不合作的锥形游戏中找到纳什平衡(NE)的分布式算法。 具体地说, 每个代理商只能使用自己的平稳本地成本功能, 并且可以在一个时间变化的定向通信网络中从邻居那里接收信息。 为此, 我们提出一个分布式梯度游戏算法, 通过玩家之间的本地信息交流来计算NE。 在这个算法中, 每个代理商都执行一个梯度步骤, 以最大限度地减少其自身的成本功能, 同时在邻居之间分享和检索信息。 现有方法规定了强有力的假设, 比如混合矩阵的平衡性以及网络通信结构的全球知识, 包括相邻矩阵的 Perron- Frobenius 和图象形连接常数。 相反, 我们的方法仅仅依靠合理和广泛使用的混合矩阵的行相近性假设。 我们分析了时间变化方向图表的算法, 并证明它与 NEE的趋同, 当代理商的成本功能非常坚固, 并且拥有Lipschitz 连续梯度时, 。 Numeralice 模拟是用来说明拟议的纳什- Cour 游戏的功效。