论文标题
在N-Cluster游戏中寻求无梯度的NASH平衡
Gradient-Free Nash Equilibrium Seeking in N-Cluster Games with Uncoordinated Constant Step-Sizes
论文作者
论文摘要
这项工作调查了同时全球成本最小化和NASH均衡寻求问题的问题，该问题通常存在于$ n $ cluster的非合作游戏中。具体而言，同一集群中的代理商合作，以最大程度地减少全球成本功能，总结其个人成本功能，并与其他群集作为玩家共同玩不合作的游戏。对于问题设置，我们假设代理的本地成本函数的显式分析表达式未知，但是可以测量函数值。我们通过合成高斯平滑技术和梯度跟踪，提出了一种无梯度的NASH平衡来寻求算法。此外，我们不使用统一协调的步进尺寸，而是允许不同簇的代理选择不同的恒定步骤尺寸。当最大的台阶大小足够小时，我们证明了在强烈单调的游戏映射条件下，代理的动作与独特的NASH平衡的邻里的线性收敛，其误差差距是最大的步进大小和平滑参数的误差差距。所提出的算法的性能通过数值模拟验证。
This work investigates a problem of simultaneous global cost minimization and Nash equilibrium seeking, which commonly exists in $N$-cluster non-cooperative games. Specifically, the agents in the same cluster collaborate to minimize a global cost function, being a summation of their individual cost functions, and jointly play a non-cooperative game with other clusters as players. For the problem settings, we suppose that the explicit analytical expressions of the agents' local cost functions are unknown, but the function values can be measured. We propose a gradient-free Nash equilibrium seeking algorithm by a synthesis of Gaussian smoothing techniques and gradient tracking. Furthermore, instead of using the uniform coordinated step-size, we allow the agents across different clusters to choose different constant step-sizes. When the largest step-size is sufficiently small, we prove a linear convergence of the agents' actions to a neighborhood of the unique Nash equilibrium under a strongly monotone game mapping condition, with the error gap being propotional to the largest step-size and the smoothing parameter. The performance of the proposed algorithm is validated by numerical simulations.
