PaperlayerView exact revision on arXiv

Source-linked AI summary

Nash Equilibrium Computation in Subnetwork Zero-Sum Games with Switching Communications

Youcheng Lou, Yiguang Hong, Lihua Xie, Guodong Shi, Karl Henrik Johansson

arXiv:1312.7050v2eess.SYcs.GTmath.OC

TL;DR

The paper studies distributed Nash equilibrium computation for zero-sum games on time-varying networks with two subnetworks, where weight-unbalanced communication complicates convergence. It develops a subgradient-based algorithm with heterogeneous stepsizes, proves convergence with homogeneous stepsizes for UJSC weight-balanced digraphs, and establishes heterogeneous-step convergence results for broader settings.

  • Problem

    Weight-unbalanced switching graphs make distributed Nash equilibrium convergence difficult, while homogeneous-stepsize methods may fail unless objective-function conditions hold.

  • Method

    The paper proposes a subgradient-based distributed algorithm with heterogeneous stepsizes and adaptive stepsize updates for two standard weight-unbalanced cases.

  • Results

    The algorithm achieves a Nash equilibrium under UJSC weight-balanced digraphs with homogeneous stepsizes, and adaptive heterogeneous stepsizes guarantee convergence in two specified cases.

  • Takeaways & Limitations

    Heterogeneous and adaptively updated stepsizes extend distributed Nash equilibrium computation beyond the weight-balanced setting considered by most existing results.

Abstract

from arXiv · show

In this paper, we investigate a distributed Nash equilibrium computation problem for a time-varying multi-agent network consisting of two subnetworks, where the two subnetworks share the same objective function. We first propose a subgradient-based distributed algorithm with heterogeneous stepsizes to compute a Nash equilibrium of a zero-sum game. We then prove that the proposed algorithm can achieve a Nash equilibrium under uniformly jointly strongly connected (UJSC) weight-balanced digraphs with homogenous stepsizes. Moreover, we demonstrate that for weighted-unbalanced graphs a Nash equilibrium may not be achieved with homogenous stepsizes unless certain conditions on the objective function hold. We show that there always exist heterogeneous stepsizes for the proposed algorithm to guarantee that a Nash equilibrium can be achieved for UJSC digraphs. Finally, in two standard weight-unbalanced cases, we verify the convergence to a Nash equilibrium by adaptively updating the stepsizes along with the arc weights in the proposed algorithm.

I. INTRODUCTION

The paper addresses distributed Nash equilibrium computation for zero-sum games over switching multi-agent networks, focusing on the difficulty of weight-unbalanced communication graphs. It proposes heterogeneous stepsizes and establishes conditions under which distributed algorithms achieve equilibrium.

  • Motivation: Weight-unbalanced switching graphs complicate convergence because common Lyapunov functions may not exist or may be difficult to construct.This motivates studying methods beyond the commonly analyzed weight-balanced setting.
  • Problem setting: Distributed Nash equilibrium computation uses two subnetworks whose agents cooperate within subnetworks while playing antagonistic roles across subnetworks.The network seeks a Nash equilibrium through distributed computation, with each subnetwork associated with one side of the zero-sum game.
  • Contributions: The paper proposes a subgradient-based distributed algorithm with heterogeneous stepsizes for Nash equilibrium computation under time-varying graphs.The approach studies cooperative equilibrium computation in general weight-unbalanced cases.
  • Contributions: With homogeneous stepsizes, the algorithm achieves a Nash equilibrium under UJSC weight-balanced digraphs.The result applies when the relevant weight-balance and connectivity conditions hold.
  • Contributions: Homogeneous-stepsize algorithms may fail in weight-unbalanced cases, even when the two subnetworks are identical.The paper therefore investigates stepsize choices that compensate for unbalanced communication structures.

III. DISTRIBUTED NASH EQUILIBRIUM COMPUTATION

