Gradient-Free Nash Equilibrium Seeking in N-Cluster Games with Uncoordinated Constant Step-Sizes

Abstract

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.

References in corpus (7)

• Game Design and Analysis for Price based Demand Response: An Aggregate Game Approach
• A distributed primal-dual algorithm for computation of generalized Nash equilibria with shared affine coupling constraints via operator splitting methods
• Dynamic control of agents playing aggregative games with coupling constraints
• A Unified Strategy for Solution Seeking in Graphical N-coalition Noncooperative Games
• Distributed stochastic optimization with gradient tracking over strongly-connected networks
• Nash Equilibrium Seeking in N-Coalition Games via a Gradient-Free Method
• Nonsmooth Aggregative Games with Coupling Constraints and Infinitely Many Classes of Players

Cited by in corpus (4)

• Distributed Nash Equilibrium Seeking Algorithm Design for Multi-Cluster Games with High-Order Players
• Generalized Nash Equilibrium Seeking Algorithm Design for Distributed Constrained Multi-Cluster Games
• Distributed Generalized Nash Equilibrium Seeking of N-Coalition Games with Full and Distributive Constraints
• Distributed Nash Equilibrium Seeking in N-Cluster Games with Fully Uncoordinated Constant Step-Sizes