Nash equilibrium seeking over directed graphs
Tóm tắt
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.
Tài liệu tham khảo
D. Fudenberg, J. Tirole, Game Theory (MIT Press, Cambridge, 1991)
T. Başar, G. Zaccour, Handbook of Dynamic Game Theory (Springer, New York, 2018)
M. Maschler, S. Zamir, E. Solan, Game Theory (Cambridge University Press, Cambridge, 2020)
S. Li, T. Başar, Distributed algorithms for the computation of noncooperative equilibria. Automatica 23(4), 523–533 (1987)
T. Basar, G.J. Olsder, Dynamic Noncooperative Game Theory (2nd) (SIAM, Philadelphia, 1999)
M.S. Stankovic, K.H. Johansson, D.M. Stipanovic, Distributed seeking of Nash equilibria with applications to mobile sensor networks. IEEE Trans. Autom. Control 57(4), 904–919 (2011)
M. Mesbahi, M. Egerstedt, Graph Theoretic Methods in Multiagent Networks (Princeton University Press, Princeton, 2010)
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)
P. Frihauf, M. Krstic, T. Basar, Nash equilibrium seeking in noncooperative games. IEEE Trans. Autom. Control 57(5), 1192–1207 (2011)
G. Scutari, F. Facchinei, J.-S. Pang, D.P. Palomar, Real and complex monotone communication games. IEEE Trans. Inf. Theory 60(7), 4197–4231 (2014)
S. Grammatico, Dynamic control of agents playing aggregative games with coupling constraints. IEEE Trans. Autom. Control 62(9), 4537–4548 (2017)
R. Olfati-Saber, J.A. Fax, R.M. Murray, Consensus and cooperation in networked multi-agent systems. Proc. IEEE 95(1), 215–233 (2007)
B. Swenson, S. Kar, J. Xavier, Empirical centroid fictitious play: an approach for distributed learning in multi-agent games. IEEE Trans. Signal Process. 63(15), 3888–3901 (2015)
Y. Lou, Y. Hong, L. Xie, G. Shi, K.H. Johansson, Nash equilibrium computation in subnetwork zero-sum games with switching communications. IEEE Trans. Autom. Control 61(10), 2920–2935 (2016)
J. Koshal, A. Nedić, U.V. Shanbhag, Distributed algorithms for aggregative games on graphs. Oper. Res. 64(3), 680–704 (2016)
F. Salehisadaghiani, L. Pavel, Distributed Nash equilibrium seeking: a gossip-based algorithm. Automatica 72, 209–216 (2016)
D. Gadjov, L. Pavel, A passivity-based approach to Nash equilibrium seeking over networks. IEEE Trans. Autom. Control 64(3), 1077–1092 (2019)
M. Ye, G. Hu, Distributed Nash equilibrium seeking in multiagent games under switching communication topologies. IEEE Trans. Cybern. 48(11), 3208–3217 (2017)
S. Liang, P. Yi, Y. Hong, Distributed Nash equilibrium seeking for aggregative games with coupled constraints. Automatica 85, 179–185 (2017)
X. Zeng, J. Chen, S. Liang, Y. Hong, Generalized Nash equilibrium seeking strategy for distributed nonsmooth multi-cluster game. Automatica 103, 20–26 (2019)
C. De Persis, S. Grammatico, Distributed averaging integral Nash equilibrium seeking on networks. Automatica 110, 108548 (2019)
P. Yi, L. Pavel, Distributed generalized Nash equilibria computation of monotone games via double-layer preconditioned proximal-point algorithms. IEEE Trans. Control Netw. Syst. 6(1), 299–311 (2018)
A. Romano, L. Pavel, Dynamic NE seeking for multi-integrator networked agents with disturbance rejection. IEEE Trans. Control Netw. Syst. 7(1), 129–139 (2020)
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)
Z. Deng, S. Liang, Distributed algorithms for aggregative games of multiple heterogeneous Euler–Lagrange systems. Automatica 99, 246–252 (2019)
T. Tatarenko, W. Shi, A. Nedić, Geometric convergence of gradient play algorithms for distributed Nash equilibrium seeking. IEEE Trans. Autom. Control 66(11), 5342–5353 (2020)
A. Ruszczynski, Nonlinear Optimization (Princeton University Press, Princeton, 2006)
F. Facchinei, J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems (Springer, New York, 2003)
H.K. Khalil, Nonlinear Systems, 3rd edn. (Prentice Hall, New Jersey, 2002)
A. Berman, R.J. Plemmons, Nonnegative Matrices in the Mathematical Sciences (SIAM, Philadelphia, 1994)
C.N. Hadjicostis, A.D. Domínguez-García, T. Charalambous, Distributed averaging and balancing in network systems: with applications to coordination and control. Found. Trends Syst. Control. 5(2–3), 99–292 (2018)
R.J. LeVeque, Finite Difference Methods for Ordinary and Partial Differential Equations (SIAM, Philadelphia, 2007)
Y. Tang, X. Wang, Optimal output consensus for nonlinear multiagent systems with both static and dynamic uncertainties. IEEE Trans. Autom. Control 66(4), 1733–1740 (2020)