Source-linked AI summary
A distributed primal-dual algorithm for computation of generalized Nash equilibria with shared affine coupling constraints via operator splitting methods
Peng Yi, Lacra Pavel
TL;DR
The paper addresses distributed computation of variational GNE in network games with interdependent objectives and globally shared affine constraints. It develops a primal-dual forward-backward operator-splitting algorithm using localized data and multiplier communication, proving fixed-step convergence under mild assumptions and analyzing an inertial variant. The main scope boundary is that the considered game has a unique variational-inequality solution, while the GNE itself may not be unique.
Problem
The paper addresses how agents can compute GNE when both objectives and feasible sets are coupled through a globally shared affine constraint without requiring complete game information.
Method
The paper reformulates variational GNE conditions as zeros of a sum of monotone operators and applies a distributed primal-dual forward-backward splitting scheme with local multiplier copies and auxiliary variables.
Results
The proposed distributed algorithms are proved to converge to variational GNE under fixed step-sizes and mild assumptions on objectives and communication graphs.
Takeaways & Limitations
Agents can seek the variational GNE using local data, local affine-constraint blocks, interference observations, and neighboring multiplier communication; an inertial variant may accelerate convergence.
Takeaways & Limitations
The assumptions guarantee a unique solution to the variational inequality, but the game may still have multiple GNE, and computing all GNE remains open.
Abstract
from arXiv · showhide
In this paper, we propose a distributed primal-dual algorithm for computation of a generalized Nash equilibrium (GNE) in noncooperative games over network systems. In the considered game, not only each player's local objective function depends on other players' decisions, but also the feasible decision sets of all the players are coupled together with a globally shared affine inequality constraint. Adopting the variational GNE, that is the solution of a variational inequality, as a refinement of GNE, we introduce a primal-dual algorithm that players can use to seek it in a distributed manner. Each player only needs to know its local objective function, local feasible set, and a local block of the affine constraint. Meanwhile, each player only needs to observe the decisions on which its local objective function explicitly depends through the interference graph and share information related to multipliers with its neighbors through a multiplier graph. Through a primal-dual analysis and an augmentation of variables, we reformulate the problem as finding the zeros of a sum of monotone operators. Our distributed primal-dual algorithm is based on forward-backward operator splitting methods. We prove its convergence to the variational GNE for fixed step-sizes under some mild assumptions. Then a distributed algorithm with inertia is also introduced and analyzed for variational GNE seeking. Finally, numerical simulations for network Cournot competition are given to illustrate the algorithm efficiency and performance.
1. Introduction
The paper motivates distributed computation of variational GNE for network games whose objectives and feasible sets are coupled, and develops an operator-splitting primal-dual approach with fixed-step convergence.
- Motivation: Centralized optimization requires communication with a control center, motivating distributed methods that decompose data, computation, and communication across agents.Distributed optimization also lets agents formulate local objectives without sharing all private data.
- Motivation: Large network decision problems involve local objectives depending on other agents and feasible sets coupled by shared resources.Examples of shared resources include bandwidth, spectrum, and power.
- Problem formulation: GNE models noncooperative decisions with coupled feasible sets, while variational GNE selects an equilibrium with a common shadow price for shared resources.The paper adopts variational GNE because it also has sensitivity and stability properties.
- Method: The proposed algorithm uses local multiplier copies, auxiliary variables, and a graph Laplacian to enforce multiplier consensus among neighboring agents.Its reformulation splits the problem into monotone operators under a suitable metric matrix.
- Method: Each player uses only local objective and feasible-set data, a local affine-constraint block, and information received through separate interference and multiplier graphs.The model is more localized because no player knows the entire shared constraint.
- Results: The operator-splitting analysis proves convergence to variational GNE under fixed step-sizes and mild assumptions, unlike related approaches relying on diminishing step-sizes.The paper also introduces an inertial distributed algorithm for possible acceleration.
2. Notations and preliminary background
This section establishes notation for Euclidean spaces, convex analysis, monotone operators, projections, and communication graphs used in the algorithm and convergence analysis.
- Notation: Vectors, matrices, inner products, norms, componentwise inequalities, block diagonals, Cartesian products, interiors, and boundaries are defined.A symmetric positive definite matrix induces a corresponding inner product and norm.
- Convex analysis: Projection maps a point to a set, and convexity requires every segment between two set points to remain in the set.The section also defines extended-value convex functions.
- Monotone operators: For set-valued operators, the domain, range, graph, inverse, zero set, fixed points, composition, and sum are introduced.These definitions support the later reformulation as a zero-finding problem.
- Monotone operators: Subdifferentials of proper lower-semicontinuous convex functions are maximally monotone, and their resolvents define proximal operators.For closed convex sets, the subdifferential of the indicator is the normal-cone operator.
- Graph theory: An information-sharing graph specifies which agents communicate, with neighbor sets determined by incoming edges.Connectivity means every pair of agents is joined by a graph path.
- Graph theory: For connected undirected graphs, the weighted Laplacian has a simple zero eigenvalue associated with the consensus subspace, while all other eigenvalues are positive.The section also introduces the ordered nonzero eigenvalues and a maximal weighted-degree bound.
3. Problem formulation and distributed algorithm
The paper formulates network games with globally shared affine constraints and targets variational GNEs, then develops a distributed algorithm using local data and sparse communication.
- 3.1. Game formulation: Each player’s objective and feasible set may depend on other players, while a globally shared affine constraint couples all feasible decisions.The constraint may be represented locally through each player’s block A_i, without any agent knowing the complete global constraint.
- 3.1. Game formulation: A GNE is obtained at the intersection of all players’ best-response sets, but GNEs may be nonunique and their multipliers may differ across players.The paper instead seeks equilibria with a common multiplier across agents.
- 3.1. Game formulation: Under differentiable convex objectives, closed convex private sets, and Slater’s condition, the variational inequality formulation provides a tractable equilibrium refinement.Every VI solution is a GNE, and its KKT multiplier satisfies the GNE KKT conditions.
- 3.1. Game formulation: A variational GNE uses the same multiplier for every player and is associated with no price discrimination, stability, and sensitivity properties.It is the equilibrium concept selected by the proposed distributed coordination mechanism.
- 3.1. Game formulation: The formulation assumes the pseudo-gradient is strongly monotone and Lipschitz continuous, ensuring a unique variational GNE even when other GNEs may exist.The stronger goal of computing all GNEs remains an open research topic in the cited discussion.
- 3.2. Distributed algorithm: The distributed algorithm lets each player use local objectives, private feasible sets, and local affine-constraint blocks while protecting data privacy.The global right-hand side can also be decomposed, and no player needs the full shared constraint.
- 3.2. Distributed algorithm: Decision observations follow the interference graph, whereas multiplier information is exchanged over a separate multiplier graph.Sparse edges reduce observation and communication burdens, and the two information flows remain decoupled.
- 3.2. Distributed algorithm: The algorithm converges with fixed step-sizes under mild conditions and supports Gauss-Seidel multiplier updates, while two specified updates can be computed in parallel.These features are presented as key properties of the totally distributed Algorithm 3.5.
4. Algorithm development
The algorithm is derived by augmenting variables and expressing the distributed primal-dual iteration as forward-backward splitting for monotone operators. Its limiting points correspond to variational GNEs with consensus multipliers.
- 4. Algorithm development: Algorithm 3.5 is developed by augmenting local multiplier copies and auxiliary variables to enable distributed computation.The augmented operators extend the centralized formulation and use graph Laplacians to enforce multiplier consensus.
- 4. Algorithm development: The primal update can be written through the resolvent of the normal-cone operator, equivalently as projection onto the private feasible sets.Because the product normal cone decomposes across players, these projections can be computed locally.
- 4. Algorithm development: The metric matrix Φ is symmetric, while the block Laplacian L̄ = L ⊗ I_m represents the multiplier graph.Positive definiteness of Φ and maximal monotonicity of the operators support the splitting interpretation.
- 4. Algorithm development: The compact iteration applies a forward step to one operator and a resolvent-based backward step to another.With T1 := Id − Φ^-1 Ā and T2 := (Id + Φ^-1 B̄)^-1, the update is ϖ^(k+1) = T2 ◦ T1 ϖ^k.
- 4. Algorithm development: Any limiting point of the iteration is a fixed point of T2 ◦ T1 and a zero of the sum of the augmented monotone operators.The equivalence follows from the forward-backward splitting representation and continuity of the iteration map.
- 4. Algorithm development: Every zero of the augmented operator sum yields a solution of VI(F, X), hence a variational GNE, with consensus multiplier copies.Specifically, λ̄* = 1_N ⊗ λ* and (x*, λ*) satisfies the original KKT system.
- 4. Algorithm development: Under Assumptions 1 and 2, the game has a unique variational GNE and the original operator sum has a nonempty zero set.The augmented operator system is then shown to possess a corresponding zero through multiplier consensus and auxiliary variables.
5. Convergence Analysis
The convergence analysis recasts the distributed algorithm as forward-backward splitting for zeros of a sum of monotone operators. Under suitable fixed step-sizes and assumptions, the players’ strategies converge to a variational GNE and their local multipliers agree.
- Operator-splitting formulation: The algorithm is analyzed as forward-backward splitting for finding zeros of a sum of monotone operators.The compact reformulation is also an iterative fixed-point computation.
- Operator properties: The analysis uses cocoercivity, maximal monotonicity, averaged operators, and firmly nonexpansive operators rather than restrictive contractivity assumptions.These properties are established under a matrix-induced norm and suitable step-size conditions.
- Operator properties: Operators ¯A and ¯B are respectively shown to be cocoercive and maximally monotone under Assumptions 1–3.The cocoercivity bound uses β ≤ min{1/(2d∗), η/θ^2}.
- Step-size conditions: Local fixed step-sizes satisfying the stated rules make Φ positive definite and Φ−δI positive semidefinite.Each agent can independently choose τ_i, ν_i, and σ_i using a globally known δ.
- Convergence result: With the prescribed step-sizes, each player’s local strategy converges to its variational GNE component, while all local multipliers converge to a common KKT multiplier.The same convergence statement is established for the distributed algorithm under fixed step-sizes.
6. Distributed algorithm with inertia
The paper adds an inertial distributed algorithm that extrapolates from the two most recent iterates before applying the original update. Its convergence follows under sufficient step-size restrictions, while the analysis motivates potentially improved convergence properties.
- Algorithm design: The inertial algorithm adds a predictive acceleration phase followed by the original distributed update phase.Predictive variables are obtained by simple linear extrapolation using local state information from the last two steps.
- Algorithm design: Compared with the original algorithm, inertia introduces only a simple local computation burden but requires choosing an additional step-size α.The algorithm remains totally distributed and preserves the original information-sharing features.
- Dynamical-systems interpretation: The inertial method is derived as a discretization of a second-order dynamical system with an additional inertial term.The extrapolation relation is ϖ̃_k = ϖ_k + α(ϖ_k − ϖ_{k−1}).
- Dynamical-systems interpretation: The paper expects the inertial algorithm to have better convergence properties than the original method because its underlying second-order system has an inertial term.This is presented as an expectation based on the dynamical-systems interpretation.
- Convergence result: Under Assumptions 1–3 and sufficient choices of α, δ, β, and local step-sizes, strategies converge to the variational GNE and local multipliers reach consensus.The condition includes 2βδ(1 − 3α − ϵ) ≥ (1 − α)^2 with 0 < α < 1.
- Convergence result: The convergence proof establishes boundedness, vanishing successive differences, and convergence of the full iterate sequence to a zero of the operator sum.The limiting point is then linked to the variational GNE through the operator characterization.
7. Network Cournot game and simulation studies
The section formulates network Cournot games with shared market-capacity constraints and presents simulations comparing distributed algorithms, including an inertial variant.
- 7.1. Network Cournot game: Network Cournot games model companies distributing production across markets subject to local production limits and globally shared capacity constraints.Each company’s strategy specifies production in connected markets, while the aggregate decision satisfies Ax ≤ r.
- 7.1. Network Cournot game: Each company’s objective combines local production costs with payments determined by market prices that depend on total supply.With linear inverse demand, the objective is formed from production cost minus revenue.
- 7.1. Network Cournot game: The interference graph connects companies whose objective functions depend on one another, while sparse market participation induces sparse graph connections.Companies are neighbors when they participate in a common market and can observe one another’s relevant decisions.
- 7.2. Simulation studies: Both algorithms converge in the simulations, while the inertial Algorithm 6.1 exhibits superior convergence speed.Figure 4 compares trajectories of successive-iterate differences and auxiliary variables; Figure 5 tracks decision error relative to x∗.
8. Conclusions
The paper proposes and analyzes distributed primal-dual algorithms for variational GNE under shared affine constraints. It proves fixed-step convergence and reports faster convergence for the inertial method, while identifying observation requirements and extensions as open issues.
- 8. Conclusions: The proposed primal-dual algorithm computes variational GNE using local information and operator splitting for zeros of a sum of monotone operators.Each player needs local data, including a block of the affine coupling constraints.
- 8. Conclusions: Convergence is proved for fixed step-sizes under mild assumptions, and a distributed inertial algorithm is analyzed for possible acceleration.The convergence analysis exploits properties of compositions of averaged operators.
- 8. Conclusions: Network Cournot simulations demonstrate the efficiency of both algorithms and superior convergence speed for the inertial algorithm.The numerical conclusion is specific to the reported network Cournot study.
- 8. Conclusions: The current method assumes players can observe all neighboring decisions through the interference graph, although local consensus dynamics are suggested as a relaxation.The conclusion also identifies stochastic observations and weaker monotonicity as directions for future extensions.