PaperlayerView exact revision on arXiv

Source-linked AI summary

On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games

Eric V. Mazumdar, Michael I. Jordan, S. Shankar Sastry

arXiv:1901.00838v2cs.LGmath.OCstat.ML

TL;DR

Existing gradient-based methods for zero-sum games can converge to non-Nash stationary points, leaving local Nash convergence without a guarantee. The paper introduces a two-timescale method that uses the game’s differential structure; its attracting hyperbolic equilibria are local Nash equilibria, and its analysis excludes oscillations near equilibria. The analysis is limited to equilibrium neighborhoods, and the algorithm may converge to limit cycles elsewhere.

  • Problem

    Previous gradient-based algorithms can converge to non-Nash stationary points, so they do not guarantee convergence to local Nash equilibria.

    Source: §1 · p. 2, §2.1 · p. 5

  • Method

    Local symplectic surgery discretizes a continuous-time flow using a two-timescale procedure that avoids matrix inversion.

    Source: §1 · p. 2

  • Results

    The algorithm’s only hyperbolic critical points to which it can converge are local Nash equilibria, and its analysis rules out oscillations near those equilibria.

    Source: §6 · p. 14

  • Takeaways & Limitations

    The method provides game-theoretically relevant limit points while ruling out oscillations near equilibria, with per-iteration complexity similar to other gradient-based algorithms.

    Source: §6 · p. 14

    The analysis covers neighborhoods of equilibria; limit cycles may occur elsewhere, and the assumed existence of local Nash equilibria is difficult to establish in general.

    Source: §6 · pp. 14–15

Abstract

from arXiv · show

We propose local symplectic surgery, a two-timescale procedure for finding local Nash equilibria in two-player zero-sum games. We first show that previous gradient-based algorithms cannot guarantee convergence to local Nash equilibria due to the existence of non-Nash stationary points. By taking advantage of the differential structure of the game, we construct an algorithm for which the local Nash equilibria are the only attracting fixed points. We also show that the algorithm exhibits no oscillatory behaviors in neighborhoods of equilibria and show that it has the same per-iteration complexity as other recently proposed algorithms. We conclude by validating the algorithm on two numerical examples: a toy example with multiple Nash equilibria and a non-Nash equilibrium, and the training of a small generative adversarial network (GAN).

1. Introduction

The introduction motivates local Nash equilibrium search in zero-sum games and identifies a failure of existing gradient-based methods: they can attract to non-Nash stationary points. It presents a two-timescale algorithm whose attracting stationary points are local Nash equilibria, with numerical examples planned to validate it.

1. Introduction

  • The paper positions game-theoretic learning as a growing connection to machine learning, including adversarial learning, robustness, and systems embedded in economic networks.Earlier connections between game theory and machine learning had focused principally on single- and multi-agent decision-making rather than pattern recognition.Source: §1 · p. 1
  • Existing gradient-based methods can converge to non-Nash stationary points, so they cannot guarantee convergence to local Nash equilibria.The paper identifies this issue across consensus optimization, symplectic gradient adjustment, and two-timescale simultaneous gradient descent.Source: §1 · p. 2
  • The paper introduces a two-timescale gradient-based algorithm whose only convergent stationary points are local Nash equilibria.Its discretization of a continuous-time ODE avoids matrix inversion and has computational complexity similar to other gradient-based algorithms.Source: §1 · p. 2
  • Two numerical examples are outlined: a toy game with three local Nash equilibria and one non-Nash fixed point, and training a small GAN.The proposed method converges only to local Nash equilibria in the toy example and reaches a suitable GAN solution in a number of steps similar to simultaneous gradient descent.Source: §1 · p. 2

2. Preliminaries

The paper studies local Nash equilibria in two-player zero-sum games, where each player optimizes the same function in opposing directions. It shows why ordinary gradient dynamics and related adjustments can attract to critical points that are not Nash equilibria, motivating dynamics that target Nash solutions directly.

2. Preliminaries

  • A local Nash equilibrium is locally optimal for each player with respect to that player’s own decision variable.The game has one player minimize f(x, y) and the other maximize it; local and differential Nash equilibria are saddle points with curvature aligned to those player variables.Source: §2 · p. 3

