Distributed GNE seeking under partial-decision information over networks via a doubly-augmented operator splitting approach

Lacra Pavel

Source-linked AI summary

Distributed GNE seeking under partial-decision information over networks via a doubly-augmented operator splitting approach

Lacra Pavel

arXiv:1808.04465v1Aug 13, 2018math.OCcs.GTeess.SY

TL;DR

The paper addresses distributed GNE computation when players have only partial access to opponents’ decisions over networks without global information. It introduces doubly augmented primal-dual operator splitting with local estimates and multipliers, and proves convergence to a variational GNE with fixed step-sizes over connected graphs.

Problem
Existing distributed GNE computation generally assumes full-decision information, although networked agents may only exchange decisions with neighbours.
Method
The paper lifts the problem into a doubly augmented space, distributes primal decision estimates and dual multipliers, and applies forward-backward splitting to monotone operators.
Results
The algorithm converges with fixed step-sizes to a variational GNE over any connected graph.
Takeaways & Limitations
The approach provides a fully distributed primal-dual method for variational GNE seeking under partial-decision information and arbitrary connected network topology.

Abstract

from arXiv · show

We consider distributed computation of generalized Nash equilibrium (GNE) over networks, in games with shared coupling constraints. Existing methods require that each player has full access to opponents' decisions. In this paper, we assume that players have only partial-decision information, and can communicate with their neighbours over an arbitrary undirected graph. We recast the problem as that of finding a zero of a sum of monotone operators through primal-dual analysis. To distribute the problem, we doubly augment variables, so that each player has local decision estimates and local copies of Lagrangian multipliers. We introduce a single-layer algorithm, fully distributed with respect to both primal and dual variables. We show its convergence to a variational GNE with fixed step-sizes, by reformulating it as a forward-backward iteration for a pair of doubly-augmented monotone operators.

I. INTRODUCTION

The introduction motivates distributed GNE computation when agents lack global decision information and presents a fully distributed operator-splitting approach for arbitrary network topologies.

Research gap: Existing distributed GNE results primarily assume full-decision information, whereas many networked applications provide only neighbours’ decisions.Partial-decision settings arise in peer-to-peer and other networks without a central node supplying global information.
Contributions: The paper proposes a fully distributed GNE algorithm for generally coupled costs and affine coupling constraints over arbitrary network topologies.The stated contribution addresses both the information constraint and the absence of a required central coordinator.
Contributions: The approach reformulates primal-dual KKT conditions as zeros of a sum of monotone operators and uses the graph Laplacian to distribute computation.The Laplacian is used to enforce consensus among local decision estimates and local multipliers.
Contributions: Agents estimate opponents’ decisions locally and distribute both primal and dual variables rather than relying on perfect opponent information.This introduces nonlinear coupling between estimates and agent dynamics compared with perfect-information methods.

III. GAME FORMULATION

The game formulation models players with private feasible sets and globally shared affine coupling constraints, then characterizes variational GNE through variational inequalities and KKT conditions.

Game model: Each player chooses a local decision xi to optimize a cost coupled to the other players’ decisions over a private feasible set.The joint feasible region additionally imposes globally shared affine coupling constraints.
Game model: A GNE is a decision profile in which each player’s decision solves its constrained optimization problem given the other players’ decisions.The feasible set for player i depends on the decisions of the other players.
Assumptions: Under differentiability, convexity, compact private feasible sets, and Slater’s condition, the game satisfies the paper’s existence assumptions.These conditions are collected in Assumption 1.
Variational GNE: A variational GNE has common Lagrangian multipliers across agents and is characterized through the variational inequality and corresponding KKT conditions.The common multipliers have the economic interpretation of no price discrimination.
Variational GNE: Under the stated assumptions, every solution of the variational inequality is a GNE, and a solution with common multipliers is a variational GNE.The paper therefore targets variational GNE through its primal-dual characterization.

A. Iterative Algorithm under Full-Decision Information

Under full-decision information, the paper presents a semi-decentralized primal-dual projected-gradient method and interprets it as a forward-backward splitting iteration.

