Computing Quasi-Nash Equilibria via Gradient-Response Schemes

Abstract

We consider a class of smooth static N-player noncooperative games, where player objectives are expectation-valued and potentially nonconvex. In such a setting, we consider the largely open question of efficiently computing a suitably defined quasi-Nash equilibrium (QNE) via a stochastic gradient-response framework. First, under a suitably defined quadratic growth property, we prove that both the stochastic synchronous gradient-response (SSGR) scheme and its asynchronous counterpart (SAGR) are characterized by almost sure convergence to a QNE and a sublinear rate guarantee. Notably, when a potentiality requirement is overlaid under a somewhat stronger pseudomonotonicity condition, this claim can be made for a Nash equilibrium (NE), rather than a QNE. Second, under the weak sharpness property, we show that the deterministic synchronous variant (SGR) displays a linear rate of convergence sufficiently close to a QNE by leveraging a geometric decay in steplengths. This suggests the development of a two-stage scheme with global non-asymptotic sublinear rates and a local linear rate. We also present applications satisfying the prescribed requirements where preliminary numerics appear promising.