2.1 Issues with gradient-based algorithms in zero-sum games

  • Simultaneous gradient descent updates the minimizing and maximizing players along their respective gradients, but its attracting equilibria need not be Nash.While differential Nash equilibria are locally asymptotically stable under the gradient dynamics, the converse does not hold.Source: §2.1 · pp. 3–5
  • Non-Nash locally attracting stable equilibria can arise when a critical point’s curvature is misaligned with the players’ variables.Every saddle point that is not a local Nash equilibrium is a candidate, and three recently proposed algorithms can converge to such points.Source: §2.1 · p. 5
  • The proposed dynamics are designed so that their only locally asymptotically stable equilibria are differential Nash equilibria, without oscillations near those equilibria.The paper contrasts this guarantee with prior adjustments that reduce oscillations but do not rule out convergence to non-Nash equilibria.Source: §2.1 · pp. 5–6

3. Constructing the limiting differential equation

The paper constructs a continuous-time flow whose attracting hyperbolic equilibria correspond to differential Nash equilibria. Its adjustment targets the rotational component of the gradient dynamics, and the resulting Jacobian has real eigenvalues at critical points.

3. Constructing the limiting differential equation

  • The proposed flow adjusts gradient dynamics so trajectories approach critical points along the players’ decision axes, allowing a player to push away from a point that is not locally optimal for them.Near critical points, the adjustment cancels the rotational contribution of the antisymmetric Jacobian component.Source: §3 · pp. 6–7
  • Under the stated assumptions, the flow’s locally asymptotically stable equilibria are exactly the differential Nash equilibria, and its Jacobian has real eigenvalues at critical points.The assumptions include smoothness and Lipschitz conditions, hyperbolic critical points, and invertibility of the Jacobian at critical points.Source: §3 · pp. 6–7
  • Critical points that are not differential Nash equilibria are linearly unstable and almost surely avoided under random initialization.The result applies when at least one relevant second-derivative condition fails, as described in the theorem discussion.Source: §3 · pp. 7–8
  • The dynamics do not oscillate near critical points, regardless of the choice of λ that satisfies the assumptions.The paper notes that oscillations can slow convergence of the discretized process and contrasts its result with prior methods whose reduction of oscillations depends on hyperparameter choice.Source: §3 · p. 8
  • A damping function can make the dynamics track simultaneous gradient descent away from critical points while limiting the adjustment when the Jacobian is ill-conditioned.The function is chosen to equal one at critical points.Source: §3 · p. 8

4. Two-timescale approximation

Local symplectic surgery approximates the limiting ODE with a two-timescale process that avoids matrix inversion. Under the stated assumptions and boundedness condition, it tracks the ODE and has only differential Nash equilibria as locally asymptotically stable points.

4. Two-timescale approximation

  • LSS uses a two-timescale approximation to remove the Jacobian’s symplectic component near hyperbolic critical points while preserving the limiting behavior without costly matrix inversion.The fast process tracks a regularized least-squares solution; the slower process then tracks the limiting ODE.Source: §4 · pp. 8–9
  • Jacobian-vector products give each iteration the same order of computational complexity as simGD, consensus optimization, and the symplectic gradient adjustment.Neither process requires a matrix inversion.Source: §4 · p. 9

4.1 Long-term behavior of the two-timescale approximation

  • With unbiased estimates, LSS asymptotically tracks the limiting ODE when the stochastic approximation process remains bounded and the stated assumptions hold.The analysis establishes almost-sure tracking under this boundedness condition.Source: §4.1 · pp. 9–10
  • Under the stated assumptions and boundedness condition, LSS asymptotically tracks the limiting ODE, whose only locally asymptotically stable points are differential Nash equilibria.Consequently, the approximation avoids non-Nash equilibria of the gradient dynamics.Source: §4.1 · pp. 9–11

5. Numerical Examples

The examples compare the limiting ODE and LSS with simGD in a two-dimensional game and a small GAN. In the GAN example, LSS reaches the target distribution while simGD suffers mode collapse; in the toy game, the limiting ODE converges only to local Nash equilibria.

