Simultaneous Social Cost Minimization and Nash Equilibrium Seeking in Non-cooperative Games
详细信息 查看官网全文
- 英文论文题名：Simultaneous Social Cost Minimization and Nash Equilibrium Seeking in Non-cooperative Games
- 论文作者：Maojiao Ye ; Guoqiang Hu
- 英文论文作者：Maojiao Ye ; Guoqiang Hu ; School of Electrical and Electronic Engineering ; Nanyang Technological University
- 年：2017
- 作者机构：School of Electrical and Electronic Engineering,Nanyang Technological University;
- 英文论文关键词：Nash equilibrium seeking ; social cost minimization ; interacting coalitions ; non-cooperative game
- 会议召开时间：2017-07-26
- 会议录名称：第36届中国控制会议论文集（B）
- 英文会议录名称：Proceedings of the 36th Chinese Control Conference（B）
- 语种：英文
- 分类号：O225
- 学会代码：KZLL
- 会议名称：第36届中国控制会议
- 会议地点：中国辽宁大连
- 主办单位：中国自动化学会控制理论专业委员会
- 学会名称：中国自动化学会控制理论专业委员会
- 页数：8
- 文件大小：337k
- 原文格式：D
- 会议级别：全国
摘要
An N-coalition non-cooperative game is formulated in this paper. In the considered game, there are N interacting coalitions and each of them includes a set of agents. Each coalition acts as a virtual player(VP) in the game that aims to minimize its own objective function, which is defined as the sum of the agents' local objective functions in the coalition. However, the actual decision-makers are not the coalitions but the agents therein. That is, the agents within each coalition collaboratively minimize the coalition's objective function while constituting an entity that serves as a self-interested player(i.e., the coalition)in the game among the interacting coalitions. A seeking strategy is designed for the agents to find the Nash equilibrium of the N-coalition non-cooperative games. The equilibrium seeking strategy is based on an adaptation of a dynamic average consensus protocol and the gradient play. The dynamic average consensus protocol is leveraged to estimate the averaged gradients of the coalitions' objective functions. The gradient play is then implemented by utilizing the estimated information to achieve the Nash equilibrium seeking. Convergence results are established by utilizing Lyapunov stability analysis. A numerical example is given in supportive of the theoretical results.
An N-coalition non-cooperative game is formulated in this paper. In the considered game, there are N interacting coalitions and each of them includes a set of agents. Each coalition acts as a virtual player(VP) in the game that aims to minimize its own objective function, which is defined as the sum of the agents' local objective functions in the coalition. However, the actual decision-makers are not the coalitions but the agents therein. That is, the agents within each coalition collaboratively minimize the coalition's objective function while constituting an entity that serves as a self-interested player(i.e., the coalition)in the game among the interacting coalitions. A seeking strategy is designed for the agents to find the Nash equilibrium of the N-coalition non-cooperative games. The equilibrium seeking strategy is based on an adaptation of a dynamic average consensus protocol and the gradient play. The dynamic average consensus protocol is leveraged to estimate the averaged gradients of the coalitions' objective functions. The gradient play is then implemented by utilizing the estimated information to achieve the Nash equilibrium seeking. Convergence results are established by utilizing Lyapunov stability analysis. A numerical example is given in supportive of the theoretical results.
An N-coalition non-cooperative game is formulated in this paper. In the considered game, there are N interacting coalitions and each of them includes a set of agents. Each coalition acts as a virtual player(VP) in the game that aims to minimize its own objective function, which is defined as the sum of the agents' local objective functions in the coalition. However, the actual decision-makers are not the coalitions but the agents therein. That is, the agents within each coalition collaboratively minimize the coalition's objective function while constituting an entity that serves as a self-interested player(i.e., the coalition)in the game among the interacting coalitions. A seeking strategy is designed for the agents to find the Nash equilibrium of the N-coalition non-cooperative games. The equilibrium seeking strategy is based on an adaptation of a dynamic average consensus protocol and the gradient play. The dynamic average consensus protocol is leveraged to estimate the averaged gradients of the coalitions' objective functions. The gradient play is then implemented by utilizing the estimated information to achieve the Nash equilibrium seeking. Convergence results are established by utilizing Lyapunov stability analysis. A numerical example is given in supportive of the theoretical results.
引文
[1]B.Gharesifard and J.Cortes,“Distributed convergence to Nash equilibria in two-network zero-sum games,”Automatica,vol.49,pp.1683-1692,2013.
[2]Y.Lou,Y.Hong,L.Xie,G.Shi and K.Johansson,“Nash equilibrium computation in subnetwork zero-sum games with switching communications,”IEEE Transactions on Automatic Control,vol.61,no.10,pp.2920-2935,2016.
[3]M.Ye and G.Hu,“Game design and analysis for pricebased demand response:an aggregate game approach,”IEEE Transactions on Cybernetics,vol.47,no.3,pp.720-730,2017.
[4]M.Ye and G.Hu,“Distributed Nash equilibrium seeking by a consensus based approach,”IEEE Transactions on Automatic Control,accepted,DOI:10.1109/TAC.2017.2688452.
[5]J.Shamma and G.Arslan,“Dynamic fictitious play,dynamic gradient play,and distributed convergence to Nash equilibria,”IEEE Transactions on Automatic Control,vol.50,pp.312-327,2005.
[6]D.Fudenberg and D.Levine,The theory of learning in games,Cambridge,MA:MIT Press,1998.
[7]P.Frihauf,M.Krstic and T.Basar,“Nash equilibrium seeking in non-coopearive games,”IEEE Transactions on Automatic Control,vol.57,pp.1192-1207,2012.
[8]M.Stankovi,K.Johansson and D.Stipanovi,“Distributed seeking of Nash equilibria with applications to mobile sensor networks,”IEEE Transactions on Automatic Control,vol.57,pp.904-919,2012.
[9]S.Liu and M.Krstic,“Stochastic Nash equilibrium seeking for games with general nonlinear payoffs,”SIAM Journal on Control and Optimization,vol.49,pp.1659-1679,2011.
[10]K.Vamvoudakis,F.Lewis and G.Hudas,“Multi-agent differential graphical games:online adaptive learning solution for synchronization with optimality,”Automatica,vol.48,pp.1598-1611,2012.
[11]M.Zhu,E.Frazzoli,“Distributed robust adaptive equilibrium computation for generalized convex games,”Automatica,vol.63,pp.82-91,2016.
[12]M.Ye and G.Hu,“Distributed extremum seeking for constrained networked optimization and its application to energy consumption control in smart grid,”IEEE Transactions on Control Systems Technology,vol.24,pp.2048-2058,2016.
[13]C.Sun,M.Ye,G.Hu,“Distributed time-varying quadratic optimization for multiple agents under undirected graphs,”IEEE Transactions on Automatic Control,accepted,DOI:10.1109/TAC.2017.2673240.
[14]A.Nedic and A.Olshevsky,“Distributed optimization over time-varying directed graphs,”IEEE Transactions on Automatic Control,vol.60,pp.601-615,2015.
[15]S.Boyd,N.Parikh,E.Chu,B.Peleato and J.Eckstein,“Distributed optimization and statistical learning via the alternating direction method of multiplier,”Foundations and Trends in Machine Learning,vol.3,pp.1-122,2011.
[16]S.Kia,J.Cortes and S.Martinez,“Distributed convex optimization via continuous-time coordination algorithmns with discrete-time communication,”Automatica,vol.55,pp.254-264,2015.
[17]N.Li and J.Marden,“Designing games for distributed optimization,”IEEE Journal of Selected Topics in Signal Processing,vol.7,pp.230-242,2013.
[18]M.Ye and G.Hu,“Distributed optimization for systems with time-varying quadratic objective functions,”IEEE Conference on Decision and Control,pp.3285-3290,2015.
[19]P.Lin,W.Ren and Y.Song,“Distributed multi-agent optimization subject to nonidentical constraints and communication delays,”Automatica,vol.65,pp.120-131,2016.
[20]G.Droge,H.Kawashima and M.Egerstedt,“Continuoustime proportional-integral distributed optimization for networked systems,”Journal of Decision and Control,vol.1,pp.191-213,2014.
[21]A.Menon and J.Baras,“Collaborative extremum seeking for welfare optimization,”IEEE Conference on Decision and Control,pp.346-351,2014.
[22]S.Dougherty and M.Guay,“Extremum-seeking control of distributed systems using consensus estimation,”IEEE Conference on Decision and Control,pp.3450-3455,2014.
[23]L.Bai,M.Ye,C.Sun and G.Hu,“Distributed control for optimal economic dispatch via saddle point dynamics and consensus algorithms,”IEEE Conference on Decision and Control,pp.6934-6939,2016.
[24]D.Niyato,A.Vasilakos and Z.Kun,“Resource and revenue sharing with coalition formation of cloud providers:game theoretic approach,”IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing,pp.215-224,2011.
[25]R.Freeman,P.Yang and K.Lynch,“Stability and convergence properties of dynamic average consensus estimators,”IEEE Conference on Decision and Control,pp.398-403,2006.
[26]H.Khailil,Nonlinear System,Prentice Hall,3rd edtion,2002.
[27]J.Rosen,“Existence and uniquness of equilibrium points for concave N-person games,”Econometrica,vol.33,no.3,p.520,Jul.1965.
1 Related definitions on the graphs and games are given in the Section6.1.
2 Throughout this paper,(xi,x-i) and (xi*,x-i*) might be alternatively written as x and x*,respectively,for notational convenience.
[2]Y.Lou,Y.Hong,L.Xie,G.Shi and K.Johansson,“Nash equilibrium computation in subnetwork zero-sum games with switching communications,”IEEE Transactions on Automatic Control,vol.61,no.10,pp.2920-2935,2016.
[3]M.Ye and G.Hu,“Game design and analysis for pricebased demand response:an aggregate game approach,”IEEE Transactions on Cybernetics,vol.47,no.3,pp.720-730,2017.
[4]M.Ye and G.Hu,“Distributed Nash equilibrium seeking by a consensus based approach,”IEEE Transactions on Automatic Control,accepted,DOI:10.1109/TAC.2017.2688452.
[5]J.Shamma and G.Arslan,“Dynamic fictitious play,dynamic gradient play,and distributed convergence to Nash equilibria,”IEEE Transactions on Automatic Control,vol.50,pp.312-327,2005.
[6]D.Fudenberg and D.Levine,The theory of learning in games,Cambridge,MA:MIT Press,1998.
[7]P.Frihauf,M.Krstic and T.Basar,“Nash equilibrium seeking in non-coopearive games,”IEEE Transactions on Automatic Control,vol.57,pp.1192-1207,2012.
[8]M.Stankovi,K.Johansson and D.Stipanovi,“Distributed seeking of Nash equilibria with applications to mobile sensor networks,”IEEE Transactions on Automatic Control,vol.57,pp.904-919,2012.
[9]S.Liu and M.Krstic,“Stochastic Nash equilibrium seeking for games with general nonlinear payoffs,”SIAM Journal on Control and Optimization,vol.49,pp.1659-1679,2011.
[10]K.Vamvoudakis,F.Lewis and G.Hudas,“Multi-agent differential graphical games:online adaptive learning solution for synchronization with optimality,”Automatica,vol.48,pp.1598-1611,2012.
[11]M.Zhu,E.Frazzoli,“Distributed robust adaptive equilibrium computation for generalized convex games,”Automatica,vol.63,pp.82-91,2016.
[12]M.Ye and G.Hu,“Distributed extremum seeking for constrained networked optimization and its application to energy consumption control in smart grid,”IEEE Transactions on Control Systems Technology,vol.24,pp.2048-2058,2016.
[13]C.Sun,M.Ye,G.Hu,“Distributed time-varying quadratic optimization for multiple agents under undirected graphs,”IEEE Transactions on Automatic Control,accepted,DOI:10.1109/TAC.2017.2673240.
[14]A.Nedic and A.Olshevsky,“Distributed optimization over time-varying directed graphs,”IEEE Transactions on Automatic Control,vol.60,pp.601-615,2015.
[15]S.Boyd,N.Parikh,E.Chu,B.Peleato and J.Eckstein,“Distributed optimization and statistical learning via the alternating direction method of multiplier,”Foundations and Trends in Machine Learning,vol.3,pp.1-122,2011.
[16]S.Kia,J.Cortes and S.Martinez,“Distributed convex optimization via continuous-time coordination algorithmns with discrete-time communication,”Automatica,vol.55,pp.254-264,2015.
[17]N.Li and J.Marden,“Designing games for distributed optimization,”IEEE Journal of Selected Topics in Signal Processing,vol.7,pp.230-242,2013.
[18]M.Ye and G.Hu,“Distributed optimization for systems with time-varying quadratic objective functions,”IEEE Conference on Decision and Control,pp.3285-3290,2015.
[19]P.Lin,W.Ren and Y.Song,“Distributed multi-agent optimization subject to nonidentical constraints and communication delays,”Automatica,vol.65,pp.120-131,2016.
[20]G.Droge,H.Kawashima and M.Egerstedt,“Continuoustime proportional-integral distributed optimization for networked systems,”Journal of Decision and Control,vol.1,pp.191-213,2014.
[21]A.Menon and J.Baras,“Collaborative extremum seeking for welfare optimization,”IEEE Conference on Decision and Control,pp.346-351,2014.
[22]S.Dougherty and M.Guay,“Extremum-seeking control of distributed systems using consensus estimation,”IEEE Conference on Decision and Control,pp.3450-3455,2014.
[23]L.Bai,M.Ye,C.Sun and G.Hu,“Distributed control for optimal economic dispatch via saddle point dynamics and consensus algorithms,”IEEE Conference on Decision and Control,pp.6934-6939,2016.
[24]D.Niyato,A.Vasilakos and Z.Kun,“Resource and revenue sharing with coalition formation of cloud providers:game theoretic approach,”IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing,pp.215-224,2011.
[25]R.Freeman,P.Yang and K.Lynch,“Stability and convergence properties of dynamic average consensus estimators,”IEEE Conference on Decision and Control,pp.398-403,2006.
[26]H.Khailil,Nonlinear System,Prentice Hall,3rd edtion,2002.
[27]J.Rosen,“Existence and uniquness of equilibrium points for concave N-person games,”Econometrica,vol.33,no.3,p.520,Jul.1965.
1 Related definitions on the graphs and games are given in the Section6.1.
2 Throughout this paper,(xi,x-i) and (xi*,x-i*) might be alternatively written as x and x*,respectively,for notational convenience.