This section formulates distributed Nash equilibrium computation for a two-subnetwork zero-sum game with time-varying communications and presents a subgradient algorithm using heterogeneous stepsizes. The design accommodates UJSC subnetworks, intermittent interconnection, and weight-unbalanced graphs.

  • Problem formulation: The network has two subnetworks whose agents minimize or maximize a shared convex-concave objective through local communications.Agents within each subnetwork cooperate, while the two subnetworks play antagonistic roles in the zero-sum game.
  • Problem formulation: The network seeks a Nash equilibrium represented by limiting states x* and y* in the saddle-point solution sets.Achievement requires convergence from any initial condition for all agents in the respective subnetworks.
  • Connectivity assumptions: The communication structure consists of two time-varying intranetwork digraph sequences and a time-varying bipartite interconnection sequence.The interconnection is modeled separately because communication between subnetworks need not be continuously available.
  • Connectivity assumptions: Connectivity requires uniformly jointly bipartite interconnection and UJSC intranetwork graphs.The bipartite condition excludes isolated nodes across subnetworks, while each subnetwork must be jointly strongly connected over bounded intervals.
  • Algorithm: The proposed distributed Nash equilibrium computation algorithm combines weighted neighbor aggregation, subgradient updates, projections, and heterogeneous stepsizes.Stepsizes may vary by agent and time, and cross-subnetwork information is incorporated through the most recent available interconnection.
  • Algorithm: Unlike rescaling, push-sum, objective reweighting, and subgradient-push methods, the proposed approach addresses weight-unbalanced graphs through nonidentical agent stepsizes.The method uses subgradients rather than extreme-seeking techniques and includes adaptive stepsize design for general unbalanced cases.
  • Stepsize conditions: Under homogeneous stepsizes, the standard stepsize sequence is non-increasing with divergent total sum and finite squared sum.These conditions are the conventional homogeneous stepsize requirements used in distributed subgradient methods for weight-balanced graphs.

IV. MAIN RESULTS

The results establish convergence with homogeneous stepsizes for UJSC weight-balanced graphs, identify when homogeneous stepsizes fail on unbalanced graphs, and show how heterogeneous stepsizes restore Nash equilibrium convergence. The analysis also covers identical subnetworks and distributed saddle-point computation as a special case.

  • A. Weight-balanced Graphs: For switching weight-balanced digraphs, homogeneous stepsizes achieve a Nash equilibrium when the sum objective is strictly convex-concave or the equilibrium set contains an interior point.The result applies under assumptions A1–A5 and allows time-varying communication structures and nonsmooth objectives.
  • B. Homogenous Stepsizes vs. Unbalanced Graphs: The identical-subnetwork case reduces the proposed dynamics to a distributed saddle-point computation algorithm for a sum objective whose local functions are known separately by the agents.Each paired agent uses the same objective, neighbor structure, and communication pattern across the two subnetworks.
  • B. Homogenous Stepsizes vs. Unbalanced Graphs: The algorithm also serves as a distributed version of a centralized saddle-point method for computing the saddle point of a sum objective.The formulation applies when each agent knows only its own local objective function.
  • B. Homogenous Stepsizes vs. Unbalanced Graphs: Homogeneous stepsizes may converge on fixed weight-unbalanced graphs without reaching the desired Nash equilibrium.The algorithm can converge to a saddle point of a Perron-weighted objective instead of the intended sum objective.
  • B. Homogenous Stepsizes vs. Unbalanced Graphs: For general UJSC switching digraphs, homogeneous stepsizes achieve a Nash equilibrium if and only if all local objectives share the same saddle point.With strictly convex-concave local objectives, this condition concerns their unique saddle points.

C. Weight-unbalanced Graphs

