基于Peaceman-Rachford分裂的广义纳什均衡问题的分布式算法

doi:10.15960/j.cnki.issn.1007-6093.2026.03.005

Abstract

Abstract: 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.

Key words: generalized Nash equilibrium problem, Peaceman-Rachford splitting method, inertial, convergence analysis

CLC Number:

O221.2

JIN Zhushi, GAN Tao, XU Lingling. Distributed algorithms for generalized Nash equilibrium problems based on Peaceman-Rachford splitting[J]. Operations Research Transactions, 2026, 30(3): 73-98.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2026.03.005

https://www.ort.shu.edu.cn/EN/Y2026/V30/I3/73

[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.

Distributed algorithms for generalized Nash equilibrium problems based on Peaceman-Rachford splitting

PDF

Knowledge

Abstract

Cite this article

share this article

Related Articles 6

Recommended Articles

Metrics

Comments

[1]	JIA Zehui, LI Dandan, XIAO Yujiao, YUE Suyun. A variance-reduced federated symmetric alternating direction method of multipliers [J]. Operations Research Transactions, 2026, 30(3): 116-132.
[2]	WANG Qingyang, YUAN Zihang, YANG Jiawen, KONG Xiangyu, CHEN Caihua. On the convergence of the alternating direction method of multipliers for non-convex optimization [J]. Operations Research Transactions, 2026, 30(3): 99-115.
[3]	Xihong YAN, Xiaoni TANG. An inertial alternating direction method of multiplier for low rank matrix completion [J]. Operations Research Transactions, 2025, 29(1): 172-184.
[4]	Minglu YE, Ming HUANG. An inertial projection algorithm for nonmonotone continuous variational inequalities [J]. Operations Research Transactions, 2024, 28(2): 81-92.
[5]	DANG Yazheng, XUE Zhonghui. Parallel approximate subgradient projection algorithm for convex feasibility problem [J]. Operations Research Transactions, 2015, 19(1): 117-124.
[6]	QIAN Xiao-Yan, SHI Qing-Sheng, LIU Hao, SHI Kui-Ran. A class of limited memory BFGS-type algorithms for large-scale unconstrainedoptimization [J]. Operations Research Transactions, 2011, 15(3): 9-18.