PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Nash Equilibrium Seeking by A Consensus Based Approach

Maojiao Ye, Guoqiang Hu

arXiv:1602.00771v3math.OC

TL;DR

The paper addresses Nash equilibrium seeking when players cannot directly observe non-neighbors’ actions. It combines leader-following consensus with gradient play, proving local and non-local results for non-quadratic games and global exponential stability for quadratic games under stated conditions.

  • Problem

    The paper studies Nash equilibrium seeking when players lack direct access to non-neighbors’ actions and must rely on local communication.

  • Method

    The strategy combines leader-following consensus with gradient play while players maintain estimates of the players’ actions.

  • Results

    The analysis establishes local convergence for non-quadratic games, stronger non-local convergence under stronger conditions, and global exponential stability for quadratic games under certain conditions.

  • Takeaways & Limitations

    Neighbor communication can support distributed Nash equilibrium seeking for the game classes and conditions analyzed in the paper.

Abstract

from arXiv · show

In this paper, Nash equilibrium seeking among a network of players is considered. Different from many existing works on Nash equilibrium seeking in non-cooperative games, the players considered in this paper cannot directly observe the actions of the players who are not their neighbors. Instead, the players are supposed to be capable of communicating with each other via an undirected and connected communication graph. By a synthesis of a leader-following consensus protocol and the gradient play, a distributed Nash equilibrium seeking strategy is proposed for the non-cooperative games. Analytical analysis on the convergence of the players' actions to the Nash equilibrium is conducted via Lyapunov stability analysis. For games with non-quadratic payoffs, where multiple isolated Nash equilibria may coexist in the game, a local convergence result is derived under certain conditions. Then, a stronger condition is provided to derive a non-local convergence result for the non-quadratic games. For quadratic games, it is shown that the proposed seeking strategy enables the players' actions to converge to the Nash equilibrium globally under the given conditions. Numerical examples are provided to verify the effectiveness of the proposed seeking strategy.

non-quadratic games.

The section identifies the paper’s core topics: Nash equilibrium, gradient play, leader-following consensus, and neighboring communication.

  • The paper concerns Nash equilibrium.
  • Gradient play is a central approach.
  • Leader-following consensus and neighboring communication frame the distributed setting.

I. INTRODUCTION

The introduction motivates distributed Nash equilibrium seeking when players lack access to non-neighbors’ actions. It proposes combining leader-following consensus with gradient play and establishes convergence results under stated conditions.

  • Full observation of opponents’ actions is often assumed, but full communication is impractical in many engineering systems.
  • The paper addresses Nash equilibrium seeking over a local communication network where players communicate only with neighbors.
  • The proposed strategy combines a leader-following consensus protocol with gradient play.
  • Players communicate estimates of other players’ actions rather than requiring full communication.
  • Lyapunov stability analysis establishes convergence under certain conditions, treating non-quadratic games before quadratic games.

II. PROBLEM FORMULATION

The problem is to design a strategy for players who cannot directly access non-neighbors’ actions to learn an existing Nash equilibrium through an undirected, connected graph.

  • The game has N players with action vector x and payoff function f_i(x) for player i.
  • A player has no direct access to the action of any player who is not its neighbor.
  • The design objective is a Nash equilibrium seeking strategy that players can use to learn the equilibrium.
  • A Nash equilibrium is an action profile where no player can gain more payoff by unilaterally changing its own action.
  • The communication graph is assumed to be undirected and connected, and each payoff function is C2.

III. MAIN RESULTS

The main strategy lets each player estimate all players’ actions and update its own action using gradient play while consensus dynamics propagate information. The analysis considers non-quadratic and quadratic games.

  • The strategy is based on a leader-following consensus protocol and gradient play.
  • Strategy design: Each player maintains an estimate vector y_i of the players’ actions, with y_ij estimating player j’s action.
  • Strategy design: Each player’s action is updated using its estimate of the players’ actions, while estimate dynamics are generated through communication-graph coefficients a_ij.
  • Strategy design: A small positive parameter δ scales the action-update gains and supports the convergence analysis.
  • Insight into the strategy design: At the quasi-steady state, every estimate y_ij equals the corresponding action x_j because the graph is undirected and connected.
  • The gradient-play component can yield convergence to a Nash equilibrium under certain conditions.

A. Games with Non-quadratic Payoffs

For non-quadratic games, the proposed strategy provides local convergence near each qualifying isolated Nash equilibrium, while stronger conditions yield non-local convergence under additional assumptions.

  • Scope: Existence, uniqueness, and isolation of Nash equilibria are outside the paper’s scope; the analysis instead assumes equilibria satisfying stated conditions.The paper refers readers to prior work for those characterizations.
  • Local convergence: Theorem 1 establishes exponential stability near each isolated Nash equilibrium satisfying Assumptions 3–4, for sufficiently small δ.The result follows for agents using updates (3)–(4).
  • Conditions: The analysis assumes the matrix k̄B is Hurwitz, a conservative condition for deriving the convergence result.The paper notes that this assumption is conservative.
  • Non-local convergence: Assumption 5 requires each payoff to be concave in its own action and imposes a stronger condition used to derive exponential stability.This condition also implies uniqueness of the Nash equilibrium.
  • Non-local convergence: Theorem 2 gives exponential convergence to the equilibrium and synchronized estimates within any prescribed bounded initial-error region, under Assumptions 1, 2, and 5.For every positive Δ, a corresponding δ*(Δ) exists such that δ ∈ (0, δ*(Δ)) ensures convergence.
  • Global result: If all payoff derivatives ∂fi/∂xi are globally Lipschitz, Corollary 1 upgrades the result to global exponential stability for sufficiently small δ.The equilibrium and synchronized estimates are globally exponentially stable under the stated assumptions.

