Exponentially convergent distributed Nash equilibrium seeking for constrained aggregative games

Abstract

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

Keywords

Distributed algorithms / Aggregative games / Projected gradient play / Weight-balanced graph / Exponential convergence

References

[1] SaadW., HanZ., PoorH.V., BasarT.. Game-theoretic methods for the smart grid: an overview of microgrid systems, demand-side management, and smart grid communications. IEEE Signal Process. Mag., 2012, 29(5):86-105

[2] WurmanP.R., BarrettS., KawamotoK., et al.. Outracing champion Gran Turismo drivers with deep reinforcement learning. Nature, 2022, 602: 223-228

[3] KhalilH.K., KokotovicP.V.. Feedback and well-posedness of singularly perturbed Nash games. IEEE Trans. Autom. Control, 1979, 24(5):699-708

[4] ShammaJ.S., ArslanG.. Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria. IEEE Trans. Autom. Control, 2005, 50(3):312-327

[5] ZinkevichM., JohansonM., BowlingM., PiccioneC.. Regret minimization in games with incomplete information. Advances in Neural Information Processing Systems, 2007 Vancouver Curran Associates 1729-1736

[6] FrihaufP., KrsticM., BasarT.. Nash equilibrium seeking in noncooperative games. IEEE Trans. Autom. Control, 2012, 57(5):1192-1207

[7] BarreraJ., GarciaA.. Dynamic incentives for congestion control. IEEE Trans. Autom. Control, 2015, 60(2):299-310

[8] CornesR.. Aggregative environmental games. Environ. Resour. Econ., 2016, 63(2):339-365

[9] NockeV., SchutzN.. Multiproduct-firm oligopoly: an aggregative games approach. Econometrica, 2018, 86(2):523-557

[10] KoshalJ., NedićA., ShanbhagU.V.. Distributed algorithms for aggregative games on graphs. Oper. Res., 2016, 63(3):680-704

[11] YeM., HuG.. Game design and analysis for price-based demand response: an aggregate game approach. IEEE Trans. Cybern., 2017, 47(3):720-730

[12] LiangS., YiP., HongY.. Distributed Nash equilibrium seeking for aggregative games with coupled constraints. Automatica, 2017, 85(11):179-185

[13] DengZ.. Distributed generalized Nash equilibrium seeking algorithm for nonsmooth aggregative games. Automatica, 2021, 132

[14] GadjovD., PavelL.. Single-timescale distributed GNE seeking for aggregative games over networks via forward–backward operator splitting. IEEE Trans. Autom. Control, 2021, 66(7):3259-3266

[15] ZhuY., YuW., WenG., ChenG.. Distributed Nash equilibrium seeking in an aggregative game on a directed graph. IEEE Trans. Autom. Control, 2021, 66(6):2746-2753

[16] BelgioiosoG., NedićA., GrammaticoS.. Distributed generalized Nash equilibrium seeking in aggregative games on time-varying networks. IEEE Trans. Autom. Control, 2021, 66(5):2061-2075

[17] YiP., HongY., LiuF.. Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and its application to economic dispatch of power systems. Automatica, 2016, 74(12):259-269

[18] NedićA., OlshevskyA., ShiW.. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM J. Optim., 2017, 27(4):2597-2633

[19] FacchineiF., PangJ.. Finite-Dimensional Variational Inequalities and Complementarity Problems. Operations Research, 2003 New York Springer

[20] GodsilC., RoyleG.F.. Algebraic Graph Theory, 2001 New York Springer

[21] YiP., PavelL.. An operator splitting approach for distributed generalized Nash equilibria computation. Automatica, 2019, 102: 111-121

[22] DengZ., NianX.. Distributed generalized Nash equilibrium seeking algorithm design for aggregative games over weight-balanced digraphs. IEEE Trans. Neural Netw. Learn. Syst., 2019, 30(3):695-706

[23] PariseF., GentileB., LygerosJ.. A distributed algorithm for almost-Nash equilibria of average aggregative games with coupling constraints. IEEE Trans. Control Netw. Syst., 2020, 7(2):770-782

[24] ZhangH., WeiJ., YiP., HuX.. Projected primal–dual gradient flow of augmented Lagrangian with application to distributed maximization of the algebraic connectivity of a network. Automatica, 2018, 98: 34-41

[25] HornR.A., JohnsonC.R.. Matrix Analysis, 2013 2 Cambridge Cambridge University Press

[26] LiangS., WangL., YinG.. Exponential convergence of distributed primal-dual convex optimization algorithm without strong convexity. Automatica, 2019, 105: 298-306

Funding

National Natural Science Foundation of China(72171171)