# Learning Rationality in Potential Games

Stefan Clarke ID 1, Gabriele Dragotto ID 1, Jaime Fernández Fisac ID 2,
and Bartolomeo Stellato ID 1
1 Department of Operations Research and Financial Engineering, Princeton
University
2 Department of Electrical and Computer Engineering, Princeton University

###### Abstract

We propose a stochastic first-order algorithm to learn the _rationality_
parameters of simultaneous and non-cooperative potential games, i.e., the
parameters of the agents’ optimization problems. Our technique combines (i.)
an active-set step that enforces that the agents play at a Nash equilibrium
and (ii.) an implicit-differentiation step to update the estimates of the
rationality parameters. We detail the convergence properties of our algorithm
and perform numerical experiments on Cournot and congestion games, showing
that our algorithm effectively finds high-quality solutions (in terms of out-
of-sample loss) and scales to large datasets.

##  1 Introduction

Decision-making is rarely an individual task; on the contrary, it often
involves several self-driven interacting agents. Non-cooperative game theory
provides the ideal playground to model the outcome of multi-agent decision-
making. Among these outcomes, the most popular one for _non-cooperative_ and
_simultaneous_ games is arguably the Nash equilibrium [20]. Intuitively,
whenever the game’s agents play Nash equilibrium strategies, no agent has the
incentive to deviate to another strategy, and the multi-agent system is
stable. Monderer and Shapley [19] proved that Nash equilibria are guaranteed
to exist in _potential_ games, a large subclass of non-cooperative and
simultaneous games; specifically, if the _rationality parameters_ of a
potential game, i.e., the parameters describing the agents’ payoffs and
strategy sets, are common information and observable, there always exists a
Nash equilibrium that is an extremum of a so-called _potential function_.
Several games with practical applications can be modeled as _potential games_
, for example, congestion games, Cournot games [19], and certain urban driving
games [26].

However, the agents’ self-driven behavior frequently conflicts with the
greater societal goals; in such cases, external regulators (e.g., governments)
can intervene in the agents’ interaction via incentives, laws, and
regulations. For instance, the transportation company of a large city adds or
remove subway rides starting from its understanding of the commuters’
preferences. Therefore, accurately estimating the rationality parameters as a
proxy of the agents’ behavior is arguably the most critical ingredient for
deploying effective regulatory interventions. In the specific case of
potential games, if the external regulator can directly observe the
rationality parameters, any extrema of the potential function is a Nash
equilibrium. Assuming that the regulator can directly observe such rationality
parameters is, however, rather unrealistic; in several contexts, these
parameters are often unknown and not directly observable. Although the
rationality parameters are seldom observable, outcomes such as Nash equilibria
are often observable through data. The observability of outcomes, as opposed
to the observability of the rationality parameters, is the starting assumption
of the techniques we present here. In this paper, we propose an algorithm that
learns the rationality parameters starting from some data containing the
outcomes (i.e., Nash equilibria) of the past agents’ interactions. Our
algorithm enables external regulators to learn the agents’ rationality
parameters from data to deploy effective regulatory interventions. We assume
that each agent solves a convex quadratic optimization problem parametrized in
some unknown _rationality_ parameters and some _context_ parameters (e.g.,
some observable environmental conditions), and, further, that there exists a
convex quadratic potential function in the agents’ variables.

The majority of the learning literature focused on the problem of learning the
optimal strategy from the perspective of the agents [6, 11, 14, 15]. In this
paper, we study the less explored topic of learning the rationality parameters
from the perspective of an external regulator, as in [8, 16, 12, 5, 2]. In
contrast with the previous literature, our algorithm:  (a.) learns rationality
parameters that induce _exact_ and _exact generalized_ Nash equilibria,
instead of approximate equilibria or Nash equilibria [16, 12, 5], and  (b.) is
an _anytime_ algorithm, i.e., the intermediate estimates always induce exact
Nash equilibria, as opposed to [8, 16, 12, 5, 2], and  (c.) learns both the
agents’ utilities and constraints, as opposed to only utilities [8], and  (d.)
scales to high-dimensional datasets.  We summarize our contributions as
follows:

  1. 1.

We propose a stochastic active-set-based first-order algorithm to learn the
rationality parameters of the agents of a potential game given a dataset of
past observed equilibria and context parameters.

  2. 2.

We provide a detailed analysis of the asymptotic convergence properties of our
algorithm.

  3. 3.

We showcase the effectiveness and efficiency of our algorithm via
computational experiments on Cournot and congestion games.

The code associated with this work is available at
https://github.com/stellatogrp/learning_rationality_in_potential_games.

##  2 Related work

#### Learning in games.

The majority of the learning literature focuses on the problem of learning
optimal strategies from the perspective of the agents [6, 11, 14, 15]. These
approaches are useful to determine suitable agent strategies, yet it is hard
to use these techniques to determine how to correctly _intervene_ in the game
to achieve a specific purpose. In this paper, we study the less explored topic
of learning the parameters of the game, i.e., affecting the utilities and the
strategies of the agents, from the perspective of an external observer [8]. In
contrast with [23, 17, 24], our approach does not employ normal or extensive-
form formulations. Instead, we let each agent decide their strategy by solving
a parametrized optimization problem, as in [9, 7]. Furthermore, compared to
[8], we allow agents to have individual constraints parametrized in both
rationality and context parameters.

#### Inverse equilibrium.

Our work is closely related to the _inverse equilibrium problem_ , i.e., the
problem using data to estimate the parameters affecting the game. Several
works tackle these problems using variational inequalities [5] and implicit
neural networks [12], with applications in reinforcement learning [21],
decision making [25], and motion planning [18]. However, these works often do
not scale up to large datasets and do not provide anytime algorithms. In
contrast, our method models the inverse learning task as a (nonconvex
quadratic) optimization problem, and, in this sense, it is closer to [1] in
the context of learning the parameters of convex optimization models.
Similarly to [13], we employ a complementarity problem for our learning task;
however, our algorithm enforces exact complementarity at each iteration
whereas [13] incorporates it as a violation-based penalty function.

##  3 Problem formulation

We consider a class of potential games among $n$ solving optimization problems
as in Definition 3.1. We assume there are known and observable context
parameters $\mu$, and some unknown rationality parameters $\theta$ which we
seek to infer.

######  Definition 3.1 (Mathematical programming game).

