NashOpt - A Python Library for Computing Generalized Nash Equilibria
Alberto Bemporad · 2025
Read NashOpt - A Python Library for Computing Generalized Nash Equilibria by Alberto Bemporad (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-23636.txt.
Introduction
Alberto Bemporad releases NashOpt, an open-source Python library for computing generalized Nash equilibria in games where players share constraints. In such games each player's feasible choices depend on the others, so ordinary equilibrium solvers do not apply. The library works from the joint optimality conditions of all players at once.
General nonlinear games are solved as nonlinear least-squares problems, with the JAX library supplying automatic differentiation. Linear-quadratic games are reformulated as mixed-integer linear programs, which also makes it possible to enumerate several equilibria. NashOpt further supports inverse games, where the game is inferred from observed play, and Stackelberg design problems. Examples include game-theoretic control problems built on linear quadratic regulation and model predictive control. The code is public on GitHub.
Catalog record
| CREATOR | Alberto Bemporad |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-23636
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
NashOpt - A Python Library for Computing Generalized Nash Equilibria Alberto Bemporad Abstract NashOpt is an open-source Python library for computing and designing generalized Nash equilibria (GNEs) in noncooperative games with shared constraints and real-valued decision variables. The library exploits the joint Karush–Kuhn–Tucker (KKT) conditions of all players to handle both general nonlinear GNEs and linear–quadratic games, including their variational versions. Nonlinear games are solved via nonlinear least-squares formulations, relying on JAX for automatic differentiation. Linear–quadratic GNEs are reformulated as mixed-integer linear programs, enabling efficient computation of multiple equilibria. The framework also supports inverse-game and Stackelberg game-design problems. The capabilities of NashOpt are demonstrated through several examples, including noncooperative game-theoretic control problems of linear quadratic regulation and model predictive control. The library is available at https://github.com/bemporad/nashopt . 1 Introduction Generalized games describe situations where several agents take decisions by optimizing individual objective functions under common constraints on their decision variables. Examples include traffic participants using the same roads, wireless systems sharing limited bandwidth, energy systems where prosumers share transmission capacity and balance constraints [ 9 , 36 ] , or firms competing in a market [ 3 ] . The solution concept for these problems, in which the cost function and the feasible set of each agent depends on the decisions taken by the other agents, is the generalized Nash equilibrium (GNE), a state in which no agent has an incentive or the possibility to change their decision [ 2 ] . GNEPs have been widely studied in the literature, with various algorithms proposed for their solution, including splitting-based operator frameworks [ 37 , 3 ] , approaches built on augmented Lagrangian formulations [ 32 , 26 ] , interior-point optimization strategies [ 11 ] , Newton-type algorithms [ 15 ] , distributed algorithms [ 37 , 35 , 3 ] , and learning-based methods only relying on measuring best responses [ 13 ] . For the specific class of GNEPs in which the shared constraints are linear, efficient solution methods exist for linear objectives [ 12 , 19 ] , multiparametric quadratic programming for strictly convex quadratic objectives [ 23 ] , and distributed payoff-based algorithms for convex games [ 34 ] . 1.1 Contribution Motivated by the relative scarcity of software packages for solving rather general classes of GNEPs and their application to game-theoretic control problems, in this paper we describe the mathematical formulations of our package NashOpt , a Python library for solving GNEPs based on satisfying the KKT conditions of each player jointly. The library supports nonlinear GNEPs, which are solved via nonlinear least-squares methods, and linear-quadratic GNEPs, which can be solved more efficiently to global optimality via mixed-integer linear programming (MILP) and can be used to enumerate multiple equilibria for the same game corresponding to different combinations of active constraints at optimality. We also address game-design problems, where a central authority can optimize some parameters of the game to achieve a desired equilibrium in accordance with the Single-Leader-Multi-Follower (SLMF) Stackelberg game setting [ 1 ] . Moreover, we leverage the GNE solution methods to solve game-theoretic control problems, including non-cooperative linear quadratic regulation (LQR) and model predictive control (MPC) problems [ 22 , 28 ] . The main purpose of the tool is to analyze and predict the effect of different agents pursuing their own objectives in a shared environment, and to design the game to promote desired equilibrium behaviors. For nonlinear GNEs, we leverage JAX [ 7 ] for automatic differentiation and just-in-time compilation to achieve high performance, and on the open-source MILP solver HiGHS [ 25 ] or Gurobi [ 21 ] for the linear-quadratic case, using the so-called “big-M” formulation to encode the complementary slackness conditions of the KKT system [ 24 , 18 ] . The library is open-source and available at https://github.com/bemporad/nashopt , and can be easily installed via pip install nashopt . 1.2 Notation We denote by \mathbb{R} the set of real numbers. Given N vectors x_{i}\in\mathbb{R}^{n_{i}} , i=1,\ldots,N , we denote by x=\mathop{\rm col}\nolimits(x_{1},\ldots,x_{N})\in\mathbb{R}^{n} their vertical concatenation, where n=\sum_{i=1}^{N}n_{i} . We denote by \mathbf{1} the vector of all ones of appropriate dimension, by I the identity matrix, and by e_{i} the i th column of I . Given a matrix A , we denote by A^{\top} its transpose and by \|A\|_{F} its Frobenius norm. 2 Problem Formulation Consider the following game-design problem based on a multiparametric generalized Nash equilibrium problem (GNEP) with N players: \begin{array}[]{rrl}\min_{p\in P}&J(x^{\star}(p),p)\\ \text{s.t. }&x_{i}^{\star}(p)\in\arg\min_{x_{i}}&f_{i}(x,p)\\ &\text{s.t. }&g(x,p)\leq 0\\ &&h(x,p)=0\\ &&\ell_{i}\leq x\leq u_{i}\\ &&x_{-i}=x_{-i}^{\star}(p)\\ &&i=1,\ldots,N\\ \end{array} (1) where x_{i}\in\mathbb{R}^{n_{i}} collects the decision variables optimized by agent i , i=1,\ldots,N , x_{-i} collects those of all other agents, x=\mathop{\rm col}\nolimits(x_{1},\ldots,x_{N})\in\mathbb{R}^{n} is the stacked vector of all agents’ decision variables, x^{\star}(p) is the generalized Nash equilibrium (GNE) of the game for a given parameter vector p\in\mathbb{R}^{n_{p}} , n_{p}\geq 0 , where by n_{p}=0 we mean that no parameter enters ( 1 ). In the sequel, we will also write x=(x_{i},x_{-i}) to highlight the dependence of x on x_{i} and x_{-i} . In ( 1 ), f_{i}:\mathbb{R}^{n}\to\mathbb{R} is the objective of agent i , g:\mathbb{R}^{n}\to\mathbb{R}^{n_{g}} and h:\mathbb{R}^{n}\to\mathbb{R}^{n_{h}} define, respectively, (shared) inequality and equality constraints, and \ell_{i}\in(\mathbb{R}\cup\{-\infty\})^{n_{i}} , u_{i}\in(\mathbb{R}\cup\{+\infty\})^{n_{i}} define the (local) box constraints for each player i . Moreover, J:\mathbb{R}^{n}\times\mathbb{R}^{n_{p}}\to\mathbb{R} is the objective function used to shape the desired equilibrium behavior of the game, and P\subseteq\mathbb{R}^{n_{p}} is a given feasible set for the parameter vector p , such as the hyper-box P=\{p\in\mathbb{R}^{n_{p}}:\ \ell_{p}\leq p\leq u_{p}\} where \ell_{p},u_{p} are (possibly infinite) bounds. Problem ( 1 ) is also referred to as an optimistic equilibrium of Single-Leader-Multi-Follower (Stackelberg) game [ 1 ] , with the leader optimizing p and the followers playing the GNEP parameterized by p . A GNE x^{\star}(p) is a vector where no agent can reduce their cost given the others’ strategies and feasibility constraints, i.e., f_{i}(x_{i}^{\star},x_{-i}^{\star},p)\leq f_{i}(x_{i},x_{-i}^{\star},p)\qquad\forall x_{i}\in X_{i}(x_{-i}^{\star},p) where X_{i}(x_{-i}^{\star},p)\subseteq\mathbb{R}^{n_{i}} is the feasible set of player i defined by the constraints in ( 1 ) given the strategies x_{-i}^{\star}(p) of the other players. We highlight special cases of ( 1 ) in the next sections. 2.1 Solving a specific GNEP To just solve a given game, we set J(x^{\star},p)\equiv 0 and P=\{p_{0}\} a singleton, leading to the standard GNEP: \begin{array}[]{rl}x_{i}^{\star}=\arg\min_{\ell_{i}\leq x_{i}\leq u_{i}}&f_{i}(x_{i},p_{0})\\ \text{s.t. }&g(x,p_{0})\leq 0,\ h(x,p_{0})=0\\ &x_{-i}=x_{-i}^{\star},\quad i=1,\ldots,N.\end{array} (2) 2.2 Finding a parameter vector for which a GNE exists If no specific equilibrium is desired, we can set J(x^{\star},p)\equiv 0 and let P be a non-singleton set, leading to the problem of finding a parameter vector p\in P for which an equilibrium exists. 2.3 Inverse game problem Given an observed agents’ equilibrium x_{\textrm{d}es} (or a desired one we wish to achieve), by setting J(x^{\star},p)=\|x^{\star}-x_{\rm des}\|_{2}^{2} , or J(x^{\star},p)=\|x^{\star}-x_{\rm des}\|_{\infty} or \|x^{\star}-x_{\rm des}\|_{1} , we solve the inverse game of finding a vector p (if one exists) such that x^{\star}\approx x_{\textrm{d}es} . 3 KKT Conditions and Nonlinear Least-Squares Formulation Let us assume that f_{i} , g , and h are continuously differentiable with respect to x_{i} and that suitable constraint qualifications hold, such as the Linear Independence Constraint Qualification (LICQ) condition at the GNE x^{\star}(p) 1 1 1 The LICQ condition is verified if the gradients of the active constraints at x^{\star}(p) \bigl\{\nabla_{x_{i}}g_{j}(x^{\star},p):j\in\mathcal{A}(x^{\star})\bigr\}\;\cup\;\bigl\{\nabla_{x_{i}}h_{k}(x^{\star},p)\bigr\}\;\cup\;\bigl\{\pm e_{k}:x_{i,k}^{\star}=\ell_{i,k}\text{ or }u_{i,k}\bigr\} are