PaperlayerView exact revision on arXiv

Source-linked AI summary

Input-to-State Stability Framework for Fully Distributed Primal-Dual Dynamics for Quadratic GNEPs Without Multiplier Consensus

Shao-An Yin

arXiv:2609.06983v2math.OCcs.AIcs.GTcs.LGcs.MA

TL;DR

GNEPs couple agents’ feasible sets through shared constraints, while distributed methods often exchange multipliers and target variational GNEs. This paper proposes fully distributed continuous-time primal–dual dynamics for quadratic GNEPs without multiplier sharing. It establishes convergence under sufficient conditions, with different initializations potentially leading to different GNEs, including non-variational ones.

Abstract

from arXiv · show

Generalized Nash Equilibrium Problems (GNEPs) often arise in multi-agent engineering applications that require distributed algorithms. Unlike traditional approaches that enforce consensus on multipliers, our method removes the need to share multipliers, reducing communication and improving privacy. As a result, different initializations can lead to different GNEs, including non-variational ones. We establish convergence under sufficient conditions using an input-to-state stability (ISS) framework.

I. INTRODUCTION

GNEPs model agents whose feasible sets are coupled by shared constraints, motivating distributed methods for large-scale or privacy-sensitive applications. This work avoids multiplier exchange and targets convergence to a broader set of GNEs, including non-variational equilibria, under sufficient conditions.

I. INTRODUCTION

  • GNEPs arise when agents’ feasible sets depend on shared constraints, including road capacity in traffic routing and shared capacity in resource allocation and power systems.These applications motivate scalable distributed solution methods when information is distributed or privacy-sensitive.Source: §I · p. 1
  • The method avoids multiplier exchange and can converge to non-variational GNEs, with the equilibrium depending on initialization.The paper also reports convergence of its fully distributed algorithm on a robot sensing problem.Source: §I · p. 1

A. Literature Review

  • Many distributed methods target v-GNEs and rely on multiplier consensus, while this work targets a broader class of GNEs.The paper says this extension covers linear inequalities, where the induced primal–dual dynamics need not be monotone and the solution set may be disconnected.Source: A. Literature Review · p. 1
  • The analysis uses bounded-input bounded-output and bounded-trajectory arguments to establish convergence under sufficient conditions despite nonmonotone dynamics and potentially disconnected solution sets.The work extends a preliminary version with shared equality and convex local constraints to linear inequalities.Source: A. Literature Review · p. 1

A. Notation

The notation section specifies vector and matrix conventions, including transpose, inner product, element-wise comparison, and the largest singular value.

A. Notation

  • Boldface 1 and 0 denote all-ones and all-zeros vectors of appropriate dimensions.The transpose is denoted by a⊤, and a⊤b denotes the inner product.Source: A. Notation · p. 1
  • The relation a ≤ b denotes an element-wise comparison, and ¯σ(A) denotes the largest singular value of A.The projection operator is introduced following,.Source: A. Notation · p. 1
  • The notation [a_i]+ denotes the i-th component of a vector whose components are projected onto the nonnegative values.The supplied projection passages give the componentwise cases for this operator.Source: A. Notation · p. 1

B. Problem Formulation

The problem formulation considers agents with quadratic costs and coupled feasible sets, including shared linear constraints that agents sense only in part. It assumes strong monotonicity and states an existence result for a nonempty feasible set.

B. Problem Formulation

  • Each agent’s cost is quadratic and may depend on its own decision variables as well as those of other agents.The problem formulation defines each agent’s cost function over the stacked decision vector.Source: B. Problem Formulation · p. 1
  • The agents are jointly constrained by a global constraint set, but each agent senses only a relevant subset that may overlap with other agents’ subsets.A sensed constraint may depend on multiple agents’ decisions; a local constraint is the special case depending only on the sensing agent’s decision.Source: B. Problem Formulation · p. 2
  • The global constraints are linear, with each row representing a constraint and agents sensing the rows relevant to them.The matrix A has size p × n and b has size p.Source: B. Problem Formulation · p. 2
  • Under strong monotonicity and a nonempty feasible set, at least one GNE is guaranteed, even though the equilibrium set may be disconnected.Source: B. Problem Formulation · p. 2

C. Generalized Nash Equilibrium and KKT Conditions

The section relates GNEs to KKT conditions under convexity and LICQ, and contrasts multiplier-consensus methods targeting v-GNEs with the proposed method’s ability to converge to a general GNE.

C. Generalized Nash Equilibrium and KKT Conditions

D. Projected Dynamical System

The section introduces projected dynamical systems by projecting a vector at a point in a closed convex set. Under the stated Lipschitz and polyhedral-set conditions, trajectories are unique and defined for all nonnegative time.

D. Projected Dynamical System

  • A projected dynamical system is an ordinary differential equation defined using a vector projected at a point in a closed convex set.The definition introduces x in the set and a vector v, then defines its projection with respect to that set.Source: D. Projected Dynamical System · p. 2
  • For a Lipschitz vector field on a closed convex polyhedron, every initial point in the set has a unique trajectory defined for all t ≥ 0.This domain allows asymptotic analysis as t → ∞.Source: D. Projected Dynamical System · p. 3

III. A FULLY DISTRIBUTED ALGORITHM