Let $\theta\in{\mbox{\bf R}}^{p}$ be the vector of rationality parameters, and
$\mu\in{\mbox{\bf R}}^{k}$ be the vector of context parameters. We consider a
_non-cooperative_ and _simultaneous_ game among $n$ agents such that each
agent $i=1,\dots,n$ solves the (parametrized) optimization problem

$\begin{array}[t]{ll}\underset{x_{i}\in{\mbox{\bf R}}^{m}}{\text{\rm
minimize}}&u_{i}(x_{i};x_{-i},\theta,\mu)\\\ \text{\rm subject
to}&B_{i}(\theta,\mu)x_{i}+D_{i}(\theta,\mu)x_{-i}\leq
b_{i}(\theta,\mu),\end{array}$ (1)

where $x\in{\mbox{\bf R}}^{mn}$ is the strategy profile made of the decisions
of all players, including other agents’ decisions $x_{-i}$ and the decisions
$x_{i}$ of $i$; $B_{i}(\theta,\mu)\in{\mbox{\bf R}}^{l\times m}$,
$D_{i}(\theta,\mu)\in{\mbox{\bf R}}^{l\times(n-1)m}$ and
$b_{i}(\theta,\mu)\in{\mbox{\bf R}}^{l}$; and $u_{i}(x_{i};x_{-i},\theta,\mu)$
is a convex quadratic function in both $x_{i}$ and $x_{-i}$.

Without loss of generality, each agent controls $m$ variables, and, given the
other agents’ choices and parameters $\mu$, $\theta$, it optimizes a convex
quadratic function subject to polyhedral constraints. We say that $x^{\star}$
is a (generalized) Nash equilibrium of 1 if it satisfies Definition 3.2.

######  Definition 3.2 (Nash equilibrium).

A strategy profile $x^{\star}=(x^{\star}_{1},\dots,x^{\star}_{n})$ is a Nash
equilibrium for some given $\theta$ and $\mu$ if, for any agent $i$,
$u_{i}(x^{\star}_{i};x^{\star}_{-i},\theta,\mu)\leq
u_{i}(x_{i};x^{\star}_{-i},\theta,\mu)$ for any
$x_{i}\in\\{B_{i}(\theta)x_{i}+D_{i}(\theta)x_{-i}\leq b_{i}(\theta)\\}$.

We assume that the game is potential as in Definition 3.3.

######  Definition 3.3 (Potential game).

A game of the form 3.1 is a potential game if there exists a function
$\Phi(x;\theta,\mu)$ such that $x^{\star}$ is a Nash Equilibrium of the game
if and only if $x^{\star}$ is the optimal solution of

$\begin{array}[]{ll}\underset{x\in{\mbox{\bf R}}^{mn}}{\text{\rm
minimize}}&\Phi(x;\theta,\mu)\\\ \text{\rm subject
to}&B_{i}(\theta,\mu)x_{i}+D_{i}(\theta,\mu)x_{-i}\leq b_{i}(\theta,\mu)\\\
&\hfill i=1,\dots,n.\end{array}$ (2)

We assume that the potential function $\Phi(x;\theta,\mu)$ is a convex
quadratic function in $x$. Let $R$ and $c$ be a matrix and a vector of
appropriate dimensions, respectively. Then,

$\displaystyle\Phi(x;\theta,\mu)$
$\displaystyle=(1/2)x^{T}R(\theta,\mu)x+c(\theta,\mu)^{T}x.$

Let the complementarity operator $\clubsuit\perp\spadesuit$ be equivalent to
$\clubsuit^{\top}\spadesuit=0$. By taking the Karush–Kuhn–Tucker conditions of
the problem of Definition 3.3, a vector $x^{\star}$ is a Nash equilibrium if
and only if there exists a $\lambda^{\star}$ such that

$\displaystyle
0=R(\theta,\mu)x^{\star}+c(\theta,\mu)+A(\theta,\mu)^{T}\lambda^{\star},$
$\displaystyle 0\leq
b(\theta,\mu)-A(\theta,\mu)x^{\star}\perp\lambda^{\star}\geq 0,$

where we define $A(\theta,\mu)$ to be such that the inequality $0\leq
b(\theta,\mu)-A(\theta,\mu)x$ is equivalent to
$B_{i}(\theta,\mu)x_{i}+D_{i}(\theta,\mu)x_{-i}\leq b_{i}(\theta,\mu)$ for
every agent $i=1,\dots,n$.

##  4 Our method

In this section, we describe the fundamental ingredients for our learning
algorithm. Given a dataset
$\mathcal{D}=\\{(\bar{x}^{k},\bar{\mu}^{k})\\}^{K}_{k=1}$ where the agents
play Nash equilibria $\bar{x}^{k}$ for every $k=1,\dots,K$, our algorithm
learns the parameters $\theta$ such that each $(\bar{x}^{k},\bar{\mu}^{k})$ is
as close to a Nash equilibrium as possible, e.g., so that the data
$\mathcal{D}$ minimizes the prediction-based loss function with respect to the
Nash equilibria induced by $\theta$. For each datapoint $k\in\\{1,\dots,K\\}$,
let $x^{k}=x^{k}(\theta,\bar{\mu}^{k})$ be the Nash equilibrium induced by
some parameters $\theta\in\Theta$, where $\Theta$ is the space of the
rationality parameters. We will consider the loss function over $\mathcal{D}$
given by,

${\textstyle\mathcal{L}(\theta;\mathcal{D})=(1/|\mathcal{D}|)\sum_{\bar{x}^{k}\in\mathcal{D}}\parallel
x^{k}-\bar{x}^{k}\parallel^{2}_{2}.}$ (3)

To compute the points $x^{k}$, we devise a bilevel problem enforcing that
$x^{k}$ is a Nash equilibrium given $\theta$.

###  4.1 Bilevel formulation

For the given data $\mathcal{D}$, and set of possible parameters $\Theta$, we
aim to find the parameters $\theta\in\Theta$ that minimize, for each
$k=1,\dots,K$, the squared $L_{2}$-norm of $x^{k}-\bar{x}^{k}$. Equivalently,
we aim to find the $\theta$ that solves the optimization problem

