Fast generalized Nash equilibrium seeking under partial-decision information

Abstract

We address the generalized Nash equilibrium seeking problem in a partial-decision information scenario, where each agent can only exchange information with some neighbors, although its cost function possibly depends on the strategies of all agents. The few existing methods build on projected pseudo-gradient dynamics, and require either double-layer iterations or conservative conditions on the step sizes. To overcome both these flaws and improve efficiency, we design the first fully-distributed single-layer algorithms based on proximal best-response. Our schemes are fixed-step and allow for inexact updates, which is crucial for reducing the computational complexity. Under standard assumptions on the game primitives, we establish convergence to a variational equilibrium (with linear rate for games without coupling constraints) by recasting our algorithms as proximal-point methods, opportunely preconditioned to distribute the computation among the agents. Since our analysis hinges on a restricted monotonicity property, we also provide new general results that significantly extend the domain of applicability of proximal-point methods. Besides, the operator-theoretic approach favors the implementation of provably correct acceleration schemes that can further improve the convergence speed. Finally, the potential of our algorithms is demonstrated numerically, revealing much faster convergence with respect to projected pseudo-gradient methods and validating our theoretical findings.

arXiv comment13 pages, 6 figures, published in Automatica,

References in corpus (14)

• A Passivity-Based Approach to Nash Equilibrium Seeking over Networks
• 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
• Real and Complex Monotone Communication Games
• 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
• Fully distributed Nash equilibrium seeking over time-varying communication networks with linear convergence rate
• Single-timescale distributed GNE seeking for aggregative games over networks via forward-backward operator splitting
• Distributed generalized Nash equilibria computation of monotone games via a preconditioned proximal point algorithm
• Empirical Centroid Fictitious Play: An Approach For Distributed Learning In Multi-Agent Games
• Semi-decentralized generalized Nash equilibrium seeking in monotone aggregative games
• A continuous-time distributed generalized Nash equilibrium seeking algorithm over networks for double-integrator agents

Cited by in corpus (6)

• Operationally-Safe Peer-to-Peer Energy Trading in Distribution Grids: A Game-Theoretic Market-Clearing Mechanism
• Tracking-based distributed equilibrium seeking for aggregative games
• Nash equilibrium seeking under partial-decision information over directed communication networks
• Receding Horizon Games with Coupling Constraints for Demand-Side Management
• Distributed equilibrium seeking in aggregative games: linear convergence under singular perturbations lens
• Distributed Computation of Stochastic GNE with Partial Information: An Augmented Best-Response Approach