For weight-unbalanced graphs, homogeneous stepsizes may fail to achieve a Nash equilibrium, motivating heterogeneous and adaptive stepsize designs. The paper proves existence of suitable heterogeneous stepsizes for UJSC graphs and convergence under two standard adaptive cases.

  • Homogeneous stepsizes may not make a weight-unbalanced network achieve its Nash equilibrium.
  • For UJSC time-varying communication graphs and strictly convex-concave objectives, suitable heterogeneous stepsizes always exist to guarantee Nash equilibrium convergence.
  • The stepsize design compensates for graph imbalance through agent-specific reciprocals and promotes consensus and cooperative optimization through a shared sequence.
  • The proposed adaptive algorithms use only locally available information before each time step rather than future adjacency-matrix sequences.
  • Under adaptive stepsize updates, Nash equilibrium convergence is guaranteed when subnetworks have common left eigenvectors or periodically switching adjacency matrices.
  • When adjacency matrices lack a common left eigenvector, adaptive learning generally cannot recover the true stepsizes and may fail to achieve a Nash equilibrium.

V. PROOFS

This section introduces the lemmas used to prove the paper’s theorems.

  • The section presents auxiliary lemmas before proving the theorems from the preceding section.

A. Supporting Lemmas

The supporting lemmas establish stochastic-matrix convergence, consensus, boundedness, and error estimates needed for the distributed Nash equilibrium analysis.

  • The supporting results include deterministic sequence lemmas and stochastic-matrix contraction tools based on ergodicity coefficients.
  • Under the stated connectivity assumptions, transition-matrix products converge to rank-one limits with positive stochastic Perron vectors at a geometric rate.
  • A common left eigenvector of a UJSC stochastic-matrix sequence determines the Perron vector of each limiting product.
  • The disturbance introduced by cross-subnetwork interactions is bounded by the corresponding local perturbation magnitude.
  • Weighted disagreement terms vanish under the lemma’s summability condition, while vanishing agent stepsizes imply consensus within both subnetworks.
  • The consensus lemma extends a weight-balanced-graph result to general, possibly weight-unbalanced, graph sequences.

B. Proof of Theorem 4.1

The proof establishes boundedness, controls consensus and perturbation errors, and shows that limit points satisfy the saddle-point conditions required for Nash equilibrium convergence.

  • Error control: Subgradient inequalities and Lipschitz bounds control the objective changes and cross-subnetwork error terms.
  • Error control: Weight balance converts local adjacency-weight sums into the averaging relation needed in the Lyapunov-style estimate.
  • Proof structure: The proof first establishes bounded system states and then analyzes limit points through objective-function inequalities.
  • Convergence: For strictly convex-concave objectives, the saddle-point set is a singleton, so every agent state converges to the unique saddle point.
  • Convergence: Under the alternative condition, the subnetworks’ average states have unique limits that satisfy the saddle-point inequalities, and consensus transfers convergence to every agent.

C. Proof of Theorem 4.3

The proof establishes that any common saddle point of all local objective functions is necessary for convergence under the considered stepsize setting. It then uses consensus and boundedness to conclude convergence to the unique Nash equilibrium.

  • Necessity: A convergent network must reach a saddle point shared by every local objective function.The proof derives each local saddle inequality from weighted-sum conditions and concludes that (x*, y*) is a saddle point of every f_i.
  • Convergence: The proof first shows the iterates remain bounded using a finite bound on ζ*.The non-positive objective terms and a convergence lemma yield bounded system states.
  • Necessity: Strict convexity-concavity makes the limiting subsequence equal to the unique saddle point (x*, y*).Any subsequential limit satisfying the equality conditions must coincide with (x*, y*).
  • Convergence: Consensus within the two subnetworks and the limiting saddle-point argument imply ζ* = 0.Consequently, x_i(k) and y_i(k) converge to x* and y*, respectively.

D. Proof of Theorem 4.4