$\displaystyle\\!\\!\\!\\!\underset{x^{k},\lambda^{k},\theta}{\text{\rm
minimize}}\\!\\!\\!\quad$
$\displaystyle\textstyle(1/K)\sum_{k=1}^{K}\|x^{k}-\bar{x}^{k}\|^{2}_{2}$ (4a)
subject to $\displaystyle
0=R(\theta,\bar{\mu}^{k})x^{k}+c(\theta,\bar{\mu}^{k})+A(\theta,\bar{\mu}^{k})^{T}\lambda^{k},$
$\displaystyle 0\leq
b(\theta,\bar{\mu}^{k})-A(\theta,\bar{\mu}^{k})x^{k}\perp\lambda^{k}\geq 0$
$\displaystyle x^{k}\in{\mbox{\bf R}}^{mn},\lambda^{k}\in{\mbox{\bf
R}}^{ln}_{+}\quad k=1,\dots,K,$ (4b) $\displaystyle\theta\in\Theta.$ (4c)

The variables $x^{k}\in{\mbox{\bf R}}^{nm}$ and $\lambda^{k}\in{\mbox{\bf
R}}^{ln}_{+}$ are the strategy profile and the dual variables associated with
the agents’ optimization problem, respectively, while $\theta$ are the
variables associated with the rationality parameters. In 4b, we enforce that
the strategy profiles $x$ are Nash equilibria of the game induced by $\theta$
and the game parameters $\bar{\mu}$. In 4a, we minimize the average over data
points of the squared $L_{2}$-distance between each data point $\bar{x}^{k}$
and $x^{k}$. The optimization problem 4 is nonconvex due to the
complementarity constraints. We can obtain an equivalent formulation by
explicitly setting either the LHS or the RHS of the complementarity
constraints 4b to $0$. For each data point $k$, we define an _active-set_
$Z^{k}\subseteq\\{1,\dots,lm\\}$, i.e., the set of indices of tight
complementarity constraints; whenever $z\in Z^{k}$, the $z$-th constraint
$b(\theta,\bar{\mu}^{k})_{z}-A(\theta,\bar{\mu}^{k})_{z}x^{k}=0$ (is tight).
Otherwise, if $z\notin Z^{k}$, then $\lambda^{k}_{z}=0$. For a given active-
set $Z^{k}$, let $Y^{k}$ be its complement. Then, problem 4 is equivalent to
the following minimization problem over $Z^{k},x^{k},\lambda^{k},\theta$,

minimize $\displaystyle\textstyle(1/K)\sum_{k=1}^{K}\parallel
x^{k}-\bar{x}^{k}\parallel^{2}_{2}$ (5a) subject to $\displaystyle
0=R(\theta,\bar{\mu}^{k})x^{k}+c(\theta,\bar{\mu}^{k})+A(\theta,\bar{\mu}^{k})^{T}\lambda^{k},$
(5b) $\displaystyle 0\leq
b(\theta,\bar{\mu}^{k})-A(\theta,\bar{\mu}^{k})x^{k},\quad\lambda^{k}\geq 0,$
(5c) $\displaystyle
0=b(\theta,\bar{\mu}^{k})_{Z^{k}}-A(\theta,\bar{\mu}^{k})_{Z^{k}}x^{k},\;0=\lambda^{k}_{Y^{k}},$
(5d) $\displaystyle x^{k}\in{\mbox{\bf R}}^{mn},\lambda^{k}\in{\mbox{\bf
R}}^{ln}_{+},\quad k=1,\dots,K,$ $\displaystyle\theta\in\Theta,$

where we use the subscript $Z^{k}$ to refer to the set of constraints with
indices contained in $Z^{k}\subseteq\\{1,\dots,lm\\}$, and $Y^{k}=\\{1,\dots
lm\\}\backslash Z^{k}$. In 5c, we relax the complementarity constraints of 4b
by enforcing non-negativity on both the LHS and RHS involved in the
complementarity constraints; in 5d, we enforce the tightness conditions on the
active-sets $Z^{k}$ for any $k$. Although 5 does not include any
complementarity constraints, it involves exponentially many choices of $Z^{k}$
for any $k$. However, given some fixed $Z=(Z^{1},\dots,Z^{k})$, we can employ
5 to formulate the loss function 3 and devise a differentiation method to
iteratively refine the estimates of $\theta$.

#### Implicit differentiation of the loss function.

For any fixed $Z$, we aim to find a global minimum of 5 with a first-order
method. To do so, we will exploit the gradient information of the loss
function 3 associated with problem 5. Let
$x^{k}=x^{k}_{Z^{k}}(\theta,\bar{\mu}^{k})$ (we omit $Z^{k}$ when the context
is clear) be implicitly defined as

$\displaystyle F(x^{k},\lambda^{k})$
$\displaystyle=\begin{bmatrix}R(\theta,\bar{\mu}^{k})x^{k}+c(\theta,\bar{\mu}^{k})+A(\theta,\bar{\mu}^{k})^{T}\lambda^{k}\\\
b(\theta,\bar{\mu}^{k})_{Z^{k}}-A_{Z}x^{k}\\\ \lambda_{Y^{k}}\end{bmatrix}=0,$

i.e., $x^{k}$ solves $0=F(x^{k},\lambda^{k})$, or, in other words, $x^{k}$ is
a Nash equilibrium given $Z$. Therefore, for a given active-set $Z$, we
reformulate the loss function 5 over $\mathcal{D}$ as

${\textstyle\mathcal{L}(\theta,Z;\mathcal{D})=(1/|\mathcal{D}|)\sum_{\bar{x}^{k}\in\mathcal{D}}\parallel
x_{Z^{k}}^{k}-\bar{x}^{k}\parallel^{2}_{2}.}$ (6)

We evaluate the gradient of $\mathcal{L}(\theta,Z;\mathcal{D})$ with respect
to $\theta$ as

$\displaystyle{\textstyle\\!\\!\\!\\!\\!\\!\nabla_{\theta}\mathcal{L}(\theta,Z;\mathcal{D})=\\!(1/|\mathcal{D}|)\sum_{\bar{x}^{k}\in\mathcal{D}}2\nabla_{\theta}(x_{Z^{k}}^{k})^{T}(x_{Z^{k}}^{k}-\bar{x}^{k}).}$
(7)

Equivalently, we can compute 7 by employing the implicit function theorem [3,
Theorem 1B.1], as in Theorem 4.1.

######  Theorem 4.1 (Implicit function theorem).