5. Numerical Examples

  • The numerical examples test the limiting ODE and LSS in a two-dimensional zero-sum game and use LSS to train a GAN on a mixture of eight Gaussians.The Gaussian modes are uniformly spaced around the unit circle.Source: §5 · p. 11, §5.2 · p. 14

5.1 2-D example

  • In the two-dimensional game, simGD converges to all four gradient-dynamics LASE, including a non-Nash equilibrium, while the limiting ODE converges only to local Nash equilibria.The game has three local Nash equilibria and one non-Nash LASE.Source: §5.1 · pp. 11–12, Figure 1 · p. 12
  • Near a local Nash equilibrium, the limiting ODE approaches directly even when simGD oscillates.This behavior is empirically shown in Figure 1B.Source: §5.1 · p. 12, Figure 1 · p. 12
  • LSS tracks gradient dynamics before its fast timescale converges, then tracks the limiting ODE and exits the non-Nash neighborhood, though such points can slow convergence.Figure 2 shows this behavior across four initializations.Source: §5.1 · p. 12, Figure 2 · p. 13

5.2 Generative adversarial network

  • With identical initial weights and biases, LSS converges to the eight-Gaussian target distribution while simGD suffers mode collapse.The plotted generator progression is shown at 0, 5,000, 12,000, and 20,000 iterations.Source: §5.2 · p. 14, Figure 3 · p. 14

6. Discussion

Local symplectic surgery gives stronger convergence guarantees than prior gradient-based methods while avoiding oscillations near equilibria at similar per-iteration complexity. The analysis has important limits: it is local, assumes equilibria exist, and uses second-order information.

6. Discussion

  • The algorithm guarantees that only hyperbolic critical points it can converge to are local Nash equilibria, unlike prior methods without that guarantee.Its limit points have game-theoretic relevance, and the analysis rules out oscillations near equilibria.Source: §6 · p. 14
  • The analysis covers neighborhoods of equilibria; limit cycles can still occur elsewhere in the state space.The authors say such cycles are hard to rule out completely and may have game-theoretic relevance.Source: §6 · pp. 14–15
  • The convergence analysis assumes local Nash equilibria exist, and divergence does not certify that none exist.The algorithm may diverge if no equilibria exist or if none lie in its region of attraction.Source: §6 · p. 15
  • The method uses Jacobian-vector products, making it inherently slower to compute than pure first- or zeroth-order methods.The two-timescale approximation does not require access to the full Jacobian.Source: §6 · p. 15
  • The authors position the method as a way to overcome some inherent flaws of gradient-based methods by using zero-sum game structure.They report similar per-iteration complexity to existing methods, which lack the same guarantees.Source: §6 · pp. 14–15

Appendix A. Time-varying adjustment

The time-varying adjustment adds a term to the limiting dynamics to remove an eigenvector assumption while retaining the guarantee that stable equilibria are differential Nash equilibria. A two-timescale process tracks these dynamics and preserves the theoretical properties under the stated assumptions.

Appendix A. Time-varying adjustment

  • The added time-varying term removes the assumption that ω(z) is never an eigenvector of the adjustment matrix with eigenvalue −1.The term is designed to vanish only when ω(z) is zero and to change over time away from critical points.Source: Appendix A · pp. 17–18
  • The paper defines a locally uniformly asymptotically stable equilibrium for time-varying dynamics using a time-invariant Jacobian with eigenvalues having positive real parts.Under this definition, such equilibria are also locally exponentially attracting under the flow.Source: Appendix A · p. 17
  • Only differential Nash equilibria are locally asymptotically stable equilibria of the adjusted time-varying dynamics.The theorem also states that stable equilibria are exactly the differential Nash equilibria.Source: Appendix A · p. 18
  • At an equilibrium of the time-varying dynamics, the Jacobian is time-invariant and has real eigenvalues.At critical points, the added term's Jacobian contribution disappears, leaving the matrix S(z).Source: Appendix A · p. 18
  • The two-timescale process asymptotically tracks the time-varying limiting ODE and gives rise to time-varying local symplectic surgery.The process is stated to maintain the theoretical properties while relaxing some assumptions.Source: Appendix A · pp. 19–20
  • The process uses separate step sizes for the state updates and auxiliary variable, with the algorithm returning the converged state pair.Algorithm 2 updates x and y with a_n and v with b_n.Source: Appendix A · p. 20