The proof analyzes the heterogeneous stepsizes by separating imbalance correction from summable perturbation terms. Geometric convergence of transition matrices and vanishing error terms then yield convergence to the Nash equilibrium.

  • Error control: The stepsize design eliminates the imbalance term and makes the remaining error terms summable.The proof explicitly separates imbalance correction from terms controlled by geometric transition-matrix convergence.
  • Error control: Geometric transition-matrix convergence controls the accumulated perturbations through a factor 0 < ρ < 1.The resulting bounds decay with powers of ρ and support the required zero-limit estimates.
  • Error control: The proof obtains lim_{r→∞} sup_{k≥r} ϱ(k,r) = 0 for the aggregate error term.This follows after combining the zero limits for the weighted error components and γ_rς(r).
  • Convergence: A convergent subsequence reaches (x*, y*), after which consensus and the error bound imply x_i(k) → x* and y_i(k) → y*.The argument selects a sufficiently late iterate near the equilibrium and propagates the bound for all later k.

E. Proof of Theorem 4.5

The proof shows that adaptive auxiliary-state dynamics can estimate the heterogeneous stepsizes needed for weight-unbalanced graphs. It treats common-left-eigenvector and periodically switching cases, establishing convergence in both settings.

  • Case (i): Auxiliary states are introduced to estimate the desired heterogeneous stepsizes in the common-left-eigenvector case.The states evolve through the graph dynamics and remain compatible with the stepsize rule.
  • Case (i): The adaptive rule remains well-defined because the estimated stepsizes satisfy α̂_i(k) ≥ η^k > 0.This positivity condition supports the subsequent convergence analysis.
  • Case (i): A common positive left eigenvector ensures the auxiliary estimates converge geometrically to the required stepsize weights.The transition products converge to 1(φℓ)′, which determines the limiting estimates.
  • Case (ii): For periodically switching graphs, vector auxiliary states estimate the stepsizes across each phase of the period.Separate state vectors are propagated for the two subnetworks and their phase indices.
  • Case (ii): The periodic auxiliary-state estimates converge geometrically, allowing the same convergence argument to establish the Nash equilibrium.The proof notes that the lemmas and analysis from Theorem 4.4 continue to apply under the new rule.

VI. NUMERICAL EXAMPLES

The numerical examples examine homogeneous stepsizes on balanced graphs, heterogeneous stepsizes on unbalanced graphs, and adaptive stepsizes under periodic switching. In each reported case, the agents converge to the unique Nash equilibrium.

  • Experimental design: The experiments cover balanced graphs with homogeneous stepsizes and two unbalanced-graph cases using heterogeneous or adaptive stepsizes.The third case specifically tests the adaptive strategy for periodically switching unbalanced graphs.
  • Example 6.1: The communication graph in Example 6.1 switches periodically between G_e and G_o.The switching sequence alternates according to G(2k) = G_e and G(2k + 1) = G_o.
  • Example 6.1: The balanced-graph experiment converges to the unique Nash equilibrium (x*, y*) = (0.6102, 0.8844).The graphs are weight-balanced and all agents use the common stepsize γ_k.
  • Example 6.2: The heterogeneous-stepsize experiment on weight-unbalanced digraphs converges to the unique Nash equilibrium.The result is shown for the stepsizes constructed in the existence theorem.
  • Example 6.3: The adaptive-stepsize experiment also converges to the unique Nash equilibrium for the periodically switching unbalanced case.The adaptive auxiliary-state updates are used in the third example.

VII. CONCLUSIONS

The paper develops distributed algorithms for Nash equilibrium computation in zero-sum games over switching communication graphs, addressing both weight-balanced and weight-unbalanced cases.

  • The proposed subgradient-based algorithm computes Nash equilibria for zero-sum games with switching communication graphs.
  • Homogeneous stepsizes suffice for switching weight-balanced digraphs under the stated sufficient conditions.
  • For weight-unbalanced graphs, homogeneous stepsizes may fail to reach a Nash equilibrium.
  • Heterogeneous stepsizes can guarantee Nash equilibrium achievement, and adaptive updates verify convergence in two special weight-unbalanced cases.
Loading 1312.7050v2…