Let $G(\lambda)$ be implicitly defined by the relation $0=H(x,\lambda)$ for
$H:{\mbox{\bf R}}^{d_{1}}\times{\mbox{\bf R}}^{d_{2}}\mapsto{\mbox{\bf
R}}^{d_{1}}$. Assume  1. $H$is continuously differentiable in a neighborhood
of $(x_{0},\lambda_{0})$,  2. $F(x_{0},\lambda_{0})=0$, and  3.
$\nabla_{x}H(x_{0},\lambda_{0})$is nonsingular.  Then, $G$ is continuously
differentiable in a neighborhood of $(x_{0},\lambda_{0})$ with Jacobian,

$\nabla_{\lambda}G(\lambda)=\nabla_{x}H(x_{0},\lambda_{0})^{-1}\nabla_{\lambda}H(x_{0},\lambda_{0}).$

Following Theorem 4.1, in 5, for a given datapoint $k$, $H(x,\lambda)$
corresponds to

$\begin{bmatrix}R(\theta,\bar{\mu}^{k})&A(\theta,\bar{\mu}^{k})^{T}\\\
-A(\theta,\bar{\mu}^{k})_{Z^{k}}&0\\\
0&I_{Y^{k}}\end{bmatrix}\begin{bmatrix}x_{k}\\\
\lambda_{k}\end{bmatrix}-\begin{bmatrix}c(\theta,\bar{\mu}^{k})\\\
b_{Z^{k}}(\theta,\bar{\mu}^{k})\\\ 0\end{bmatrix}.$ (8)

In practice, this theorem allows us to differentiate the loss function 6 with
respect to $\theta$ for any active set $Z$ of 5.

###  4.2 The algorithm

We employ the ingredients of Sections 4.1 and 4.1 to create a stochastic
first-order method to learn the parameters $\theta$ given the dataset
$\mathcal{D}$. We formalize our approach in Algorithm 1. Given an instance of
a game of Definition 3.1, the dataset $\mathcal{D}$, a maximum number of
iterations $T$, and a series of learning rates $\\{\eta_{t}\\}_{t=1}^{T}$, the
algorithm returns the estimated rationality parameters $\theta_{T}$.

Algorithm 1 Active-set algorithm

0: The data $\mathcal{D}=\\{(\bar{x}^{k},\bar{\mu}^{k})\\}^{K}_{k=1}$, the
maximum number of iterations $T$, and step sizes $\\{\eta_{t}\\}_{t=1}^{T}$

1: Initialize $\theta_{0}$

2: for $t=0,\dots,T-1$ do

3: Choose $(\bar{x}^{k},\bar{\mu}^{k})$ uniformly from $\mathcal{D}$

4: $x^{(t)},\lambda^{(t)}\leftarrow$ primal and dual variables from 2

5:
$Z^{(t)}\leftarrow\\{z:b(\theta^{(t)},\bar{\mu}^{k})_{z}-A(\theta^{(t)},\bar{\mu}^{k})_{z}x^{(t)}=0\\}$

6: $Y^{(t)}\leftarrow\\{z:\lambda^{(t)}_{z}=0\\}$

7: Set
$\mathcal{L}_{t}(x)\leftarrow\mathcal{L}(\theta^{(t)},Z^{(t)};\\{\bar{x}^{k}\\})$

8:
$\nabla_{\theta}\mathcal{L}_{t}(x^{(t)})=\nabla_{\theta}(x^{(t)}(\theta^{(t)}))^{T}\nabla_{x}\mathcal{L}_{t}(x^{(t)}(\theta^{(t)}))$

9:
$\theta^{(t+1)}\leftarrow\theta^{(t)}-\eta_{t}\nabla_{\theta}\mathcal{L}_{t}(x^{(t)})$

10: end for

11: return $\theta^{(T)}$

After initializing $\theta^{(0)}$ (line 1), at each step $t$, the algorithm
picks a random datapoint $(\bar{x}^{k},\bar{\mu}^{k})$ from $\mathcal{D}$ with
uniform probability (line 3). Given $(\bar{x}^{k},\bar{\mu}^{k})$, the
algorithm solves the optimization problem in line 2 to compute $x^{(t)}$ and
$\lambda^{(t)}$, with $x^{(t)}$ being a Nash equilibrium of the game induced
by $\theta^{(t)}$ and $\bar{\mu}^{k}$ (line 4). Let
$Z^{(t)}=\\{z:b(\theta^{(t)},\bar{\mu}^{k})_{z}-A(\theta^{(t)},\bar{\mu}^{k})_{z}x^{(t)}=0\\}$
be the active-set at $x^{(t)}$, and $Y^{(t)}=\\{z:\lambda_{z}^{(t)}=0\\}$
(lines 5 and 6). On the one hand, if $Z^{(t)}\cap Y^{(t)}=\emptyset$, i.e.,
there is no degeneracy in the complementarities, then the matrix in Step 8 is
invertible. We can obtain the gradient of $x^{(t)}$ with respect to
$\theta^{(t)}$ using Theorem 4.1 (line 8). We use this gradient information to
update the estimates for $\theta^{(t)}$ to reduce the loss proportionally to
$\eta_{t}$, and we continue to iterate (line 9). On the other hand, if
$Z^{(t)}\cap Y^{(t)}\neq\emptyset$, we have a degenerate solution. In the
following subsection, we explain how to retrieve gradient information in
degenerate active-sets. When the algorithm reaches its iteration limit, it
returns the last estimate $\theta^{(T)}$.

#### Degenerate active-set.

Whenever, at some step $t$, $Z^{(t)}\cap Y^{(t)}\neq\emptyset$, we cannot
obtain the gradient from 8 since the matrix is not invertible. This implies we
must choose an alternative non-degenerate active-set on which we evaluate the
gradient 7. We do so using the following rule, which is motivated by the
theory in Section 5.

######  Rule 1.

Suppose we are at iteration $t$ of Algorithm 1, $Z^{(t)}\cap
Y^{(t)}\neq\emptyset$. Let $W^{(t)}=Z^{(t)}\cap Y^{(t)}$. Randomly and
uniformly partition $W(t)$ into two sets, $W_{1}^{(t)}$ and $W_{2}^{(t)}$. Let
$\tilde{Z}^{(t)}=Z^{(t)}\backslash W_{1}^{(t)}$ and
$\tilde{Y}^{(t)}=Y^{(t)}\backslash W_{2}^{(t)}$. Use
$\mathcal{L}_{t}(x)\leftarrow\mathcal{L}(\theta^{(t)},\tilde{Z}^{(t)};\\{x_{k}\\})$
in Step 7 of Algorithm 1.

Essentially, in the presence of degeneracy, Rule 1 randomly partitions the
intersection (i.e.the elements causing the degeneracy) of $Z$ and $Y$ and uses
this active-set to update the gradient in Step 8.