Appendix B. Counter-examples for other algorithms

Counterexamples show that several gradient-based approaches can converge to non-Nash equilibria in the same zero-sum game. This includes two-timescale simultaneous gradient ascent, consensus optimization, and symplectic gradient adjustment.

Appendix B. Counter-examples for other algorithms

  • Three state-of-the-art algorithms are shown to be attracted to non-Nash equilibria, so their limit points are not guaranteed to be locally optimal.The counterexample is constructed in R^2.Source: Appendix B · p. 20
  • Two-timescale simultaneous gradient ascent can converge to a non-Nash equilibrium even when the maximizing player uses the slower timescale.The example's origin is non-Nash, yet the process converges to it.Source: Appendix B · p. 21
  • Consensus optimization converges to the non-Nash equilibrium at (0,0) in Example 2 for every positive hyperparameter value.The dynamics' Jacobian has eigenvalues with strictly positive real parts for λ > 0.Source: Appendix B · p. 22
  • Symplectic gradient adjustment also converges to the non-Nash equilibrium at (0,0) in Example 2 for all λ > 0.Its dynamics have eigenvalues with strictly positive real parts throughout that range.Source: Appendix B · pp. 22–23

Appendix C. Efficient computation of the two-timescale update

The two-timescale update can be computed efficiently using Jacobian-vector products and the block structure of the Jacobian in two-player zero-sum games. Its per-iteration complexity is on the same order as consensus optimization and symplectic gradient adjustment.

Appendix C. Efficient computation of the two-timescale update

  • A Jacobian-vector product computes J^T(z)u by differentiating ω^T(z)u with respect to the variable.This supplies a clean form for the x and y updates in Algorithm 1.Source: Appendix C · p. 23
  • Computing J(z)v requires two Jacobian-vector products, using the Jacobian structure of two-player zero-sum games.The authors attribute this computation to the game's block structure.Source: Appendix C · p. 23
  • The resulting per-iteration complexity is on the same order as consensus optimization and symplectic gradient adjustment.The comparison concerns the computation of the two-timescale update.Source: Appendix C · p. 23

Appendix D. Further numerical examples

Appendix D reports GAN experiments across different initial conditions: both methods converge correctly in one case, while LSS reaches the correct solution where simGD misses mixture modes. The appendix also specifies the GAN training setup and notes that its step sizes do not meet the assumed sequences.

Appendix D. Further numerical examples

  • In Figure 4B, simGD identifies only five mixture Gaussians while LSS converges to the correct solution; both methods converge correctly in Figure 4A.The figure compares simGD and the two-timescale method across two GAN training examples.Source: Appendix D · p. 23, Figure 4 · p. 24
  • GAN weights and biases use standard TensorFlow initialization, and simGD and LSS use RMSProp with step size 2e−4 for the x and y processes.LSS uses step size 1e−5 for v, damping g(z) = e−0.001||ω(z)||2, and batch size 128.Source: Appendix D · p. 24
  • The GAN training step sizes do not satisfy the assumed two-timescale sequences, but are intended to show that the approach works in practical settings.Source: Appendix D · p. 24

Appendix E. Useful propositions

Appendix E introduces a prior-work proposition used in the proofs, giving conditions for a stochastic-approximation process to be an asymptotic pseudo-trajectory of an underlying ODE.

Appendix E. Useful propositions

  • The proposition gives conditions under which a stochastic-approximation process is an asymptotic pseudo-trajectory of the underlying ODE.Source: Appendix E · p. 24
  • Proposition 15 assumes a continuous, globally integrable vector field h and considers trajectories of the system dot x = −h(x).Source: Appendix E · p. 24
  • The reference trajectory x(t, s, x_s) starts from state x_s at time s, for t ≥ s.Source: Appendix E · p. 24
Loading 1901.00838v2…