| Title:
|
Distributed Nash equilibrium tracking via the alternating direction method of multipliers (English) |
| Author:
|
Ma, Ji |
| Author:
|
Yang, Zheng |
| Author:
|
Chen, Ziqin |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
59 |
| Issue:
|
4 |
| Year:
|
2023 |
| Pages:
|
612-632 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
Nash equilibrium is recognized as an important solution concept in non-cooperative game theory due to its broad applicability to economics, social sciences, computer science, and engineering. In view of its importance, substantial progress has been made to seek a static Nash equilibrium using distributed methods. However, these approaches are inapplicable in dynamic environments because, in this setting, the Nash equilibrium constantly changes over time. In this paper, we propose a dynamic algorithm that can track the time-varying Nash equilibrium in a non-cooperative game. Our approach enables each player to update its action using an alternating direction method of multipliers while ensuring this estimated action of each player always converges to a neighborhood of the Nash equilibrium at each sampling instant. We prove that the final tracking error is linearly proportional to the sampling interval, which implies that the tracking error can be sufficiently close to zero when the sampling interval is small enough. Finally, numerical simulations are conducted to verify the correctness of our theoretical results. (English) |
| Keyword:
|
game theory |
| Keyword:
|
time-varying Nash equilibrium tracking |
| Keyword:
|
alternating direction method of multipliers |
| MSC:
|
68W15 |
| MSC:
|
90C33 |
| idZBL:
|
Zbl 07790653 |
| idMR:
|
MR4660381 |
| DOI:
|
10.14736/kyb-2023-4-0612 |
| . |
| Date available:
|
2023-10-17T08:00:45Z |
| Last updated:
|
2024-02-13 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/151854 |
| . |
| Reference:
|
[1] Ardagna, D., Panicucci, B., Passacantando, M.: Generalized Nash equilibria for the service provisioning problem in cloud systems..IEEE Trans. Serv. Comput. 6 (2012), 429-442. |
| Reference:
|
[2] Bhatti, B. A., Broadwater, R.: Distributed Nash equilibrium seeking for a dynamic micro-grid energy trading game with non-quadratic payoffs..Energy. 202 (2020), 117709. |
| Reference:
|
[3] Cadre, H. Le, Jacquot, P., Wan, C., Alasseur, C.: Peer-to-peer electricity market analysis: From variational to generalized Nash equilibrium..Eur. J. Oper. Res., 282 (2020), 753-771. MR 4042753, |
| Reference:
|
[4] Chen, Z., Ma, J., Liang, S., Li, L.: Distributed Nash equilibrium seeking under quantization communication..Automatica 141 (2022), 110318. MR 4409952, |
| Reference:
|
[5] Persis, C. De, Grammatico, S.: Distributed averaging integral Nash equilibrium seeking on networks..Automatica 110 (2019), 1085448. MR 4001040, |
| Reference:
|
[6] Huang, B., Yang, C., Meng, Z., Chen, F., Ren, W.: Distributed nonlinear placement for multicluster systems: A time-varying Nash equilibrium-seeking approach..IEEE Trans. Cybernet. 52 (2022), 11614-11623. |
| Reference:
|
[7] Li, Z., Li, Z., Ding, Z.: Distributed generalized Nash equilibrium seeking and its application to Femtocell networks..IEEE Trans. Cybern., 52 (2022), 2505-2517. MR 4486900, |
| Reference:
|
[8] Li, X., Li, X., Hong, Y., Chen, J., Wang, L.: A survey of decentralized online learning..arxiv preprint (2022). MR 4070203, |
| Reference:
|
[9] Ling, Q., Ribeiro, A.: Decentralized dynamic optimization through the alternating direction method of multipliers..IEEE Trans. Signal Process. 62 (2014), 1185-1197. MR 3168144, |
| Reference:
|
[10] Lu, K., Jing, G., Wang, L.: Distributed algorithms for searching generalized Nash equilibrium of noncooperative games..IEEE Trans. Cybernet. 49 (2019), 2362-2371. |
| Reference:
|
[11] Lu, K., Li, H., Wang, L.: Online distributed algorithms for seeking generalized Nash equilibria in dynamic environments..IEEE Trans. Autom. Control 66 (2020), 2289-2296. MR 4250871, |
| Reference:
|
[12] Maskery, M., Krishnamurthy, V., Zhao, Q.: Decentralized dynamic spectrum access for cognitive radios: Cooperative design of a noncooperative game..IEEE Trans. Commun. 57 (2009), 459-469. |
| Reference:
|
[13] Meng, M., Li, X., Hong, Y., Chen, J., Wang, L.: Decentralized online learning for noncooperative games in dynamic environments..arxiv preprint (2021). |
| Reference:
|
[14] Ospina, A. M., Simonetto, A., Dall'Anese, E.: Time-varying optimization of networked systems with human preferences..IEEE Trans. Control Netw. Syst. 10 (2023), 503-515. MR 4597837, |
| Reference:
|
[15] Salehisadaghiani, F., Pavel, L.: Distributed Nash equilibrium seeking: A gossip-based algorithm..Automatica 72 (2016), 209-216. MR 3542934, |
| Reference:
|
[16] Simonetto, A., Mokhtari, A., Koppel, A., Leus, G., Ribeiro, A.: A class of prediction-correction methods for time-varying convex optimization..IEEE Trans. Signal Process. 64 (2016), 4576-4591. MR 3530422, |
| Reference:
|
[17] Tao, Q., Liu, Y., Xian, C., Zhao, Y.: Prescribed-time distributed time-varying Nash equilibrium seeking for formation placement control..IEEE Trans. Circuits Syst., II, Exp. Briefs 69 (2022), 4423-4427. |
| Reference:
|
[18] Ye, M., Hu, G.: Distributed seeking of time-varying Nash equilibrium for non-cooperative games..IEEE Trans. Autom. Control 60 (2015), 3000-3005. MR 3419589, |
| Reference:
|
[19] Ye, M., Hu, G.: Distributed Nash equilibrium seeking by a consensus based approach..IEEE Trans. Autom. Control 62 (2017), 4811-4818. MR 3691908, |
| Reference:
|
[20] Zeng, X., Chen, J., Liang, S., Hong, Y.: Generalized Nash equilibrium seeking strategy for distributed nonsmooth multi-cluster game..Automatica 103 (2019), 20-26. MR 3908257, |
| . |
