Distributed Nash Equilibrium Seeking by A Consensus Based Approach

• Each agent acts as a virtual leader broadcasting its action as a reference; leader-following consensus forms action estimates that feed each player’s gradient play.Source: §I · p. 1
• Unlike, the paper considers Nash equilibrium seeking in a deterministic, continuous-time scenario rather than asynchronous updates.Source: §I · p. 2
• The paper addresses Nash equilibrium seeking when players cannot observe non-neighbors’ actions and full communication is impractical, restricting communication to neighbors.Source: §I · p. 2
• Lyapunov analysis explores convergence to Nash equilibrium under conditions, investigating non-quadratic games before quadratic games.Source: §I · p. 2

II. PROBLEM FORMULATION

• The problem is to design a strategy for N players to learn an existing Nash equilibrium when players lack direct access to non-neighbors’ actions.Each player i has payoff f_i(x) and scalar action x_i.Source: §II · p. 2
• A Nash equilibrium is an action profile at which no player can gain more payoff by unilaterally changing its own action.Source: §II · p. 2
• The formulation assumes players communicate over an undirected, connected graph and each player’s payoff function is C2.Source: §II · p. 2

Strategy design

• Because players cannot observe non-neighbors’ actions directly, the strategy combines leader-following consensus with gradient play and has each player estimate all players’ actions.The gain is set as k_i = δ k̄_i, where δ is small and positive and k̄_i is fixed and positive.Source: §III · pp. 2–3

Insight into the strategy design

• For an undirected, connected communication graph, each player’s estimates of others’ actions have the quasi-steady state y_ij = x_j.The communication protocol uses a_ij, the (i,j) element of the graph’s adjacency matrix.Source: §III · p. 3
• With δ = 0 freezing the estimates at their quasi-steady state, convergence to a Nash equilibrium can be derived under certain conditions, as in and.The analysis considers the slower time scale τ = δt.Source: §III · p. 3

A. Games with Non-quadratic Payoffs

• Under Assumptions 1–4, each qualifying isolated Nash equilibrium is exponentially stable for sufficiently small δ.The allowable δ lies in (0, δ*); the analysis notes that Assumption 4 is conservative because convergence depends on a Hurwitz condition for the gradient play.Source: A. Games with Non-quadratic Payoffs · p. 3
• Assumption 5 makes each payoff concave in its own action and yields a unique equilibrium; for any bounded initial-error radius ∆, sufficiently small δ ensures exponential convergence to it.The allowable bound δ*(∆) depends on ∆, and Assumption 5 is slightly stronger than condition (13) to ensure exponential stability.Source: A. Games with Non-quadratic Payoffs · pp. 3–4
• If the payoff gradients are globally Lipschitz as well as Assumptions 1, 2, and 5 holding, the equilibrium is globally exponentially stable for sufficiently small δ.The convergence applies to all initial states.Source: A. Games with Non-quadratic Payoffs · p. 4

B. Quadratic Games

• Under Assumption 6, the quadratic game has a unique Nash equilibrium x* = -H^-1v,.Here v = [v1_1, v2_2, ..., vN_N]^T.Source: B. Quadratic Games · p. 4
• With Assumptions 1, 2, and 6, updates (3)–(4) make (x*, 1_N ⊗ x*) globally exponentially stable for all sufficiently small positive δ.The result holds for δ in (0, δ*) for some positive constant δ*.Source: B. Quadratic Games · p. 4
• If Assumptions 1–2 hold, H is Hurwitz, and the quadratic game is a potential game, the Nash equilibrium is globally exponentially stable for sufficiently small positive δ.The result applies to updates (3)–(4).Source: B. Quadratic Games · p. 4
• The results also hold with an alternative estimation dynamic when the specified matrix -m(L ⊗ I_N×N + B0) is Hurwitz.The passage defines m = diag{m_ij}, with each m_ij a fixed positive constant.Source: B. Quadratic Games · p. 4
• For aggregative games, dynamic average consensus can estimate the aggregate instead of every action; interference-graph adaptation for subset interactions is left to future work,.The proposed strategy is applicable to games where each payoff depends on the player's own action and all other players' actions.Source: B. Quadratic Games · p. 4

• The examples consider three games with five players using the communication graph shown in Fig. 1.Source: §IV · p. 4, Figure 1 · p. 5

Example 1

• In Example 1, the equilibrium satisfies Theorem 1’s conditions for exponential stability, and the simulated actions converge from initial values near it.The theorem ensures only local convergence; the actions generated by the seeking strategy are plotted in Fig. 2.Source: §IV · p. 5, Figure 2 · p. 5

Example 2

