Small-Gain Nash: Certified Contraction to Nash Equilibria in Differentiable Games
Vedansh Sharma
Abstract
The SGN condition provides a framework for certifying convergence of gradient-based learning in games by constructing a weighted block metric, enabling convergence under conditions where Euclidean geometry fails.
Classical convergence guarantees for gradient-based learning in games require the pseudo-gradient to be (strongly) monotone in Euclidean geometry as shown by rosen(1965), a condition that often fails even in simple games with strong cross-player couplings. We introduce Small-Gain Nash (SGN), a block small-gain condition in a custom block-weighted geometry. SGN converts local curvature and cross-player Lipschitz coupling bounds into a tractable certificate of contraction. It constructs a weighted block metric in which the pseudo-gradient becomes strongly monotone on any region where these bounds hold, even when it is non-monotone in the Euclidean sense. The continuous flow is exponentially contracting in this designed geometry, and projected Euler and RK4 discretizations converge under explicit step-size bounds derived from the SGN margin and a local Lipschitz constant. Our analysis reveals a certified ``timescale band'', a non-asymptotic, metric-based certificate that plays a TTUR-like role: rather than forcing asymptotic timescale separation via vanishing, unequal step sizes, SGN identifies a finite band of relative metric weights for which a single-step-size dynamics is provably contractive. We validate the framework on quadratic games where Euclidean monotonicity analysis fails to predict convergence, but SGN successfully certifies it, and extend the construction to mirror/Fisher geometries for entropy-regularized policy gradient in Markov games. The result is an offline certification pipeline that estimates curvature, coupling, and Lipschitz parameters on compact regions, optimizes block weights to enlarge the SGN margin, and returns a structural, computable convergence certificate consisting of a metric, contraction rate, and safe step-sizes for non-monotone games.
Community
Gradient methods in games are usually proven to converge only under strong monotonicity in the Euclidean geometry (Rosen-style assumptions). That fails even for simple coupled quadratic games, yet in practice we still often see convergence.
This paper takes a structural “design the geometry” viewpoint. Small-Gain Nash (SGN) uses per-player curvature and cross-player coupling bounds to build a block-weighted metric where the pseudo-gradient becomes strongly monotone and the joint gradient flow is contracting on a certified region.
Once SGN holds on a region, you get:
– existence + uniqueness of a Nash equilibrium there,
– exponential contraction of the continuous flow,
– explicit safe step-size bounds for projected Euler and RK4 via a game-theoretic CFL number, and
– a finite “timescale band” that plays a TTUR-like role i.e instead of vanishing two-timescale step sizes, it tells you for which relative player weights a single global step size is provably stable.
The paper ends with an offline certification pipeline that estimates curvature/couplings on compact regions, optimizes the metric to enlarge the SGN margin, and certifies convergence in non-monotone quadratic and Markov games (including mirror/Fisher geometries for entropy-regularized policy gradient).
Models citing this paper 0
No model linking this paper
Datasets citing this paper 0
No dataset linking this paper
Spaces citing this paper 0
No Space linking this paper
Collections including this paper 0
No Collection including this paper