PaperlayerView exact revision on arXiv

Source-linked AI summary

A Passivity-Based Approach to Nash Equilibrium Seeking over Networks

Dian Gadjov, Lacra Pavel

arXiv:1705.02424v1math.OC

TL;DR

The paper studies distributed Nash equilibrium seeking when players have limited local information rather than instantaneous all-to-all communication. It introduces a passivity-based augmented gradient-play dynamics with neighbour-driven estimates and correction, formulated as a multi-agent coordination problem. Under strict monotonicity of the pseudo-gradient, the dynamics converges to consensus on the game’s Nash equilibrium, while the analysis exposes tradeoffs between game properties and communication-graph connectivity.

  • Problem

    The problem is to seek a Nash equilibrium in general N-player games when players cannot observe all other players’ actions and communicate only with neighbours.

  • Method

    The paper reformulates networked Nash equilibrium seeking as multi-agent coordination and uses incremental passivity with distributed Laplacian feedback, auxiliary estimates, and an action correction term.

  • Results

    Under strict monotonicity of the pseudo-gradient, the augmented gradient-play dynamics converges to consensus on the Nash equilibrium over a connected graph.

  • Takeaways & Limitations

    The analysis shows that Laplacian feedback and estimate time-scale design can balance game coupling against communication-graph connectivity requirements.

Abstract

from arXiv · show

In this paper we consider the problem of distributed Nash equilibrium (NE) seeking over networks, a setting in which players have limited local information. We start from a continuous-time gradient-play dynamics that converges to an NE under strict monotonicity of the pseudo-gradient and assumes perfect information, i.e., instantaneous all-to-all player communication. We consider how to modify this gradient-play dynamics in the case of partial, or networked information between players. We propose an augmented gradient-play dynamics with correction in which players communicate locally only with their neighbours to compute an estimate of the other players' actions. We derive the new dynamics based on the reformulation as a multi-agent coordination problem over an undirected graph. We exploit incremental passivity properties and show that a synchronizing, distributed Laplacian feedback can be designed using relative estimates of the neighbours. Under a strict monotonicity property of the pseudo-gradient, we show that the augmented gradient-play dynamics converges to consensus on the NE of the game. We further discuss two cases that highlight the tradeoff between properties of the game and the communication graph.

I. INTRODUCTION

The paper addresses distributed Nash equilibrium seeking when players have only local network information. It develops a passivity-based augmented gradient-play dynamics with estimation and correction that converges to consensus on the Nash equilibrium under suitable monotonicity and graph conditions.

  • Motivation: The problem concerns distributed Nash equilibrium seeking for general N-player games when players have limited local information over communication networks.The paper situates this setting in applications including wireless and optical networks, distributed optimization, and flow control.
  • Approach: The proposed continuous-time dynamics reformulates the problem as multi-agent coordination and equips each player with estimates of the other players’ actions.Each player combines gradient-type action dynamics with auxiliary estimate dynamics driven by relative feedback from neighbours.
  • Approach: The augmented gradient-play dynamics with correction and estimation combines a gradient action component with a consensus component for synchronizing estimates.The correction term is described as critical for convergence on a single timescale.
  • Results: Under strict monotonicity of the extended pseudo-gradient, the proposed dynamics converges to consensus on the Nash equilibrium over a connected graph.The paper also studies weaker Lipschitz assumptions, sufficiently connected graphs, and time-scale separation to relax connectivity requirements.
  • Motivation: Existing networked Nash equilibrium results are mostly discrete-time or rely on special game structures such as aggregative, potential, or zero-sum formulations.The paper contrasts these restrictions with its general N-player game setting.
  • Results: The analysis highlights a tradeoff between game coupling and communication-graph connectivity, with Laplacian feedback compensating for insufficient passivity in game-dependent terms.A faster estimate-consensus timescale can relax the graph connectivity bound, but introduces a global parameter.

C. Equilibrium Independent and Incremental Passivity

