Small-Gain Nash: Certified Contraction to Nash Equilibria in Differentiable Games

1 Introduction

• Classical Euclidean monotonicity assumptions can fail even in simple coupled quadratic games, where simultaneous gradient descent may oscillate or diverge.The games can have convex per-player objectives and strong couplings.Source: §1 · p. 1
• SGN converts player-wise curvature and cross-player coupling bounds into strong monotonicity in a designed block metric.The condition uses a block-diagonal small-gain inequality.Source: §1 · pp. 1–2
• SGN certifies existence and uniqueness of a variational-inequality/Nash solution and exponential contraction of pseudo-gradient flow on certified regions.The contraction is in the SGN metric.Source: §1 · p. 2
• A finite band of relative player weights makes scalar-step pseudo-gradient dynamics contractive, without requiring TTUR-style slowdown for the certified class of games.The band is specified by the geometric ratio r = w2/w1.Source: §1 · p. 2
• The offline pipeline estimates curvature, coupling, and Lipschitz bounds on compact regions, optimizes block weights, and returns a metric, contraction rate, and safe step sizes.The framework is validated on non-monotone quadratic games and extended to mirror/Fisher geometry for a tabular Markov game.Source: §1 · p. 2

2.1 Games, pseudo-gradients, and Nash equilibria

• A Nash equilibrium is a strategy profile at which each player satisfies its own first-order optimality condition; under the stated convexity assumptions, Nash solutions coincide with solutions of the Euclidean variational inequality.The paper also defines a metric variational inequality, equivalent to a Euclidean one under a linear change of variables.Source: §2.1 · pp. 2–3

2.2 Block metrics and induced norms

• The block metric uses an SPD matrix for each player's variables, while player weights rescale the blocks to form the SGN geometry.Arbitrary per-player blocks capture preconditioning and geometries such as Fisher metrics.Source: §2.2 · p. 3, §2.3 · p. 3

2.3 Block curvature and cross couplings

• Block bounds summarize each player's own curvature and cross-player couplings through parameters µi and Lij, and are certified on a closed convex region.The region is often a compact forward-invariant set; global claims refer to the region where the structural bounds hold.Source: §2.3 · p. 3, §2.1 · p. 3

3.1 Weighted small-gain condition

• The SGN condition tests positive definiteness of C(w, α), a weighted small-gain matrix linking player curvature and cross-player couplings.A diagonal-dominance interpretation compares reweighted own-player curvature with aggregate cross-couplings.Source: §3.1 · p. 4

3.2 Strong monotonicity in the SGN geometry

• On a region where the block bounds hold, SGN implies strong monotonicity in M(w), a unique VI solution and, under the stated convexity assumptions, a unique Nash equilibrium.The continuous flow contracts exponentially at rate α in the SGN metric.Source: §3.2 · pp. 4–5

3.3 Best SGN margin

• Optimizing the player weights seeks the largest strong-monotonicity margin within the diagonal SGN metric family, but SGN is sufficient rather than necessary and may be conservative.More general Jacobian-based directional stability conditions can certify larger regions or margins.Source: §3.3 · p. 5

3.4 Generalization to non-Euclidean geometries

• The curvature and coupling parameters extend to mirror geometries on simplices, where Bregman distances and Fisher metrics replace Euclidean norms.The paper describes mirror-SGN contraction guarantees in this geometry.Source: §3.4 · p. 5

4 Discrete-Time Dynamics: Euler and Runge-Kutta

• Projected Euler and RK4 use steps on the order of α/β^2 and 1/β, respectively, where α sets contraction strength and β the Lipschitz scale.These step-size scales play a CFL-type role for the discretizations.Source: §4 · p. 6

4.1 Projected forward-Euler

• Projected Euler is contractive on X ∩ R when F is α-strongly monotone there and G is β-Lipschitz, provided the step size satisfies the theorem's bound.The contraction result applies in the fixed M-norm.Source: §4.1 · p. 6

4.2 Explicit Runge-Kutta methods

