Distributed Nash Equilibrium Seeking over Time-Varying Directed Communication Networks
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916518787284992 |
|---|---|
| author | Nguyen, Duong Thuy Anh Nguyen, Duong Tung Nedić, Angelia |
| author_facet | Nguyen, Duong Thuy Anh Nguyen, Duong Tung Nedić, Angelia |
| contents | This paper proposes a distributed algorithm to find the Nash equilibrium in a class of non-cooperative convex games with partial-decision information. Our method employs a distributed projected gradient play approach alongside consensus dynamics, with individual agents minimizing their local costs through gradient steps and local information exchange with neighbors via a time-varying directed communication network. Addressing time-varying directed graphs presents significant challenges. Existing methods often circumvent this by focusing on static graphs or specific types of directed graphs or by requiring the stepsizes to scale with the Perron-Frobenius eigenvectors. In contrast, we establish novel results that provide a contraction property for the mixing terms associated with time-varying row-stochastic weight matrices. Our approach explicitly expresses the contraction coefficient based on the characteristics of the weight matrices and graph connectivity structures, rather than implicitly through the second-largest singular value of the weight matrix as in prior studies. The established results facilitate proving geometric convergence of the proposed algorithm and advance convergence analysis for distributed algorithms in time-varying directed communication networks. Numerical results on a Nash-Cournot game demonstrate the efficacy of the proposed method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2201_02323 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Distributed Nash Equilibrium Seeking over Time-Varying Directed Communication Networks Nguyen, Duong Thuy Anh Nguyen, Duong Tung Nedić, Angelia Computer Science and Game Theory 91A10, 91A43, 05C20, 68W15 This paper proposes a distributed algorithm to find the Nash equilibrium in a class of non-cooperative convex games with partial-decision information. Our method employs a distributed projected gradient play approach alongside consensus dynamics, with individual agents minimizing their local costs through gradient steps and local information exchange with neighbors via a time-varying directed communication network. Addressing time-varying directed graphs presents significant challenges. Existing methods often circumvent this by focusing on static graphs or specific types of directed graphs or by requiring the stepsizes to scale with the Perron-Frobenius eigenvectors. In contrast, we establish novel results that provide a contraction property for the mixing terms associated with time-varying row-stochastic weight matrices. Our approach explicitly expresses the contraction coefficient based on the characteristics of the weight matrices and graph connectivity structures, rather than implicitly through the second-largest singular value of the weight matrix as in prior studies. The established results facilitate proving geometric convergence of the proposed algorithm and advance convergence analysis for distributed algorithms in time-varying directed communication networks. Numerical results on a Nash-Cournot game demonstrate the efficacy of the proposed method. |
| title | Distributed Nash Equilibrium Seeking over Time-Varying Directed Communication Networks |
| topic | Computer Science and Game Theory 91A10, 91A43, 05C20, 68W15 |
| url | https://arxiv.org/abs/2201.02323 |