This section connects passivity and monotonicity while formulating the networked game and its equilibrium conditions. It assumes connected communication and monotone pseudo-gradient properties that support existence, uniqueness, and convergence analysis.

  • Passivity concepts: An equilibrium-independent passive system admits a positive semidefinite storage function satisfying a passivity relation around each equilibrium input.Maximal equilibrium-independent passivity additionally allows a maximally monotone equilibrium input-output map.
  • Passivity concepts: Incremental passivity compares two system trajectories, and for a static map it is equivalent to monotonicity.The paper uses this equivalence to interpret monotonicity properties of pseudo-gradients through passivity.
  • Game and communication model: Players communicate over an undirected graph, and the baseline communication assumption is that this graph is connected.The graph describes information sharing among the N players.
  • Game and communication model: Each player minimizes a cost depending on its own action and possibly all opponents’ actions, so each player controls only part of the full action profile.This strategic coupling distinguishes the game structure from distributed optimization based on full-argument individual optimization.
  • Equilibrium conditions: The stacked pseudo-gradient collects every player’s partial gradient with respect to that player’s own action.A Nash equilibrium satisfies a variational inequality, with projected methods needed for compact action sets.
  • Equilibrium conditions: Strict or strong monotonicity of the pseudo-gradient ensures a unique Nash equilibrium under the stated game assumptions.The strong-monotonicity assumption is paired with Lipschitz continuity in the paper’s convergence analysis.

B. Gradient Dynamics with Perfect information

The paper first analyzes continuous-time gradient dynamics with perfect information, then extends the design to networked communication using auxiliary estimates and passivity. The extended system is incrementally passive under monotonicity assumptions, supporting convergence results for the augmented dynamics.

  • Perfect-information gradient dynamics: Perfect-information gradient play uses each player’s full action profile and can converge to the Nash equilibrium under strict monotonicity of the pseudo-gradient.The dynamics require instantaneous all-to-all information exchange over a complete communication graph.
  • Networked-information problem: The networked-information problem asks how to modify gradient dynamics so players converge to an NE over a connected communication graph.Each player controls only its own action while its cost depends on opponents’ actions, creating challenges absent from distributed optimization.
  • Augmented dynamics: Each player augments its gradient dynamics with an auxiliary state containing estimates of the other players’ actions.The estimates may initially differ, but the design seeks consensus among all players’ estimate vectors.
  • Augmented dynamics: The augmented agents’ dynamics are modeled in stacked form using an extended pseudo-gradient defined on the enlarged action-and-estimate space.The extended pseudo-gradient agrees with the original pseudo-gradient on consensus states.
  • Passivity properties: Under monotonicity of the extended pseudo-gradient, the overall augmented system is incrementally passive, enabling a passivity-based distributed feedback design.A weaker Lipschitz condition is also considered for convergence over sufficiently connected graphs, while locally valid assumptions yield local results.

A. Distributed feedback design

The distributed design reformulates networked NE seeking as a multi-agent agreement problem and applies Laplacian feedback based on relative estimates. The resulting augmented dynamics combine local gradient updates with consensus correction and have equilibria at consensus on the NE.

  • Distributed feedback design: Each player designs its control input from relative output feedback provided by neighboring agents.This makes the feedback distributed over the communication graph.
  • Consensus objective: The overall objective is to drive the estimate vectors to consensus while their common value converges to the Nash equilibrium.The consensus condition is expressed as Lx = 0 for the augmented Laplacian L.
  • Passivity-based design: A Laplacian feedback u = −Lx is selected because the agent dynamics are incrementally passive and the Laplacian is positive semidefinite.The closed-loop system is represented as the feedback interconnection of the agent dynamics and the Laplacian.
  • Individual dynamics: The individual dynamics combine each player’s gradient term with an integrator-type auxiliary dynamics driven by a neighbor-based control signal.The gradient reduces the player’s own cost while the consensus term moves estimates toward neighboring values.
  • Correction and equilibrium: The action dynamics include an extra correction term compared with the gossip-based algorithm, which is instrumental for single-timescale convergence.The equilibrium analysis shows that all estimates agree and equal the Nash equilibrium profile.

V. CONVERGENCE ANALYSIS

