×

Edge-based distributed primal-dual algorithms for seeking generalized Nash equilibria. (English) Zbl 1537.91066

Summary: This paper introduces two novel distributed algorithms aimed at finding the generalized Nash equilibria (GNE) in noncooperative games. To tackle this, we utilize the variational inequality framework, transforming the noncooperative game into the challenge of identifying the zeros of a sum of monotone operators. Within noncooperative games, the decisions made by individual players are interlinked via shared affine constraints. Our proposed approach involves two edge-based distributed algorithms, differentiated by their access to players’ actions, whether it is full-decision information or partial-decision information. We establish the parameter range and demonstrate the convergence of both algorithms, showcasing their efficacy under local constant step-sizes. Additionally, we validate the effectiveness and advantages of these algorithms through two numerical experiments.

MSC:

91A68 Algorithmic game theory and complexity
91A11 Equilibrium refinements
91A10 Noncooperative games
Full Text: DOI

References:

[1] Bahrami, S.; Sheikhi, A., From demand response in smart grid toward integrated demand response in smart energy hub, IEEE Transactions on Smart Grid, 7, 2, 650-658, 2016
[2] Belgioioso, G.; Nedic, A.; Grammatico, S., Distributed generalized Nash equilibrium seeking in aggregative games on time-varying networks, IEEE Transactions on Automatic Control, 66, 5, 2061-2075, 2021 · Zbl 1536.91016
[3] Cenedese, C., Belgioioso, G., Grammatico, S., & Cao, M. (2019). An asynchronous, forward-backward, distributed generalized Nash equilibrium seeking algorithm. In 2019 18th European control conference.
[4] Combettes, P.; Bauschke, H., Correction to: Convex analysis and monotone operator theory in Hilbert spaces, 2019
[5] Debreu, G., A social equilibrium existence theorem, Proceedings of the National Academy of Sciences, 38, 10, 886-893, 1952 · Zbl 0047.38804
[6] Dian, G.; Pavel, L., A passivity-based approach to nash equilibrium seeking over networks, IEEE Transactions on Automatic Control, 64, 3, 1077-1092, 2018 · Zbl 1482.91047
[7] Facchinei, F.; Fischer, A.; Piccialli, V., On generalized Nash games and variational inequalities, Operations Research Letters, 35, 2, 159-164, 2007 · Zbl 1303.91020
[8] Facchinei, F.; Kanzow, C., Generalized Nash equilibrium problems, Annals of Operations Research, 175, 1, 177-211, 2010 · Zbl 1185.91016
[9] Fischer, A.; Herrich, M.; Schonefeld, L., Generalized Nash equilibrium problems-recent advances and challenges, Pesquisa Operacional, 34, 3, 521-558, 2014
[10] Franci, B.; Grammatico, S., A distributed forward-backward algorithm for stochastic generalized Nash equilibrium seeking, IEEE Transactions on Automatic Control, 66, 11, 5467-5473, 2021 · Zbl 1536.91019
[11] Grammatico, S., Dynamic control of players playing aggregative games with coupling constraints, IEEE Transactions on Automatic Control, 62, 9, 4537-4548, 2017 · Zbl 1390.91063
[12] Grammatico, S.; Parise, F.; Colombino, M.; Lygeros, J., Decentralized convergence to Nash equilibria in constrained deterministic mean field control, IEEE Transactions on Automatic Control, 61, 11, 3315-3329, 2016 · Zbl 1359.91004
[13] Ishai, M.; Ozdaglar, A., Network games: Theory, models, and dynamics, Synthesis Lectures on Communication Networks, 4, 1, 1-159, 2011 · Zbl 1304.91008
[14] Kuhn; Tucker, H. W., Nonlinear programming, (Proceed- ings of 2nd Berkeley symposium, 1951, University of California Press: University of California Press Berkeley), 481-492 · Zbl 0044.05903
[15] Lei, J.; Shanbhag, U. V.; Pang, J.-S.; Sen, S., On synchronous, asynchronous, and randomized best-response schemes for computing equilibria in stochastic Nash games, Mathematics of Operations Research, 45, 1, 2017
[16] Li, S., Li, H., Li, Z., Fan, L., Zheng, L., & Li, J. Distributed Primal-Dual Algorithm for Seeking Generalized Nash Equilibria in Aggregative Games. 2023 2nd Asia conference on electrical, power and computer engineering (EPCE), Xiamen, China. (pp. 110-115).
[17] Lou, Y.; Hong, Y.; Xie, L.; Shi, G.; Johansson, K. H., Nash equilibrium computation in subnetwork zero-sum games with switching communications, IEEE Transactions on Automatic Control, 61, 10, 2920-2935, 2016 · Zbl 1359.91022
[18] Lu, K.; Jing, G.; Wang, L., Distributed algorithms for searching generalized nash equilibrium of noncooperative games, IEEE Transactions on Cybernetics, 49, 6, 2362-2371, 2018
[19] Opial; Zdzisaw, Weak convergence of the sequence of successive approximations for nonexpansive mappings, American Mathematical Society. Bulletin, 73, 4, 591-597, 1967 · Zbl 0179.19902
[20] Paccagnan, D., Gentile, B., Parise, F., Kamgarpour, M., & Lygeros, J. (2016). Distributed computation of generalized Nash equilibria in quadratic aggregative games with affine coupling constraints. In 55th IEEE conference on decision and control (pp. 6123-6128).
[21] Pan, Y.; Pavel, L., Games with coupled propagated constraints in optical networks with multi-link topologies, Automatica, 45, 4, 871-880, 2009 · Zbl 1162.91326
[22] Pavel, L., An extension of duality to a game-theoretic framework, Automatica, 43, 2, 226-237, 2007 · Zbl 1115.93005
[23] Pavel, L. (2018). A doubly-augmented operator splitting approach for distributed GNE seeking over networks. In 2018 IEEE annual conference on decision and control.
[24] Pavel, L., Distributed GNE seeking under partial-decision information over networks via a doubly-augmented operator splitting approach, IEEE Transactions on Automatic Control, 65, 4, 1584-1597, 2020 · Zbl 1533.91017
[25] Salehisadaghiani, F.; Pavel, L., Distributed Nash equilibrium seeking: A gossip-based algorithm, Automatica, 72, 209-216, 2016 · Zbl 1344.93045
[26] Salehisadaghiani, F.; Pavel, L., Distributed Nash equilibrium seeking via the alternating direction method of multipliers, Computer Science and Game Theory, 50, 1, 6166-6171, 2016
[27] Shi, W.; Ling, Q.; Wu, G.; Yin, W., A proximal gradient algorithm for decentralized composite optimization, IEEE Transactions on Signal Processing, 63, 22, 6013-6023, 2015 · Zbl 1394.94531
[28] Wu, C.; Gu, W.; Bo, R., Energy trading and generalized nash equilibrium in combined heat and power market, IEEE Transactions on Power Systems, 99, 5, 3378-3387, 2020
[29] Ye, M.; Hu, G., Distributed Nash equilibrium seeking by a consensus based approach, IEEE Transactions on Automatic Control, 62, 9, 4811-4818, 2017 · Zbl 1390.91081
[30] Ye, M.; Hu, G., Game design and analysis for price-based demand response: An aggregate game approach, IEEE Transactions on Cybernetics, 47, 3, 720-730, 2017
[31] Yi, P.; Pavel, L., Distributed generalized Nash equilibria computation of monotone games via a preconditioned proximal point algorithm, IEEE Transactions on Control of Network Systems, 6, 1, 299-311, 2017 · Zbl 1515.91023
[32] Yi, P.; Pavel, L., Asynchronous distributed algorithms for seeking generalized Nash equilibria under full and partial decision information, IEEE Transactions on Cybernetics, 50, 6, 2514-2526, 2019
[33] Yi, P.; Pavel, L., Distributed generalized Nash equilibria computation of monotone games via double-layer preconditioned proximal-point algorithms, IEEE Transactions on Control of Network Systems, 6, 1, 299-311, 2019 · Zbl 1515.91023
[34] Yi, P.; Pavel, L., An operator splitting approach for distributed generalized Nash equilibria computation, Automatica, 102, 111-121, 2019 · Zbl 1411.91031
[35] Yin, H.; Shanbhag, U. V.; Mehta, P. G., Nash equilibrium problems with scaled congestion costs and shared constraints, IEEE Transactions on Automatic Control, 56, 7, 1702-1708, 2011 · Zbl 1368.91011
[36] Zhang, G., & Heusdens, R. (2015). Bi-alternating direction method of multipliers over graphs. In ICASSP, IEEE international conference on acoustics, speech and signal processing - proceedings (pp. 3571-3575).
[37] Zhu, M.; Frazzoli, E., Distributed robust adaptive equilibrium computation for generalized convex games, Automatica, 97, 186-188, 2016 · Zbl 1406.93117
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.