• RK4 is contractive in the M-norm when the DSC margin is α > 0 and G is β-Lipschitz, for step sizes within a method-dependent bound.The bound uses method-dependent constants C4 and c4.Source: RK4 contraction · p. 7

4.3 Projected integrators in the SGN metric

• On product strategy sets, the SGN metric weights do not change the projected scalar-step update; they serve as an analysis instrument for certifying contraction.For constrained RK4, projection after each step preserves the contraction factor, but generally lowers local boundary accuracy from fourth to second order.Source: §4.3 · pp. 7–8

5.1 Two-player SGN region and timescale band

• For two players, SGN holds over a finite interval of weight ratios, complementing TTUR by certifying contraction without TTUR-style asymptotic timescale separation.The interval is characterized by explicit roots for each admissible margin.Source: §5.1 · p. 8
• For more than two players, valid SGN weights form a convex cone in the positive orthant that can be identified or optimized through a generalized eigenvalue problem.This cone generalizes the two-player timescale interval.Source: §5.1 · p. 8
• With µ1=µ2=1, a=10, and b=0.05, Euclidean monotonicity fails, yet balanced weights yield a positive SGN margin.The weighted geometry compensates for the strong cross-couplings and certifies contraction.Source: §5.1 · pp. 8–9

5.2 High-dimensional LQ validation

• At λ=1, the Euclidean symmetric margin is ≈−4.03, while SGN and true metric margins coincide at ≈0.293 and β≈1.71.The margin equality holds wherever SGN certifies strong monotonicity in this canonical game.Source: §5.2 · p. 10
• Across coupling strengths, certified Euler and RK4 step-size bounds stayed inside the true stability boundaries while remaining within a moderate factor of empirical thresholds.The phase diagrams compare the certified bounds with spectral-radius stability thresholds.Source: Figure 5 · p. 12, §5.2 · p. 12
• In random LQ games, SGN margins become more conservative as couplings depart from the canonical structure, while still providing nontrivial RK4 step-size bounds across an ensemble.For the structured canonical game, the block bounds are exact; the detailed NTK-based treatment is left for future work.Source: §5.2 · pp. 10–12

6 Verifying SGN on Compact Regions

• The pipeline is most natural for games with modest effective dimension or exploitable structure, and it bounds curvature, coupling, and Lipschitz parameters on a compact region.The region may be a trust region or a candidate forward-invariant set.Source: §6 · p. 13, §6.1 · p. 13

6.1 Certification pipeline and guarantees

• Given these bounds, the pipeline searches for weights and an SGN margin, optionally trading off the margin against the local Lipschitz bound, then outputs the metric and safe step-size ranges.The certificate supports projected Euler and RK4 on the region.Source: §6.1 · p. 13

6.2 Operational usage

• Certification is intended to run offline or be updated slowly; after certification, projected Euler or RK4 can use the corresponding step-size policy, with periodic recertification if operating conditions change slowly.This separates heavier certification from lightweight online iteration.Source: §6.2 · p. 13

7.1 Mirror SGN on the simplex

• The SGN framework applies local curvature and coupling bounds defined through mirror metrics and Bregman divergences on probability simplices.Under mirror-SGN, the mirror flow is exponentially contractive toward an interior Nash equilibrium, and mirror-Euler and mirror-RK inherit geometric Lyapunov decay.Source: §7.1 · p. 14
• With negative-entropy mirror maps, the simplex construction recovers Fisher/information geometry for entropy-regularized policy-gradient dynamics.In the Markov-game example, the negative-entropy mirror map yields the softmax Fisher metric used by the natural policy gradient.Source: §7.1 · p. 14, §7.2 · p. 14

7.2 Markov game experiment: mirror-SGN for natural policy gradient