The convergence analysis treats a single-timescale design and a faster-estimate two-timescale design. The proofs use incremental passivity and Laplacian properties, or singular perturbation for the faster estimator.

  • Scope: The convergence analysis is conducted for the new individual or overall dynamics over a connected communication graph.The section explicitly considers both the individual player dynamics and the stacked overall system.
  • Single-timescale convergence: The single-timescale analysis proves convergence under two alternative sets of assumptions using incremental passivity and diffusive Laplacian properties.These results are presented in Theorems 1 and 2.
  • Two-timescale convergence: The two-timescale analysis modifies the estimate dynamics to be much faster and proves convergence using singular perturbation.This result is given in Theorem 3 under the stated monotonicity and Lipschitz-related assumptions.

A. Single-Timescale Consensus and Player Optimization

Under strict monotonicity, the augmented continuous-time dynamics converges to consensus on the Nash equilibrium over any connected communication graph. With weaker Lipschitz conditions, convergence requires a connectivity bound that reflects the tradeoff between game coupling and graph connectivity.

  • Single-timescale convergence: Theorem 1 establishes boundedness and asymptotic convergence of the proposed dynamics to consensus on the unique Nash equilibrium over any connected graph.The consensus state is 1_N ⊗ x∗, and the action components converge to x∗.
  • Single-timescale convergence: A quadratic Lyapunov function and LaSalle’s invariance principle certify convergence by forcing both disagreement and equilibrium errors to vanish.The Laplacian term eliminates disagreement, while strict monotonicity identifies the Nash equilibrium within the consensus subspace.
  • Connectivity-dependent convergence: Under a weaker Lipschitz property, convergence is asymptotic when λ2(L) > θ^2/(µ + θ), where λ2(L) measures graph connectivity and θ, µ describe game-related properties.Theorem 2 also gives exponential convergence when λ2(L) > Nθ^2/(µ + θ).
  • Game–graph tradeoff: The Laplacian’s excess passivity can compensate for insufficient passivity in the pseudo-gradient terms, linking communication connectivity to coupling in the game.This is the paper’s central game–graph tradeoff for the single-timescale design.
  • Equivalent representation: The action and estimate dynamics admit an equivalent block representation, but the action path remains coupled because each player’s cost depends on opponents’ actions.This distinguishes the game formulation from distributed optimization settings with additive cost decompositions.

B. Two-Timescale Singular Perturbation Analysis

The paper relaxes the connectivity requirement by accelerating estimate dynamics relative to action dynamics. Singular perturbation analysis shows that sufficiently fast estimates preserve convergence to the Nash equilibrium under weaker graph conditions.

  • Two-timescale design: The estimate dynamics are scaled by 1/ϵ, making estimates fast and actions slow in a singularly perturbed system.The modified dynamics separate the action and estimate components while retaining the same networked-information structure.
  • Stability result: For sufficiently small ϵ, the two-timescale dynamics is exponentially stable at (x∗, S(1N ⊗ x∗)); asymptotic stability also holds over a stated interval of ϵ values.Theorem 3 formalizes this result under the weaker Lipschitz and strong monotonicity assumptions.
  • Reduced system: The reduced system obtained at the quasi-steady state v = 0 is the original gradient dynamics, with equilibrium x∗ at the Nash equilibrium.Under strong monotonicity, this reduced gradient system is exponentially stable.
  • Stability analysis: The boundary-layer system is exponentially stable because SLST is positive definite, while the reduced system is exponentially stable under strong monotonicity.These two stability properties support the singular perturbation argument.
  • Tradeoff: Increasing the estimate gain can relax the required graph connectivity, but ϵ is global, exposing a tradeoff among game coupling, consensus connectivity, and information speed.The modified design therefore exchanges a connectivity requirement for a global timescale parameter.

VI. PROJECTED NE DYNAMICS FOR COMPACT ACTION SETS