##  5 Convergence analysis

In this section, we will provide a proof of the convergence behavior of
Algorithm 1. In particular, we will prove that a smoothed version of the
gradient of the loss with respect to $\theta^{(t)}$ at iteration $t$ converges
to zero (Theorem 5.1). For notational simplicity, we will let $A(\theta,\mu)$
be $A$. First, for any $\theta$ and any non-degenerate active-set $Z$ (i.e.,
$Z\cap Y=\emptyset$), 6 provides an explicit expression for
$\nabla_{\theta}\mathcal{L}(\theta;Z,\\{\bar{x}_{k}\\})$ at any point
$\bar{x}_{k}\in\mathcal{D}$. Specifically,
$\nabla_{\theta}\mathcal{L}(\theta;Z,\mathcal{D})$ is given by,

$\displaystyle\nabla_{\theta}\mathcal{L}(\theta;Z,\mathcal{D})$
$\displaystyle=\frac{2}{|\mathcal{D}|}\sum_{k=1}^{K}S_{k}(Z_{k},\theta)^{-T}\begin{bmatrix}x^{k}_{Z_{k}}-\bar{x}^{k}\\\
0\end{bmatrix},$ $\displaystyle S_{k}(Z_{k},\theta)$
$\displaystyle=\begin{bmatrix}R(\theta,\bar{\mu}^{k})&A^{T}\\\ -A_{Z_{k}}&0\\\
0&I_{Y_{k}}\end{bmatrix},$

and the $j$-th row of the Hessian
$\nabla^{2}\mathcal{L}(\theta,Z,\mathcal{D})_{j}$ is given by,

$\frac{2}{|\mathcal{D}|}\sum_{k=1}^{K}S_{k}(Z_{k},\theta)^{-T}\partial_{\theta_{j}}S_{k}(Z_{k},\theta)S_{k}(Z_{k},\theta)^{-T}\begin{bmatrix}x^{k}_{Z_{k}}-\bar{x}^{k}\\\
0\end{bmatrix}.$

To prove our result, we will assume the following.

######  Assumption 1 (Constraint qualifications).

.

  1. 1.

The linear independence constraint qualifications (LICQs) holds for the set
$\\{x\mid b(\theta,\bar{\mu}^{k})-Ax\geq 0\\}$ for every $\theta\in\Theta$,
and $k=1\dots K$, and

  2. 2.

the set $\\{x\mid Ax\leq b(\theta,\mu)\\}$ is uniformly bounded in $x$ for all
$\theta$, $\mu$.

######  Assumption 2 (Well-behaved derivatives).

.

  1. 1.

there exists an $L_{0}>0$ such that,
$\|S_{k}(Z_{k},\theta)^{-T}\|_{\infty}<L_{0}$ for every
$\theta\in\Theta,Z_{k}\subseteq\\{1,2,\dots,lm\\}$ and $k=1,\dots,K$,

  2. 2.

for almost all $\theta\in\Theta$ (in the Lebesgue-measure sense),
$Z_{k}(\theta)\cap Y_{k}(\theta)=\emptyset$ for every $k=1\dots K$, and

  3. 3.

the function $\partial_{\theta_{j}}R(\theta,\bar{\mu}^{k})$ is bounded,
namely, there exists an $L_{3}>0$ such that for all $k=1,\dots,K$ and all
$\theta\in\Theta$,
$\|\partial_{\theta_{j}}R(\theta,\bar{\mu}^{k})\|_{\infty}\leq L_{3}$.

Assumptions 2 and 1 are satisfied in several practical applications; for
instance, in Proposition 5.1, we prove these assumptions hold for the games we
consider in Section 6.

######  Proposition 5.1.

Suppose that $b(\theta,\mu)=b(\mu)$ has no dependency on $\theta$, $A$ is
constant, and $R$ and $c$ are affine functions of $\theta$, i.e.,

$\displaystyle R(\theta,\mu)$
$\displaystyle=R_{0}(\mu)+\textstyle\sum_{i=1}^{p}R_{i}(\mu)\theta_{i},\quad
c(\theta,\mu)=C(\mu)\theta,$

with $R_{0}(\mu)\succ 0$ and $R_{i}(\mu)\succeq 0$ for $i=1,\dots,p$. If
Assumption 1 holds, then Assumption 2 holds.

###### Proof.

First we prove that, under our assumptions, $S_{k}(Z_{k},0)$ is an invertible
matrix. Otherwise, there would exist an $(x_{0},\lambda_{0})$ such that
$S_{k}(Z_{k},0)(x_{0},\lambda_{0})^{T}=0$ and therefore
$x_{0}=-R(0,\bar{\mu}^{k})^{-1}A^{T}\lambda_{0}$, meaning that,

$\begin{bmatrix}A_{Z_{k}}R(0,\bar{\mu}^{k})^{-1}A^{T}\\\
I_{Y_{k}}\end{bmatrix}\lambda_{0}=0.$

This is equivalent to,

${\lambda_{0}}_{Y_{k}}=0,\quad
A_{Z_{k}}R(0,\bar{\mu}^{k})^{-1}A_{Z_{k}}^{T}{\lambda_{0Z_{k}}}=0,$

and since, by Assumption 1, the matrix
$A_{Z_{k}}R(0,\bar{\mu}^{k})^{-1}A_{Z_{k}}^{T}$ is invertible. This implies
that $\lambda_{0}=0$ and $x_{0}=0$, which is a contradiction. Now we will
prove that the infinity norm of $S_{k}(Z_{k},\theta)$ is bounded. Let $M_{0}$
and $M_{1}(\theta)$ be defined as

$M_{0}=\begin{bmatrix}R_{0}(\mu)&A^{T}\\\ -A_{Z}&0\\\
0&I_{Y}\end{bmatrix}\quad
M_{1}(\theta)=\begin{bmatrix}\sum_{i=1}^{p}R_{i}(\mu)\theta_{i}&0\\\ 0&0\\\
0&0\end{bmatrix},$

so that $S_{k}(Z_{k},\theta)=M_{0}+M_{1}(\theta)$. Then

$\displaystyle S_{k}(Z_{k},\theta)^{T}S_{k}(Z_{k},\theta)$
$\displaystyle=M_{0}^{T}M_{0}+\textstyle\sum_{i=1}^{p}\theta_{i}^{2}R_{i}^{T}R_{i}$
$\displaystyle\quad+\textstyle\sum_{i=1}^{p}\theta_{i}(R_{i}^{T}R_{0}+R_{0}^{T}R_{i}).$
(9)

