×

An asynchronous distributed and scalable generalized Nash equilibrium seeking algorithm for strongly monotone games. (English) Zbl 1458.91017

Summary: In this paper, we present three distributed algorithms to solve a class of generalized Nash equilibrium (GNE) seeking problems in strongly monotone games. The first one (SD-GENO) is based on synchronous updates of the agents, while the second and the third (AD-GEED and AD-GENO) represent asynchronous solutions that are robust to communication delays. AD-GENO can be seen as a refinement of AD-GEED, since it only requires node auxiliary variables, enhancing the scalability of the algorithm. Our main contribution is to prove convergence to a v-GNE variational-GNE (vGNE) of the game via an operator-theoretic approach. Finally, we apply the algorithms to network Cournot games and show how different activation sequences and delays affect convergence. We also compare the proposed algorithms to a state-of-the-art algorithm solving a similar problem, and observe that AD-GENO outperforms it.

MSC:

91A11 Equilibrium refinements
91A10 Noncooperative games
91A68 Algorithmic game theory and complexity

Software:

ARock; HOGWILD
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bauschke, H. H.; Combettes, P. L., Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 408 (2011), Springer · Zbl 1218.47001
[2] 20th IFAC World Congress
[3] Belgioioso, G.; Grammatico, S., Semi-decentralized Nash equilibrium seeking in aggregative games with coupling constraints and non-differentiable cost functions, IEEE Control Syst. Lett., 1, 2, 400-405 (2017)
[4] Bertsekas, D. P.; Tsitsiklis, J. N., Parallel and Distributed Computation: Numerical Methods, 23 (1989), Prentice hall Englewood: Prentice hall Englewood Cliffs, NJ · Zbl 0743.65107
[5] Bertsekas, D. P.; Tsitsiklis, J. N., Some aspects of parallel and distributed iterative algorithms survey, Automatica, 27, 1, 3-21 (1991) · Zbl 0728.65041
[6] Cenedese, C.; Kawano, Y.; Grammatico, S.; Cao, M., Towards time-varying proximal dynamics in multi-agent network games, 2018 IEEE Conference on Decision and Control (CDC), 4378-4383 (2018)
[7] Cenedese, C.; Belgioioso, G.; Grammatico, S.; Cao, M., An asynchronous, forward-backward, distributed generalized Nash equilibrium seeking algorithm, 2019 18th European Control Conference (ECC), 3508-3513 (2019)
[8] Cenedese, C.; Fabiani, F.; Cucuzzella, M.; Scherpen, J. M.A.; Cao, M.; Grammatico, S., Charging plug-in electric vehicles as a mixed-integer aggregative game, 2019 IEEE 58th Conference on Decision and Control (CDC), 4904-4909 (2019)
[9] C. Cenedese, G. Belgioioso, S. Grammatico, M. Cao, Time-varying constrained proximal type dynamics in multi-agent network games (2020).
[10] (in press)
[11] Combettes, P.; Pesquet, J., Stochastic quasi-fejér block-coordinate fixed point iterations with random sweeping, SIAM J. Optim., 25, 2, 1221-1248 (2015) · Zbl 1317.65135
[12] Dörfler, F.; Simpson-Porco, J.; Bullo, F., Breaking the hierarchy: Distributed control and economic optimality in microgrids, IEEE Trans. Control Netw. Syst., 3, 3, 241-253 (2016) · Zbl 1370.93157
[13] Dreves, A.; Facchinei, F.; Kanzow, C.; Sagratella, S., On the solution of the KKT conditions of generalized Nash equilibrium problems, SIAM J. Optim., 21, 3, 1082-1108 (2011) · Zbl 1230.90176
[14] Eckstein, J., Splitting Methods for Monotone Operators With Applications to Parallel Optimization (1989), Massachusetts Institute of Technology, Ph.D. thesis
[15] Facchinei, F.; Pang, J., Finite-dimensional Variational Inequalities and Complementarity Problems (2003), Springer Verlag · Zbl 1062.90002
[16] Facchinei, F.; Kanzow, C., Generalized Nash equilibrium problems, 4or, 5, 3, 173-210 (2007) · Zbl 1211.91162
[17] Facchinei, F.; Fischer, A.; Piccialli, V., On generalized Nash games and variational inequalities, Oper. Res. Lett., 35, 159-164 (2007) · Zbl 1303.91020
[18] Feingold, D. G.; Varga, R. S., Block diagonally dominant matrices and generalizations of the Gerschgorin circle theorem., Pac. J. Math., 12, 4, 1241-1250 (1962) · Zbl 0109.24802
[19] Govaert, A.; Cenedese, C.; Grammatico, S.; Cao, M., Relative best response dynamics in finite and convex network games, 2019 IEEE 58th Conference on Decision and Control (CDC), 3134-3139 (2019)
[20] Grammatico, S., Proximal dynamics in multi-agent network games, IEEE Trans. Control Netw. Syst. (2018) · Zbl 1515.91037
[21] Kulkarni, A. A.; Shanbhag, U., On the variational equilibrium as a refinement of the generalized Nash equilibrium, Automatica, 48, 45-55 (2012) · Zbl 1245.91006
[22] Kulkarni, A. A.; Shanbhag, U. V., Revisiting generalized Nash games and variational inequalities, J. Optim. Theory Appl., 154, 1, 175-186 (2012) · Zbl 1261.90065
[23] Nedic, A., Asynchronous broadcast-based convex optimization over a network, IEEE Trans. Autom. Control, 56, 6, 1337-1351 (2011) · Zbl 1368.90126
[24] Paccagnan, D.; Gentile, B.; Parise, F.; Kamgarpour, M.; Lygeros, J., Distributed computation of generalized Nash equilibria in quadratic aggregative games with affine coupling constraints, 2016 IEEE 55th Conference on Decision and Control (CDC), 6123-6128 (2016)
[25] Paccagnan, D.; Gentile, B.; Parise, F.; Kamgarpour, M.; Lygeros, J., Nash and Wardrop equilibria in aggregative games with coupling constraints, IEEE Trans. Autom. Control, 64, 4, 1373-1388 (2019) · Zbl 1482.91045
[26] Peng, Z.; Xu, Y.; Yan, M.; Yin, W., Arock: an algorithmic framework for asynchronous parallel coordinate updates, SIAM J. Sci. Comput., 38, 5, A2851-A2879 (2016) · Zbl 1350.49041
[27] Recht, B.; Re, C.; Wright, S.; Niu, F., Hogwild: a lock-free approach to parallelizing stochastic gradient descent, Advances in Neural Information Processing Systems, 693-701 (2011)
[28] Rosen, J., Existence and uniqueness of equilibrium points for concave n-person games, Econometrica, 33, 520-534 (1965) · Zbl 0142.17603
[29] Scutari, G.; Palomar, D. P.; Facchinei, F.; Pang, J., Convex optimization, game theory, and variational inequality theory, IEEE Signal Processing Magazine, 27, 3, 35-49 (2010)
[30] Yi, P.; Pavel, L., An operator splitting approach for distributed generalized Nash equilibria computation, Automatica, 102, 111-121 (2019) · Zbl 1411.91031
[31] Yi, P.; Pavel, L., Asynchronous distributed algorithms for seeking generalized Nash equilibria under full and partial-decision information, IEEE Trans. Cybern., 1-13 (2019)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.