For compact action sets, the paper replaces unconstrained gradient dynamics with projected dynamics and analyzes their equilibria and convergence over communication graphs.

  • Equilibrium characterization: Equilibria of the projected perfect-information dynamics coincide with Nash equilibria characterized by the associated variational inequality.This follows from the projection condition and the normal-cone characterization of boundary equilibria.
  • Perfect-information convergence: Under strict monotonicity, projected perfect-information trajectories converge asymptotically to the Nash equilibrium.A Lyapunov function decreases strictly away from the equilibrium.
  • Perfect-information convergence: Under strong monotonicity, the same projected dynamics converge exponentially to the Nash equilibrium.The Lyapunov derivative satisfies a linear decay bound with rate parameter µ > 0.
  • Projected dynamics: Projected dynamics keep action components within the compact set Ω while retaining auxiliary estimate dynamics for networked information.The projection operator is discontinuous at the boundary, so solutions are defined using projected dynamical-system conventions.
  • Networked feedback: The networked projected system uses relative-neighbour feedback through the graph Laplacian to synchronize players’ estimates and actions.The resulting closed loop is formed by applying u(t) = −Lx(t) to the incrementally passive agent dynamics.
  • Networked equilibrium: At equilibrium, all estimate vectors agree and equal the Nash equilibrium, so every player’s action component equals the equilibrium action.The connectedness assumption implies the stacked equilibrium lies in the Laplacian nullspace.
  • Networked convergence: Under strict monotonicity and the stated regularity assumptions, the networked projected dynamics converge asymptotically to consensus on the Nash equilibrium.The convergence is single-timescale and holds for any initial actions in Ω and arbitrary initial estimates.
  • Connectivity trade-off: With weaker monotonicity conditions, convergence depends on a lower bound involving the graph’s algebraic connectivity λ2(L).Theorem 5 requires λ2(L) to exceed thresholds involving θ and µ.

A. Unconstrained Ωand Dynamics

The unconstrained dynamics are tested on quadratic games over random and cycle communication graphs, revealing convergence under global assumptions and connectivity-dependent behavior otherwise.

  • Example 1: In the 20-firm quadratic game, the proposed dynamics converge over both a randomly generated graph and a cycle graph.The assumptions ensure convergence even over a minimally connected graph.
  • Example 2: In the 8-player game, convergence occurs over a sufficiently connected random graph but not over a cycle graph.The global passivity assumption fails, so the theorem applies only locally and depends on λ2(L).

B. Compact Ωand Projected Dynamics

Projected simulations show convergence for compact action sets under global assumptions, while weaker conditions make convergence depend on communication connectivity and estimate scaling.

  • Example 1: For 20 firms with Ωi = [0, 200], projected dynamics converge over both random and cycle graphs.The assumptions support convergence even over a minimally connected graph.
  • Example 2: For the 8-player compact-action game, projected dynamics converge over a sufficiently connected random graph when global passivity fails.The result follows from the local assumptions and the connectivity-dependent theorem.
  • Example 2: A higher 1/ϵ for the estimates can balance insufficient communication connectivity in the compact-action example.This is reported as a trade-off between estimate scaling and graph connectivity.
  • Example 3: For a 20-player game whose Nash equilibrium lies on the action-set boundary, projected dynamics converge over both random and cycle graphs.The simulations use Ωi = [0, 200] and compare the two graph structures.

VIII. CONCLUSION

The paper develops a continuous-time distributed Nash-seeking dynamics with local neighbour communication and estimation. Passivity-based Laplacian feedback yields consensus on the Nash equilibrium under strict pseudo-gradient monotonicity, while examples expose game–connectivity trade-offs.

  • Conclusion: The proposed augmented gradient-play dynamics lets players estimate other actions using communication only with their neighbours.The design targets distributed Nash equilibrium seeking over networks in continuous time.
  • Conclusion: The dynamics arise from a multi-agent coordination reformulation and use incremental passivity with distributed Laplacian feedback based on relative estimates.The feedback synchronizes the agents over the communication graph.
  • Conclusion: Under strict pseudo-gradient monotonicity, the new dynamics converge to the game’s Nash equilibrium.The paper also discusses trade-offs between game properties and communication-graph properties.
Loading 1705.02424v1…