Since $R_{i}$ is positive semi-definite, $R_{0}$ is positive-definite, and
$M_{0}$ is an invertible matrix, 9 is positive-definite. Furthermore, its
smallest eigenvalue is at least as large as the minimum eigenvalue
$\epsilon_{0}$ of $M_{0}^{T}M_{0}$. Therefore, the largest eigenvalue of
$(S_{k}(Z_{k},\theta)^{T}S_{k}(Z_{k},\theta))^{-1}$ is $1/\epsilon_{0}$ and so
the greatest singular value of $S_{k}(Z_{k},\theta)^{-T}$ is
$1/\sqrt{\epsilon_{0}}$. This means that the infinity norm of $S_{k}$ must be
bounded. ∎

Furthermore, we assume that for any $\theta$ such that $Z$ is a degenerate
active-set, we employ Rule 2 instead of Rule 1.

######  Rule 2.

Suppose we are at iteration $t$ of Algorithm 1, $Z^{(t)}\cap
Y^{(t)}\neq\emptyset$. Update $\theta^{(t+1)}$ using the gradient
$\nabla_{\theta}\mathcal{L}(\tilde{\theta};\\{\bar{x}^{k}\\})$, where
$\tilde{\theta}$ is chosen uniformly on $\text{B}_{\epsilon}(\theta^{(t)})$,
i.e., the euclidean ball of radius $\epsilon$.

We remark that $\nabla_{\theta}\mathcal{L}(\tilde{\theta};\\{\bar{x}^{k}\\})$
is well-defined by Assumption 2 because $\tilde{\theta}$ is a continuous
random variable and the gradient is defined almost-everywhere. For any fixed
$\epsilon$ and $\theta_{0}$, let $g$ be,

$\textstyle
g(\theta)=(1/K)\sum_{k=1}^{K}\int_{\theta_{0}}^{\theta}\int_{\text{B}_{\epsilon}(v)}\frac{1}{\pi\epsilon^{2}}\nabla\mathcal{L}(u;\\{\bar{x}^{k}\\})\text{d}u\text{d}v,$

where the outer integral can be taken along any path from $\theta_{0}$ to
$\theta$ since $\nabla\mathcal{L}(u;\\{\bar{x}^{k}\\})$ is potential. $g$ can
then be interpreted as a smoothed version of $\mathcal{L}$. We will show that
Algorithm 1 with the update rule 2 is equivalent to performing gradient
descent on the smooth, nonconvex function $g$; this will allow us to provide
our main convergence result.

######  Theorem 5.1.

For appropriately given step-sizes $\\{\eta_{t}\\}_{t=1}^{T}$ the active-set
algorithm with gradient Rule 2 satisfies $\lim_{T\rightarrow\infty}\mathop{\bf
E{}}[\|\nabla g(\theta_{T})\|_{2}]=0$.

###### Proof.

We will begin by bounding relevant derivatives of $g$. Since terms in the
relevant expressions for each derivative are bounded (using the boundedness of
$S_{k}(S_{k},\theta)$ and $\partial_{\theta}R(\theta,\bar{\mu}^{k})$), there
exist some constants $L_{1}$ and $L_{2}>0$ such that, for all $k=1\dots K$ and
$Z\subseteq\\{1,\dots,lm\\}$,

$\|\nabla\mathcal{L}(\theta;Z,\\{X_{k}\\})\|_{2}\leq
L_{1},\;\;-L_{2}\preceq\nabla^{2}\mathcal{L}(\theta,Z,\\{X_{k}\\})\preceq
L_{2}.$

Note that $\mathop{\bf E{}}[\nabla\mathcal{L}(\tilde{\theta})]=\nabla
g(\theta)$, where the randomness stems from the choice of the datapoint and
the update rule 2. By the claim, $g$ is Lipschitz continuous with constant
$L_{1}$ since,

$\displaystyle\|\nabla g(\theta)\|_{2}$
$\displaystyle={\textstyle\big{\|}(1/K)\sum_{k=1}^{K}\frac{1}{\pi\epsilon^{2}}\int_{\text{B}_{\epsilon}(\theta)}\nabla\mathcal{L}(u;\\{X_{k}\\})\text{d}u\big{\|}_{2}}$
$\displaystyle\leq{\textstyle(1/K)\textstyle\sum_{k=1}^{K}\frac{1}{\pi\epsilon^{2}}\int_{\text{B}_{\epsilon}(\theta)}\|\nabla\mathcal{L}(u;\\{X_{k}\\})\|_{2}\text{d}u}$
$\displaystyle\leq L_{1}.$

This and the Cauchy-Schwarz inequality also imply that,

$\mathop{\bf E{}}[\|\nabla\tilde{\mathcal{L}}(\theta)-\nabla
g(\theta)\|_{2}^{2}]\leq 4L_{1}^{2}.$

Since $\mathcal{L}$ is twice-differentiable on any $Z$, we have that

$\textstyle\nabla^{2}g(\theta)=(1/K)\sum_{k=1}^{K}(1/(\pi\epsilon^{2}))\int_{\text{B}_{\epsilon}(\theta)}\nabla^{2}\mathcal{L}(u;\\{X_{k}\\})\text{d}u.$

Since $\nabla^{2}g$ is an average of $\nabla^{2}\mathcal{L}$, we have that
$-L_{2}\preceq\nabla^{2}g(\theta)\preceq L_{2}$. Using the facts above, the
active-set algorithm with gradient Rule 2 mirrors a stochastic gradient
descent on $g$, a Lipschitz-continuous function with bounded second
derivatives. We can then use a standard theorem about the convergence of
stochastic gradient descent on smooth nonconvex functions such as [4]. ∎

Using the definition of $g$ again, we have shown that,

$\textstyle\lim_{T\rightarrow\infty}\mathop{\bf
E{}}_{\theta^{(T)}}[\|\mathop{\bf
E{}}_{\mathcal{U}}[\nabla_{\theta}\mathcal{L}(\theta^{(T)}+\mathcal{U};\mathcal{D})]\|_{2}]=0,$