The proposed fully distributed algorithm avoids multiplier consensus and keeps agents’ costs, multipliers, and constraints private while communicating decision variables. Under the stated communication model, its per-iteration communication cost is one-third that of consensus-based methods.

III. A FULLY DISTRIBUTED ALGORITHM

  • Algorithm 1 updates each agent’s decision vector using the gradient of its Lagrangian and its multiplier using the positive part of its shared-constraint value.The initial decision vector and nonnegative multiplier are inputs.Source: §III · p. 3
  • The method exchanges only decision variables, keeping each agent’s cost function, multipliers, and constraints private.Decision variables are communicated over the cost-function and shared-constraint connectivity graphs; the worst case may require sharing them with all other agents.Source: §III · p. 3
  • Under Gf = Gg, the method communicates |Ef|d entries per iteration versus 3|Ef|d for consensus-based methods, reducing cost to one-third.The comparison counts decision, multiplier, and auxiliary-variable exchange for consensus-based methods.Source: §III · p. 3
  • The trajectories are well-defined for all time, and every equilibrium corresponds to a KKT point of the game.Lemma 1 identifies Algorithm 1 as implementing the projected dynamical system formed by stacking all agents’ dynamics.Source: §III · p. 3

A. Convergence of the Difference Vector

The section studies differences among agents’ copies of shared-constraint multipliers. Identical initialization preserves consensus and yields convergence to a variational GNE, while difference-vector limits can depend on initialization.

A. Convergence of the Difference Vector

  • For a reference agent under a shared constraint, the multiplier difference is nonincreasing and nonnegative.The section describes the difference from the reference state and its evolution.Source: A. Convergence of the Difference Vector · p. 3
  • When all copies of each shared-constraint multiplier start identically, the system converges to an equilibrium that is a v-GNE.In this case, the difference vector remains zero and the dynamics reduce to projected primal–dual dynamics with consensus multipliers.Source: A. Convergence of the Difference Vector · p. 3
  • With strong monotonicity of F and full row rank of A, the dynamics converge to a unique equilibrium corresponding to the v-GNE.The argument uses a nonincreasing Lyapunov function and LaSalle’s invariance principle.Source: A. Convergence of the Difference Vector · p. 3
  • The difference vector converges to a limit that depends on the initial condition, and any component that reaches zero remains zero.Each component is nonincreasing and nonnegative.Source: A. Convergence of the Difference Vector · p. 3

B. Input-to-State Stability with Respect to Active KKT Points

The analysis treats the changing shift as an external input and establishes an ISS-type error bound around active KKT points. It then proves convergence to the GNE associated with the initialization-dependent limiting shift when that shift is admissible.

B. Input-to-State Stability with Respect to Active KKT Points

  • The proof considers only shifts for which an active-constraint KKT point exists, and not every nonnegative shift necessarily has one.Assumption 3 requires at least one such admissible shift.Source: B. Input-to-State Stability with… · p. 4
  • The analysis defines the input as the difference between the time-varying shift and a fixed shift, and measures error from an associated active KKT point.The bound applies relative to any point satisfying the stated KKT conditions, rather than a uniquely specified reference solution.Source: B. Input-to-State Stability with… · p. 4
  • The error system satisfies an ISS-type estimate with exponential decay and an input term, with constants independent of the chosen active-KKT shift.The estimate applies under Assumptions 1–3 and to bounded inputs.Source: B. Input-to-State Stability with… · pp. 4–5
  • When the limiting shift belongs to Dact, the trajectory converges to the GNE associated with that shift.The theorem assumes Assumption 3; outside Dact, it does not establish convergence to a GNE, although the boundedness result remains valid.Source: B. Input-to-State Stability with… · p. 5

IV. SIMULATION

The simulation applies Algorithm 1 to a multi-agent sensing-placement problem with grouped agents constrained by half-planes. Results from five initializations show convergence to different GNEs.

IV. SIMULATION

  • Each agent’s sensing-placement cost depends on its position relative to its target and its proximity to other agents.The decision variable for agent v is its position z_v in R^2.Source: §IV · p. 5
  • Algorithm 1 converges to different GNEs from five initializations, illustrating nonuniqueness in the sensing-placement problem.The simulation assigns ten targets to agents in three categories, with each group center constrained to remain within a half-plane.Source: §IV · p. 6, Figure 1 · p. 6
  • The figure marks group half-planes with colored regions, trajectories from different starts with dotted lines, and equilibria with circles and crosses.Circles identify converged GNEs; crosses indicate distinct GNE solutions from various starts.Source: Figure 1 · p. 6

V. CONCLUSION

The paper proposes a continuous-time algorithm for quadratic GNEPs that avoids sharing Lagrange multipliers. Its convergence result is sufficient-condition based, and extending the analysis beyond that condition and to general convex costs remains future work.

V. CONCLUSION

  • The proposed continuous-time algorithm for quadratic GNEPs avoids sharing Lagrange multipliers.The stated convergence guarantee requires the limiting shift to belong to Dact.Source: §V · p. 6
  • The convergence analysis is established under the sufficient condition that the limiting shift belongs to Dact.The paper reports empirical convergence even when this condition is not satisfied.Source: §V · p. 6
  • Removing that sufficient condition from the theoretical analysis and extending the framework to general convex costs are left for future work.Source: §V · p. 6
Loading 2609.06983v2…