Nash equilibrium seeking over directed graphs

Abstract

In this paper, we aim to develop distributed continuous-time algorithms over directed graphs to seek the Nash equilibrium in a noncooperative game. Motivated by the recent consensus-based designs, we present a distributed algorithm with a proportional gain for weight-balanced directed graphs. By further embedding a distributed estimator of the left eigenvector associated with zero eigenvalue of the graph Laplacian, we extend it to the case with arbitrary strongly connected directed graphs having possible unbalanced weights. In both cases, the Nash equilibrium is proven to be exactly reached with an exponential convergence rate. An example is given to illustrate the validity of the theoretical results.

Keywords

Nash equilibrium / Directed graph / Exponential convergence / Proportional control / Distributed computation

References

[1] FudenbergD., TiroleJ.. Game Theory, 1991 Cambridge MIT Press

[2] BaşarT., ZaccourG.. Handbook of Dynamic Game Theory, 2018 New York Springer

[3] MaschlerM., ZamirS., SolanE.. Game Theory, 2020 Cambridge Cambridge University Press

[4] LiS., BaşarT.. Distributed algorithms for the computation of noncooperative equilibria. Automatica, 1987, 23(4):523-533

[5] BasarT., OlsderG.J.. Dynamic Noncooperative Game Theory (2nd), 1999 Philadelphia SIAM

[6] StankovicM.S., JohanssonK.H., StipanovicD.M.. Distributed seeking of Nash equilibria with applications to mobile sensor networks. IEEE Trans. Autom. Control, 2011, 57(4):904-919

[7] MesbahiM., EgerstedtM.. Graph Theoretic Methods in Multiagent Networks, 2010 Princeton Princeton University Press

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

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

[10] ScutariG., FacchineiF., PangJ.-S., PalomarD.P.. Real and complex monotone communication games. IEEE Trans. Inf. Theory, 2014, 60(7):4197-4231

[11] GrammaticoS.. Dynamic control of agents playing aggregative games with coupling constraints. IEEE Trans. Autom. Control, 2017, 62(9):4537-4548

[12] Olfati-SaberR., FaxJ.A., MurrayR.M.. Consensus and cooperation in networked multi-agent systems. Proc. IEEE, 2007, 95(1):215-233

[13] SwensonB., KarS., XavierJ.. Empirical centroid fictitious play: an approach for distributed learning in multi-agent games. IEEE Trans. Signal Process., 2015, 63(15):3888-3901

[14] LouY., HongY., XieL., ShiG., JohanssonK.H.. Nash equilibrium computation in subnetwork zero-sum games with switching communications. IEEE Trans. Autom. Control, 2016, 61(10):2920-2935

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

[16] SalehisadaghianiF., PavelL.. Distributed Nash equilibrium seeking: a gossip-based algorithm. Automatica, 2016, 72: 209-216

[17] GadjovD., PavelL.. A passivity-based approach to Nash equilibrium seeking over networks. IEEE Trans. Autom. Control, 2019, 64(3):1077-1092

[18] YeM., HuG.. Distributed Nash equilibrium seeking in multiagent games under switching communication topologies. IEEE Trans. Cybern., 2017, 48(11):3208-3217

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

[20] ZengX., ChenJ., LiangS., HongY.. Generalized Nash equilibrium seeking strategy for distributed nonsmooth multi-cluster game. Automatica, 2019, 103: 20-26

[21] De PersisC., GrammaticoS.. Distributed averaging integral Nash equilibrium seeking on networks. Automatica, 2019, 110

[22] YiP., PavelL.. Distributed generalized Nash equilibria computation of monotone games via double-layer preconditioned proximal-point algorithms. IEEE Trans. Control Netw. Syst., 2018, 6(1):299-311

[23] RomanoA., PavelL.. Dynamic NE seeking for multi-integrator networked agents with disturbance rejection. IEEE Trans. Control Netw. Syst., 2020, 7(1):129-139

[24] Y. Zhang, S. Liang, X. Wang, H. Ji, Distributed Nash equilibrium seeking for aggregative games with nonlinear dynamics under external disturbances. IEEE Trans. Cybern., 1–10 (2019)

[25] DengZ., LiangS.. Distributed algorithms for aggregative games of multiple heterogeneous Euler–Lagrange systems. Automatica, 2019, 99: 246-252

[26] TatarenkoT., ShiW., NedićA.. Geometric convergence of gradient play algorithms for distributed Nash equilibrium seeking. IEEE Trans. Autom. Control, 2020, 66(11):5342-5353

[27] RuszczynskiA.. Nonlinear Optimization, 2006 Princeton Princeton University Press

[28] FacchineiF., PangJ.-S.. Finite-Dimensional Variational Inequalities and Complementarity Problems, 2003 New York Springer

[29] KhalilH.K.. Nonlinear Systems, 2002 3 New Jersey Prentice Hall

[30] BermanA., PlemmonsR.J.. Nonnegative Matrices in the Mathematical Sciences, 1994 Philadelphia SIAM

[31] HadjicostisC.N., Domínguez-GarcíaA.D., CharalambousT.. Distributed averaging and balancing in network systems: with applications to coordination and control. Found. Trends Syst. Control., 2018, 5(2–3):99-292

[32] LeVequeR.J.. Finite Difference Methods for Ordinary and Partial Differential Equations, 2007 Philadelphia SIAM

[33] TangY., WangX.. Optimal output consensus for nonlinear multiagent systems with both static and dynamic uncertainties. IEEE Trans. Autom. Control, 2020, 66(4):1733-1740

Funding

National Natural Science Foundation of China(62003239)