where the outer expectation is taken over the steps of the algorithm, and the
inner expectation is taken over the uniform distribution on the euclidean ball
$\mathcal{U}\sim U[B_{\epsilon}(0)]$. However, applying update Rule 2 is
rather difficult from a computational perspective as we can not compute the
boundaries of the active-sets in the $\Theta$-space, because they are defined
implicitly by the function $\Phi$. Therefore, we heuristically approximate
Rule 2 using Rule 1. In practice, Rule 1 checks which active-set boundaries
$\theta^{(t)}$ are close to in the $x(\theta)$-space and chooses uniformly
among those candidate active-sets.

##  6 Computational results

In this section, we showcase the effectiveness of our algorithm via some
computational experiments. We run the experiments on a _Intel Xeon Gold 6246R_
with $16$GB of RAM, and we use _Gurobi 9.5_ [10] as the optimization solver.
For each experiment, we generate a training dataset
$\mathcal{D}_{\text{train}}$ with $90$ samples, and a test dataset for
evaluation $\mathcal{D}_{\text{test}}$ with $10$ datapoints. In both the
datasets, the datapoints $\bar{x}_{k}$ are Nash equilibria given
$\bar{\theta}_{k},\bar{\mu}_{k}$ with the addition of an independent Gaussian
error vector $\epsilon_{k}\sim\mathcal{N}(0,\sigma)$ with $\sigma=0.1$. We
remark that the true rationality parameters $\bar{\theta}_{k}$ are unknown. To
assess the performance of Algorithm 1 given the estimated parameters
$\theta^{\star}$, we employ the test error

$\textstyle\sqrt{(1/|\mathcal{D}_{\text{test}}|)\sum_{(\bar{\mu}_{k},\bar{x}_{k})\in\mathcal{D}_{\text{test}}}\|x(\theta^{\star};\bar{\mu}_{k})-\bar{x}_{k}\|_{2}^{2}}.$

###  6.1 Cournot Games

A generalized Cournot game is a simultaneous non-cooperative game where a
series of agents decide the quantity of a homogeneous product to inject into a
market. For every agent $i$, let the variable $x_{i}\geq 0$ represent the
quantity of product produced, and the parameter $c_{i}\in{\mbox{\bf R}}$ be
the unit-cost of production. The price of the product is determined by the
_inverse demand function_ $F(x)=a-b\sum_{j=1}^{n}x_{j}$, where $\theta=(a,b)$
and $a,b\in{\mbox{\bf R}}$. The utility (cost) function of $i$ is

${\textstyle
u_{i}(x_{i};x_{-i},\theta,\mu)=-F(\sum_{j=1}^{n}x_{j})x_{i}+c_{i}x_{i}},$

i.e., the revenues due to selling $x_{i}$ units at price $F$ minus the
production cost $c_{i}x_{i}$. We define $\mu=(c_{1},\dots,c_{n})$ and the
potential function $\Phi(x;\theta,\mu)$ as

$\textstyle c^{T}x+bx^{2}+b\sum_{1\leq i<j\leq n}x_{i}x_{j}-a^{T}x.$

We consider $n=50$, $70$, and $100$ agents, and we randomly generate
$\bar{\theta}_{k}$ and $\bar{\mu}_{k}$ according to the modulus of a Gussian
distribution $\mathcal{N}(0,\sigma)$ with $\sigma=1$. We report the test error
for the Cournot instances in the top half of Figure 1. In all three cases,
Algorithm 1 learns accurate rationality parameters $\theta$ inducing low test
errors. Furthermore, in Figure 2, we compare the running times and the test
errors of Algorithm 1 with Gurobi solving the nonconvex problem 4. Since the
solver runs out of time on our smallest instance with $n=50$, we generated two
smaller instances with $n\in\\{5,10,20\\}$. While Gurobi times out (time limit
of $2000$ seconds) whenever $n>10$, our algorithm solves all the instances.

Figure 1: Test error for the Cournot and congestion games. Figure 2:
Comparison to Gurobi for the Cournot game.

###  6.2 Congestion games

We consider a class of congestion games [22] defined over a direct graph
$G=(V,E)$, where $V$ is the set of vertices and $E$ is the set of edges. Each
agent $i$ has to route $d_{i}\in{\mbox{\bf R}}$ units of traffic from a node
$s_{i}\in V$ to a destination $t_{i}\in V$. Let the variable $x_{ie}$
represent the amount of traffic agent $i$ routes through edge $e\in E$, and
$C_{e}\in{\mbox{\bf R}}$ be the cost parameter for edge $e$. Let
$C=(C_{e_{1}},\dots C_{e_{|E|}})$ be the vector of edge costs and
$L\in{\mbox{\bf R}}^{|E|\times p}$ be a matrix of factors relating to each
edge (e.g., the length, width, and elevation of a road or the frequency of
public transport). We assume that $C=L\theta$ for some unknown rationality
parameters $\theta\in{\mbox{\bf R}}^{p}$ and $\mu={(s_{i},t_{i},d_{i})}_{i\in
I}$. All considered, each agent $i$ minimizes

$\displaystyle u_{i}(x_{i};x_{-i},\theta,\mu)$
$\displaystyle=\textstyle\sum_{e\in E}C_{e}x_{ie}(x_{1e}+\dots+x_{ne}),$

subject to the standard flow constraints on $G$. The potential function of the
game is

${\textstyle\Phi(x;\theta,\mu)=\sum_{e\in
E}C_{e}\sum_{i=1}^{n}((1/2)x_{ie}^{2}+\sum_{j\neq i}x_{ie}x_{je})}.$

We generate instances with $n=3$ and $|V|\in\\{8,10,20,30,40\\}$. The graphs
$G$ are Erdős–Rényi random graphs where each edge has a probability $p=0.3$ of
being present. Finally, we randomly generate $\bar{\theta}_{k}$ according to
the modulus of a Gussian distribution $\mathcal{N}(0,\sigma)$ with $\sigma=1$.
In Figure 1, we report the test errors on the congestion games. Similarly to
the Cournot games, our algorithm converges to small test errors. In Figure 3,
we provide a small toy example on a congestion game with $n=2$.

Figure 3: Three instances with different $\mu$ of a small congestion game with
$n=2$ among the red and the green player. The edge thickness represents the
amount of traffic routed through the edge.

##  7 Conclusions

We introduced a stochastic first-order algorithm to estimate the parameters of
potential games. Our active-set-based algorithm alternates between an active-
set step enforcing that the parameters induce Nash equilibria and an implicit-
differentiation step to update the estimates of the parameters. From a
theoretical perspective, we proved that our algorithm is guaranteed to
converge. From a practical perspective, we demonstrated the efficiency of our
technique via computational tests on Cournot and congestion games.

