Skip to main content
SpringerLink
Log in

Distributed best response dynamics for Nash equilibrium seeking in potential games

  • Published:
Control Theory and Technology Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. 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.

    Article  Google Scholar 

  2. T. Alpcan, T. Başar, R. Srikant, et al. CDMA uplink power control as a noncooperative game. Wireless Networks, 2002, 8(6): 659–670.

    Article  Google Scholar 

  3. 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.

    Article  MathSciNet  Google Scholar 

  4. 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.

    Article  Google Scholar 

  5. 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.

    Article  Google Scholar 

  6. 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.

    Article  MathSciNet  Google Scholar 

  7. J. Ghaderi, R. Srikant. Opinion dynamics in social networks with stubborn agents: equilibrium and convergence rate. Automatica, 2014, 50(12): 3209–3215.

    Article  MathSciNet  Google Scholar 

  8. 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.

    Article  MathSciNet  Google Scholar 

  9. 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.

    Article  MathSciNet  Google Scholar 

  10. P. Yi, L. Pavel. An operator splitting approach for distributed generalized Nash equilibria computation. Automatica, 2019, 102: 111–121.

    Article  MathSciNet  Google Scholar 

  11. 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.

    Article  MathSciNet  Google Scholar 

  12. 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.

  13. M. Ye, G. Hu. Distributed Nash equilibrium seeking by a consensus based approach. IEEE Transactions on Automatic Control, 2017, 62(9): 4811–4818.

    Article  MathSciNet  Google Scholar 

  14. F. Salehisadaghiani, L. Pavel. Distributed Nash equilibrium seeking in networked graphical games. Automatica, 2018, 87: 17–24.

    Article  MathSciNet  Google Scholar 

  15. S. Liang, P. Yi, Y. Hong. Distributed Nash equilibrium seeking for aggregative games with coupled constraints. Automatica, 2017, 85: 179–185.

    Article  MathSciNet  Google Scholar 

  16. N. Li, J. R. Marden. Designing games for distributed optimization. IEEE Journal of Selected Topics in Signal Processing, 2013, 7(2): 230–242.

    Article  Google Scholar 

  17. W. Saad, Z. Han, H. V. Poor, et al. Game theoretic methods for the smart grid. arXiv, 2012: arXiv:1202.0452.

  18. 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.

    Google Scholar 

  19. 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.

    Google Scholar 

  20. 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.

    Article  MathSciNet  Google Scholar 

  21. B. Swenson, R. Murray, S. Kar. On best-response dynamics in potential games. SIAM Journal on Control and Optimization, 2018, 56(4): 2734–2767.

    Article  MathSciNet  Google Scholar 

  22. G. W. Brown. Iterative solution of games by fictitious play. Activity Analysis of Production and Allocation, 1951, 13(1): 374–376.

    MathSciNet  MATH  Google Scholar 

  23. A. Cortés, S. Martínez. Self-triggered best-response dynamics for continuous games. IEEE Transactions on Automatic Control, 2014, 60(4): 1115–1120.

    Article  MathSciNet  Google Scholar 

  24. 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.

    Article  MathSciNet  Google Scholar 

  25. 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.

  26. P. Yi, Y. Hong. Stochastic sub-gradient algorithm for distributed optimization with random sleep scheme. Control Theory and Technology, 2015, 13(4): 333–347.

    Article  MathSciNet  Google Scholar 

  27. X. Wang, P. Yi, Y. Hong. Dynamic optimization for multiagent systems with external disturbances. Control Theory and Technology, 2014, 12(2): 132–138.

    Article  MathSciNet  Google Scholar 

  28. 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.

    Article  MathSciNet  Google Scholar 

  29. B. Swenson, C. Eksin, S. Kar, et al. Distributed inertial best-response dynamics. IEEE Transactions on Automatic Control, 2018, 63(12): 4294–4300.

    Article  MathSciNet  Google Scholar 

  30. 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.

    Article  MathSciNet  Google Scholar 

  31. 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.

    Article  Google Scholar 

  32. Y. Nesterov. Lectures on Convex Optimization. New York: Springer, 2018.

    Book  Google Scholar 

  33. D. Monderer, L. S. Shapley. Potential games. Games and Economic Behavior, 1996, 14(1): 124–143.

    Article  MathSciNet  Google Scholar 

  34. D. P. Bertsekas. Convex Optimization Theory. Belmont: Athena Scientific, 2009.

    MATH  Google Scholar 

  35. E. A. Ok. Real Analysis with Economic Applications. Princeton: Princeton University Press, 2007.

    Book  Google Scholar 

  36. 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.

    Google Scholar 

  37. A. F. Filippov. Differential Equations with Discontinuous Righthand Sides: Control Systems. New York: Springer Science & Business Media, 2013.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Key Lab of Systems and Control, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 100190, China

    Shijie Huang

  2. School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, 100190, China

    Shijie Huang

  3. Department of Control Science & Engineering, Tongji University, Shanghai, 201804, China

    Peng Yi

  4. Shanghai Institute of Intelligent Science and Technology, Tongji University, Shanghai, 201804, China

    Peng Yi

Authors
  1. Shijie Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Peng Yi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Peng Yi.

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

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11768-020-9204-4

Keywords

Search

Navigation