A fully-distributed proximal-point algorithm for Nash equilibrium seeking with linear convergence rate

Mattia Bianchi, Giuseppe Belgioioso, Sergio Grammatico

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

1 Downloads (Pure)

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.

Original languageEnglish
Title of host publicationProceedings of the 59th IEEE Conference on Decision and Control, CDC 2020
Place of PublicationPiscataway, NJ, USA
PublisherIEEE
Pages2303-2308
ISBN (Electronic)978-1-7281-7447-1
DOIs
Publication statusPublished - 2020
Event59th IEEE Conference on Decision and Control, CDC 2020 - Virtual, Jeju Island, Korea, Republic of
Duration: 14 Dec 202018 Dec 2020

Conference

Conference59th IEEE Conference on Decision and Control, CDC 2020
CountryKorea, Republic of
CityVirtual, Jeju Island
Period14/12/2018/12/20

Fingerprint

Dive into the research topics of 'A fully-distributed proximal-point algorithm for Nash equilibrium seeking with linear convergence rate'. Together they form a unique fingerprint.

Cite this