Exponentially convergent distributed Nash equilibrium seeking for constrained aggregative games

Autonomous Intelligent Systems - 2022
Shu Liang1, Peng Yi1, Hong Ye1, Kaixiang Peng2
1Department of Control Science & Engineering, Tongji University, Shanghai, 200092, China
2School of Automation and Electrical Engineering, University of Science and Technology Beijing, Beijing 100083, China

Tóm tắt

AbstractDistributed Nash equilibrium seeking of aggregative games is investigated and a continuous-time algorithm is proposed. The algorithm is designed by virtue of projected gradient play dynamics and aggregation tracking dynamics, and is applicable to games with constrained strategy sets and weight-balanced communication graphs. The key feature of our method is that the proposed projected dynamics achieves exponential convergence, whereas such convergence results are only obtained for non-projected dynamics in existing works on distributed optimization and equilibrium seeking. Numerical examples illustrate the effectiveness of our methods.

Từ khóa


Tài liệu tham khảo

W. Saad, Z. Han, H.V. Poor, T. Basar, Game-theoretic methods for the smart grid: an overview of microgrid systems, demand-side management, and smart grid communications. IEEE Signal Process. Mag. 29(5), 86–105 (2012)

P.R. Wurman, S. Barrett, K. Kawamoto et al., Outracing champion Gran Turismo drivers with deep reinforcement learning. Nature 602, 223–228 (2022)

H.K. Khalil, P.V. Kokotovic, Feedback and well-posedness of singularly perturbed Nash games. IEEE Trans. Autom. Control 24(5), 699–708 (1979)

J.S. Shamma, G. Arslan, Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria. IEEE Trans. Autom. Control 50(3), 312–327 (2005)

M. Zinkevich, M. Johanson, M. Bowling, C. Piccione, Regret minimization in games with incomplete information, in Advances in Neural Information Processing Systems, vol. 20 (Curran Associates, Vancouver, 2007), pp. 1729–1736

P. Frihauf, M. Krstic, T. Basar, Nash equilibrium seeking in noncooperative games. IEEE Trans. Autom. Control 57(5), 1192–1207 (2012)

J. Barrera, A. Garcia, Dynamic incentives for congestion control. IEEE Trans. Autom. Control 60(2), 299–310 (2015)

R. Cornes, Aggregative environmental games. Environ. Resour. Econ. 63(2), 339–365 (2016)

V. Nocke, N. Schutz, Multiproduct-firm oligopoly: an aggregative games approach. Econometrica 86(2), 523–557 (2018)

J. Koshal, A. Nedić, U.V. Shanbhag, Distributed algorithms for aggregative games on graphs. Oper. Res. 63(3), 680–704 (2016)

M. Ye, G. Hu, Game design and analysis for price-based demand response: an aggregate game approach. IEEE Trans. Cybern. 47(3), 720–730 (2017)

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

Z. Deng, Distributed generalized Nash equilibrium seeking algorithm for nonsmooth aggregative games. Automatica 132, 109794 (2021)

D. Gadjov, L. Pavel, Single-timescale distributed GNE seeking for aggregative games over networks via forward–backward operator splitting. IEEE Trans. Autom. Control 66(7), 3259–3266 (2021)

Y. Zhu, W. Yu, G. Wen, G. Chen, Distributed Nash equilibrium seeking in an aggregative game on a directed graph. IEEE Trans. Autom. Control 66(6), 2746–2753 (2021)

G. Belgioioso, A. Nedić, S. Grammatico, Distributed generalized Nash equilibrium seeking in aggregative games on time-varying networks. IEEE Trans. Autom. Control 66(5), 2061–2075 (2021)

P. Yi, Y. Hong, F. Liu, Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and its application to economic dispatch of power systems. Automatica 74(12), 259–269 (2016)

A. Nedić, A. Olshevsky, W. Shi, Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM J. Optim. 27(4), 2597–2633 (2017)

F. Facchinei, J. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems. Operations Research (Springer, New York, 2003)

C. Godsil, G.F. Royle, Algebraic Graph Theory. Graduate Texts in Mathematics, vol. 207 (Springer, New York, 2001)

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

Z. Deng, X. Nian, Distributed generalized Nash equilibrium seeking algorithm design for aggregative games over weight-balanced digraphs. IEEE Trans. Neural Netw. Learn. Syst. 30(3), 695–706 (2019)

F. Parise, B. Gentile, J. Lygeros, A distributed algorithm for almost-Nash equilibria of average aggregative games with coupling constraints. IEEE Trans. Control Netw. Syst. 7(2), 770–782 (2020)

H. Zhang, J. Wei, P. Yi, X. Hu, Projected primal–dual gradient flow of augmented Lagrangian with application to distributed maximization of the algebraic connectivity of a network. Automatica 98, 34–41 (2018)

R.A. Horn, C.R. Johnson, Matrix Analysis, 2nd ed. (Cambridge University Press, Cambridge, 2013)

S. Liang, L. Wang, G. Yin, Exponential convergence of distributed primal-dual convex optimization algorithm without strong convexity. Automatica 105, 298–306 (2019)

Thông tin
Thông tin xuất bản

Autonomous Intelligent Systems

Thông tin tác giả