## References

  * Agrawal et al. [2021] Akshay Agrawal, Shane Barratt, and Stephen Boyd.  Learning convex optimization models.  _IEEE/CAA Journal of Automatica Sinica_ , 8(8):1355–1364, 2021.
  * Allen et al. [2022] Stephanie Allen, Steven A Gabriel, and John P Dickerson.  Using inverse optimization to learn cost functions in generalized nash games.  _Computers & Operations Research_, 142:105721, 2022.
  * Asen L. Dontchev [2009] R. Tyrrell Rockafellar Asen L. Dontchev.  _Implicit Functions and Solution Mappings_.  Springer Monographs in Mathematics, 2009.
  * Bertsekas and Tsitsiklis [1999] Dimitri Bertsekas and John Tsitsiklis.  Gradient convergence in gradient methods with errors.  _SIAM Journal on Optimization_ , 10, 1999.  doi: 10.1137/S1052623497331063.
  * Bertsimas et al. [2015] Dimitris Bertsimas, Vishal Gupta, and Ioannis Ch. Paschalidis.  Data-driven estimation in equilibrium using inverse optimization.  _Mathematical Programming_ , 153(2):595–633, 2015\.  ISSN 0025-5610, 1436-4646.
  * Daskalakis et al. [2021] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich.  Near-optimal no-regret learning in general games.  _Advances in Neural Information Processing Systems_ , 34:27604–27616, 2021.
  * Dragotto [2022] Gabriele Dragotto.  _Mathematical Programming Games_.  PhD thesis, Polytechnique Montréal, 2022.
  * Fabiani and Bemporad [2022] Filippo Fabiani and Alberto Bemporad.  A learning-based approach to multi-agent decision-making.  _arXiv:2212.12561_ , 2022.
  * Facchinei et al. [2007] Francisco Facchinei, Andreas Fischer, and Veronica Piccialli.  On generalized Nash games and variational inequalities.  _Operations Research Letters_ , 35(2):159–164, 2007.  ISSN 01676377.
  * Gurobi Optimization, LLC [2023] Gurobi Optimization, LLC.  Gurobi Optimizer Reference Manual, 2023.  URL https://www.gurobi.com.
  * Hartline et al. [2015] Jason Hartline, Vasilis Syrgkanis, and Éva Tardos.  No-Regret Learning in Bayesian Games.  In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 28. Curran Associates, Inc., 2015.
  * Heaton et al. [2021] Howard Heaton, Daniel McKenzie, Qiuwei Li, Samy Wu Fung, Stanley Osher, and Wotao Yin.  Learn to Predict Equilibria via Fixed Point Networks.  _arXiv:2106.00906_ , 2021.
  * Jin et al. [2022] Wanxin Jin, Alp Aydinoglu, Mathew Halm, and Michael Posa.  Learning Linear Complementarity Systems.  In _Learning for Dynamics and Control Conference_ , pages 1137–1149. PMLR, 2022.
  * Kleinberg et al. [2009] Robert Kleinberg, Georgios Piliouras, and Éva Tardos.  Multiplicative updates outperform generic no-regret learning in congestion games.  In _Proceedings of the forty-first annual ACM symposium on Theory of computing_ , pages 533–542, 2009.
  * Krichene et al. [2015] Walid Krichene, Benjamin Drighès, and Alexandre M Bayen.  Online learning of nash equilibria in congestion games.  _SIAM Journal on Control and Optimization_ , 53(2):1056–1081, 2015.
  * Li et al. [2020] Jiayang Li, Jing Yu, Yu Nie, and Zhaoran Wang.  End-to-end learning and intervention in games.  _Advances in Neural Information Processing Systems_ , 33:16653–16665, 2020.
  * Ling et al. [2018] Chun Kai Ling, Fei Fang, and J. Zico Kolter.  What Game Are We Playing? End-to-end Learning in Normal and Extensive Form Games.  In _IJCAI_ , pages 396–402, 2018.
  * Liu et al. [2022] Xinjie Liu, Lasse Peters, and Javier Alonso-Mora.  Learning to Play Trajectory Games Against Opponents with Unknown Objectives.  _arXiv:2211.13779_ , 2022.
  * Monderer and Shapley [1996] Dov Monderer and Lloyd S. Shapley.  Potential Games.  _Games and Economic Behavior_ , 14(1):124–143, 1996.  ISSN 08998256.
  * Nash [1950] John F. Nash.  Equilibrium Points in n-Person Games.  _Proc. of the National Acad. of Sciences of the United States of America_ , 36(1):48–49, 1950.
  * Ng and Russell [2000] Andrew Y. Ng and Stuart J. Russell.  Algorithms for inverse reinforcement learning.  In _Proceedings of the Seventeenth International Conference on Machine Learning_ , ICML ’00, page 663–670. Morgan Kaufmann Publishers Inc., 2000\.  ISBN 1558607072.
  * Rosenthal [1973] Robert W. Rosenthal.  A class of games possessing pure-strategy Nash equilibria.  _International Journal of Game Theory_ , 2(1):65–67, 1973.  ISSN 0020-7276, 1432-1270.
  * Vorobeychik et al. [2007] Yevgeniy Vorobeychik, Michael P Wellman, and Satinder Singh.  Learning payoff functions in infinite games.  _Machine Learning_ , 67(1):145–168, 2007.
  * Waugh et al. [2011] Kevin Waugh, Brian D. Ziebart, and J. Andrew Bagnell.  Computational Rationalization: The Inverse Equilibrium Problem.  In _Proceedings of the 28th International Conference on International Conference on Machine Learning_ , ICML’11, page 1169–1176. Omnipress, 2011.  ISBN 9781450306195.
  * Wu et al. [2022] Jibang Wu, Weiran Shen, Fei Fang, and Haifeng Xu.  Inverse game theory for stackelberg games: the blessing of bounded rationality.  _arXiv 2210.01380_ , 2022.  doi: 10.48550/ARXIV.2210.01380.
  * Zanardi et al. [2021] Alessandro Zanardi, Enrico Mion, Mattia Bruschetta, Saverio Bolognani, Andrea Censi, and Emilio Frazzoli.  Urban driving games with lexicographic preferences and socially efficient nash equilibria.  _IEEE Robotics and Automation Letters_ , 6(3):4978–4985, 2021.  doi: 10.1109/LRA.2021.3068657.