• Optimizing weight ratios using the stated bounds yields best diagonal margin α∗(w⋆)≈0.33 at near-balanced r⋆≈0.98; using the same Fisher metric and grid gives local Lipschitz bound β≈1.57.Source: §7.2 · p. 14
• In the tabular Markov game, NPG in the Fisher metric decays exponentially faster than EPG and remains empirically stable for η/ηSGN≲1.The comparison uses a conservative step size η=0.5ηSGN; EPG also converges in this setting but more slowly and without a comparable step-size certificate.Source: Figure 6 · p. 15, §7.2 · p. 15
• The Fisher-metric SGN margin is positive across a nontrivial interval of player-weight ratios, while extreme timescale imbalances violate the small-gain inequalities.Figure 7 plots the margin against r=w2/w1; a moderate interval admits a diagonal mirror metric certifying local contraction.Source: §7.2 · p. 15, Figure 7 · p. 16

8 Future Work

• Future work would relax convexity assumptions to estimate attraction basins and study bifurcations and multi-equilibrium stability beyond fixed compact trust regions.The current framework certifies fixed compact trust regions.Source: §8 · p. 16
• Extending mirror/Fisher SGN to general statistical manifolds and function-approximation policies would move beyond finite-dimensional simplices.Such settings have Fisher metrics on infinite-dimensional spaces of probability distributions.Source: §8 · p. 16
• A proposed Fisher-Bellman SGN model would represent actor-critic methods as coupled policy and environment/critic blocks on a statistical manifold.The proposed viewpoint would separate policy entropy curvature from value-function scale and discount-horizon coupling; its full development is left to future work.Source: §8 · p. 16
• Further studies could compare certified and empirically stable rates and step sizes, and measure certificate cost and conservatism as game size grows.The paper notes that such evaluation would help identify amenable game classes and where additional assumptions or approximations are needed.Source: §8 · p. 16

9 Related Work

• Rosen’s diagonal strict concavity and variational inequalities provide classical monotonicity-based guarantees, while SGN uses coarse block curvature and coupling summaries with structured weights.The SGN matrix condition acts as a block-diagonal refinement of diagonal-stability and gain-matrix certificates.Source: §9 · pp. 16–17
• Gain-matrix contraction methods use player-wise norms and cross-coupling gains; SGN’s condition C(w,α)≻0 has a related structure in a block metric.The cited gain-matrix approach obtains a weighted norm from Hurwitzness of its Metzler gain matrix.Source: §9 · p. 17
• Passivity, potential games, and variational-stability approaches offer other routes to convergence, whereas SGN supplies a sufficient condition from curvature and Lipschitz bounds plus metric design.The paper presents SGN as complementary to these approaches.Source: §9 · p. 17
• General contraction-metric methods may search for state-dependent Riemannian metrics, while SGN restricts to constant block-diagonal metrics and algebraic small-gain inequalities.In the mirror case, SGN’s metric yields a Bregman Lyapunov function; the paper also instantiates classical explicit-integrator stability bounds in SGN geometries.Source: §9 · p. 17
• SGN complements methods such as Extragradient and OGDA by providing a structural condition and geometry that could also be applied to their underlying pseudo-gradients.The paper describes such combinations as possible in principle.Source: §9 · p. 17

10 Conclusion

• SGN certifies strong monotonicity in a tailored block geometry and contraction of continuous flow and explicit discretizations on regions satisfying SGN and Lipschitz bounds.The framework also extends to local mirror/Fisher geometry on simplices and outlines closed-loop Markov-game applications.Source: §10 · pp. 17–18

A Additional Details on Verifying Small-Gain

• On compact regions, the pipeline searches weights and a margin satisfying C(w,α)≻0, then uses α and β bounds to produce explicit projected-Euler and RK4 step-size ranges.Bounds may be obtained analytically or refined by sampling; in the reported experiments, sample-wise estimates are used without interval inflation, so the certificates are numerically validated but not strictly worst-case rigorous.Source: A Additional Details on Verifying… · pp. 19–20

A.1 Gershgorin-style sufficient conditions for SGN

• A Gershgorin-style diagonal-dominance test is an easy-to-check sufficient condition for H(w)⪰αI, yielding strong monotonicity in M(w).It is conservative and need not be necessary; the exact SGN certificate is C(w,α)≻0.Source: §A.1 · pp. 20–21

A.2 Two-player SGN band