B. Quadratic Games

For quadratic games, the proposed strategy has global exponential convergence under strict diagonal dominance, and also under a Hurwitz condition for potential games. The quadratic-game equilibrium is unique and explicitly characterized.

  • Strict diagonal dominance guarantees a unique Nash equilibrium, given by x∗ = −H−1v.The equilibrium exists and is unique under Assumption 6.
  • Under Assumptions 1, 2, and 6, the equilibrium and players’ estimates are globally exponentially stable for sufficiently small δ.The stability claim applies to the updates in (3)-(4).
  • For quadratic potential games, global exponential stability also follows when H is Hurwitz, provided δ is sufficiently small.
  • For general games whose payoffs depend on every player’s action, each player estimates all players’ actions through neighbor communication.Aggregative and interference-graph games may permit reduced estimation or computation, but that adaptation is left for future work.

IV. NUMERICAL EXAMPLES

The numerical section evaluates the strategy on three five-player games sharing a communication graph. The examples include a locally convergent non-quadratic case and cases where simulations verify convergence from distant initial conditions.

  • Three games with five players use the communication graph shown in Fig. 1.
  • Example 1: In Example 1, the equilibrium x = [3 … 12]^T satisfies Theorem 1’s conditions, yielding exponential stability for sufficiently small δ.
  • Example 1: In Example 1, the proposed strategy converges to the Nash equilibrium from initial conditions close to the equilibrium, consistent with Theorem 1’s local result.The actions are plotted in Fig. 2.
  • Example 2: In Example 2, the common payoff function is maximized at x = 0^5, which is also the game’s Nash equilibrium.The passage states that deviations reduce all players’ payoffs.
  • Example 2: In Example 2, the actions converge to the unique Nash equilibrium from initial values far away from equilibrium, verifying Theorem 2 in simulation.The actions are plotted in Fig. 3.

B. A quadratic game

Example 3 applies the strategy to a quadratic game modeling energy consumption for heating, ventilation, and air-conditioning systems. The simulation converges globally to the computed unique equilibrium from distant initial conditions.

  • Example 3 models an energy consumption game for heating, ventilation, and air-conditioning systems.
  • The computed unique Nash equilibrium is x∗ = [2.0147, 6.7766, 11.5385, 16.3004, 21.0623]^T.
  • Strict diagonal dominance of H with negative diagonal elements satisfies Corollary 2’s conditions for global exponential stability.The result holds for sufficiently small δ.
  • Starting all variables at −10, the simulated players’ actions converge to the Nash equilibrium, verifying Corollary 2.The trajectories are plotted in Fig. 4.

V. CONCLUSION

The paper develops distributed Nash equilibrium seeking using neighboring communication, with convergence guarantees that range from local for general games to global exponential stability for quadratic games.

  • The proposed algorithm combines leader-following consensus with gradient play over an undirected, connected communication graph.Players communicate estimates of actions through neighboring links rather than directly observing all opponents.
  • Non-quadratic games admit local convergence under mild conditions and non-local convergence under stronger conditions.
  • Quadratic games have globally exponentially stable Nash equilibria under the proposed strategy and certain conditions.

B. Proof of Theorem 1

Theorem 1 is established by constructing Lyapunov functions for the gradient-play and consensus-error dynamics, then proving exponential decay under sufficiently small δ.

  • The proof first establishes exponential stability of the gradient-play equilibrium by linearizing at x∗ and showing k̄B is Hurwitz.The Hurwitz property follows from strict diagonal dominance and the Gershgorin Circle Theorem.
  • A Lyapunov candidate combines the action error and consensus error using a positive definite matrix P1 satisfying a Lyapunov equation.The matrix Q1 is positive definite because the communication-induced matrix is Hurwitz for an undirected, connected graph.
  • Under the stated Lipschitz bounds and a positive definite B1, the Lyapunov derivative satisfies V̇ ≤ −δλmin(B1)||z||^2.The Comparison Lemma then yields exponential decay of the error.
  • The proof relates the auxiliary error z to the full error Er(t), yielding an exponential bound with constants K1 and K2.
  • The composite Lyapunov function is bounded above and below by constants times ||z||^2, where z stacks the action and consensus errors.
  • For quadratic games, linearity and uniqueness of the Nash equilibrium extend exponential stability from sufficiently small δ to global exponential stability.

F. Proof of Corollary 3

For quadratic potential games, negative definiteness of the Hessian makes the gradient-play linearization exponentially stable, supporting the corollary's convergence result.

  • The Hessian H is symmetric negative definite, and an auxiliary transformation is used to analyze the matrix k̄H.
  • The relation k̄Ψ = Φ^T HΦ < 0 establishes that k̄H is Hurwitz.
  • Because k̄H is Hurwitz, the Nash equilibrium is exponentially stable under the gradient play, after which the Theorem 1 argument applies.
Loading 1602.00771v3…