Distributed Nash equilibrium tracking via the alternating direction method of multipliers

Ma, Ji, Yang, Zheng, and Chen, Ziqin. "Distributed Nash equilibrium tracking via the alternating direction method of multipliers." Kybernetika 59.4 (2023): 612-632. <http://eudml.org/doc/299554>.

@article{Ma2023,
abstract = {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.},
author = {Ma, Ji, Yang, Zheng, Chen, Ziqin},
journal = {Kybernetika},
keywords = {game theory; time-varying Nash equilibrium tracking; alternating direction method of multipliers},
language = {eng},
number = {4},
pages = {612-632},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Distributed Nash equilibrium tracking via the alternating direction method of multipliers},
url = {http://eudml.org/doc/299554},
volume = {59},
year = {2023},
}

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
PB - Institute of Information Theory and Automation AS CR
VL - 59
IS - 4
SP - 612
EP - 632
AB - 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.
LA - eng
KW - game theory; time-varying Nash equilibrium tracking; alternating direction method of multipliers
UR - http://eudml.org/doc/299554
ER -