Distributed generalized Nash equilibrium seeking for noncooperative games with unknown cost functions
Xin Cai
State Key Laboratory of Alternate Electrical Power System with Renewable Energy Sources, North China Electric Power University, Beijing, China
School of Control and Computer Engineering, North China Electric Power University, Beijing, China
School of Electrical Engineering, Xinjiang University, Urumpqi, China
Search for more papers by this authorCorresponding Author
Feng Xiao
State Key Laboratory of Alternate Electrical Power System with Renewable Energy Sources, North China Electric Power University, Beijing, China
School of Control and Computer Engineering, North China Electric Power University, Beijing, China
Correspondence Feng Xiao, School of Control and Computer Engineering, North China Electric Power University, Beijing 102206, China.
Email: [email protected]
Search for more papers by this authorBo Wei
School of Control and Computer Engineering, North China Electric Power University, Beijing, China
Search for more papers by this authorXin Cai
State Key Laboratory of Alternate Electrical Power System with Renewable Energy Sources, North China Electric Power University, Beijing, China
School of Control and Computer Engineering, North China Electric Power University, Beijing, China
School of Electrical Engineering, Xinjiang University, Urumpqi, China
Search for more papers by this authorCorresponding Author
Feng Xiao
State Key Laboratory of Alternate Electrical Power System with Renewable Energy Sources, North China Electric Power University, Beijing, China
School of Control and Computer Engineering, North China Electric Power University, Beijing, China
Correspondence Feng Xiao, School of Control and Computer Engineering, North China Electric Power University, Beijing 102206, China.
Email: [email protected]
Search for more papers by this authorBo Wei
School of Control and Computer Engineering, North China Electric Power University, Beijing, China
Search for more papers by this authorFunding information: Beijing Natural Science Foundation, Grant/Award Number: 4222053; National Natural Science Foundation of China, Grant/Award Numbers: 61873074; 61903140
Abstract
In this article, a distributed nonmodel based generalized Nash equilibrium (GNE) seeking algorithm is proposed for a class of constrained noncooperative games with unknown cost functions. In the game, the strategy of each agent is restricted by both the coupled equality constraint and local inequality constraints. By virtue of the exact penalty method, an auxiliary cost function is constructed with the cost function and the local constraints. The main feature of the proposed algorithm depends on the capability to estimate the gradient information of auxiliary cost functions with only the values of costs. This is obtained by the extremum seeking control (ESC). To deal with the coupled constraints, only the Lagrange multiplier is transmitted among agents with some prior information about the coupled constraints. Moreover, a diminishing dither signal is introduced in the seeking algorithm to remove undesirable steady-state oscillations occurred in the classical ESC. As a result, the nonlocal convergence of the designed seeking algorithm to the GNE of the game is obtained by the singular perturbation theory, averaging analysis and Lyapunov stability theory. Numerical examples are given to verify the effectiveness of our proposed method.
CONFLICT OF INTEREST
The authors declare no potential conflict of interests.
Open Research
DATA AVAILABILITY STATEMENT
Data sharing not applicable to this article as no datasets were generated or analyzed during the current study.
REFERENCES
- 1Stanković MS, Johansson KH, Stipanović DM. Distributed seeking of Nash equilibria with applications to mobile sensor networks. IEEE Trans Automat Control. 2012; 57(4): 904-919. doi:10.1109/TAC.2011.2174678
- 2Ma J, Ye M, Zheng Y, Zhu Y. Consensus analysis of hybrid multiagent systems: a game-theoretic approach. Int J Robust Nonlinear Control. 2019; 29(6): 1840-1853. doi:10.1002/rnc.4462
- 3Wang J, Peng M, Jin S, Zhao C. A generalized Nash equilibrium approach for robust cognitive radio networks via generalized variational inequalities. IEEE Trans Wireless Commun. 2014; 13(7): 3701-3714. doi:10.1109/TWC.2014.2318719
- 4Peng Y, Lacra P. Distributed generalized Nash equilibria computation of monotone games via double-layer preconditioned proximal-point algorithms. IEEE Trans Control Network Syst. 2019; 6(1): 299-311. doi:10.1109/TCNS.2018.2813928
- 5Gharesifard B, Başar T, Dominguez-García AD. Price-based coordinated aggregation of networked distributed energy resources. IEEE Trans Automatic Control. 2016; 61(10): 2936-2946. doi:10.1109/TAC.2015.2504964
- 6Li M, Qin JH, Ma QC, Zheng WX, Kang Y. Hierarchical optimal synchronization for linear systems via reinforcement learning: a Stackelberg-Nash game perspective. IEEE Trans Neural Networks and Learn Syst. 2021; 32(4): 1600-1611. doi:10.1109/TNNLS.2020.2985738
- 7Wan Y, Qin JH, Li F, Yu X, Kang Y. Game theoretic-based distributed charging strategy for PEVs in a smart charging station. IEEE Trans Smart Grid. 2021; 12(1): 538-547. doi:10.1109/TSG.2020.3020466
- 8Frihauf P, Krstic M, Başar T. Nash equilibrium seeking in noncooperative games. IEEE Trans Automatic Control. 2012; 57(5): 1192-1207. doi:10.1109/TAC.2011.2173412
- 9Wu C, Gu W, Bo R, et al. Energy trading and generalized Nash equilibrium in combined heat and power market. IEEE Trans Power Syst. 2020; 35(5): 3378-3387. doi:10.1109/TPWRS.2020.2973423
- 10 Wang Z, Liu F, Ma Z, et al. Distributed generalized Nash equilibrium seeking for energy sharing games in prosumers. IEEE Trans Power Syst. 2021; 36(5): 3973-3986. doi:10.1109/TPWRS.2021.3058675
- 11Yi P, Pavel L. Asynchronous distributed algorithms for seeking generalized Nash equilibria under full and partial-decision information. IEEE Trans Cybernetics. 2020; 50(6): 2514-2526. doi:10.1109/TCYB.2019.2908091
- 12Yi P, Pavel L. An operator splitting approach for distributed generalized Nash equilibria computation. Automatica. 2019; 102: 111-121. doi:10.1016/j.automatica.2019.01.008
- 13Pavel L. Distributed GNE seeking under partial-decision information over networks via a doubly-augmented operator splitting approach. IEEE Trans Automatic Control. 2020; 65(4): 1584-1597. doi:10.1109/TAC.2019.2922953
- 14Lu K, Li G, Wang L. Online distributed algorithm for seeking generalized Nash equilibria in dynamic environments. IEEE Trans Automatic Control. 2021; 66(5): 2289-2296. doi:10.1109/TAC.2020.3002592
- 15 Ye M, Hu G, Xie L, Xu S. Differentially private distributed Nash equilibrium seeking for aggregative games. IEEE Trans Automatic Control. 2022; 67(5): 2451-2458. doi:10.1109/TAC.2021.3075183
- 16
Ye M, Li D, Han QL, Ding L. Distributed Nash equilibrium seeking for general networked games with bounded disturbances. IEEE/CAA J Automatica Sinica. 2022; 1-12. [Early Access]. doi:10.1109/JAS.2022.105428
10.1109/JAS.2022.105428 Google Scholar
- 17Ai X, Wang L. Distributed adaptive Nash equilibrium seeking and disturbance rejection for noncooperative games of high-order nonlinear systems with input saturation and input delay. Int J Robust Nonlinear Control. 2021; 31(7): 2827-2846. doi:10.1002/rnc.5418
- 18Pan W, Lu Y, Jia Z, Zhang W. Distributed Nash equilibrium learning: a second-order proximal algorithm. Int J Robust Nonlinear Control. 2021; 31(13): 6392-6409. doi:10.1002/rnc.5618
- 19Shakarami M, Persis C, De MN. Distributed dynamics for aggregative games: robustness and privacy guarantees. Int J Robsut Nonlinear Control. 2022; 32: 5048-5069. doi:10.1002/rnc.6077
- 20Freeman R, Yang P, Lynch K. Stability and convergence properties of dynamic average consensus estimators. Proceedings of the 45th IEEE Conference on Decision and Control. 2006: 398-403.
- 21Dai MZ, Liu J, Wu J, Zhang C, Zhao D. Integral-type edge-event- and edge-self-triggered synchronization to multi-agent systems with Lur'e nonlinear dynamics. Appl Sci Basel. 2021; 11(19): 9137. doi:10.3390/app11199137
- 22Liu J, Yao Y, He HB, Sun CY. Team-triggered practical fixed-time consensus of double-integrator agents with uncertain disturbance. IEEE Trans Cybernetics. 2021; 51(6): 3263-3272. doi:10.1109/TCYB.2020.2999199
- 23Lu K, Jing G, Wang L. Distributed algorithms for searching generalized Nash equilibrium of noncooperative games. IEEE Trans Cybernetics. 2019; 49(6): 2362-2371. doi:10.1109/TCYB.2018.2828118
- 24Deng Z. Distributed generalized Nash equilibrium seeking algorithm for nonsmooth aggregative games. Automatica. 2021; 132:109794. doi:10.1016/j.automatica.2021.109794
- 25Zeng X, Chen J, Liang S, Hong Y. Generalized Nash equilibrium seeking strategy for distributed nonsmooth multi-cluster game. Automatica. 2019; 103: 20-26. doi:10.1016/j.automatica.2019.01.025
- 26Deng Z, Nian X. Distributed algorithm design for aggregative games of disturbed multiagent systems over weight-balanced digraphs. Int J Robust Nonlinear Control. 2018; 28(17): 5344-5357. doi:10.1002/rnc.4316
- 27Deng Z, Nian X. Distributed generalized Nash equilibrium seeking algorithm design for aggregative games over weight-balanced digraphs. IEEE Trans Neural Networks and Learn Syst. 2019; 30(3): 695-706. doi:10.1109/TNNLS.2018.2850763
- 28Liang S, Yi P, Hong Y. Distributed Nash equilibrium seeking for aggregative games with coupled constraints. Automatica. 2017; 85: 179-185. doi:10.1016/j.automatica.2017.07.064
- 29Ye M, Hu G. Adaptive approaches for fully distributed Nash equilibrium seeking in networked games. Automatica. 2021; 129:109661. doi:10.1016/j.automatica.2021.109661
- 30Cai X, Xiao F, Wei B. A distributed strategy-updating rule with event-triggered communication for noncooperative games. Proceedings of the 39th Chinese Control Conference. 2020: 4747-4752.
- 31Cai X, Xiao F, Wei B. A distributed event-triggered generalized Nash equilibrium seeking algorithm. Proceedings of the 40th Chinese Control Conference. 2021: 5252-5257.
- 32Ye M, Hu G. Distributed extremum seeking for constrained networked optimization and its application to energy consumption control in smart grid. IEEE Trans Control Syst Technol. 2016; 24(6): 2048-2058. doi:10.1109/TCST.2016.2517574
- 33Marden JR, Ruben SD, Pao LY. A model-free approach to wind farm control using game theoretic methods. IEEE Trans Control Syst Technol. 2013; 21(4): 1207-1214. doi:10.1109/TCST.2013.2257780
- 34Marden JR, Young HP, Arslan G, Shamma JS. Payoff-based dynamics for multiplayer weakly acyclic games. SIAM J Control Optim. 2009; 48(1): 373-396. doi:10.1137/070680199
- 35Tan Y, Nešić D, Mareels I. On non-local stability properties of extremum seeking control. Automatica. 2006; 42: 889-903. doi:10.1016/j.automatica.2006.01.014
- 36Tan Y, Nešić D, Mareels IMY, Astolfi A. On global extremum seeking in the presence of local Extrema. Automatica. 2009; 45: 245-251. doi:10.1016/j.automatica.2008.06.010
- 37Pan Y, Acarman T, Özgüner Ü. Nash solution by extremum seeking control approach. Proceedings of the 41st IEEE Conference on Decision and Control. 2002: 329-334.
- 38 Ye M, Hu G, Xu S. An extremum seeking-based approach for Nash equilibrium seeking in N-cluster noncooperative games. Automatica. 2020; 114:108815. doi:10.1016/j.automatica.2020.108815
- 39Zahedi Z, Arefi MM, Khayatian A. Fast convergence to Nash equilibria without steady-state oscillation. Syst Control Lett. 2019; 123: 124-133. doi:10.1016/j.sysconle.2018.11.009
- 40Başar T, Olsder G. Dynamic Noncooperative Game Theory. 2nd ed. SIAM; 1999.
- 41Bullo F. Lectures on Network Systems. 1st ed. Kindle Direct Publishing; 2020.
- 42Cai X, Xiao F, Wei B. Distributed strategy-updating rules for aggregative games of multi-integrator systems with coupled constraints. arXiv:2106.10697v1. 2021: 1-9.
- 43Facchinei F, Fischer A, Piccialli V. On generalized Nash games and variational inequalities. Oper Res Lett. 2007; 35: 159-164.
- 44Cherukuri A, Cortés J. Distributed generator coordination for initialization and anytime optimization in economic dispatch. IEEE Trans Control Network Syst. 2015; 2(3): 226-237. doi:10.1109/TCNS.2015.239919
- 45Stephen B, Lieven V. Convex Optimization. Cambridge University Press; 2004.
- 46Zhu Y, Yu W, Wen G, Chen G. Distributed Nash equilibrium seeking in an aggregative game on a directed graph. IEEE Trans Automatic Control. 2021; 66(6): 2746-2753. doi:10.1109/TAC.2020.3008113
- 47Khalil HK. Nonlinear Systems. 3rd ed. Prentice-Hall; 2002.
- 48Wang L, Chen S, Ma K. On stability and application of extremum seeking control without steady-state oscillation. Automatica. 2016; 68: 18-26. doi:10.1016/j.automatica.2016.01.009
- 49Shao G, Wang R, Wang XF, Liu KZ. Consensus-based and extremum seeking methods for distributed generalized Nash equilibrium. Optim Control Appl Methods. 2020; 42(3): 684-699. doi:10.1002/oca.2694