• For two players, SGN with margin α holds exactly when the weight ratio r lies in the open interval between explicit roots, provided the stated root-existence condition holds.At α=0, the condition reduces to µ1µ2>L12L21 and the band has a simple closed form.Source: §A.2 · p. 22

• Positive definiteness of C(w, α) turns weighted curvature and coupling bounds into strong monotonicity in M(w).The proof weights and sums the block inequalities, then applies C(w, α) ≻ 0 to the vector of player-wise block distances.Source: §A.3 · pp. 22–23
• When each player’s objective is convex in their own strategy on a convex product set, strong monotonicity yields a unique variational-inequality solution and Nash equilibrium.The proof uses a linear change of variables to apply monotone VI theory, then invokes the VI–Nash equivalence under the stated convexity conditions.Source: §A.3 · p. 23
• On a convex region, the directional/DSC condition gives α-contraction of the continuous flow and lets the discrete-time contraction results apply when the field is β-Lipschitz.The Euler and RK4 results use the directional margin α in place of the SGN margin.Source: §A.3 · p. 23
• SGN implies diagonal stability in M(w), so its margin is a lower bound on the directional margin that Jacobian-based estimation can certify.The constant block-diagonal metric also avoids the additional geometric terms associated with state-dependent contraction metrics.Source: §A.3 · pp. 23–24

B Mirror Geometry and Small-Gain Nash

• On a compact interior region with bounded, invertible Hessians, mirror block bounds and mirror-SGN support exponential decay of a Bregman Lyapunov function to an interior Nash equilibrium.The mirror flow result assumes the trajectory remains in the region and that F(x*) = 0 in the chosen coordinates.Source: B Mirror Geometry and Small-Gain Nash · pp. 24–25

B.4 Mirror Euler and mirror RK discretizations

• Mirror-Euler and mirror-RK4 contract for sufficiently small steps under Lipschitz and log-norm bounds, by applying the discretization estimates in dual coordinates.For simplex policies, RK4 stages can be integrated in unconstrained dual coordinates and mapped back, avoiding primal-boundary stages and simplex projection.Source: B Mirror Geometry and Small-Gain Nash · p. 25, §B.4 · p. 26

B.1 Mirror block bounds from Hessians

• Hessian bounds on the players’ objectives and mirror maps yield the mirror block inequalities, with Bregman divergences serving as squared-distance analogues.The coupling bounds use mixed operator norms induced by the local mirror metrics.Source: §B.1 · p. 25

B.2 Proof of mirror strong monotonicity

• Weighting and summing the mirror block inequalities shows that H(w) ⪰ αI implies mirror strong monotonicity around the equilibrium.The resulting inequality is expressed using weighted Bregman distances to x*.Source: B Mirror Geometry and Small-Gain Nash · p. 24, §B.2 · p. 25

B.3 Lyapunov derivative for the mirror flow

• The mirror-flow proof differentiates the weighted Bregman Lyapunov function along trajectories and combines that derivative with mirror strong monotonicity.It uses the Legendre change of variables and the equilibrium condition F(x*) = 0.Source: §B.3 · p. 26

• SGN step-size curves lie inside the true spectral stability boundaries but within a moderate factor, and measured flow decay closely tracks the true metric margin when SGN holds.Figure 8 compares median balanced-metric norms for representative couplings with exponential references at αtrue and α*.Source: C Additional Numerical Results for the… · p. 26, Figure 8 · p. 27
• At zero structured-noise fraction αtrue/α* is close to 1; as the noise fraction approaches 1, SGN grows more conservative but remains a valid lower bound whenever it certifies.The reported ratio averages the true metric margin divided by the SGN margin.Source: C Additional Numerical Results for the… · p. 27, Figure 9 · p. 27
• In the random LQ ensemble, α*/αtrue is typically 0.15–1 when the fixed balanced metric certifies, while log10(hSGN/hstab) clusters just below zero.At larger couplings, the true metric margin may remain positive even when SGN in the fixed metric fails, indicating a need for metric redesign.Source: C Additional Numerical Results for the… · p. 27, Figure 10 · p. 28