本文研究带线性耦合约束的广义纳什均衡问题,提出两类基于算子分裂的分布式算法。通过引入各玩家对其他玩家决策的局部估计,将变分广义纳什均衡点的求解转化为双增广算子的零点问题。在此基础上,分别构造了带惯性的松弛Douglas-Rachford分裂算法和基于Peaceman-Rachford分裂的分布式算法。在线性耦合约束、凸可行集以及伪梯度映射强单调且Lipschitz连续的条件下,证明了所提算法的收敛性。数值实验验证了算法的有效性。
This paper studies generalized Nash equilibrium problems with linear coupling constraints and proposes two distributed algorithms based on operator splitting. By introducing local estimates of other players' decisions for each player, the computation of variational generalized Nash equilibria is reformulated as a zero-finding problem of a double-augmented operator. Based on this reformulation, an inertial relaxed Douglas-Rachford splitting algorithm and a distributed algorithm based on Peaceman-Rachford splitting are constructed. Under linear coupling constraints, convex feasible sets, and the strong monotonicity and Lipschitz continuity of the pseudo-gradient mapping, the convergence of the proposed algorithms is established. Numerical experiments verify the effectiveness of the algorithms.
[1] Ye M J, Hu G Q. Distributed Nash equilibrium seeking by a consensus based approach [J]. IEEE Transactions on Automatic Control, 2017, 62(9): 4811-4818.
[2] Zhu M H, Frazzoli E. Distributed robust adaptive equilibrium computation for generalized convex games [J]. Automatica, 2016, 63: 82-91.
[3] Pan Y, Pavel L. Games with coupled propagated constraints in optical networks with multi-link topologies [J]. Automatica, 2009, 45(4): 871-880.
[4] Pavel L. An extension of duality to a game-theoretic framework [J]. Automatica, 2007, 43(2): 226-237.
[5] Alpcan T, Bąsar T. Distributed algorithms for Nash equilibria of flow control games [M]//Nowak A S, Szajowski K. (eds.) Advances in dynamic games: applications to economics; finance; optimization; and stochastic control, Boston: Birkhäuser, 2005: 473-498.
[6] Yin H B, Shanbhag U V, Mehta P G. Nash equilibrium problems with scaled congestion costs and shared constraints [J]. IEEE Transactions on Automatic Control, 2011, 56(7): 1702-1708.
[7] Ozdaglar A, Menache I. Network games: theory; models; and dynamics [M]. San Rafael: Morgan & Claypool Publishers, 2011.
[8] Grammatico S. Dynamic control of agents playing aggregative games with coupling constraints [J]. IEEE Transactions on Automatic Control, 2017, 62(9): 4537-4548.
[9] Facchinei F, Kanzow C. Generalized Nash equilibrium problems [J]. Annals of Operations Research, 2010, 175(1): 177-211.
[10] Salehisadaghiani F, Pavel L. Distributed Nash equilibrium seeking: a gossip-based algorithm [J]. Automatica, 2016, 72: 209-216.
[11] Tatarenko T, Shi W, Nedić A. Geometric convergence of gradient play algorithms for distributed Nash equilibrium seeking [J]. IEEE Transactions on Automatic Control, 2021, 66(11): 5342-5353.
[12] Koshal J, Nedić A, Shanbhag U V. Distributed algorithms for aggregative games on graphs [J]. Operations Research, 2016, 64(3): 680-704.
[13] Ye M, Han Q L, Ding L, et al. Distributed Nash equilibrium seeking in games with partial decision information: a survey [J]. Proceedings of the IEEE, 2023, 111(2): 140-157.
[14] Pavel L. On operator theory and applications in game theory [J]. Annual Review of Control, Robotics, and Autonomous Systems, 2025, 9: 99-122.
[15] Pavel L. Distributed GNE seeking under partial-decision information over networks via a doubly-augmented operator splitting approach [J]. IEEE Transactions on Automatic Control, 2020, 65(4): 1584-1597.
[16] Yi P, Pavel L. Distributed generalized Nash equilibria computation of monotone games via double-layer preconditioned proximal-point algorithms [J]. IEEE Transactions on Control of Network Systems, 2018, 6(1): 299-311.
[17] Bianchi M, Belgioioso G, Grammatico S. Fast generalized Nash equilibrium seeking under partial-decision information [J]. Automatica, 2022, 136: 110080.
[18] Huang Y H, Hu J H. Distributed solution of GNEP over networks via the Douglas-Rachford splitting method [C]//Proceedings of the 60th IEEE Conference on Decision and Control, 2021: 3110-3116.
[19] Zheng Z Q, Li H Q, Niu Y et al. Distributed generalized Nash equilibrium seeking: a backward-reflected-forward-backward-based algorithm [J]. Journal of the Franklin Institute, 2024, 361(1): 150-163.
[20] Ran L, Li H Q, Zheng L F, et al. Distributed generalized Nash equilibria computation of noncooperative games via novel primal-dual splitting algorithms [J]. IEEE Transactions on Signal and Information Processing over Networks, 2024, 10: 179-194.
[21] Belgioioso G, Grammatico S. Semi-decentralized generalized Nash equilibrium seeking in monotone aggregative games [J]. IEEE Transactions on Automatic Control, 2021, 68(1): 140-155.
[22] Shi L Y, He W L. Generalized Nash equilibrium seeking for networked noncooperative games with a dynamic event-triggered mechanism [J]. Applied Mathematical Modelling, 2023, 118: 39-52.
[23] Wang M X, Chen J N, Wen C Y, et al. Adaptive generalized Nash equilibrium seeking algorithm for nonsmooth aggregative game under dynamic event-triggered mechanism [J]. Automatica, 2024, 169: 111835.
[24] Li H Q, Li J, Ran L, et al. A survey of distributed algorithms for aggregative games [J]. IEEE/CAA Journal of Automatica Sinica, 2025, 12(5): 859-871.
[25] Bauschke H H, Combettes P L. Convex analysis and monotone operator theory in Hilbert spaces [M]. New York: Springer, 2011.
[26] Paccagnan D, Gentile B, Parise F, et al. Distributed computation of generalized Nash equilibria in quadratic aggregative games with affine coupling constraints [C]//2016 IEEE 55th Conference on Decision and Control, 2016: 6123-6128.
[27] Belgioioso G, Grammatico S. Projected-gradient algorithms for generalized equilibrium seeking in aggregative games are preconditioned forward-backward methods [C]//2018 European Control Conference, 2018: 2188-2193.
[28] Facchinei F, Pang J S. Finite-dimensional variational inequalities and complementarity problems [M]. New York: Springer, 2003.
[29] Bianchi M, Grammatico S. A continuous-time distributed generalized Nash equilibrium seeking algorithm over networks for double-integrator agents [C]//2020 European Control Conference, 2020: 1474-1479.
[30] Lions P L, Mercier B. Splitting algorithms for the sum of two nonlinear operators [J]. SIAM Journal on Numerical Analysis, 1979, 16(6): 964-979.
[31] Bell H E. Gershgorin’s theorem and the zeros of polynomials [J]. The American Mathematical Monthly, 1965, 72(3): 292-295.
[32] Robbins H, Siegmund D. A convergence theorem for non-negative almost supermartingales and some applications [M]//Rustagi J S. (ed.) Optimizing Methods in Statistics, New York: Academic Press, 1971: 233-257.
[33] Salehisadaghiani F, Pavel L. Distributed Nash equilibrium seeking via the alternating direction method of multipliers [J]. IFAC-PapersOnLine, 2017, 50(1): 6166-6171.
[34] Facchinei F, Pang J S. Nash equilibria: The variational approach [M]//Palomar D P, Eldar Y C. (eds.) Convex optimization in signal processing and communications, Cambridge: Cambridge University Press, 2010: 443-493.
[35] Schneeweiss C. Distributed decision making [M]. Berlin: Springer, 2012.
北大中文核心期刊