A fully-distributed proximal-point algorithm for Nash equilibrium seeking with linear convergence rate
arXiv:1910.11613 · doi:10.1109/CDC42340.2020.9304145
Abstract
We address the Nash equilibrium problem in a partial-decision information scenario, where each agent can only observe the actions of some neighbors, while its cost possibly depends on the strategies of other agents. Our main contribution is the design of a fully-distributed, single-layer, fixed-step algorithm, based on a proximal best-response augmented with consensus terms. To derive our algorithm, we follow an operator-theoretic approach. First, we recast the Nash equilibrium problem as that of finding a zero of a monotone operator. Then, we demonstrate that the resulting inclusion can be solved in a fully-distributed way via a proximal-point method, thanks to the use of a novel preconditioning matrix. Under strong monotonicity and Lipschitz continuity of the game mapping, We prove linear convergence of our algorithm to a Nash equilibrium. Furthermore, we show that our method outperforms the fastest known gradient-based schemes, both in terms of guaranteed convergence rate, via theoretical analysis, and in practice, via numerical simulations.
arXiv commentTo appear in the 59th Conference on Decision and Control (CDC 2020)
References in corpus (8)
- 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
- Distributed GNE seeking under partial-decision information over networks via a doubly-augmented operator splitting approach
- 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
- Distributed generalized Nash equilibria computation of monotone games via a preconditioned proximal point algorithm