Tatarenko, Tatiana ; Shi, Wei ; Nedich, Angelia (2025)
Geometric Convergence of Gradient Play Algorithms for Distributed Nash Equilibrium Seeking.
In: IEEE Transactions on Automatic Control, 2021, 66 (11)
doi: 10.26083/tuprints-00017863
Artikel, Zweitveröffentlichung, Postprint
Kurzbeschreibung (Abstract)
We study distributed algorithms for seeking a Nash equilibrium in a class of convex networked Nash games with strongly monotone mappings. Each player has access to her own smooth local cost function and can communicate to her neighbors in some undirected graph. To deal with fast distributed learning of Nash equilibria under such settings, we introduce a so called augmented game mapping and provide conditions under which this mapping is strongly monotone. We consider a distributed gradient play algorithm for determining a Nash equilibrium (GRANE). The algorithm involves every player performing a gradient step to minimize her own cost function while sharing and retrieving information locally among her neighbors in the network. Using the reformulation of the Nash equilibrium problem based on the strong monotone augmented game mapping, we prove the convergence of this algorithm to a Nash equilibrium with a geometric rate. Further, we introduce the Nesterov type acceleration for the gradient play algorithm. We demonstrate that, similarly to the accelerated algorithms in centralized optimization and variational inequality problems, our accelerated algorithm outperforms GRANE in the convergence rate. Moreover, to relax assumptions required to guarantee the strongly monotone augmented mapping, we analyze the restricted strongly monotone property of this mapping and prove geometric convergence of the distributed gradient play under milder assumptions
| Typ des Eintrags: |
Artikel
|
| Erschienen: |
2025 |
| Autor(en): |
Tatarenko, Tatiana ; Shi, Wei ; Nedich, Angelia |
| Art des Eintrags: |
Zweitveröffentlichung |
| Titel: |
Geometric Convergence of Gradient Play Algorithms for Distributed Nash Equilibrium Seeking |
| Sprache: |
Englisch |
| Publikationsjahr: |
22 Januar 2025 |
| Ort: |
Darmstadt |
| Publikationsdatum der Erstveröffentlichung: |
2021 |
| Ort der Erstveröffentlichung: |
New York, NY |
| Verlag: |
IEEE |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: |
IEEE Transactions on Automatic Control |
| Jahrgang/Volume einer Zeitschrift: |
66 |
| (Heft-)Nummer: |
11 |
| Kollation: |
12 Seiten |
| DOI: |
10.26083/tuprints-00017863 |
| URL / URN: |
https://tuprints.ulb.tu-darmstadt.de/17863 |
| Zugehörige Links: |
|
| Herkunft: |
Zweitveröffentlichungsservice |
| Kurzbeschreibung (Abstract): |
We study distributed algorithms for seeking a Nash equilibrium in a class of convex networked Nash games with strongly monotone mappings. Each player has access to her own smooth local cost function and can communicate to her neighbors in some undirected graph. To deal with fast distributed learning of Nash equilibria under such settings, we introduce a so called augmented game mapping and provide conditions under which this mapping is strongly monotone. We consider a distributed gradient play algorithm for determining a Nash equilibrium (GRANE). The algorithm involves every player performing a gradient step to minimize her own cost function while sharing and retrieving information locally among her neighbors in the network. Using the reformulation of the Nash equilibrium problem based on the strong monotone augmented game mapping, we prove the convergence of this algorithm to a Nash equilibrium with a geometric rate. Further, we introduce the Nesterov type acceleration for the gradient play algorithm. We demonstrate that, similarly to the accelerated algorithms in centralized optimization and variational inequality problems, our accelerated algorithm outperforms GRANE in the convergence rate. Moreover, to relax assumptions required to guarantee the strongly monotone augmented mapping, we analyze the restricted strongly monotone property of this mapping and prove geometric convergence of the distributed gradient play under milder assumptions |
| Status: |
Postprint |
| URN: |
urn:nbn:de:tuda-tuprints-178635 |
| Sachgruppe der Dewey Dezimalklassifikatin (DDC): |
500 Naturwissenschaften und Mathematik > 510 Mathematik |
| Hinterlegungsdatum: |
22 Jan 2025 10:20 |
| Letzte Änderung: |
23 Jan 2025 09:14 |
| PPN: |
|
| Export: |
|
| Suche nach Titel in: |
TUfind oder in Google |
Verfügbare Versionen dieses Eintrags
-
Geometric Convergence of Gradient Play Algorithms for Distributed Nash Equilibrium Seeking. (deposited 22 Jan 2025 10:20)
[Gegenwärtig angezeigt]
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum