We propose a new distributed algorithm that combines heavy-ball momentum and a consensus-based gradient method to find a Nash equilibrium (NE) in a class of non-cooperative convex games with unconstrained action sets. In this approach, each agent in the game has access to its own smooth local cost function and can exchange information with its neighbors over a communication network. The proposed method is designed to work on a general sequence of time-varying directed graphs and allows for non-identical step-sizes and momentum parameters. Our work is the first to incorporate heavy-ball momentum in the context of non-cooperative games, and we provide a rigorous proof of its geometric convergence to the NE under the common assumptions of strong convexity and Lipschitz continuity of the agents' cost functions. Moreover, we establish explicit bounds for the step-size values and momentum parameters based on the characteristics of the cost functions, mixing matrices, and graph connectivity structures. To showcase the efficacy of our proposed method, we perform numerical simulations on a Nash-Cournot game to demonstrate its accelerated convergence compared to existing methods.
翻译:我们提出了一种新的分布式算法,它结合了Heavy-Ball动量和基于共识的梯度方法,用于在一类具有非约束动作集的非合作凸博弈中寻找纳什均衡(NE)。在这种方法中,游戏中的每个智能体都可以访问自己的平滑局部成本函数,并可以在通信网络上与其邻居交换信息。所提出的方法是为了在一般的时变有向图上工作,并允许不同的步长和动量参数。我们的工作是首次将Heavy-Ball动量纳入非合作游戏的背景中,并在强凸性和Lipschitz连续性的普遍假设下证明了其几何收敛于NE。此外,我们根据成本函数,混合矩阵和图连接结构的特征为步长值和动量参数建立了显式上限。为了展示我们提出的方法的功效,我们在Nash-Cournot博弈上进行了数值模拟,以展示其相对于现有方法的加速收敛性。