Non-Normalized Solutions of Generalized Nash Equilibrium in Autonomous Racing
Mark Pustilnik, Antonio Loquercio, Francesco Borrelli · 2025
Read Non-Normalized Solutions of Generalized Nash Equilibrium in Autonomous Racing by Mark Pustilnik, Antonio Loquercio, Francesco Borrelli (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-2503-12002.txt.
Introduction
Mark Pustilnik, Antonio Loquercio, and Francesco Borrelli study game-theoretic equilibria in autonomous racing, in a two thousand twenty-five paper. When racing cars share track constraints, their joint behavior is modeled as a generalized Nash equilibrium. The standard way to compute one assumes every player shares identical multipliers for the shared constraints.
That normalized assumption, the authors show, throws away other valuable equilibria. A simple racing example exposes the shortcoming clearly. They then build a method based on the mixed complementarity problem to find non-normalized equilibria. Tests in realistic racing scenarios show richer, multi-modal interactions between cars. The approach widens the set of strategies race planners can consider.
Catalog record
| CREATOR | Mark Pustilnik, Antonio Loquercio, Francesco Borrelli |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-12002
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Non-Normalized Solutions of Generalized Nash Equilibrium in Autonomous Racing Mark Pustilnik, Antonio Loquercio, Francesco Borrelli Abstract In dynamic games with shared constraints, Generalized Nash Equilibria (GNE) are often computed using the normalized solution concept, which assumes identical Lagrange multipliers for shared constraints across all players. While widely used, this approach excludes other potentially valuable GNE. This paper addresses the limitations of normalized solutions in racing scenarios through three key contributions. First, we highlight the shortcomings of normalized solutions with a simple racing example. Second, we propose a novel method based on the Mixed Complementarity Problem (MCP) formulation to compute non-normalized Generalized Nash Equilibria (GNE). Third, we demonstrate that our proposed method overcomes the limitations of normalized GNE solutions and enables richer multi-modal interactions in realistic racing scenarios. I Introduction Computing a Nash Equilibrium (NE) in a Dynamic Game (DG) is a well-established concept. In DGs, players often share constraints, making each player’s feasible strategy set dependent on others’ strategies. This extends the problem to a Generalized Nash Equilibrium Problem (GNEP). NE serves as a fundamental tool for analyzing competitive behavior across various domains, including economics [ 1 ] and racing [ 2 , 3 ] . In general, the existence or uniqueness of a GNE is not guaranteed. We are interested in problems where GNEPs admit multiple solutions. The standard approach for solving GNEPs is to derive and combine the Karush-Kuhn-Tucker (KKT) conditions for each player’s optimization problem [ 4 ] . When shared constraints exist, the Lagrange multipliers associated with these constraints are typically assumed to be identical for all players. This concept, known as the “normalized solution”, was introduced by Rosen [ 5 ] , who demonstrated its existence and uniqueness under specific conditions. This solution also arises from reformulating the DG as a Quasi Variational Inequality (QVI) problem. Harker [ 6 ] and others [ 7 ] further showed that this reformulation reduces the solution set to the normalized solution, provided it exists. The normalized solution is widely adopted in various applications, including racing [ 2 , 8 , 3 ] , economics [ 9 ] , and traffic systems [ 10 ] , and has become the standard approach for solving DGs due to its computational, numerical, and conceptual advantages. Despite these benefits, the normalized solution may not always capture the complexity of real-world interactions, where other GNEs could better represent asymmetric or more intuitive behavior. However, computing non-normalized GNEs is challenging. Standard approaches to solving GNEPs, such as reformulating the KKT conditions as a QVI is inherently bias toward normalized solutions [ 7 ] . Reformulating the problem as Mixed Complementarity Problem (MCP) is practically also biased toward the normalized solution. In fact many numerical solvers converge to normalized solutions even when no such constraint is imposed on the solution space. This paper tackles these limitations through three key contributions: 1) highlights limits of normalized solutions in racing scenarios with a simple example, 2) Proposing a method that extends the MCP framework to calculate non-normalized GNEs and 3) show that the propose method overcome such limitations and generates interesting multi modal interactions in realistic racing scenarios. II Problem Formulation Given M players, each player i\in\{1,...,M\} controls the variables x^{i}\in\mathbb{R}^{n_{i}} . The vector x\in\mathbb{R}^{n} is formed by concatenating all the players’ decision variables: x:=[(x^{1})^{T},...,(x^{M})^{T}]^{T} (1) where n:=\sum^{M}_{i=1}n_{i} . x^{-i} represent the decision variables of all players except player i . To emphasize the decision variables of player i within x we write (x^{i},x^{-i}) instead of x . The aim of player i is to choose the x^{i} which minimizes its own cost function J_{i}(x^{i},x^{-i}) refer to such decision as strategy . The feasible set of the i -th decision depends on the strategies of the other players: \min_{x^{i}}{J_{i}(x^{i},x^{-i})}\quad\text{subject to}\quad x^{i}\in\mathcal{X}_{i}(x^{-i})\subseteq\mathbb{R}^{n_{i}} (2) The feasible set of each player can be represented in the following form: \displaystyle\mathcal{X}_{i}(x_{-i}) \displaystyle:=\{x_{i}\in\mathbb{R}^{n_{i}}|h_{i}(x_{i})=0, \displaystyle,g_{i}(x_{i})\leq 0,s(x_{i},x_{-i})\leq 0\} (3) where, h_{i}:\mathbb{R}^{n_{i}}\to\mathbb{R}^{k_{i}} defines private equality constraints that depend only on player i ’s strategy, g_{i}:\mathbb{R}^{n_{i}}\rightarrow\mathbb{R}^{m_{i}} defines the private inequality constraints of player i that depends only on player i ’s strategy. s:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m_{0}} defines the shared constraints that depends on the strategies of all players and shared by all players. The solution set of problem ( 2 ) for player i is denoted by \mathcal{S}_{i}(\bar{x}^{-i}) . The Generalized Nash Equilibrium Problem (GNEP) is the problem of finding vector \bar{x} such that: \bar{x}^{i}\in\mathcal{S}_{i}(\bar{x}^{-i})\quad\forall i\in\{1,...,M\} (4) A solution to the GNEP is the GNE. A GNE is the set of strategies that characterized by the fact that none of the players can improve unilaterally it’s cost function by changing its strategy in a feasible direction. Furthermore, it is typical to assume the following assumptions (Rosen’s setting [ 5 ] ): (i) set \mathcal{X}\subset\mathbb{R}^{n} is convex and compact. (ii) Function g_{i}:\mathbb{R}^{n}\rightarrow\mathbb{R},i=1,...,M and s:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m_{0}} are convex and continuously differentiable. (iii) The cost function of every player J_{i}(x^{i},x^{-i}) is continuously differentiable in x\in\mathcal{X} . (iv) The cost function of every player J_{i}(x^{i},x^{-i}) is pseudo-convex in x^{i} for every given x^{-i} . Define the Lagrangian function for each player as: \displaystyle\mathcal{L}_{i}:=J_{i}(x^{i} \displaystyle,x^{-i})+\mu_{i}^{T}h_{i}(x^{i})+ \displaystyle+\lambda_{i}^{T}\cdot g_{i}(x^{i})+\sigma_{i}^{T}s(x^{i},x^{-i}) (5) where, \mu_{i}\in\mathbb{R}^{k_{i}} are the Lagrange multipliers of the equality constraints of player i , \lambda_{i}\in\mathbb{R}_{+}^{m_{i}} and \sigma_{i}\in\mathbb{R}_{+}^{m_{0}} are the Lagrange multipliers of the private and shared inequality constraints of player i respectively. For a point x\in\mathcal{X} to be a GNE, the following KKT conditions have to be satisfied: \begin{split}&\nabla_{x^{i}}\mathcal{L}_{i}=0,\quad\forall i=1,...,M\\ &0\leq\lambda_{i}\perp g_{i}\leq 0,\quad\forall i=1,...,M\\ &0\leq\sigma_{i}\perp s\leq 0,\quad\forall i=1,...,M\\ &\lambda_{i}\geq 0,\sigma_{i}\geq 0\quad\forall i=1,...,M\\ &h_{i}=0,\quad\forall i=1,...,M\\ \end{split} (6) To determine the Generalized Nash Equilibrium (GNE) in a Generalized Nash Equilibrium Problem (GNEP), we rely on certain conditions. Specifically, assuming that a suitable Constraint Qualification (CQ) holds—such as Slater’s condition or linear independence CQ—the authors in [ 4 , 11 , 12 ] proved that : • If a set of variables (\bar{x},\{\bar{\mu}_{i}\}_{i=1}^{N},\{\bar{\lambda}_{i}\}_{i=1}^{N},\{\bar{\sigma}_{i}\}_{i=1}^{N}) satisfies the Karush-Kuhn-Tucker (KKT) conditions, then \bar{x} is a solution to the GNEP. • Conversely, if \bar{x} is indeed a solution to the GNEP, then there exists a corresponding set of Lagrange multipliers (\{\bar{\mu}_{i}\}_{i=1}^{N},\{\bar{\lambda}_{i}\}_{i=1}^{N},\{\bar{\sigma}_{i}\}_{i=1}^{N}) that satisfy the KKT conditions when evaluated at x=\bar{x} . In other words, solving for the GNE can be done by checking the KKT conditions, and any valid GNE must have an associated set of multipliers that satisfies these conditions. III Solutions To The GNEP Rosen introduced the concept of the normalized solution for the Generalized Nash Equilibrium Problem (GNEP) in [ 5 ] . Under the previously stated assumptions, the normalized solution corresponds to a scenario where the Lagrange multipliers associated with the shared constraints are identical for all players: \sigma^{1}=\dots=\sigma^{N}=\sigma. (7) Rosen showed that a unique normalized solution exists under the specified conditions. Subsequent works, including [ 6 , 7 ] , showed that reformulating the GNEP as a Quasi-Variational Inequality (QVI) problem inherently reduces the solution set to the normalized solution [ 7 ] . While having many numerical advantages, and of-the-shelves numerical solver that can be used, loosing is a byproduct that is unavoidable in his approach. As a result, the normalized solution has become the de facto standard in solving GNEPs, to the extent that many works do not explicitly mention this assumption . A popular method to calculate the normalized solution is by reformulating the GNEP to a