Computing Equilibria in Stochastic Nonconvex and Non-monotone Games via Gradient-Response Schemes

Abstract

We consider a class of smooth $N$-player noncooperative games, where players' objectives are expectation-valued and potentially nonconvex. In such a setting, we consider the largely open question of efficiently computing a quasi-Nash equilibrium (QNE) via a single-step gradient-response framework. First, under a suitably defined quadratic growth property, we prove that both the stochastic synchronous gradient-response (\textbf{SSGR}) scheme and its asynchronous counterpart (\textbf{SAGR}) are characterized by almost sure convergence to a QNE and a sublinear rate guarantee. Second, under a quasi sharpness property, we show that the deterministic synchronous variant displays a linear rate of convergence to a QNE by leveraging a geometric decay in steplengths. This paves the way for developing a practically implementable two-stage scheme that combines sublinearly convergent schemes with a locally linearly convergent second phase. Notably, when the game admits a pseudoconvex potential function, the above convergence claims can be strengthened to a Nash equilibrium (NE), rather than merely to a QNE. Third, when player problems are convex but the associated concatenated gradient map is potentially non-monotone, we propose a stochastic asynchronous modified gradient-response (\textbf{SAMGR}) scheme which can efficiently obtain an NE under the strict copositivity condition. Collectively, our findings represent some of the first inroads into the tractable computation of QNE/NE in nonconvex settings, leading to a set of single-step schemes that are characterized by broader reach while providing rate guarantees. We present applications satisfying the prescribed requirements where preliminary empirical studies appear promising.

32 pages, 3 figures