Assumptions: Strong monotonicity and Lipschitz continuity of the pseudo-gradient imply a unique variational GNE under the game assumptions.The uniqueness result supports fixed-step convergence analysis for projected-gradient-type methods.
Algorithm: The full-information algorithm uses fixed primal and dual step-sizes, while a coordinator handles the shared dual variable.Because the dual variable is centrally handled, the method is semi-decentralized.
Operator splitting: The algorithm is a forward-backward iteration for finding zeros of a sum of monotone operators obtained from the KKT conditions.The operator decomposition separates a maximally monotone component from a cocoercive component under the assumptions.
Convergence: Convergence follows for sufficient fixed-step conditions ensuring the metric matrix Φ is positive definite.The splitting choice determines the required monotonicity and cocoercivity conditions.

IV. DISTRIBUTED ALGORITHM UNDER PARTIAL-DECISION INFORMATION

The paper develops a distributed algorithm for variational GNE seeking when agents have only neighbour-based decision information. It combines local primal estimates, local dual copies, auxiliary coordination variables, and operator splitting to obtain a fully distributed iteration.

Algorithm variables: Agents communicate over an undirected connected graph and maintain local estimates of other players’ decisions rather than full decision information.Each agent’s estimate includes its own decision and estimates of others; steady state requires agreement across agents.
Operator formulation: The KKT conditions are lifted to a doubly augmented space, where zeros of two augmented monotone operators lie on the consensus subspace and encode a variational GNE.The augmented variables introduce local copies of primal and dual quantities while retaining the original equilibrium in consensus coordinates.
Algorithm variables: The algorithm assigns each agent a local decision, multiplier copy, and auxiliary variable for coupling-constraint coordination and dual consensus.The auxiliary variable z_i supports coordination needed to satisfy the shared constraint and align local multipliers.
Operator splitting: Any limit point of the algorithm is a zero of the augmented operator sum and a fixed point of the corresponding forward-backward composition.This operator characterization supplies the basis for the convergence analysis and links the iteration to the target equilibrium.
Operator splitting: Algorithm 1 is equivalent to a forward-backward iteration that alternates a forward operator step with a backward resolvent step under a preconditioning metric.The non-identity metric makes the resolvent distributively evaluable through projection, matrix multiplication, and local communication.
Distributed structure: Primal and dual consensus are enforced over the graph through Laplacian-based coordination, making the method distributed in both primal and dual variables.The globally shared affine constraint is not known by any individual agent, so local multiplier copies and coordination are required.

V. CONVERGENCE ANALYSIS

The analysis shows that zeros of the doubly-augmented operator sum lie in consensus and solve the variational inequality, while the forward-backward iteration converges under stated assumptions and fixed step-sizes.

Characterization of zeros: Any zero of A+B lies in the primal and multiplier consensus subspaces and corresponds to a variational GNE.The primal and dual variables take consensus forms, and the resulting variables satisfy the KKT conditions and VI characterization.
Operator-splitting convergence: Algorithm 1 is reformulated as a forward-backward fixed-point iteration for Φ^-1A+Φ^-1B.The proof uses the equivalent iteration ϖ_k+1 = T2◦T1ϖ_k.
Operator properties: Under Assumptions 1–4, A is maximally monotone and B is restricted cocoercive when c exceeds cmin.These operator properties provide the basis for the nonexpansiveness arguments used in the convergence proof.
Step-size conditions: Appropriate step-sizes make Φ positive definite and enable the induced-norm convergence analysis.For any δ > 0, the specified step-size conditions yield Φ ≻ 0 and Φ − δI ⪰ 0.
Convergence result: With c > cmin and step-sizes satisfying (32), all local decision estimates and multipliers converge to common equilibrium values.Each agent’s estimates converge to the same variational GNE, while local multipliers converge to the common KKT multiplier.

VI. NASH-COURNOT GAME OVER A NETWORK

The section studies a network Nash-Cournot game in which firms compete across markets under capacity constraints while communicating through a local graph rather than centralized information.

Network game: Firms produce a homogeneous commodity and compete across the markets to which they are connected.Each firm selects a production vector subject to its local feasible set and market participation structure.
Shared constraints: The aggregate supply is Ax, and each market imposes a shared capacity constraint Ax ≤ r.The local matrix A records firm-market participation, while r collects market capacities.
Objectives: Each firm minimizes production cost minus revenue determined by market prices and its delivered quantity.The price vector maps total market supply to corresponding market prices.
Communication: In the partial-information setting, firms exchange production decisions locally because they cannot observe all other firms’ actions.This replaces the classical assumption of instantaneous access to x−i.
Communication: The communication network connects firms as nodes, with local exchanges determined by graph edges.The example emphasizes mostly intra-continent communication with limited inter-continent links.