• In Example 2, maximizing the shared function maximizes every player’s payoff, so any deviation from the Nash equilibrium reduces all players’ payoffs.Source: §IV · p. 5
• In Example 2, actions converge to the unique Nash equilibrium even from initial values far from it, consistent with Theorem 2.Assumption 5 holds, and the theorem guarantees convergence for any bounded initial condition when δ ∈ (0, δ*); the simulation initializes all variables at 20.Source: §IV · p. 5, Figure 3 · p. 5

B. A quadratic game

• Starting all variables at −10, the simulated actions converge to the unique Nash equilibrium x*=[2.0147, 6.7766, 11.5385, 16.3004, 21.0623]^T.The trajectories are plotted in Fig. 4.Source: Figure 4 · p. 6, B. A quadratic game · p. 6
• The example can model an energy-consumption game for heating, ventilation, and air-conditioning systems.The passage also refers to references therein.Source: B. A quadratic game · p. 6
• Strict diagonal dominance of H with negative diagonal elements satisfies Corollary 2, yielding global exponential stability for each δ ∈ (0, δ*).The result applies under the given strategy.Source: B. A quadratic game · p. 6

V. CONCLUSION

• The leader-following consensus and gradient-play strategy achieves local convergence under mild conditions and non-local convergence for non-quadratic games under stronger conditions.For quadratic games, the Nash equilibrium is globally exponentially stable under certain conditions.Source: §V · p. 6
• For quadratic games, the proposed strategy makes the Nash equilibrium globally exponentially stable under certain conditions.Source: §V · p. 6
• The study considers Nash equilibrium seeking among players communicating through an undirected and connected graph, using a strategy based on consensus and gradient play.Source: §V · p. 6

A. Basics on Graph Theory

• A graph G = (V, E) is undirected when each edge (i, j) has its reverse (j, i), and connected when every pair of distinct vertices has a path between them.Source: A. Basics on Graph Theory · p. 7
• Node j is a neighbor of agent i when (j, i) ∈ E; adjacency entries aij are 1 for connected nodes and 0 otherwise, with aii = 0.Source: A. Basics on Graph Theory · p. 7
• The graph Laplacian is L = D − A, where D is diagonal with each node’s out degree on its diagonal.Source: A. Basics on Graph Theory · p. 7

B. Proof of Theorem 1

• Linearization at x* shows that k̄B is Hurwitz by Gershgorin’s Circle Theorem [39], yielding exponential stability of the equilibrium.This follows because B is strictly diagonally dominant with negative diagonal entries.Source: B. Proof of Theorem 1 · p. 7
• The Lyapunov Converse Theorem [38] supplies a function W1 on a neighborhood of x* with positive constants bounding its stability properties.The neighborhood is D0 = {x ∈ R^N : ||x − x*|| ≤ r0}.Source: B. Proof of Theorem 1 · p. 7
• The proof constructs a Lyapunov candidate using P1, whose defining matrix equation has a positive definite solution because the communication graph is undirected and connected.The proof uses that −(L ⊗ I_N×N + B0) is Hurwitz.Source: B. Proof of Theorem 1 · p. 7
• When B1 is positive definite, the candidate’s derivative is negative definite, and the Comparison Lemma [38] gives exponential decay of the action and estimation error.The error bound is derived after relating the error norm to the proof’s state variable.Source: B. Proof of Theorem 1 · pp. 7–8

C. Proof of Theorem 2

• For Theorem 2, the Lyapunov derivative estimates hold for states in a compact set, and the remaining argument follows the proof of Theorem 1.The estimates use positive constants and bounds on the gradient terms over that set.Source: C. Proof of Theorem 2 · p. 8

D. Proof of Corollary 1

• For Corollary 1, inequalities (30) and (31) hold for every z, extending the Theorem 2 proof beyond a compact set.The passage attributes this extension to properties of the functions ∂fi(x).Source: D. Proof of Corollary 1 · p. 8

E. Proof of Corollary 2

• Assumption 6 satisfies Theorem 1’s conditions and yields a unique equilibrium; for 0 < δ < δ*, linearity establishes global exponential stability.Source: E. Proof of Corollary 2 · p. 8

F. Proof of Corollary 3

• The proof uses the symmetric negative definiteness of H and an auxiliary system to establish the required Hurwitz property.It shows ¯kΨ = ΦT HΦ < 0 for nonzero Φ, then derives exponential stability for the auxiliary system.Source: F. Proof of Corollary 3 · pp. 8–9
• The Nash equilibrium is exponentially stable under gradient play (19) because ¯kH is Hurwitz.The proof establishes ¯kH is Hurwitz via exponential stability of the equilibria of auxiliary systems (32) and (33).Source: F. Proof of Corollary 3 · p. 9
• For quadratic potential games, the rest of the proof follows Theorem 1, whose argument holds for z ∈ R^N+N^2.The proof notes this domain when applying Theorem 1 to the quadratic potential games.Source: F. Proof of Corollary 3 · p. 9