Geodesic
Distributed Nash equilibrium tracking via the alternating direction method of multipliers
Kybernetika, Tome 59 (2023) no. 4, pp. 612-632
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2023-4-0612
Classification : 68W15, 90C33
Keywords: game theory; time-varying Nash equilibrium tracking; alternating direction method of multipliers 
@article{10_14736_kyb_2023_4_0612,
     author = {Ma, Ji and Yang, Zheng and Chen, Ziqin},
     title = {Distributed {Nash} equilibrium tracking via the alternating direction method of multipliers},
     journal = {Kybernetika},
     pages = {612--632},
     year = {2023},
     volume = {59},
     number = {4},
     doi = {10.14736/kyb-2023-4-0612},
     mrnumber = {4660381},
     zbl = {07790653},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2023-4-0612/}
}
TY  - JOUR
AU  - Ma, Ji
AU  - Yang, Zheng
AU  - Chen, Ziqin
TI  - Distributed Nash equilibrium tracking via the alternating direction method of multipliers
JO  - Kybernetika
PY  - 2023
SP  - 612
EP  - 632
VL  - 59
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2023-4-0612/
DO  - 10.14736/kyb-2023-4-0612
LA  - en
ID  - 10_14736_kyb_2023_4_0612
ER  - 
%0 Journal Article
%A Ma, Ji
%A Yang, Zheng
%A Chen, Ziqin
%T Distributed Nash equilibrium tracking via the alternating direction method of multipliers
%J Kybernetika
%D 2023
%P 612-632
%V 59
%N 4
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2023-4-0612/
%R 10.14736/kyb-2023-4-0612
%G en
%F 10_14736_kyb_2023_4_0612
Ma, Ji; Yang, Zheng; Chen, Ziqin. Distributed Nash equilibrium tracking via the alternating direction method of multipliers. Kybernetika, Tome 59 (2023) no. 4, pp. 612-632. doi: 10.14736/kyb-2023-4-0612

[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. | DOI

[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. | DOI

[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. | DOI | MR

[4] Chen, Z., Ma, J., Liang, S., Li, L.: Distributed Nash equilibrium seeking under quantization communication. Automatica 141 (2022), 110318. | DOI | MR

[5] Persis, C. De, Grammatico, S.: Distributed averaging integral Nash equilibrium seeking on networks. Automatica 110 (2019), 1085448. | DOI | MR

[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. | DOI

[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. | DOI | MR

[8] Li, X., Li, X., Hong, Y., Chen, J., Wang, L.: A survey of decentralized online learning. arxiv preprint (2022). | DOI | MR

[9] Ling, Q., Ribeiro, A.: Decentralized dynamic optimization through the alternating direction method of multipliers. IEEE Trans. Signal Process. 62 (2014), 1185-1197. | DOI | MR

[10] Lu, K., Jing, G., Wang, L.: Distributed algorithms for searching generalized Nash equilibrium of noncooperative games. IEEE Trans. Cybernet. 49 (2019), 2362-2371. | DOI

[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. | DOI | MR

[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. | DOI

[13] Meng, M., Li, X., Hong, Y., Chen, J., Wang, L.: Decentralized online learning for noncooperative games in dynamic environments. arxiv preprint (2021). | DOI

[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. | DOI | MR

[15] Salehisadaghiani, F., Pavel, L.: Distributed Nash equilibrium seeking: A gossip-based algorithm. Automatica 72 (2016), 209-216. | DOI | MR

[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. | DOI | MR

[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. | DOI

[18] Ye, M., Hu, G.: Distributed seeking of time-varying Nash equilibrium for non-cooperative games. IEEE Trans. Autom. Control 60 (2015), 3000-3005. | DOI | MR

[19] Ye, M., Hu, G.: Distributed Nash equilibrium seeking by a consensus based approach. IEEE Trans. Autom. Control 62 (2017), 4811-4818. | DOI | MR

[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. | DOI | MR

Cité par Sources :