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 language | English |
---|---|
Title of host publication | Proceedings of the 59th IEEE Conference on Decision and Control, CDC 2020 |
Place of Publication | Piscataway, NJ, USA |
Publisher | IEEE |
Pages | 2303-2308 |
ISBN (Electronic) | 978-1-7281-7447-1 |
DOIs | |
Publication status | Published - 2020 |
Event | 59th IEEE Conference on Decision and Control, CDC 2020 - Virtual, Jeju Island, Korea, Republic of Duration: 14 Dec 2020 → 18 Dec 2020 |
Conference
Conference | 59th IEEE Conference on Decision and Control, CDC 2020 |
---|---|
Country/Territory | Korea, Republic of |
City | Virtual, Jeju Island |
Period | 14/12/20 → 18/12/20 |
Bibliographical note
Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-careOtherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.