Fully distributed Nash equilibrium seeking over time-varying communication networks with linear convergence rate

Abstract

We design a distributed algorithm for learning Nash equilibria over time-varying communication networks in a partial-decision information scenario, where each agent can access its own cost function and local feasible set, but can only observe the actions of some neighbors. Our algorithm is based on projected pseudo-gradient dynamics, augmented with consensual terms. Under strong monotonicity and Lipschitz continuity of the game mapping, we provide a very simple proof of linear convergence, based on a contractivity property of the iterates. Compared to similar solutions proposed in literature, we also allow for a time-varying communication and derive tighter bounds on the step sizes that ensure convergence. In fact, in our numerical simulations, our algorithm outperforms the existing gradient-based methods, when the step sizes are set to their theoretical upper bounds. Finally, to relax the assumptions on the network structure, we propose a different pseudo-gradient algorithm, which is guaranteed to converge on time-varying balanced directed graphs.

References in corpus (9)

• A Passivity-Based Approach to Nash Equilibrium Seeking over Networks
• Dynamic control of agents playing aggregative games with coupling constraints
• Distributed GNE seeking under partial-decision information over networks via a doubly-augmented operator splitting approach
• Distributed generalized Nash equilibrium seeking in aggregative games on time-varying networks
• Distributed Nash Equilibrium Seeking under Partial-Decision Information via the Alternating Direction Method of Multipliers
• Distributed Learning for Stochastic Generalized Nash Equilibrium Problems
• A continuous-time distributed generalized Nash equilibrium seeking algorithm over networks for double-integrator agents
• Nash Equilibrium Seeking with Non-doubly Stochastic Communication Weight Matrix
• Geometric Convergence of Gradient Play Algorithms for Distributed Nash Equilibrium Seeking

Cited by in corpus (5)

• Fast generalized Nash equilibrium seeking under partial-decision information
• Nash equilibrium seeking under partial-decision information over directed communication networks
• A fully-distributed proximal-point algorithm for Nash equilibrium seeking with linear convergence rate
• Resilient Nash Equilibrium Seeking in the Partial Information Setting
• Networked Aggregative Games with Linear Convergence