Learning Generalized Nash Equilibria in Non-Monotone Games with Quadratic Costs

Tatiana Tatarenko, Lucas Wey Hacker · 2025

Read Learning Generalized Nash Equilibria in Non-Monotone Games with Quadratic Costs by Tatiana Tatarenko, Lucas Wey Hacker (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-18330.txt.

Introduction

Tatiana Tatarenko and Lucas Wey Hacker teach rival players to find a shared resting point in hard games. In a generalized Nash setup, each player's best move depends on the rest, and private limits tie their hands. Past learning rules demanded the game bend in a friendly monotone way, which many real contests fail.

The pair recast the balance conditions as a smooth convex program with a trait that makes plain gradient steps race in a straight line pace. Players update over a fixed talk network and still land on a balance point together. When slopes are too costly to get, a second rule uses only each player's own costs and limit gaps, and it closes in at a slower one over t rate.

Catalog record

CREATORTatiana Tatarenko, Lucas Wey Hacker
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-18330

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning Generalized Nash Equilibria in Non-Monotone Games with Quadratic Costs Tatiana Tatarenko, Lucas Wey Hacker Abstract We study generalized Nash equilibrium (GNE) problems in games with quadratic costs and individual linear equality constraints. Departing from approaches that require strong monotonicity and/or shared constraints, we reformulate the KKT conditions of the (generally non-monotone) games into a tractable convex program whose objective satisfies the Polyak–Łojasiewicz (PL) condition. This PL geometry enables a distributed gradient method over a fixed communication graph with global geometric (linear) convergence to a GNE. When gradient information is unavailable or costly, we further develop a zero-order fully distributed scheme in which each player uses only local cost evaluations and their own constraint residuals. With an appropriate step size policy, the proposed zero-order method converges to a GNE, provided one exists, at rate O ⁡ ( 1 / t ) O(1/t) . I Introduction Generalized Nash Equilibrium (GNE) problems, where players’ strategy sets are coupled, arise ubiquitously in diverse fields ranging from electricity markets to network games [ 7 , 14 ] . The challenge lies in finding solutions in these games, especially when players have limited information or computational resources. Recent work has focused on developing iterative algorithms for learning GNE, often relying on strong assumptions like monotonicity of the game mapping [ 1 , 8 , 11 , 16 , 19 ] . However, many real-world GNE problems lack such properties, demanding more sophisticated solution techniques. Furthermore, a significant portion of the existing literature on GNE focuses on games with shared constraints, where all players are subject to the same set of constraints [ 1 , 11 , 16 , 19 ] . Motivated by these limitations, our work addresses GNE problems with non-monotone game mappings and individual coupling constraints. This allows for modeling scenarios where players face distinct limitations or requirements, reflecting the heterogeneity often present in real-world systems. Specifically, we focus on games with quadratic cost functions and linear equality coupling constraints, a structure often arising in engineering and economic models [ 2 , 4 , 5 , 17 ] . By reformulating the corresponding Karush-Kuhn-Tucker conditions for GNE in games with such a specific structure, we derive a tractable convex optimization problem suitable for distributed solution. This reformulation is critical because, unlike existing approaches, it avoids relying on (strong) monotonicity assumptions. Moreover, we demonstrate that the objective function fulfills a so-called Polyak-Łojasiewicz (PL) condition, enabling the efficient application of well-established gradient-based algorithms under a defined communication topology within the system [ 18 ] . Consequently, we guarantee geometric convergence for calculating GNE in the games under consideration. It is worth noting that the work [ 1 ] presents a communication-based procedure achieving geometrically fast convergence to a GNE in games with strongly monotone pseudo-gradients and shared linear equality constraints. The paper [ 11 ] in turn proves an analogous result for strongly monotone games with shared linear inequality constraints, subject to a specific rank condition required for fast convergence. Thus, our work extends the existing literature by demonstrating geometrically fast distributed convergence in games with non-monotone pseudo-gradients and individual coupling constraints. Finally, unlike most existing approaches that rely on gradient information [ 1 , 8 , 11 ] , which is often unavailable or costly in practice, we develop a novel zero-order, fully distributed algorithm tailored to the convex reformulation of the GNE problem. Each player observes only the values of their local cost and the residuals of their own constraints. Thus, no gradients or Jacobians are available. This information setup has been considered recently in the literature [ 15 , 16 , 19 ] . For games with jointly convex coupling constraints, [ 15 ] proposes a payoff-based algorithm whose convergence relies on the existence of a convex potential. The work [ 19 ] extends this setting to non-potential games with jointly linear constraints via a Tikhonov regularization approach that yields an efficient procedure. The recent paper [ 16 ] leverages the same regularization idea to establish convergence rates for zero-order algorithms in strongly monotone games with shared affine coupling constraints. The core difficulty in our approach is that the search direction for the local objectives in the reformulated optimization problem is a coupled, global quantity and the objectives’ gradients do not coincide with any individual player’s local gradients. Our contribution is a few-query scheme that reconstructs the required gradient surrogates from function values alone while keeping bias and variance controlled that preserves fast convergence in a purely distributed implementation. We demonstrate that, under an appropriate choice of the step size parameter, the proposed zero-order procedure possesses a convergence rate of the order O(1/t) which is (up to dimension-dependent constants) asymptotically optimal within the class of strongly convex optimization problems [ 3 ] . Thus, our contributions are as follows: • We present a convex reformulation for GNE problems with general quadratic cost function (without requiring monotonicity) and individual coupling linear equality constraints. We demonstrate that the objective of the latter problem satisfies the Polyak–Łojasiewicz condition, which in particular allows for designing a distributed gradient method with geometrically fast convergence to a GNE in systems endowed with a communication topology; • We propose a payoff- and residual-only scheme to solve the obtained convex optimization problem that requires no closed-form gradients. Thus, each player uses just local cost evaluations and local constraint residuals to set up her update rules; • With an appropriate step size policy, the zero-order method achieves an O(1/t) rate, which is asymptotically optimal, up to dimension-dependent constants, in the subclass of problems with strongly convex objectives. I-A Notations. The set \{1,\ldots,n\} is denoted by [n] . We consider real normed space \mathbb{R}^{D} and denote by \mathbb{R}_{+}^{D} its non-negative orthant. The column vector \bm{x}\in\mathbb{R}^{D} is denoted by \bm{x}=[x^{1},\ldots,x^{D}] . We allow vectors to consist of blocks, i.e. \bm{x}=[\bm{x}^{1},\dots,\bm{x}^{n}]\in\mathbb{R}^{nd} is the vector with the blocks \bm{x}^{i}\in\mathbb{R}^{d} . We define the projector P_{i}\in\mathbb{R}^{nd\times nd} onto block j by P_{j}\;=\;e_{j}e_{j}^{\top}\,\otimes\,I_{d} , where e_{j}\in\mathbb{R}^{n} is the j -th standard basis vector and I_{d} is the d\times d identity matrix. Thus, for any x=[x^{1},\dots,x^{n}]\in\mathbb{R}^{nd} , P_{j}x=[0,\dots,0,\;x^{j},\;0,\dots,0]\in\mathbb{R}^{d} . For any function f:K\to\mathbb{R} , K\subseteq\mathbb{R}^{nd} , \nabla_{x^{i}}f(\bm{x})=\frac{\partial f(\bm{x})}{\partial\bm{x}^{i}}\in\mathbb{R}^{d} is the partial derivative taken in respect to the \bm{x}^{i} th block in the vector argument \bm{x}\in\mathbb{R}^{nd} . We use \langle\cdot,\cdot\rangle to denote the inner product in \mathbb{R}^{D} . We use \|\cdot\| to denote the Euclidean norm induced by the standard inner product in \mathbb{R}^{D} . Given a matrix H\in\mathbb{R}^{nd\times nd} , we denote by H_{(i,:)}\in\mathbb{R}^{d\times nd} and H^{(i,:)}\in\mathbb{R}^{nd\times d} and the i -th block of d rows and columns in H respectively. \operatorname{blkdiag}(H_{i})_{i=1}^{n} denotes the matrix of the block-diagonal concatenation of the matrices H_{1},\ldots,H_{n} , whereas \operatorname{col}(H_{i})_{i=1}^{n} denotes the matrix of the vertical concatenation of the matrices H_{1},\ldots,H_{n} . \sigma_{\min}^{+}(H) denotes the smallest positive singular value of matrix H . We write a_{t}=O(b_{t}) (as t\to\infty ), if there exists a constant C>0 and an index t_{0} such that a_{t}\leq C\,b_{t} , \forall t\geq t_{0} . We write a_{t}=\Omega(b_{t}) (as t\to\infty ), if there exists a constant c>0 and an index t_{0} such that a_{t}\geq c\,b_{t} , \forall t\geq t_{0} . The standard D -dimensional Gaussian distribution is denoted by \mathcal{N}(0,I_{D}) (with zero mean vector and identity covariance matrix). II

Read the complete text