A. Assumptions

The assumptions specialize the network game to strongly convex quadratic production costs and linear inverse-demand prices, yielding a strongly monotone and Lipschitz game mapping.

Cost and price assumptions: Each firm’s production cost is strongly convex and quadratic, with Qi symmetric positive definite.The cost specification provides the curvature needed for the operator assumptions.
Cost and price assumptions: Market prices follow the linear inverse-demand function pk(x) = ¯Pk − χk[Ax]k with ¯Pk, χk > 0.Prices decrease with total commodity supplied to each market.
Game mapping: The game mapping has the affine form F(x) = Qx + h, where Q = Σ + ATΞA.The stacked gradient and price terms are represented compactly through Q and h.
Game mapping: Q ≻ 0 because Σ ≻ 0 and ATΞA ⪰ 0, so F is strongly monotone with µ = smin(Q) > 0.The same construction establishes the stated regularity assumptions for the algorithm.
Game mapping: F is Lipschitz continuous with constant θ0 = ∥Q∥, and the proof also sets θ = θ0.The bound follows from ∥R∥ = 1 and ∥IN ⊗ Q∥ = ∥Q∥.

B. Numerical results

The numerical study tests the algorithm on a 20-firm, 7-market instance over a sparse communication graph and reports convergence to the reference variational GNE, including with larger step-sizes.

Instance and parameters: 20 firms compete across 7 markets over a communication graph with λ2(L) = 0.102.Firm bounds, market capacities, and model parameters are randomly generated within specified ranges.
Instance and parameters: The generated game mapping has smin(Q) = 1.001 = µ and smax(Q) = 2.09 = θ.The lower bound for c from Lemma 3 is 62.5, while the main run uses c = 100.
Main simulation: With c = 100 and fixed step-sizes satisfying condition (32), primal and dual variables are exchanged over the sparse graph.The resulting local-decision and dual-variable trajectories are shown in Figures 3 and 4.
Main simulation: The algorithm converges to the same GNE found by, with a comparable convergence rate despite estimating opponents’ decisions.This contrasts with, which assumes perfect opponents’ decision information.
Parameter comparison: With c = 10 and step-sizes increased tenfold while still satisfying (32), the simulation indicates fast convergence.The comparison uses the same initial conditions and is illustrated in Figure 5.

VII. CONCLUSIONS

The paper proposes a fully distributed primal-dual method for variational GNE computation under partial-decision information and proves fixed-step convergence over connected graphs.

Contributions: The proposed algorithm computes a variational GNE for games with globally shared affine coupling constraints under partial-decision information.Both primal and dual variables are distributed rather than coordinated centrally.
Method: The method is motivated by forward-backward splitting for zeros of a sum of doubly-augmented monotone operators.The operator formulation supports the distributed primal-dual design.
Guarantee: Convergence is proved with fixed step-sizes over any connected communication graph.The analysis leverages monotone operator-splitting techniques.
Future work: Future work will consider mechanism designs that encourage players to faithfully report their variables.

APPENDIX

The appendix establishes equivalence between the distributed algorithm’s block updates and a forward-backward operator iteration. It then verifies monotonicity, cocoercivity, and fixed-point properties supporting the convergence analysis.

Algorithm equivalence: The x-, z-, and λ-updates in Algorithm 1 are shown equivalent to the block relations and the compact iteration in (23).The equivalence uses the diagonal step-size identities and the relations among R, S, and the augmented variables.
Consensus analysis: The consensus-space decomposition separates estimate-consensus and orthogonal components, enabling strong-monotonicity bounds involving L_x.The orthogonal component is controlled through the positive second singular value of the graph Laplacian.
Operator properties: The operator A is maximally monotone because it combines normal-cone operators with a maximally monotone skew-symmetric component.Full row rank of R preserves maximal monotonicity under composition, while direct-sum and domain arguments complete the proof.
Cocoercivity: L_λ is cocoercive because it is the gradient of a convex quadratic, with cocoercivity bounded below by 1/(2d*).This property is combined with the bounds for the other operator terms in the restricted cocoercivity analysis.