Abstract
In this paper, we consider distributed Nash equilibrium (NE) seeking in potential games over a multi-agent network, where each agent can not observe the actions of all its rivals. Based on the best response dynamics, we design a distributed NE seeking algorithm by incorporating the non-smooth finite-time average tracking dynamics, where each agent only needs to know its own action and exchange information with its neighbours through a communication graph. We give a sufficient condition for the Lipschitz continuity of the best response mapping for potential games, and then prove the convergence of the proposed algorithm based on the Lyapunov theory. Numerical simulations are given to verify the result and illustrate the effectiveness of the algorithm.
Similar content being viewed by others
References
G. Arslan, J. R. Marden, J. S. Shamma. Autonomous vehicle-target assignment: a game-theoretical formulation. Journal of Dynamic Systems, Measurement, and Control, 2007, 129(5): 584–596.
T. Alpcan, T. Başar, R. Srikant, et al. CDMA uplink power control as a noncooperative game. Wireless Networks, 2002, 8(6): 659–670.
S. Mei, W. Wei, F. Liu. On engineering game theory with its application in power systems. Control Theory and Technology, 2017, 15(1): 1–12.
S. Buzzi, G. Colavolpe, D. Saturnino, et al. Potential games for energy-efficient power control and subcarrier allocation in uplink multicell OFDMA systems. IEEE Journal of Selected Topics in Signal Processing, 2011, 6(2): 89–103.
D. Ardagna, M. Ciavotta, M. Passacantando. Generalized nash equilibria for the service provisioning problem in multi-cloud systems. IEEE Transactions on Services Computing, 2015, 10(3): 381–395.
J. S. Pang, G. Scutari, F. Facchinei, et al. Distributed power allocation with rate constraints in Gaussian parallel interference channels. IEEE Transactions on Information Theory, 2008, 54(8): 3471–3489.
J. Ghaderi, R. Srikant. Opinion dynamics in social networks with stubborn agents: equilibrium and convergence rate. Automatica, 2014, 50(12): 3209–3215.
F. Salehisadaghiani, W. Shi, L. Pavel. Distributed Nash equilibrium seeking under partial-decision information via the alternating direction method of multipliers. Automatica, 2019, 103: 27–35.
B. Gharesifard, T. Başar, A. D. Domínguez-García. Price-based coordinated aggregation of networked distributed energy resources. IEEE Transactions on Automatic Control, 2015, 61(10): 2936–2946.
P. Yi, L. Pavel. An operator splitting approach for distributed generalized Nash equilibria computation. Automatica, 2019, 102: 111–121.
P. Yi, L. Pavel. Distributed generalized Nash equilibria computation of monotone games via double-layer preconditioned proximal-point algorithms. IEEE Transactions on Control of Network Systems, 2018, 6(1): 299–311.
S. Liang, P. Yi, Y. Hong, et al. Distributed Nash equilibrium seeking for aggregative games via a small-gain approach. arXiv, 2019: arXiv:1911.06458.
M. Ye, G. Hu. Distributed Nash equilibrium seeking by a consensus based approach. IEEE Transactions on Automatic Control, 2017, 62(9): 4811–4818.
F. Salehisadaghiani, L. Pavel. Distributed Nash equilibrium seeking in networked graphical games. Automatica, 2018, 87: 17–24.
S. Liang, P. Yi, Y. Hong. Distributed Nash equilibrium seeking for aggregative games with coupled constraints. Automatica, 2017, 85: 179–185.
N. Li, J. R. Marden. Designing games for distributed optimization. IEEE Journal of Selected Topics in Signal Processing, 2013, 7(2): 230–242.
W. Saad, Z. Han, H. V. Poor, et al. Game theoretic methods for the smart grid. arXiv, 2012: arXiv:1202.0452.
J. R. Marden, G. Arslan, J. S. Shamma. Connections between cooperative control and potential games illustrated on the consensus problem. European Control Conference, Kos, Greece: IEEE, 2007: 4604–4611.
C. Soto, B. Song, A. K. Roy-Chowdhury. Distributed multi-target tracking in a self-configuring camera network. IEEE Conference on Computer Vision and Pattern Recognition, Miami: IEEE, 2009: 1486–1493.
O. Candogan, I. Menache, A. Ozdaglar, et al. Flows and decompositions of games: Harmonic and potential games. Mathematics of Operations Research, 2011, 36(3): 474–503.
B. Swenson, R. Murray, S. Kar. On best-response dynamics in potential games. SIAM Journal on Control and Optimization, 2018, 56(4): 2734–2767.
G. W. Brown. Iterative solution of games by fictitious play. Activity Analysis of Production and Allocation, 1951, 13(1): 374–376.
A. Cortés, S. Martínez. Self-triggered best-response dynamics for continuous games. IEEE Transactions on Automatic Control, 2014, 60(4): 1115–1120.
J. Lei, U. V. Shanbhag, J. S. Pang, et al. On Synchronous, asynchronous, and randomized best-response schemes for stochastic Nash games. Mathematics of Operations Research, 2019, 45(1): 157–190.
J. Lei, U. V. Shanbhag. Distributed variable sample-size gradient-response and best-response schemes for stochastic Nash games over graphs. arXiv, 2018: arXiv:1811.11246.
P. Yi, Y. Hong. Stochastic sub-gradient algorithm for distributed optimization with random sleep scheme. Control Theory and Technology, 2015, 13(4): 333–347.
X. Wang, P. Yi, Y. Hong. Dynamic optimization for multiagent systems with external disturbances. Control Theory and Technology, 2014, 12(2): 132–138.
J. Thunberg, W. Song, Y. Hong, et al. Distributed attitude synchronization using backstepping and sliding mode control. Control Theory and Technology, 2014, 12(1): 48–55.
B. Swenson, C. Eksin, S. Kar, et al. Distributed inertial best-response dynamics. IEEE Transactions on Automatic Control, 2018, 63(12): 4294–4300.
F. Chen, Y. Cao, W. Ren. Distributed average tracking of multiple time-varying reference signals with bounded derivatives. IEEE Transactions on Automatic Control, 2012, 57(12): 3169–3174.
G. Scutari, D. P. Palomar, F. Facchinei, et al. Convex optimization, game theory, and variational inequality theory. IEEE Signal Processing Magazine, 2010, 27(3): 35–49.
Y. Nesterov. Lectures on Convex Optimization. New York: Springer, 2018.
D. Monderer, L. S. Shapley. Potential games. Games and Economic Behavior, 1996, 14(1): 124–143.
D. P. Bertsekas. Convex Optimization Theory. Belmont: Athena Scientific, 2009.
E. A. Ok. Real Analysis with Economic Applications. Princeton: Princeton University Press, 2007.
F. Facchinei, J. S. Pang. Nash equilibria: the variational approach. Convex Optimization in Signal Processing and Communications. New York: Cambridge University Press, 2010: 443–493.
A. F. Filippov. Differential Equations with Discontinuous Righthand Sides: Control Systems. New York: Springer Science & Business Media, 2013.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by the Shanghai Sailing Program (No. 20YF1453000) and the Fundamental Research Funds for the Central Universities (No. 22120200048).
Shijie HUANG received his B.Sc. degree from HuaZhong University of Science and Technology in 2018. He is currently working on the Ph.D. degree in Academy of Mathematics and Systems Science, Chinese Academy of Sciences. His research interests include distributed optimization and game theory.
Peng YI received his B.E. degree in Automation from the University of Science and Technology of China, Hefei, China, in 2011, and received his Ph.D. degree in Operations Research and Cybernetic from Academy of Mathematics and Systems Science, Chinese Academy of Science, Beijing, China, in 2016. He was a postdoctoral fellow in the Department of Electrical & Computer Engineering, University of Toronto, Canada from July 2016 to July 2017, and a postdoctoral associate in the Department of Electrical and Systems Engineering, Washington University in St. Louis, U.S.A. from July 2017 to July 2019. He is now a research professor in the Department of Control Science & Engineering, Tongji University. His research interests cover multiagent systems, distributed optimization, game theory, neural systems and smart grid.
Rights and permissions
About this article
Cite this article
Huang, S., Yi, P. Distributed best response dynamics for Nash equilibrium seeking in potential games. Control Theory Technol. 18, 324–332 (2020). https://doi.org/10.1007/s11768-020-9204-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11768-020-9204-4