A distributed primal-dual algorithm for computation of generalized Nash equilibria with shared affine coupling constraints via operator splitting methods
arXiv:1703.05388 · doi:10.1016/j.automatica.2019.01.008
Abstract
In this paper, we propose a distributed primal-dual algorithm for computation of a generalized Nash equilibrium (GNE) in noncooperative games over network systems. In the considered game, not only each player's local objective function depends on other players' decisions, but also the feasible decision sets of all the players are coupled together with a globally shared affine inequality constraint. Adopting the variational GNE, that is the solution of a variational inequality, as a refinement of GNE, we introduce a primal-dual algorithm that players can use to seek it in a distributed manner. Each player only needs to know its local objective function, local feasible set, and a local block of the affine constraint. Meanwhile, each player only needs to observe the decisions on which its local objective function explicitly depends through the interference graph and share information related to multipliers with its neighbors through a multiplier graph. Through a primal-dual analysis and an augmentation of variables, we reformulate the problem as finding the zeros of a sum of monotone operators. Our distributed primal-dual algorithm is based on forward-backward operator splitting methods. We prove its convergence to the variational GNE for fixed step-sizes under some mild assumptions. Then a distributed algorithm with inertia is also introduced and analyzed for variational GNE seeking. Finally, numerical simulations for network Cournot competition are given to illustrate the algorithm efficiency and performance.
arXiv comment21 pages,8 figures, parts are submitted to IEEE CDC
References in corpus (15)
- Graphical Models for Game Theory
- Initialization-free Distributed Algorithms for Optimal Resource Allocation with Feasibility Constraints and its Application to Economic Dispatch of Power Systems
- A Variational Perspective on Accelerated Methods in Optimization
- An inertial forward-backward algorithm for monotone inclusions
- Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence (2001)
- Distributed Nash equilibrium seeking for aggregative games with coupled constraints
- Game Design and Analysis for Price based Demand Response: An Aggregate Game Approach
- Dynamic control of agents playing aggregative games with coupling constraints
- Real and Complex Monotone Communication Games
- Decentralized Convergence to Nash Equilibria in Constrained Deterministic Mean Field Control
- Distributed Learning for Stochastic Generalized Nash Equilibrium Problems
- Empirical Centroid Fictitious Play: An Approach For Distributed Learning In Multi-Agent Games
- A Distributed Nash Equilibrium Seeking in Networked Graphical Games
- Continuous-Time Distributed Algorithms for Extended Monotropic Optimization Problems
- A Generic online acceleration scheme for Optimization algorithms via Relaxation and Inertia
Cited by in corpus (44)
- A Passivity-Based Approach to Nash Equilibrium Seeking over Networks
- Distributed GNE seeking under partial-decision information over networks via a doubly-augmented operator splitting approach
- Continuous-time fully distributed generalized Nash equilibrium seeking for multi-integrator agents
- Distributed generalized Nash equilibrium seeking in aggregative games on time-varying networks
- Nash and Wardrop equilibria in aggregative games with coupling constraints
- Fixed Point Strategies in Data Science
- Single-timescale distributed GNE seeking for aggregative games over networks via forward-backward operator splitting
- Fast generalized Nash equilibrium seeking under partial-decision information
- 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
- A feedback control algorithm to steer networks to a Cournot-Nash equilibrium
- Distributed Nash Equilibrium Seeking for Monotone Generalized Noncooperative Games by a Regularized Penalty Method
- Tracking-based distributed equilibrium seeking for aggregative games
- A distributed generalized Nash equilibrium seeking algorithm based on extremum seeking control
- Receding Horizon Games with Coupling Constraints for Demand-Side Management
- A fully-distributed proximal-point algorithm for Nash equilibrium seeking with linear convergence rate
- Nash Equilibrium Seeking in N-Coalition Games via a Gradient-Free Method
- Gradient-Free Nash Equilibrium Seeking in N-Cluster Games with Uncoordinated Constant Step-Sizes
- Stochastic Relaxed Inertial Forward-Backward-Forward splitting for Monotone Inclusions in Hilbert spaces
- Incentives and co-evolution: Steering linear dynamical systems with noncooperative agents
- Distributed Forward-Backward algorithms for stochastic generalized Nash equilibrium seeking
- A distributed algorithm for average aggregative games with coupling constraints
- Asynchronous Schemes for Stochastic and Misspecified Potential Games and Nonconvex Optimization
- Generalized Nash Equilibrium Problem by the Alternating Direction Method of Multipliers
- An asynchronous distributed and scalable generalized Nash equilibrium seeking algorithm for strongly monotone games
- Distributed equilibrium seeking in aggregative games: linear convergence under singular perturbations lens
- Distributed Nash Equilibrium Seeking with Limited Cost Function Knowledge via A Consensus-Based Gradient-Free Method
- A Warped Resolvent Algorithm to Construct Nash Equilibria
- Asynchronous Distributed Power Control of Multi-Microgrid Systems Based on the Operator Splitting Approach
- Distributed Generalized Nash Equilibrium Seeking of N-Coalition Games with Full and Distributive Constraints
- Linearly Convergent Variable Sample-Size Schemes for Stochastic Nash Games: Best-Response Schemes and Distributed Gradient-Response Schemes
- Distributed forward-backward (half) forward algorithms for generalized Nash equilibrium seeking
- Efficient Distributed Learning in Stochastic Non-cooperative Games without Information Exchange
- Asynchronous Distributed Voltage Control in Active Distribution Networks
- Nash Equilibrium Seeking for High-order Multi-agent Systems with Unknown Dynamics
- A Distributed GNE Seeking Algorithm Using the Douglas-Rachford Splitting Method
- Distributed Generalized Nash Equilibrium Seeking for Energy Sharing Games
- Locally-Aware Constrained Games on Networks
- Online distributed algorithms for seeking generalized Nash equilibria in dynamic environments
- Distributed Nash Equilibrium Seeking in N-Cluster Games with Fully Uncoordinated Constant Step-Sizes
- Bregman algorithms for mixed-strategy generalized Nash equilibrium seeking in a class of mixed-integer games
- Distributed Computation of Stochastic GNE with Partial Information: An Augmented Best-Response Approach
- SLS-BRD: A system-level approach to seeking generalised feedback Nash equilibria
- Efficient Estimation of Equilibria of Large Congestion Games with Heterogeneous Players