remarkRemark notationNotation hypothesisHypothesis claimClaim Approximate
Generalized Feedback Nash EquilibriaLaine, Fridovich-Keil, Chiu, and Tomlin

# The Computation of Approximate Generalized Feedback Nash Equilibria††thanks:
This research is supported by the DARPA Assured Autonomy Program, the ONR
Basic Research Challenge on Multibody Systems, the NASA ULI program, SRC
CONIX, and the NSF CPS program.

Forrest Laine Electrical Engineering and Computer Sciences, University of
California, Berkeley<EMAIL_ADDRESS>David Fridovich-Keil
Aerospace Engineering and Engineering Mechanics, The University of Texas at
Austin Chih-Yuan Chiu22footnotemark: 2 Claire Tomlin22footnotemark: 2

###### Abstract

We present the concept of a Generalized Feedback Nash Equilibrium (GFNE) in
dynamic games, extending the Feedback Nash Equilibrium concept to games in
which players are subject to state and input constraints. We formalize
necessary and sufficient conditions for (local) GFNE solutions at the
trajectory level, which enable the development of efficient numerical methods
for their computation. Specifically, we propose a Newton-style method for
finding game trajectories which satisfy necessary conditions for an
equilibrium, which can then be checked against sufficiency conditions. We show
that the evaluation of the necessary conditions in general requires computing
a series of nested, implicitly-defined derivatives, which quickly becomes
intractable. To this end, we introduce an approximation to the necessary
conditions which is amenable to efficient evaluation, and in turn, computation
of solutions. We term the solutions to the approximate necessary conditions
Generalized Feedback Quasi-Nash Equilibria (GFQNE), and we introduce numerical
methods for their computation. In particular, we develop a Sequential Linear-
Quadratic Game approach, in which a LQ local approximation of the game is
solved at each iteration. The development of this method relies on the ability
to compute a GFNE to inequality- and equality-constrained LQ games, and
therefore specific methods for the solution of these special cases are
developed in detail. We demonstrate the effectiveness of the proposed solution
approach on a dynamic game arising in an autonomous driving application.

###### keywords:

Generalized Feedback Nash Equilibrium, Dynamic Games, Mathematical Programming

##  1 Introduction

There has been a recent growing interest in the application of game-theoretic
concepts to applications in automated systems, as explored in [15, 22, 3, 2,
9, 10, 4, 8]. Indeed, numerous problems arising in these domains can be
modeled as games, and particularly as dynamic or repeated games. For the
purposes considered in this paper, we restrict our attention to discrete-time
dynamic games, in which players have the ability to influence the state of the
game over a finite set of game _stages_. Associated with dynamic/repeated game
solutions are game trajectories, which capture the evolution of the
_continuous_ game state and player inputs over the sequence of stages.

Solutions to dynamic games have been studied extensively, as in [1]. Within
the theory of dynamic games, there are a variety of information patterns that
can be associated with the game, and each of these patterns results in a
fundamentally different solution. Perhaps the simplest information pattern is
the _open-loop_ pattern, in which the repeated nature of the game is ignored.
In this pattern the stages of the game are combined into a single _static_
game, and the entire trajectory is chosen at once to satisfy a Nash,
Stackelberg, or other type of equilibrium. When constraints on the state
variables are imposed upon the players, a generalized equilibrium must be
considered. Formulating games with an open-loop information pattern has many
advantages as the resultant static game often admits known methods for
analysis and computing solutions, as presented, for example, in [6, 7].
However, by ignoring the dynamic nature of these games, the expressiveness of
the resultant solutions are significantly limited. Intelligent game play in
repeated games often involves observing the evolving game state and reacting
accordingly.

Reactive game-play can emerge when associating a _closed-loop_ information
pattern to the game of interest. Effectively, games with this information
pattern are such that the players choose control _policies_ which define the
control input as a function of the game state at that stage. When those
policies at each game stage are chosen to constitute an equilibrium for the
dynamic subgame played over the subsequent game stages, the resultant solution
is called a feedback equilibrium. This type of solution is capable of
capturing strategies for a player which anticipate and account for the
reaction of other players. Some advantages of this type of solution are
explored in the autonomous driving context in, e.g., [15].

While feedback equilibrium solutions are often desirable over their open-loop
counterparts, for all but simple cases, there do not exist well-developed
numerical routines for computing them. The unconstrained Linear-Quadratic (LQ)
setting is perhaps the simplest case, and methods for computing feedback
equilibria for these games are well known, as presented in [1]. The extension
to the computation of a feedback Nash equilibrium for a class of inequality-
constrained LQ games is introduced in [18, 19], although restrictive
assumptions are made on the form of the dynamics, constraints and cost terms
of the game. Numerous other approaches have considered the computation of
feedback equilibria under various special cases, such as those in [20, 21,
14], among others. Methods for computing feedback Nash equilibria have been
recently developed in the unconstrained, nonlinear case using a value-
iteration based approach [12], and an iterative LQ game approach [9].
Nevertheless, to the best of our knowledge, no methods exist for computing
feedback equilibria in games with constraints appearing on both the state and
input dimensions, both in the general LQ and nonlinear settings.

Since many emerging applications of dynamic games involve nonlinear dynamics
as well as nonlinear constraints on the game states and inputs, we have
pursued the development of a robust and efficient method for computing
feedback equilibria in this setting. The result of that work is the topic of
this paper.

The outline of the paper is the following. In Section 2 we introduce the
concept of a Generalized Feedback Nash Equilibrium (GFNE), which formally
defines the feedback concept in the constrained setting. We discuss pitfalls
with a parameterized approach to encoding GFNE problems as a means to motivate
and introduce a non-parametric alternative. We then develop necessary and
sufficient conditions on game trajectories to satisfy a GFNE using this non-
parametric formulation. Challenges associated with the computation of such
GFNE are highlighted, and a close approximation is introduced which is
amenable to efficient computation. Finally, numerical methods for the
computation of such approximate solutions are developed in detail, for the
equality-constrained LQ setting (Section 3), inequality-constrained LQ setting
(Section 4), and ultimately, the general nonlinear setting (Section 5). We
demonstrate our method on an application to autonomous driving in Section 6
and conclude the paper in Section 7.

##  2 Formulation

We focus our attention to the class of $N$-player discrete-time,
deterministic, infinite, general-sum dynamic games of discrete stage-length
$T$. Let $\mathbf{N}$ denote the set $\\{1,...,N\\}$, and similarly
$\mathbf{T}$ the set $\\{1,...,T\\}$. We also make use of the sets
$\mathbf{T^{+}}:=\mathbf{T}\cup\\{T+1\\}$, $\mathbf{T_{t}}:=\\{t,...,T\\}$,
and $\mathbf{T_{t}^{+}}:=\\{t,...,T+1\\}$. The game state at each discrete
time-step $t$ is represented by $x_{t}\in\mathcal{X}=\mathbb{R}^{n}$. The game
is assumed to start at stage $t=1$, from a pre-specified initial state
$\hat{x}_{1}$. Throughout this paper we refer to subgames starting at stage
$t$, which refers to the game played over a portion of the original game, on
the stages $\\{t,...,T\\}$.

The evolution of the game state is described by the dynamic equation:

(1) $x_{t+1}=f_{t}(x_{t},u_{t}^{1},...,u_{t}^{N}),\ \ t\in\mathbf{T},$

where $u_{t}^{i}\in\mathcal{U}_{t}^{i}=\mathbb{R}^{m_{t}^{i}}$ are the control
variables chosen by players $i\in\mathbf{N}$ at time $t$. Let
$m_{t}:=\sum_{i=1}^{N}m_{t}^{i}$, and $m_{t}^{-i}:=m_{t}-m_{t}^{i}$.

To simplify the notation in definitions and derivations, we make use of the
following shorthand to refer to various sets of state and control variables:

_Notation reference:_

$\displaystyle x$ $\displaystyle:=\\{x_{1},x_{2},...,x_{T+1}\\},$
$\displaystyle u^{i}$
$\displaystyle:=\\{u_{1}^{i},u_{2}^{i},...,u_{T}^{i}\\},$ $\displaystyle u$
$\displaystyle:=\\{u^{1},...,u^{N}\\},$ $\displaystyle u_{t}$
$\displaystyle:=\\{u_{t}^{1},...,u_{t}^{N}\\},$ $\displaystyle u_{t}^{-i}$
$\displaystyle:=\\{u_{t}^{1},...,u_{t}^{i-1},u_{t}^{i+1},...,u_{t}^{N}\\},$
$\displaystyle\\{u_{t}^{i},u_{t}^{-i}\\}$
$\displaystyle:=\\{u_{t}^{1},...,u_{t}^{N}\\}=u_{t}$

Note that the above collections may be interpreted as sets of variables or as
column vectors. In particular, at times throughout this work we will utilize
the interpretation that
$u_{t}:=[(u_{t}^{1})^{\intercal},...,(u_{t}^{N})^{\intercal}]^{\intercal}$.

Each player in the game is associated with time-separable cost-functionals:

(2)
$L^{i}(x,u^{1},...,u^{N}):=\sum_{t=1}^{T}l_{t}^{i}(x_{t},u_{t})+l^{i}_{T+1}(x_{T+1})$

Furthermore, each player may have stage-wise, non-dynamic, equality and
inequality constraints.

(3a) $\displaystyle 0=h_{t}^{i}(x_{t},u_{t}),\ t\in\mathbf{T}$ $\displaystyle
0=h_{T+1}^{i}(x_{T+1})$ (3b) $\displaystyle 0\leq g_{t}^{i}(x_{t},u_{t})\
t\in\mathbf{T,}$ $\displaystyle 0\leq g_{T+1}^{i}(x_{T+1})$

Let the dimension of the constraints $h^{i}_{t}$ and $g^{i}_{t}$, for all
$t\in\mathbf{T^{+}}$ and $i\in\mathbf{N}$, be denoted as $a^{i}_{t}\geq 0$ and
$b^{i}_{t}\geq 0$, respectively. Define
$V_{t}^{i}:\mathcal{X}\to\mathbb{R}\cup\\{\infty\\}$ as the _Value-function_
for player $i\in\mathbf{N}$ at stage $t\in\mathbf{T^{+}}$, and
$Z_{t}^{i}:\mathcal{X}\times\mathcal{U}_{t}^{i}\times...\times\mathcal{U}_{t}^{N}\to\mathbb{R}\cup\\{\infty\\}$
the _Control-Value-function_ for player $i\in\mathbf{N}$ at time
$t\in\mathbf{T}$.

A Generalized Feedback Nash Equilibrium is defined in terms of maps
$\pi_{t}^{i}:\mathcal{X}\to\mathcal{U}_{t}^{i}$, for $i\in\mathbf{N}$,
$t\in\mathbf{T}$, which we refer to as feedback policies or strategies. The
feedback policies, Value-functions, and Control-Value-functions are together
defined according to the following recursive relationships Eq. 4-Eq. 7:

(4)
$V_{T+1}^{i}(x_{T+1}):=\left\\{\begin{array}[]{@{}ll@{}}\hbox{\multirowsetup$l_{T+1}^{i}(x_{T+1})$,}&0=h_{T+1}^{i}(x_{T+1})\\\
&0\leq g_{T+1}^{i}(x_{T+1})\\\ \infty,&\text{else}\end{array}\right.$

Given $V_{t+1}^{i}$ for some $t\in\mathbf{T}$ and $i\in\mathbf{N}$, we define
$Z_{t}^{i}$ by

(5)
$Z_{t}^{i}(x_{t},u_{t}^{1},...,u_{t}^{N}):=\left\\{\begin{array}[]{@{}ll@{}}\hbox{\multirowsetup$l_{t}^{i}(x_{t},u_{t})+V_{t+1}^{i}(f_{t}(x_{t},u_{t}))$,}&0=h_{t}^{i}(x_{t},u_{t})\\\
&0\leq g_{t}^{i}(x_{t},u_{t})\\\ \infty,&\text{else}\end{array}\right.$

For a particular state $x_{t}$ at stage $t$, the feedback policies $\pi_{t}$
are defined to return a local generalized Nash equilibrium solution for the
static game defined in terms of the $N$ Control-Value-functions evaluated at
$x_{t}$ (one for each player).

(6) $\displaystyle\tilde{u}_{t}=\pi_{t}(x_{t})$ $\displaystyle\Longrightarrow$
$\displaystyle Z_{t}^{1}($ $\displaystyle
x_{t},\tilde{u}_{t}^{1},...,\tilde{u}_{t}^{N})$ $\displaystyle\leq
Z_{t}^{1}(x_{t},u_{t}^{1},\tilde{u}_{t}^{2},...,\tilde{u}_{t}^{N}),\ \ $
$\displaystyle\forall u_{t}^{1}\in\mathcal{N}(\tilde{u}_{t}^{1}),$
$\displaystyle\ \ \vdots$ $\displaystyle Z_{t}^{N}($ $\displaystyle
x_{t},\tilde{u}_{t}^{1},...,\tilde{u}_{t}^{N})$ $\displaystyle\leq
Z_{t}^{N}(x_{t},\tilde{u}_{t}^{1},...,\tilde{u}_{t}^{N-1},u_{t}^{N}),\ \ \ \ $
$\displaystyle\forall u_{t}^{N}\in\mathcal{N}(\tilde{u}_{t}^{N}),$

The set $\mathcal{N}(\tilde{u}_{t}^{i})$ is some neighborhood around
$\tilde{u}_{t}^{i}$. It is possible that no such generalized equilibrium
exists, due to the non-convexity of the Control-Value-functions w.r.t. the
control variables [5]. In such a case, the feedback policies are undefined, as
are all preceding Value and Control-Value functions. If a generalized
equilibrium exists, it may be non-unique, and potentially non-isolated. For
the purposes considered here, we require only that for any state $x_{t}$, the
policies evaluate to one arbitrarily chosen, yet particular, local
equilibrium. A more stringent definition for the policies $\pi_{t}$ could
require that the inequalities in Eq. 6 hold over the entire sets
$\mathcal{U}_{t}^{i}$ rather than some local neighborhood. In any case, the
Value-functions for stages $t\in\mathbf{T}$ are defined as

(7)
$V_{t}^{i}(x_{t}):=Z_{t}^{i}(x_{t},\pi_{t}^{1}(x_{t}),...,\pi_{t}^{N}(x_{t})).$

At each stage of the game, it may be that all player’s individual constraints
Eqs. 3a and 3b are impossible to satisfy for arbitrary choice of the game
state at that stage. If for some particular state $x_{t}$, player $i$’s
constraints are inadmissible, the associated value $V_{t}^{i}(x_{t})$ will be
infinite. Without computing the feedback policies $\pi_{s},\
s\in\mathbf{T_{t+1}}$, it is not possible to determine whether the constraints
for any given player are admissible, since their satisfaction depends on the
actions of all other players in the remaining game stages. Nevertheless,
throughout this work, we assume that the constraints for all players are
indeed admissible, when starting from known initial state $\hat{x}_{1}$, and
with other players choosing their actions according to the equilibrium
feedback policies.

######  Definition 2.1 (GFNE).

A Local Generalized Feedback Nash Equilibrium originating from $\hat{x}_{1}$
is defined by a set of policies $\pi_{t}^{i}$, $t\in\mathbf{T}$,
$i\in\mathbf{N}$ defined in Eq. 6, such that the value of
$V_{1}^{i}(\hat{x}_{1})$, defined in Eq. 7, is finite for all
$i\in\mathbf{N}$. In this paper we refer to local GFNE whenever we write GFNE.

Consider a collection of policies constituting a GFNE. Let the corresponding
_equilibrium trajectory_ be denoted by $x_{t}^{*},u_{t}^{*}$ such that

(8) $\displaystyle x_{1}^{*}$ $\displaystyle:=\hat{x}_{1},$ $\displaystyle
u_{t}^{i*}$ $\displaystyle:=\pi_{t}^{i}(x_{t}^{*}),\ $ $\displaystyle
t\in\mathbf{T},$ $\displaystyle x_{t+1}^{*}$
$\displaystyle:=f_{t}(x_{t}^{*},u_{t}^{1*},...,u_{t}^{N*}),\ \ \ $
$\displaystyle t\in\mathbf{T}.$

Despite the notion of a GFNE being well-defined, the presented formulation
does not lend itself to the computation of such equilibrium trajectories. The
remainder of this work is devoted to an alternate encoding of the GFNE
problem, which is amenable to the computation. We begin the presentation of
this approach by expressing the policies at each stage $t$ in terms of the
subgame starting at that stage.

######  Theorem 2.2.

The policies defined in Eq. 6 can equivalently be expressed in terms of the
nested Generalized Nash Equilibrium Problems Eq. 9.

(9a)
$\displaystyle\pi_{t}^{i}(x_{t}):=\tilde{u}^{i}_{t}\in\underset{u_{t}^{i}}{\textrm{\emph{arg}}}\underset{\begin{subarray}{c}u_{t:T}^{i},\\\
\tilde{u}^{-i}_{t+1:T},\\\ x_{t+1:T+1}\end{subarray}}{\textrm{\emph{min}}}\ $
$\displaystyle\sum_{s=t}^{T}l_{s}^{i}(x_{s},u_{s}^{i},\tilde{u}_{s}^{-i})+l_{T+1}^{i}(x_{T+1})$
(9b) s.t. $\displaystyle 0=\tilde{u}^{-i}_{s}-\pi^{-i}_{s}(x_{s}),\ $
$\displaystyle s\in\mathbf{T_{t+1}}$ (9c) $\displaystyle
0=x_{s+1}-f_{s}(x_{s},u_{s}^{i},\tilde{u}_{s}^{-i}),\ $ $\displaystyle
s\in\mathbf{T_{t}}$ (9d) $\displaystyle
0=h_{s}^{i}(x_{s},u_{s}^{i},\tilde{u}_{s}^{-i}),$ $\displaystyle
s\in\mathbf{T_{t}}$ (9e) $\displaystyle 0\leq
g_{s}^{i}(x_{s},u_{s}^{i},\tilde{u}_{s}^{-i}),$ $\displaystyle
s\in\mathbf{T_{t}}$ (9f) $\displaystyle 0=h^{i}_{T+1}(x_{T+1})$ (9g)
$\displaystyle 0\leq g^{i}_{T+1}(x_{T+1})$

Here
$\pi_{t}^{-i}(x_{t}):=(\pi_{t}^{1}(x_{t}),...,\pi_{t}^{i-1}(x_{t}),\pi_{t}^{i+1}(x_{t}),...,\pi_{t}^{N}(x_{t}))$,
and the notation $\underset{a}{\text{arg}}\ \underset{a,b}{\text{min}}$ is
used to indicate that the minimum is taken over $a$ and $b$, but only the
value of $a$ at the minimum is returned. The shared game state
$x_{s},s\in\mathbf{T_{t+1}^{+}}$, and control variables for all other players,
$\tilde{u}_{s}^{-i},s\in\mathbf{T_{t+1}}$ appear as decision variables in
player $i$’s decision problem. This is because the constraints Eqs. 9b and 9c
render these variables _implicit_ variables, allowing them to be effectively
shared by all players [13, Def. 2]. The value of the minimization appearing in
Eq. 9 is considered infinite for any combination of optimization variables
violating the constraints. Note also that the set $\mathbf{T}_{T+1}$ is empty,
so for stage $t=T$, the constraint Eq. 9b vanishes.

######  Proof 2.3.

Starting with stage $T$, and substituting $x_{T+1}$ using the dynamics Eq. 9c,
and moving constraints Eqs. 9d, 9e, 9f, and 9g into the objective by means of
infinite-valued indicator functions, observe that the objective of the
minimization is equivalent to $Z_{T}^{i}$ Eq. 5 as claimed.

Now, for some other stage $t\in\mathbf{T}$, assuming $\pi_{t}^{i}(x_{t+1})$
can be expressed by Eq. 9, it can be shown that $\pi_{t}^{i}(x_{t})$ must also
be equivalently expressed by Eq. 9. Eq. 9 can be re-written as the following:

(10a)
$\displaystyle\pi_{t}^{i}(x_{t}):=\tilde{u}^{i}_{t}\in\underset{u_{t}^{i}}{\textrm{arg}}$
$\displaystyle\underset{\begin{subarray}{c}u_{t}^{i},\\\
\tilde{u}_{t+1}^{-i},\\\ x_{t+1}\end{subarray}}{\textrm{min}}\Bigg{\\{}\
l_{t}^{i}(x_{t},u_{t}^{i},\tilde{u}_{t}^{-i})+$
$\displaystyle\underset{\begin{subarray}{c}u_{t+1:T}^{i},\\\
\tilde{u}^{-i}_{t+2:T},\\\ x_{t+2:T+1}\end{subarray}}{\textrm{min}}\ $
$\displaystyle\mathrlap{\sum_{s=t+1}^{T}l_{s}^{i}(x_{s},u_{s}^{i},\tilde{u}_{s}^{-i})+l_{T+1}^{i}(x_{T+1})\Bigg{\\}}}$
(10b) s.t. $\displaystyle 0=\tilde{u}^{-i}_{s}-\pi^{-i}_{s}(x_{s}),$
$\displaystyle s\in\mathbf{T_{t+2}}$ (10c) $\displaystyle
0=x_{s+1}-f_{s}(x_{s},u_{s}^{i},\tilde{u}_{s}^{-i}),\ $ $\displaystyle
s\in\mathbf{T_{t+1}}$ (10d) $\displaystyle
0=h_{s}^{i}(x_{s},u_{s}^{i},\tilde{u}_{s}^{-i}),$ $\displaystyle
s\in\mathbf{T_{t+1}}$ (10e) $\displaystyle 0\leq
g_{s}^{i}(x_{s},u_{s}^{i},\tilde{u}_{s}^{-i}),$ $\displaystyle
s\in\mathbf{T_{t+1}}$ (10f) $\displaystyle 0=h^{i}_{T+1}(x_{T+1})$ (10g)
$\displaystyle 0\leq g^{i}_{T+1}(x_{T+1})$ (10h) $\displaystyle\textrm{s.t.}\
\ \ \mathrlap{0=\tilde{u}_{t+1}^{-i}-\pi_{t+1}^{-i}(x_{t+1})}$ (10i)
$\displaystyle\ \ \ \ \ \ \
\mathrlap{0=x_{t+1}-f(x_{t},u_{t}^{i},\tilde{u}_{t}^{-i})}$ (10j)
$\displaystyle\ \ \ \ \ \ \
\mathrlap{0=h_{t}^{i}(x_{t},u_{t}^{i},\tilde{u}_{t}^{-i})}$ (10k)
$\displaystyle\ \ \ \ \ \ \ \mathrlap{0\leq
g_{t}^{i}(x_{t},u_{t}^{i},\tilde{u}_{t}^{-i})}$

The nested minimum appearing in Eq. 10 is exactly that appearing in Eq. 9 for
stage $t+1$ (ignoring Eq. 10b if $t+1=T$). Because the controls
$\tilde{u}^{-i}_{t+1}$ (for $t+1\leq T$) are constrained by the policies
$\pi_{t+1}^{-i}(x_{t+1})$, the value of this nested minimization must equal
the value function $V_{t+1}(x_{t+1})$ as defined in Eq. 7 for any minimizer
$u_{t+1}^{i}$, regardless of whether or not the minimizer corresponds to the
particular one corresponding to $\pi_{t+1}^{i}(x_{t+1})$. By substituting
$x_{t+1}$ using the constraint Eq. 10i, and using infinite-valued indicator
functions to move Eqs. 10j and 10k into the objective of Eq. 10, we see that
the objective of the minimization is equivalent to Eq. 5 for stage $t$,
despite $u^{i}_{t+1:T}$ not being constrained by equilibrium policies. Thus,
the alternate definition of $\pi_{t}^{i}(x_{t})$ in Eq. 9 is equivalent to
that in Eq. 6 for all stages $t$.

Here we have defined the GFNE policies in terms of the _nested_ equilibrium
problems with equilibrium constraints Eq. 9. These equilibrium constraints
arise in these problems because the constraints Eq. 9b are defined in terms of
equilibrium problems. Critically though, the set of players in all inner-level
equilibrium problems are exactly those in the outer-level problems, allowing
for the removal of the redundant constraint that
$u_{s}^{i}=\pi_{s}^{i}(x_{s})$, $s\in\mathbf{T_{t+1}}$ from player $i$’s
problem statement Eq. 9, as demonstrated in Theorem 2.2. When the necessary
conditions of all players are concatenated, the constraints
$u_{s}^{i}=\pi_{s}^{i}(x_{s})$, $s\in\mathbf{T_{t+1}}$ become redundant for
_all_ $i$, as we show in Theorem 2.4. This fact will allow for a compact
representation of necessary conditions associated with solutions of a GFNE,
and ultimately algorithms for finding such solutions.

######  Theorem 2.4 (Necessary Conditions).

For some stage $t\in\mathbf{T}$, consider any set of policies $\pi_{s}^{i}$,
$s\in\mathbf{T_{t}}$, $i\in\mathbf{N}$, as defined in Eq. 9. Let the state
$\hat{x}_{t}$ be such that a solution exists to equilibrium problem Eq. 9 at
stage $t$. Denote the resultant sub-game solution trajectory by
$\\{x_{s}^{*};\ s\in\mathbf{T_{t}^{+}},\ x_{t}^{*}=\hat{x}_{t}\\}$,
$\\{u_{s}^{*};\ s\in\mathbf{T_{t}}\\}$. Furthermore, assume the policies
$\pi_{s}(x_{s})$ are differentiable at the point $x_{s}^{*}$ for
$s\in\mathbf{T_{t+1}}$, and a standard constraint qualification such as the
linear independence constraint qualification holds for the optimization
problem appearing in Eq. 9, for each $i\in\mathbf{N}$. Then there exist
multipliers $\\{\lambda_{s}^{i}\in\mathbb{R}^{n};\ s\in\mathbf{T_{t}},\
i\in\mathbf{N}\\}$, $\\{\mu_{s}^{i}\in\mathbb{R}^{a^{i}_{s}};\
s\in\mathbf{T_{t}^{+}},\ i\in\mathbf{N}\\}$,
$\\{\gamma_{s}^{i}\in\mathbb{R}^{b^{i}_{s}};\ s\in\mathbf{T_{t}^{+}},\
i\in\mathbf{N}\\}$, and $\\{\psi_{s}^{i}\in\mathbb{R}^{m^{-i}};\
s\in\mathbf{T_{t+1}},\ i\in\mathbf{N}\\}$ which satisfy111The notation
$[\cdot]_{u_{t}}$ implies that if $u_{t}$ appears in the $j_{1}$ through
$j_{2}$ indices of $z_{t}$, then the $j_{1}$ through $j_{2}$ rows of the
matrix argument are selected. The notation in the first equation of Eq. 11 is
used to indicate that the gradients of the functions $l_{s}^{i}(x_{s},u_{s})$,
$f(x_{s},u_{s})$, $h_{s}^{i}(x_{s},u_{s})$, and $g_{s}^{i}(x_{s},u_{s})$ are
evaluated at $x_{s}^{*}$ and $u_{s}^{*}$. The symbol $\perp$ is used to
indicate complementarity of the left- and right-hand-side conditions. For
example, if the $k$-th element of $g_{s}^{i}(x_{s}^{*},u_{s}^{*})>0$ then the
$k$-th element of $\gamma_{s}^{i}$ must be $0$, and vice-versa. As before, for
the final stage $t=T$, the set of conditions Eqs. 11b and 11c is empty, as the
set $\mathbf{T_{T+1}}=\emptyset$. :

(11a) $\displaystyle 0$
$\displaystyle=\nabla_{u_{s}^{i}}\bigg{[}l_{s}^{i}+f_{s}^{\intercal}\lambda_{s}^{i}-h_{s}^{i\intercal}\mu_{s}^{i}-g_{s}^{i^{\intercal}}\gamma_{s}^{i}$
$\displaystyle\bigg{]}_{x_{s}^{*},u_{s}^{*}},\ \ $ $\displaystyle
i\in\mathbf{N},\ s\in\mathbf{T_{t}}$ (11b) $\displaystyle 0$
$\displaystyle=\nabla_{x_{s}}\bigg{[}l_{s}^{i}-\lambda_{s-1}^{i}+f_{s}^{\intercal}\lambda_{s}^{i}-h_{s}^{i^{\intercal}}\mu_{s}^{i}-g_{s}^{i\intercal}\gamma_{s}^{i}+\pi_{s}^{-i\intercal}\psi_{s}^{i}$
$\displaystyle\bigg{]}_{x_{s}^{*},u_{s}^{*}},\ \ $ $\displaystyle
i\in\mathbf{N},\ s\in\mathbf{T_{t+1}},$ (11c) $\displaystyle 0$
$\displaystyle=\nabla_{u^{-i}_{s}}\bigg{[}l_{s}^{i}+f_{s}^{\intercal}\lambda_{s}^{i}-h_{s}^{i^{\intercal}}\mu_{s}^{i}-g_{s}^{i\intercal}\gamma_{s}^{i}-\psi_{s}^{i}$
$\displaystyle\bigg{]}_{x_{s}^{*},u_{s}^{*}},\ \ $ $\displaystyle
i\in\mathbf{N},\ s\in\mathbf{T_{t+1}},$ (11d) $\displaystyle 0$
$\displaystyle=\nabla_{x_{T+1}}\bigg{[}l_{T+1}^{i}-\lambda_{T}^{i}-h_{T+1}^{i^{\intercal}}\mu_{T+1}^{i}-g_{T+1}^{i\intercal}\gamma_{T+1}^{i}$
$\displaystyle\bigg{]}_{x_{T+1}^{*}},\ \ $ $\displaystyle i\in\mathbf{N},$
(11e) $\displaystyle 0$
$\displaystyle=x^{*}_{s+1}-f_{s}(x^{*}_{s},u^{*}_{s}),$ $\displaystyle
s\in\mathbf{T_{t}},$ (11f) $\displaystyle 0$
$\displaystyle=h_{s}^{i}(x_{s}^{*},u_{s}^{*}),$ $\displaystyle
i\in\mathbf{N},\ s\in\mathbf{T_{t}},$ (11g) $\displaystyle 0$
$\displaystyle\leq g_{s}^{i}(x_{s}^{*},u_{s}^{*})\perp\gamma_{s}^{i}\geq 0,$
$\displaystyle i\in\mathbf{N},\ s\in\mathbf{T_{t}},$ (11h) $\displaystyle 0$
$\displaystyle=h_{T+1}^{i}(x_{T+1}^{*}),$ $\displaystyle i\in\mathbf{N},$
(11i) $\displaystyle 0$ $\displaystyle\leq
g_{T+1}^{i}(x_{T+1}^{*})\perp\gamma_{T+1}^{i}\geq 0,$ $\displaystyle
i\in\mathbf{N}.$

When strict complementarity holds (w.r.t. Eqs. 11g and 11i), let
$L_{t}(z_{t},x_{t}^{*})=0$ denote the entire set of conditions Eq. 11 formed
by treating active inequalities Eqs. 11g and 11i as equalities, and ignoring
the inactive inequalities. Here, $z_{t}$ is the set of all variables appearing
in Eq. 11 other than $x_{t}^{*}$ _and_ all multipliers $\gamma_{s}^{i}$
associated with inactive inequality constraints. For example, if at a solution
to Eq. 11, it is that $\gamma_{s,j}^{i}=0$ for some
$i\in\mathbf{N},s\in\mathbf{T_{t}},j\in\\{1...b_{s}^{i}\\}$, then
$\gamma_{s,j}^{i}=0$ is included in the system of equations
$L_{t}(z_{t},x_{t}^{*})=0$, where as the expression involving
$g_{s}^{i}(x_{s}^{*},u_{s}^{*})$ is discarded. If the matrix
$\nabla_{z_{t}}L_{t}$ is non-singular, then the policy $\pi_{t}(x_{t})$ is
also differentiable at the point $\hat{x}_{t}$, and
$\nabla_{x}\pi_{t}(x_{t}):=-[[\nabla_{z_{t}}L_{t}]^{-1}\nabla_{x_{t}}L_{t}]_{u_{t}}$.

######  Proof 2.5.

By the assumption that the optimization problems Eq. 9 satisfy a standard
constraint qualification, the first-order necessary conditions for optimality
(Karush-Kuhn-Tucker conditions) imply that there must exist multipliers
associated with each player $i\in\mathbf{N}$’s optimization problem at stage
$t$, such that both the conditions in Eq. 11 (evaluated for the particular
$i\in\mathbf{N}$) and the constraints $u_{s}^{-i*}=\pi_{s}^{-i}(x_{s})$ hold
[17, Thm. 12.1]. Concatenating these conditions for all of the $N$ players
gives rise to the conditions Eq. 11, with the addition of the constraints Eq.
9b for each $i\in\mathbf{N}$. Since there must exist multipliers satisfying
those conditions, the conditions Eq. 11 must also be satisfied, as Eq. 11 are
formed by simply removing the constraints $u_{s}^{*}=\pi_{s}(x_{s})$.

After removing all inactive inequality constraints and associated multipliers
from Eq. 11, it is straightforward to verify that the dimension of the system
$L_{t}(z_{t},x_{t}^{*})$ and $z_{t}$ are the same, and therefore that
$\nabla_{z_{t}}L_{t}$ is a square matrix. If $z_{t}^{*}$ is comprised of
$x_{t+1:T+1}^{*}$, $u_{t:T}^{*}$ and multipliers satisfying Eq. 11 such that
$L_{t}(z_{t}^{*},x_{t}^{*})=0$, then assuming this matrix is non-singular, the
Implicit Function Theorem states that there must exist a unique function
$\Pi_{t}(x_{t})$ and open set $\mathcal{X}_{t}^{*}\subset\mathcal{X}$
containing $x_{t}^{*}$ such that $L_{t}(\Pi_{t}(x_{t}),x_{t}))=0$ for all
$x_{t}\in\mathcal{X}_{t}^{*}$. By the uniqueness of this function, we must
have that for all $x_{t}\in\mathcal{X}_{t}^{*}$,
$[\Pi_{t}(x_{t})]_{u_{t}}=\pi_{t}(x_{t})$, where $[\Pi_{t}(x_{t})]_{u_{t}}$
selects the components of the function $\Pi_{t}$ corresponding to the subset
of $z_{t}$ containing $u_{t}$. Therefore, for all
$x_{t}\in\mathcal{X}_{t}^{*}$,
$\nabla_{x_{t}}\pi_{t}(x_{t})=\nabla_{x_{t}}([\Pi_{t}(x_{t})]_{u_{t}})=-[[\nabla_{z_{t}}L_{t}]^{-1}\nabla_{x_{t}}L_{t}]_{u_{t}}$.

Observe that the conditions $L_{t}(z_{t},x_{t})=0$ contain as a subset the
conditions $L_{s}(z_{s},x_{s})=0$, $s\in\mathbf{T_{t+1}}$. If the matrices
$\nabla_{x_{s}}L_{s}(z_{s},x_{s})$, $s\in\mathbf{T_{t+1}}$ are also non-
singular, then in some neighborhood of $z_{t}^{*}$, the constraints
$u_{s}^{*}=\pi_{s}(x_{s}^{*})$, $s\in\mathbf{T_{t+1}}$ are equivalent to
$L_{s}(z^{*}_{s},x^{*}_{s})=0$, motivating the removal of the constraints Eq.
9b from the conditions Eq. 11.

For games and corresponding solutions satisfying the stated assumptions,
Theorem 2.4 suggests a method for computing those solutions. Evaluating the
conditions Eq. 11 only requires the evaluation of the policy gradients
$\nabla_{x_{s}}\pi_{s}(x_{s})$, and not the policies themselves.

The procedure we propose for computing GFNE trajectories is to find a solution
to the conditions Eq. 11, which can then be checked against a sufficiency
condition to ensure that the solution indeed constitutes a GFNE.

######  Theorem 2.6 (Sufficient Conditions).

Consider any set of states $\\{x_{s}^{*}$, $s\in\mathbf{T^{+}_{t}}\\}$ and
controls $\\{u_{s}^{*}$, $s\in\mathbf{T_{t}}\\}$, which together with
multipliers $\\{\lambda_{s}^{i}\in\mathbb{R}^{n};\ s\in\mathbf{T_{t}},\
i\in\mathbf{N}\\}$, $\\{\mu_{s}^{i}\in\mathbb{R}^{a^{i}_{s}};\
s\in\mathbf{T_{t}^{+}},\ i\in\mathbf{N}\\}$,
$\\{\gamma_{s}^{i}\in\mathbb{R}^{b^{i}_{s}};\ s\in\mathbf{T_{t}^{+}},\
i\in\mathbf{N}\\}$, and $\\{\psi_{s}^{i}\in\mathbb{R}^{m^{-i}};\
s\in\mathbf{T_{t+1}},\ i\in\mathbf{N}\\}$ satisfy the conditions Eq. 11, with
the matrix $\nabla_{z_{s}}L_{s}$ non-singular for all $s\in\mathbf{T}$. If
additionally, for all $i\in\mathbf{N}$,

(12a) $\displaystyle\ \ \mathrlap{\sum_{s=t}^{T}\begin{bmatrix}d_{x,s}\\\
d_{u,s}\end{bmatrix}^{\intercal}\nabla_{x_{s},u_{s}}^{2}\mathcal{L}_{s}^{i*}\begin{bmatrix}d_{x,s}\\\
d_{u,s}\end{bmatrix}+d_{x,T+1}^{\intercal}\nabla^{2}l_{T+1}^{i}(x_{T+1}^{*})d_{x,T+1}>0,}$
(12b) $\displaystyle\ \ \forall\\{d_{x,s},d_{u,s}\\}:\ $ $\displaystyle
0=d_{u_{t}}^{-i}-\nabla_{x}\pi_{t}^{-i}(x_{t}^{*})d_{x,t},$ (12c)
$\displaystyle 0=d_{u_{s}}-\nabla_{x}\pi_{s}(x_{s}^{*})d_{x,s},$
$\displaystyle s\in\mathbf{T_{t}},$ (12d) $\displaystyle
0=d_{x,s+1}-\nabla_{x}f_{s}(x_{s}^{*},u_{s}^{*})d_{x,s}-\nabla_{u}f(x_{s}^{*},u_{s}^{*})d_{u_{s}},\
\ $ $\displaystyle s\in\mathbf{T_{t}}$

then the trajectory $x_{s}^{*}$, $u_{s}^{*}$ constitutes a GFNE trajectory for
the subgame originating from $x_{t}^{*}$ at stage $t$. In Eq. 12,
$\mathcal{L}_{s}^{*}$ is the stage-wise Lagrangian for player $i$, defined as
the following:

(13)
$\mathcal{L}_{s}^{*}:=\big{[}l_{s}^{i}-(\lambda_{s}^{*})^{\intercal}(x_{s+1}^{*}-f_{s})-(\mu_{s}^{i})^{\intercal}h_{s}^{i}-(\gamma_{s}^{i})^{\intercal}g_{s}^{i}-(\psi_{s}^{i})^{\intercal}(u_{s}^{*}-\pi_{s})\big{]}_{x_{s}^{*},u_{s}^{*}}.$

######  Proof 2.7.

The set of $d_{x,s}$, $d_{u,s}$ satisfying Eqs. 12b, 12c, and 12d is a super-
set of the critical constraint cone [17, Eq. 12.53], therefore the trajectory
$x_{s}^{*},u_{s}^{*}$ must constitute a true local minimum of the problems Eq.
9 for stage $t$ and each player $i\in\mathbf{N}$, as stated in [17, Theorem
12.6].

The sufficiency condition outlined in Theorem 2.6 is stricter than necessary
since it ignores other active constraints which reduce the volume of the
critical constraint cone, and could be relaxed by considering the
linearization of all active constraints.

Although Theorems 2.4 and 2.6 together outline a procedure for computing GFNE
trajectories, there remain some difficulties which must be addressed if such a
procedure is to be practical. While the conditions Eq. 11 do not require the
evaluation of the policies $\pi_{s}(x_{s}),s\in\mathbf{T_{t+1}}$ explicitly,
evaluating the policy gradients $\nabla_{x}\pi_{s}(x_{s})$ is required, and
their evaluation involves inverting a matrix which depends on second-order
derivatives of all policies $\pi_{r}(x_{r})$, $r\in\mathbf{T_{s+1}}$.
Furthermore, evaluating second-order derivatives of any policy requires
evaluating third-order derivatives of all subsequent policies, and so forth.
The effect of this is that $T^{th}$-order derivatives of dynamic and
constraint functions appearing at the late stages of the game must be computed
to evaluate the conditions Eq. 11 when $t=1$. While technically possible, this
requirement is impractical for many games. We therefore introduce a reasonable
approximation to the equilibrium policies $\pi_{t}(\cdot)$, which we denote by
$\hat{\pi}_{t}(\cdot)$. By ignoring all higher-order derivatives of later-game
policies $\hat{\pi}_{s}(\cdot)$, $s\in\mathbf{T_{t+1}}$, these approximate
policies are computed recursively in a computationally tractable manner.

######  Definition 2.8 (Quasi-Equilibrium Policies).

We approximate $\pi_{t}(x_{t})$ by $\hat{\pi}_{t}(x_{t})$, which for each
$t\in\mathbf{T}$ is defined as producing controls $u_{t}^{*}$, such that there
exist a sub-game trajectory and corresponding multipliers satisfying the
following conditions:

(14) $\displaystyle 0$
$\displaystyle=\nabla_{u_{s}^{i}}\bigg{[}l_{s}^{i}+f_{s}^{\intercal}\lambda_{s}^{i}-h_{s}^{i\intercal}\mu_{s}^{i}-g_{s}^{i^{\intercal}}\gamma_{s}^{i}$
$\displaystyle\bigg{]}_{x_{s}^{*},u_{s}^{*}},$ $\displaystyle i\in\mathbf{N},\
s\in\mathbf{T_{t}}$ $\displaystyle 0$
$\displaystyle=\nabla_{x_{s}}\bigg{[}l_{s}^{i}-\lambda_{s-1}^{i}+f_{s}^{\intercal}\lambda_{s}^{i}-h_{s}^{i^{\intercal}}\mu_{s}^{i}-g_{s}^{i\intercal}\gamma_{s}^{i}\bigg{]}_{x_{s}^{*},u_{s}^{*}}+$
$\displaystyle\tilde{\nabla}_{x_{s}}\hat{\pi}_{s}^{-i\intercal}\psi_{s}^{,}$
$\displaystyle i\in\mathbf{N},\ s\in\mathbf{T_{t+1}},$ $\displaystyle 0$
$\displaystyle=\nabla_{u^{-i}_{s}}\bigg{[}l_{s}^{i}+f_{s}^{\intercal}\lambda_{s}^{i}-h_{s}^{i^{\intercal}}\mu_{s}^{i}-g_{s}^{i\intercal}\gamma_{s}^{i}-\psi_{s}^{i}$
$\displaystyle\bigg{]}_{x_{s}^{*},u_{s}^{*}},$ $\displaystyle i\in\mathbf{N},\
s\in\mathbf{T_{t+1}},$ $\displaystyle 0$
$\displaystyle=\nabla_{x_{T+1}}\bigg{[}l_{T+1}^{i}-\lambda_{T}^{i}-h_{T+1}^{i^{\intercal}}\mu_{T+1}^{i}-g_{T+1}^{i\intercal}\gamma_{T+1}^{i}$
$\displaystyle\bigg{]}_{x_{T+1}^{*}},$ $\displaystyle i\in\mathbf{N},$
$\displaystyle 0$ $\displaystyle=x^{*}_{s+1}-f_{s}(x^{*}_{s},u^{*}_{s}),$
$\displaystyle s\in\mathbf{T_{t}},$ $\displaystyle 0$
$\displaystyle=h_{s}^{i}(x_{s}^{*},u_{s}^{*}),$ $\displaystyle
i\in\mathbf{N},\ s\in\mathbf{T_{t}},$ $\displaystyle 0$ $\displaystyle\leq
g_{s}^{i}(x_{s}^{*},u_{s}^{*})\perp\gamma_{s}^{i}\geq 0,$ $\displaystyle
i\in\mathbf{N},\ s\in\mathbf{T_{t}},$ $\displaystyle 0$
$\displaystyle=h_{T+1}^{i}(x_{T+1}^{*}),$ $\displaystyle i\in\mathbf{N},$
$\displaystyle 0$ $\displaystyle\leq
g_{T+1}^{i}(x_{T+1}^{*})\perp\gamma_{T+1}^{i}\geq 0,$ $\displaystyle
i\in\mathbf{N}.$

The conditions Eq. 14 are nearly the same as Eq. 11, although the policies
$\pi_{s}(x_{s})$ are replaced with the approximate policies
$\hat{\pi}_{s}(x_{s})$, and the gradients taken with respect to these
approximate policies are replaced with what we denote as _quasi-gradients_ ,
$\tilde{\nabla}_{x_{s}}\hat{\pi}_{s}(x_{s})$. Letting
$\hat{L}_{t}(z_{t},x_{t}^{*})$ represent the concatenation of active
conditions in Eq. 14 (analogous to $L_{t}(z_{t},x_{t}^{*})$ in Theorem 2.4),
then the quasi-gradient of $\hat{\pi}_{t}(x_{t})$ is defined as

(15)
$\tilde{\nabla}_{x_{t}}\hat{\pi}_{t}(x_{t}):=-[[\check{\nabla}_{z_{t}}\hat{L}_{t}]^{-1}\nabla_{x_{t}}\hat{L}_{t}]_{u_{t}},$

where $\check{\nabla}_{z_{t}}\hat{L}_{t}$, is approximate the Jacobian of
$\hat{L}_{t}$ formed by replacing any term of the form
$\nabla_{x_{s}}[\tilde{\nabla}_{x_{s}}\hat{\pi}_{s}(x_{s})^{-i\intercal}\psi_{s}^{i}]$
(appearing in the true Jacobian $\nabla_{z_{t}}\hat{L}_{t}$) with the $0$
matrix. If the matrix $\check{\nabla}_{z_{t}}\hat{L}_{t}$ is singular at some
$(z_{t},x_{t})$, we say that the policy quasi-gradient does not exist at that
point.

As with the definition of the true equilibrium policies Eq. 6, the policies
$\hat{\pi}_{t}(x_{t})$ are not true functions, in that there may be multiple
solutions to Eq. 14. Nevertheless, we treat these policies as mapping to one
arbitrarily chosen yet particular solution. So long as
$\check{\nabla}_{z_{t}}\hat{L}_{t}$ is non-singular, the solutions to Eq. 14
are isolated, and a quasi-gradient can be formed around any such solution.
This resultant quasi-gradient can then be used to define the conditions Eq. 14
at the preceding stage $t-1$.

The approximate policies $\hat{\pi}_{t}(x_{t})$ and corresponding quasi-
gradients can be evaluated without the need for computing any third- or
higher-order derivatives of any constraint or objective terms of the game.
Solutions satisfying the conditions Eq. 14 will not satisfy the conditions Eq.
11 in general. Rather, the solutions to Eq. 14 will be distinct from solutions
to Eq. 11, and therefore we introduce the notion of a Generalized Feedback
Quasi-Nash Equilibrium (GFQNE) to characterize these solutions.

######  Definition 2.9 (GFQNE).

Let $\\{x_{s}^{*};\ s\in\mathbf{T_{t}^{+}},\ x_{t}^{*}=\hat{x}_{t}\\}$,
$\\{u_{s}^{*};\ s\in\mathbf{T_{t}}\\}$, $\\{\lambda_{s}^{i}\in\mathbb{R}^{n};\
s\in\mathbf{T_{t}},\ i\in\mathbf{N}\\}$,
$\\{\mu_{s}^{i}\in\mathbb{R}^{a^{i}_{s}};\ s\in\mathbf{T_{t}^{+}},\
i\in\mathbf{N}\\}$, $\\{\gamma_{s}^{i}\in\mathbb{R}^{b^{i}_{s}};\
s\in\mathbf{T_{t}^{+}},\ i\in\mathbf{N}\\}$, and
$\\{\psi_{s}^{i}\in\mathbb{R}^{m^{-i}};\ s\in\mathbf{T_{t+1}},\
i\in\mathbf{N}\\}$ be such that the conditions Eq. 14 are satisfied. Then we
say that the trajectory $\\{x_{s}^{*};\ s\in\mathbf{T_{t}^{+}},\
x_{t}^{*}=\hat{x}_{t}\\},\\{u_{s}^{*};\ s\in\mathbf{T_{t}}\\}$ constitutes a
Generalized Feedback Quasi-Nash Equilibrium (GFQNE) trajectory for the sub-
game originating from $\hat{x}_{t}$ at stage $t$.

If all cost functionals Eq. 2 in the game are convex, and all dynamic Eq. 1
and non-dynamic Eqs. 3a to 3b constraints are linear, then the true
equilibrium policies Eq. 9 are piecewise linear, implying that
$\tilde{\nabla}_{x_{s}}\hat{\pi}_{s}(x_{s})\equiv\nabla_{x_{s}}\hat{\pi}_{s}(x_{s})$,
and $\check{\nabla}_{z_{t}}\hat{L}_{t}\equiv\nabla_{z_{t}}\hat{L}_{t}$.
Therefore Eq. 14 are equivalent to Eq. 11, and by the convexity of the cost
functionals, any solution to Eq. 14 also satisfies Eq. 12, implying that all
GFQNE are GFNE in the convex-linear setting.

In the general setting, in addition to not requiring GFQNE solutions to
satisfy any second-order conditions analogous to Eq. 12, the policy quasi-
gradients will in general not equal the policy gradients. The difference
between the GFQNE and GFNE trajectories can be understood in terms of two
approximations introduced at each stage of the game, the effects of which are
propagated over the game horizon $T$.

The first approximation is the difference between the true gradient of a
policy (either $\nabla\hat{\pi}_{t}$ or $\nabla\pi_{t}$) and the quasi-
gradient which can be computed ($\tilde{\nabla}\hat{\pi}_{t}$ and
$\tilde{\nabla}\pi_{t}$, respectively). Notice that for the ultimate stage of
the game $t=T$, there are no sub-game policies to consider, and therefore the
the set of possible equilibrium policies $\pi_{T}$ is a subset of the set of
possible approximate equilibrium policies $\hat{\pi}_{T}$. Furthermore,
whenever $\pi_{T}\equiv\hat{\pi}_{T}$, it follows that
$\tilde{\nabla}\hat{\pi}_{T}\equiv\nabla\hat{\pi}_{T}$.

For the penultimate stage $t=T-1$, the necessary conditions Eq. 14 are
equivalent to Eq. 11, which again implies that the set of possible equilibrium
policies $\pi_{T-1}$ is a subset of the set of possible approximate
equilibrium policies $\hat{\pi}_{T-1}$. However, even when
$\pi_{T-1}\equiv\hat{\pi}_{T-1}$,
$\tilde{\nabla}\hat{\pi}_{T-1}\neq\nabla\hat{\pi}_{T-1}\equiv\nabla\pi_{T-1}$.
This is true not only for the penultimate stage, but for all stages $t<T-1$.
The error between the true and approximate policy gradients can be quantified
by observing that, for any square matrices $A,B$ of compatible dimension such
that $A$, $A+B$ are non-singular [11]:

(16) $(A+B)^{-1}=A^{-1}-A^{-1}B(A+B)^{-1}$

where, in the context of Eq. 15, $(A+B)$ and $A$ correspond to
${\nabla}_{z_{t}}\hat{L}_{t}$ and $\check{\nabla}_{z_{t}}\hat{L}_{t}$,
respectively.222The usual interpretation of $A+B$ in this setting would be for
the perturbed or approximate matrix, although the reversed interpretation we
assign is also valid. In this interpretation, $B$ is a matrix comprised of
terms of the form
$\nabla_{x_{s}}[\tilde{\nabla}_{x_{s}}\hat{\pi}_{s}(x_{s})^{-i\intercal}\psi_{s}^{i}]$
appearing in the locations they do in $\nabla_{z_{t}}\hat{L}_{t}$, and zero
elsewhere. By direct substitution, right-multiplying both sides by
$\nabla_{x_{t}}\hat{L}_{t}$, bounding the norm of “$B$,” and applying the
triangle inequality, it follows that

(17)
$\frac{\|\tilde{\nabla}_{x_{t}}\hat{\pi}_{t}(x_{t})-\nabla_{x_{t}}\hat{\pi}_{t}(x_{t})\|_{2}}{\|{\nabla}_{x_{t}}\hat{\pi}_{t}(x_{t})\|_{2}}\leq\epsilon\cdot
N(T-t)\cdot\|\check{\nabla}_{z_{t}}\hat{L}_{t}^{-1}\|_{2},$

where

(18)
$\epsilon:=\max_{s\in\mathbf{T_{t+1}},i\in\mathbf{N}}\|\nabla_{x_{s}}[\tilde{\nabla}_{x_{s}}\hat{\pi}_{s}(x_{s})^{-i\intercal}\psi_{s}^{i}]\|_{2}.$

Analogous results for other choices of matrix norms are readily made. The
inequality Eq. 17 bounds the relative error of the policy gradient in terms of
the second-order derivative terms of sub-game policies, and the approximate
Jacobian $\check{\nabla}\hat{L}_{t}$. For highly non-linear policies
$\hat{\pi}_{s}$, $\epsilon$ may be large, and the bound Eq. 17 may be
uninformative.

The second source of approximation first enters at stage $t=T-2$, and is
reintroduced at every preceding stage. Given sub-game policies
$\hat{\pi}_{s},\ s\in\mathbf{T_{t+1}}$, each $\hat{\pi}_{t}$ would ideally
evaluate to an equilibrium solution to problems analogous to Eq. 9, though
with the sub-game policies appearing in Eq. 9b replaced with the approximate
sub-game policies $\hat{\pi}_{s}(x_{s})$. We denote such policies as the
idealized approximate policies. Instead, $\hat{\pi}_{t}$ is characterized as a
solution to the approximate necessary conditions Eq. 14, where all gradients
of $\hat{\pi}_{s}$ are replaced with quasi-gradients. In general, the
approximation error in $\tilde{\nabla}\hat{\pi}_{s},s\in\mathbf{T_{t+1}}$ can
greatly influence the resultant difference between solutions generated by
$\hat{\pi}_{t}$ and the idealized policies, making it difficult (or
potentially impossible) to bound the difference for non-infinitesimal errors.

It is important to emphasize that these two forms of approximation are
recursively made at each stage of the game. The difference between the true
and approximate equilibrium policies will, in general, become increasingly
pronounced when computing backwards from the ultimate stage $T$. Therefore it
is likely that the GFNE and GFQNE trajectories are considerably different.
Despite this, it is simply intractable to compute GFNE trajectories for non-
trivial games, and we believe GFQNE trajectories are the closest
computationally tractable approximation possible.

### Note on constraint dimension

So far we have also made an important, limiting assumption, which is that the
matrices $\nabla_{z_{t}}L_{t}$ and $\check{\nabla}_{z_{t}}\hat{L}_{t}$ are
non-singular for all $t\in\mathbf{T}$. For many common forms of constraints
Eq. 3a, Eq. 3b, this assumption cannot hold. This will occur, for example,
when there is a terminal constraint on the entire game state, such as
$h_{T+1}^{i}(x_{T+1}):=x_{T+1}$. If $m_{t}^{i}<n$, then the matrices
$\check{\nabla}_{z_{t}}\hat{L}_{t}$ necessarily must be singular. Since many
games involve constraints of this form, we handle them in the following way.

If at any stage $t$, the matrix $\check{\nabla}_{z_{t}}\hat{L}_{t}$ is found
to be singular, but the game is otherwise well-posed,333For example, the
quadratic cost functionals of every player have sufficient curvature in the
tangent cone of the game. then this is likely due to an over-constrained sub-
game. In this situation, we can combine the stage $t$ with the preceding stage
$t-1$, and define new combined-stage dynamics and constraint functions
accordingly. For example, assume at stage $t$ the matrix
$\check{\nabla}_{z_{t}}\hat{L}_{t}$ is singular. We then define
$\hat{u}_{t-1}:=[u_{t-1}^{\intercal}\ u_{t}^{\intercal}]^{\intercal}$,
$\hat{\mathcal{U}}_{t-1}^{i}:=\mathcal{U}_{t-1}^{i}\times\mathcal{U}_{t}^{i}$,
and the updated dynamic, constraint, and stage-wise cost functionals as

(19a) $\displaystyle\hat{f}_{t-1}(x_{t-1},\hat{u}_{t-1})$
$\displaystyle:=f_{t}(f_{t-1}(x_{t-1},u_{t-1}),u_{t}),$ (19b)
$\displaystyle\hat{g}^{i}_{t-1}(x_{t-1},\hat{u}_{t-1})$
$\displaystyle:=[g^{i}_{t-1}(x_{t-1},u_{t-1})^{\intercal}\
g^{i}_{t}(f(x_{t-1},u_{t-1}),u_{t})^{\intercal}]^{\intercal},$ (19c)
$\displaystyle\hat{h}^{i}_{t-1}(x_{t-1},\hat{u}_{t-1})$
$\displaystyle:=[h^{i}_{t-1}(x_{t-1},u_{t-1})^{\intercal}\
h^{i}_{t}(f(x_{t-1},u_{t-1}),u_{t})^{\intercal}]^{\intercal},$ (19d)
$\displaystyle\hat{l}_{t-1}^{i}(x_{t-1},\hat{u}_{t-1})$
$\displaystyle:=l_{t-1}^{i}(x_{t-1},u_{t-1})+l_{t}^{i}(f(x_{t-1},u_{t-1}),u_{t}).$

In this procedure, we effectively reduce the number of stages of the game by
$1$, but the dimension of all controls input to the game and the cost and
constraints imposed upon each player are unchanged.

Throughout the remainder of this paper, we will assume that game stages are
combined as necessary to ensure the subgame policy quasi-gradients are well-
defined, and the game horizon $T$, dynamics, constraints, and cost-functionals
all reflect any such modifications. In what follows we focus on the derivation
of numerical methods for computing Generalized Feedback Quasi-Nash Equilibria.
We begin our presentation by considering a special-case, which will serve as a
building block for more general methods.

##  3 Equality-Constrained LQ Games

We consider the case in which the dynamics equation describing the game
evolution Eq. 1 is linear in its arguments, the cost-functionals Eq. 2 for
each player are quadratic functions of the state and control variables, and
each player is subject only to linear equality constraints.

In particular, let

(20) $x_{t+1}=A_{t}x_{t}+B_{t}^{1}u_{t}^{1}+...+B_{t}^{N}u_{t}^{N}+c_{t},\ \
t\in\mathbf{T},$

for (time-varying) matrices $A_{t}\in\mathbb{R}^{n\times n}$,
$B_{t}^{i}\in\mathbb{R}^{m_{t}^{i}\times n}$, and vectors
$c_{t}\in\mathbb{R}^{n}$. Associated with the dynamic constraints are
multipliers $\lambda_{t}^{i}$ for each player $i\in\mathbf{N}$. Let

(21) $\displaystyle B_{t}$
$\displaystyle:=\begin{bmatrix}B_{t}^{1}&...&B_{t}^{N}\end{bmatrix},\ \ \ \
\hat{B}_{t}:=\begin{bmatrix}B_{t}^{1}\\\ &\ddots\\\ &&B_{t}^{N}\end{bmatrix},\
\ \ \ \lambda_{t}:=\begin{bmatrix}\lambda_{t}^{1}\\\ \vdots\\\
\lambda_{t}^{N}\end{bmatrix},$ $\displaystyle\tilde{B}_{t}$
$\displaystyle:=\begin{bmatrix}B_{t}^{2}&\ldots&B_{t}^{N}\\\ &&&\ddots\\\
&&&&B_{t}^{1}&\ldots&B_{t}^{N-1}\end{bmatrix}.$

In this setting, the cost functionals for each player can be expressed as:

(22) $\displaystyle l^{i}_{t}(x_{t},u_{t})$
$\displaystyle:=\frac{1}{2}\bigg{(}\begin{bmatrix}x_{t}\\\
u_{t}\end{bmatrix}^{\intercal}\begin{bmatrix}Q_{t}^{i}&S_{t}^{i\intercal}\\\
S_{t}^{i}&R_{t}^{i}\end{bmatrix}\begin{bmatrix}x_{t}\\\
u_{t}\end{bmatrix}+2\begin{bmatrix}x_{t}\\\
u_{t}\end{bmatrix}^{\intercal}\begin{bmatrix}q_{t}^{i}\\\
r_{t}^{i}\end{bmatrix}\bigg{)},$ $\displaystyle l^{i}_{T+1}(x_{T+1})$
$\displaystyle:=\frac{1}{2}\bigg{(}x_{T+1}^{\intercal}Q_{T+1}^{i}x_{T+1}+2x_{T+1}^{\intercal}q_{T+1}^{i}\bigg{)},$

for (time-varying) matrices $Q_{t}^{i}\in\mathbb{R}^{n\times n}$,
$S_{t}^{i}\in\mathbb{R}^{m_{t}\times n}$, $R_{t}^{i}\in\mathbb{R}^{m_{t}\times
m}$, and vectors $q_{t}^{i}\in\mathbb{R}^{n}$,
$r_{t}^{i}\in\mathbb{R}^{m_{t}}$. For notational purposes, let the terms
$R_{t}^{i}$, $S_{t}^{i}$, and $r_{t}^{i}$ be comprised of sub-matrices,
$R_{t}^{i,j,k}\in\mathbb{R}^{m_{t}^{j}\times m_{t}^{k}}$,
$S_{t}^{i,j}\in\mathbb{R}^{m_{t}^{j}\times n}$, and sub-vectors
$r_{t}^{i,j}\in\mathbb{R}^{m_{t}^{j}}$, for $j,k\in\mathbf{N}$:

(23) $\displaystyle
R_{t}^{i}:=\begin{bmatrix}R_{t}^{i,1,1}&\ldots&R_{t}^{i,1,N}\\\
\vdots&\ddots&\vdots\\\ R_{t}^{i,N,1}&\ldots&R_{t}^{i,N,N}\end{bmatrix},\ \ \
\ S_{t}^{i}:=\begin{bmatrix}S_{t}^{i,1}\\\ \vdots\\\
S_{t}^{i,N}\end{bmatrix},\ \ \ \ r_{t}^{i}:=\begin{bmatrix}r_{t}^{i,1}\\\
\vdots\\\ r_{t}^{i,N}\end{bmatrix}$

We additionally make use of the following matrix terms for brevity, which
combine components from the cost functionals of all players:

(24) $\displaystyle
R_{t}:=\begin{bmatrix}R_{t}^{1,1,1}&\ldots&R_{t}^{1,1,N}\\\
R_{t}^{2,2,1}&\ldots&R_{t}^{2,2,N}\\\ \vdots&\ddots&\vdots\\\
R_{t}^{N,N,1}&\ldots&R_{t}^{N,N,N}\end{bmatrix},\ \ \ \ $ $\displaystyle
S_{x_{t}}:=\begin{bmatrix}S_{t}^{1,1}\\\ S_{t}^{2,2}\\\ \vdots\\\
S_{t}^{N,N}\end{bmatrix},\ \ \ \ \ \ \ \ $ $\displaystyle
r_{t}:=\begin{bmatrix}r_{t}^{1,1}\\\ r_{t}^{2,2}\\\ \vdots\\\
r_{t}^{N,N}\end{bmatrix},$ $\displaystyle Q_{t}:=\begin{bmatrix}Q_{t}^{1}\\\
\vdots\\\ Q_{t}^{N}\end{bmatrix},\ \ \ \ $ $\displaystyle
S_{u_{t}}:=\begin{bmatrix}S_{t}^{1\intercal}\\\ \vdots\\\
S_{t}^{N\intercal}\end{bmatrix},\ \ \ \ \ \ \ \ $ $\displaystyle
q_{t}:=\begin{bmatrix}q_{t}^{1}\\\ \vdots\\\ q_{t}^{N}\end{bmatrix},$
$\displaystyle\tilde{R}_{t}:=\mathrlap{\begin{bmatrix}R_{t}^{1,2,1}&\ldots&R_{t}^{1,2,N}\\\
\vdots&\ddots&\vdots\\\ R_{t}^{1,N,1}&\ldots&R_{t}^{1,N,N}\\\ &&&\ddots\\\
&&&&R_{t}^{N,1,1}&\ldots&R_{t}^{N,1,N}\\\ &&&&\vdots&\ddots&\vdots\\\
&&&&R_{t}^{N,N-1,1}&\ldots&R_{t}^{N,N-1,N}\end{bmatrix},\tilde{S}_{x_{t}}:=\begin{bmatrix}S_{t}^{1,2}\\\
\vdots\\\ S_{t}^{1,N}\\\ S_{t}^{2,1}\\\ S_{t}^{2,3}\\\ \vdots\\\
S_{t}^{2,N}\\\ \vdots\\\ S_{t}^{N,N-1}\end{bmatrix}}$

We impose the regularity assumptions

(25) $R_{t}^{i,i,i}\succ 0,\ \ R_{t}^{i}\succeq 0,\ \ Q_{t}^{i}\succeq 0$

to ensure that the objective of each player is strictly convex. These
conditions are sufficient for any solution to the conditions Eq. 11 to
constitute a GFNE, as stated in Theorem 2.6, but not necessary.

The constraints imposed upon each player take the form

(26) $\displaystyle 0$
$\displaystyle=H_{x_{t}}^{i}x_{t}+H_{u_{t}^{1}}^{i}u_{t}^{1}+...+H_{u_{t}^{N}}^{i}u_{t}^{N}+h_{t}^{i},\
\ t\in\mathbf{T}$ $\displaystyle 0$
$\displaystyle=H_{x_{T+1}}^{i}x_{T+1}+h_{T+1}^{i},$

for matrices $H_{x_{t}}^{i}\in\mathbb{R}^{a_{t}^{i}\times n}$,
$H_{u_{t}^{j}}^{i}\in\mathbb{R}^{a_{t}^{i}\times m_{t}^{j}}$, and vectors
$h_{t}^{i}\in\mathbb{R}^{a_{t}^{i}}$, where $a_{t}^{i}$ is the dimension of
the equality constraint imposed on player $i$ at stage $t\in\mathbf{T^{+}}$.
As in Section 2, we associate multipliers
$\mu_{t}^{i}\in\mathbb{R}^{a_{t}^{i}}$, $t\in\mathbf{T^{+}}$ with these
constraints for each player $i\in\mathbf{N}$. Let

(27) $\displaystyle H_{u_{t}}$
$\displaystyle:=\begin{bmatrix}H_{u_{t}^{1}}^{1}&\ldots&H_{u_{t}^{N}}^{1}\\\
\vdots&\ddots&\vdots\\\
H_{u_{t}^{1}}^{N}&\ldots&H_{u_{t}^{N}}^{N}\end{bmatrix},\ \ $
$\displaystyle\hat{H}_{u_{t}}:=\begin{bmatrix}H_{u_{t}^{1}}^{1}\\\ &\ddots\\\
&&H_{u_{t}^{N}}^{N}\end{bmatrix},$ $\displaystyle H_{x_{t}}$
$\displaystyle:=\begin{bmatrix}H_{x_{t}}^{1}\\\ \vdots\\\
H_{x_{t}}^{N}\end{bmatrix},\ \ \ $
$\displaystyle\hat{H}_{x_{t}}:=\begin{bmatrix}H_{x_{t}}^{1}\\\ &\ddots\\\
&&H_{x_{t}}^{N}\end{bmatrix},$ $\displaystyle h_{t}^{\intercal}$
$\displaystyle:=\begin{bmatrix}(h_{t}^{1})^{\intercal}&\ldots&(h_{t}^{N})^{\intercal}\end{bmatrix},$
$\displaystyle\mu_{t}^{\intercal}:=\begin{bmatrix}(\mu_{t}^{1})^{\intercal}&\ldots&(\mu_{t}^{N})^{\intercal}\end{bmatrix},$
$\displaystyle\tilde{H}_{u_{t}}$
$\displaystyle:=\begin{bmatrix}H_{u_{t}^{2}}^{1}&\ldots&H_{u_{t}^{N}}^{1}\\\
&&&\ddots\\\ &&&&H_{u_{t}^{1}}^{N}&\ldots&H_{u_{t}^{N-1}}^{N}\end{bmatrix}$

Due to the linearity of all dynamic and non-dynamic constraint functions
appearing in the game, and the quadratic cost functionals, the solutions of
the conditions Eq. 11 and Eq. 14 will be identical, as stated in Section 2.
Therefore we will use the terms $K_{t}$ and $\nabla_{x_{t}}\pi_{t}(x_{t})$
interchangeably in this section.

Using the above-defined dynamic, constraint and cost terms, we are able to
proceed with development of numerical methods for computing GFNE solutions to
this game. Instead of taking a dynamic programming perspective as is, for
example, taken in the classic derivation of Feedback Nash Equilibria for
unconstrained LQ games in [1, Chapter 6], we derive our method using what we
refer to as a _dynamic matrix factorization_. The primary idea behind this
derivation is simply that the computation used to evaluate $K_{t+1}$ can be
reused to compute $K_{t}$ efficiently.

To start, the conditions Eq. 14 for stage $t=T$ can be expressed in terms of
the following matrix system:

(28)
$\begin{bmatrix}R_{T}&-\hat{H}_{u_{T}}^{\intercal}&\hat{B}_{T}^{\intercal}&\\\
H_{u_{T}}\\\ -B_{T}&&&I_{n}\\\
&&-I_{N*n}&Q_{T+1}&\hat{H}_{x_{T+1}}^{\intercal}\\\
&&&H_{x_{T+1}}\end{bmatrix}\begin{bmatrix}u_{T}\\\ \mu_{T}\\\ \lambda_{T}\\\
x_{T+1}\\\ \mu_{T+1}\end{bmatrix}+\begin{bmatrix}S_{x_{t}}\\\ H_{x_{T}}\\\
-A_{T}\\\ 0\\\ 0\end{bmatrix}x_{T}+\begin{bmatrix}r_{t}\\\ h_{T}\\\ -c_{T}\\\
q_{T+1}\\\ h_{T+1}\end{bmatrix}=0$

In Eq. 28, the matrices $I_{\Box}$ denote the $\Box\times\Box$-dimensional
identity matrix. Letting the system in Eq. 28 be denoted in shorthand as

(29) $M_{T}z_{T}+N_{T}x_{T}+n_{T}=0,$

where $z_{T}:=[u_{T}^{\intercal}\ \mu_{T}^{\intercal}\
\lambda_{T}^{\intercal}\ x_{T+1}^{\intercal}\
\mu_{T+1}^{\intercal}]^{\intercal}$, we have that

(30) $\displaystyle\pi(x_{T})$ $\displaystyle:=K_{T}x_{T}+k_{T},$
$\displaystyle\lambda_{T}$
$\displaystyle:=K_{\lambda_{T}}x_{T}+k_{\lambda_{T}},$ $\displaystyle\mu_{T}$
$\displaystyle:=K_{\mu_{T}}x_{T}+k_{\mu_{T}},$ $\displaystyle\mu_{T+1}$
$\displaystyle:=K_{\mu_{T+1}}x_{T}+k_{\mu_{T+1}},$ $\displaystyle K_{T}$
$\displaystyle:=-[M_{T}^{-1}N_{T}]_{u_{T}},\ \ $ $\displaystyle
k_{T}:=-[M_{T}^{-1}n_{T}]_{u_{T}},$ $\displaystyle K_{\lambda_{T}}$
$\displaystyle:=-[M_{T}^{-1}N_{T}]_{\lambda_{T}},\ \ $ $\displaystyle
k_{\lambda_{T}}:=-[M_{T}^{-1}n_{T}]_{\lambda_{T}},$ $\displaystyle
K_{\mu_{T}}$ $\displaystyle:=-[M_{T}^{-1}N_{T}]_{\mu_{T}},\ \ $ $\displaystyle
k_{\mu_{T}}:=-[M_{T}^{-1}n_{T}]_{\mu_{T}},$ $\displaystyle K_{\mu_{T+1}}$
$\displaystyle:=-[M_{T}^{-1}N_{T}]_{\mu_{T+1}},\ \ $ $\displaystyle
k_{\mu_{T+1}}:=-[M_{T}^{-1}n_{T}]_{\mu_{T+1}},$

For any stage $t$, we also make use of the matrix

(31)
$\displaystyle\Pi_{t}^{\intercal}:=\setcounter{MaxMatrixCols}{11}\begin{bmatrix}K_{t}^{2\intercal}&\cdots&K_{t}^{N\intercal}\\\
&&&K_{t}^{1\intercal}&K_{t}^{3\intercal}&\cdots&K_{t}^{N\intercal}\\\
&&&&&&&\ddots\\\
&&&&&&&&K_{t}^{1\intercal}&\cdots&K_{t}^{(N-1)\intercal}\end{bmatrix}^{\intercal}$

Notice that if we denote the conditions Eq. 14 for some stage $t+1$ as

(32) $M_{t+1}z_{t+1}+N_{t+1}x_{t+1}+n_{t+1}=0,$

as we did for $t+1=T$, then we have also that the conditions Eq. 14 for stage
$t$ can be denoted as

(33) $M_{t}z_{t}+N_{t}x_{t}+n_{t}=0,$

where $z_{t}:=[u_{t}^{\intercal}\ \mu_{t}^{\intercal}\
\lambda_{t}^{\intercal}\ \psi_{t+1}^{\intercal}\ x_{t+1}^{\intercal}\
z_{t+1}^{\intercal}]^{\intercal}$, and $M_{t}$, $N_{t}$, and $n_{t}$ are
defined as:

(34) $\displaystyle M_{t}$ $\displaystyle:=\begin{bmatrix}\lx@intercol\hfil
D_{t}^{1}\hfil\lx@intercol&D_{t}^{2}\\\
\begin{bmatrix}0&N_{t+1}\end{bmatrix}&M_{t+1}\end{bmatrix}$ $\displaystyle
D_{t}^{1}$
$\displaystyle:=\begin{bmatrix}R_{t}&-\hat{H}_{u_{t}}^{\intercal}&\hat{B}_{t}^{\intercal}&\\\
H_{u_{t}}\\\ -B_{t}&&&&I_{n}\\\ &&-I_{N*n}&\Pi_{t}^{\intercal}&Q_{t+1}\\\
&&&-I_{(N-1)*m_{t+1}}&\tilde{S}_{x_{t+1}}\end{bmatrix},$ $\displaystyle
D_{t}^{2}$ $\displaystyle:=\setcounter{MaxMatrixCols}{12}\begin{bmatrix}&\\\
&\\\
S_{u_{t+1}}&-\hat{H}_{x_{t+1}}^{\intercal}&\hat{A}_{t+1}^{\intercal}&&&&&&&&&\\\
\tilde{R}_{t+1}&-\tilde{H}_{u_{t+1}}^{\intercal}&\tilde{B}_{t+1}^{\intercal}&&&&&&\\\
\end{bmatrix},$ $\displaystyle N_{t}^{\intercal}$
$\displaystyle:=\begin{bmatrix}S_{x_{t}}^{\intercal}&H_{x_{t}}^{\intercal}&-A_{t}^{\intercal}&&\
\end{bmatrix},\ \
n_{t}^{\intercal}:=\begin{bmatrix}r_{t}^{\intercal}&h_{t}^{\intercal}&-c_{t}^{\intercal}&0&0&n_{t+1}^{\intercal}\end{bmatrix}.$

From this form, we have as before, that

(35) $\displaystyle\pi(x_{t})$ $\displaystyle:=K_{t}x_{t}+k_{t},$
$\displaystyle\lambda_{t}$
$\displaystyle:=K_{\lambda_{t}}x_{t}+k_{\lambda_{t}},$ $\displaystyle\mu_{t}$
$\displaystyle:=K_{\mu_{t}}x_{t}+k_{\mu_{t}},$ $\displaystyle\psi_{t+1}$
$\displaystyle:=K_{\psi_{t+1}}x_{t}+k_{\psi_{t+1}},$ $\displaystyle K_{t}$
$\displaystyle:=-[M_{t}^{-1}N_{t}]_{u_{t}},\ \ $ $\displaystyle
k_{t}:=-[M_{t}^{-1}n_{t}]_{u_{t}},$ $\displaystyle K_{\lambda_{t}}$
$\displaystyle:=-[M_{t}^{-1}N_{t}]_{\lambda_{t}},\ \ $ $\displaystyle
k_{\lambda_{t}}:=-[M_{t}^{-1}n_{t}]_{\lambda_{t}},$ $\displaystyle
K_{\psi_{t+1}}$ $\displaystyle:=-[M_{t}^{-1}N_{t}]_{\psi_{t+1}},\ \ $
$\displaystyle k_{\psi_{t+1}}:=-[M_{t}^{-1}n_{t}]_{\psi_{t+1}},$
$\displaystyle K_{\mu_{t}}$ $\displaystyle:=-[M_{t}^{-1}N_{t}]_{\mu_{t}},\ \ $
$\displaystyle k_{\mu_{t}}:=-[M_{t}^{-1}n_{t}]_{\mu_{t}},$

The advantage of expressing our system in the form Eq. 34 is that the
computation performed to solve $K_{t+1}$ and $k_{t+1}$ can be reused to solve
$K_{t}$ and $k_{t}$. Using the block form of $M_{t}$ defined in Eq. 34, and
pre suming $M_{t+1}$ is non-singular, we have from [16]:

(36) $\displaystyle]_{u_{t},\mu_{t},\lambda_{t},\psi_{t},x_{t+1}}$
$\displaystyle=\begin{bmatrix}P_{t}^{1}&P_{t}^{2}\end{bmatrix}\begin{bmatrix}N_{t}&n_{t}\end{bmatrix},$
$\displaystyle=\begin{bmatrix}P_{t}^{1}N_{t},&P_{t}^{1}\begin{bmatrix}r_{t}\\\
h_{t}\\\ -c_{t}\\\ \\\ \ \end{bmatrix}+P_{t}^{2}n_{t+1}\end{bmatrix}$

where the matrices $P_{t}^{1}$ and $P_{t}^{2}$ are defined as

(37) $\displaystyle P_{t}^{1}$
$\displaystyle:=\big{(}D_{t}^{1}-D_{t}^{2}M_{t+1}^{-1}[0\
N_{t+1}]\big{)}^{-1}$ $\displaystyle P_{t}^{2}$
$\displaystyle:=-P_{t}^{1}D_{t}^{2}M_{t+1}^{-1}$

Substituting in the form of the matrices in Eq. 34, we have that

(38) $\displaystyle P_{t}^{1}$
$\displaystyle:=\begin{bmatrix}R_{t}&-\hat{H}_{u_{t}}^{\intercal}&\hat{B}_{t}^{\intercal}&\\\
H_{u_{t}}\\\ -B_{t}&&&&I_{n}\\\
&&-I_{N*n}&\Pi_{t}^{\intercal}&\hat{P}_{t}^{1,a}\\\
&&&-I_{(N-1)*m_{t+1}}&\hat{P}_{t}^{1,b}\end{bmatrix}^{-1},$
$\displaystyle\hat{P}_{t}^{1,a}$
$\displaystyle:=Q_{t+1}-S_{u_{t+1}}K_{t+1}+\hat{H}_{x_{t+1}}^{\intercal}K_{\mu_{t+1}}-\hat{A}_{t+1}^{\intercal}K_{\lambda_{t+1}},$
$\displaystyle\hat{P}_{t}^{1,b}$
$\displaystyle:=\tilde{S}_{x_{t+1}}-\tilde{R}_{t+1}K_{t+1}+\tilde{H}_{u_{t+1}}^{\intercal}K_{\mu_{t+1}}-\tilde{B}_{t+1}^{\intercal}K_{\lambda_{t+1}},$
$\displaystyle P_{t}^{2}n_{t+1}$ $\displaystyle:=-P_{t}^{1}\begin{bmatrix}\\\
S_{u_{t+1}}k_{t+1}-\hat{H}_{x_{t+1}}^{\intercal}k_{\mu_{t+1}}+\hat{A}_{t+1}^{\intercal}k_{\mu_{t+1}}\\\
\tilde{R}_{t+1}k_{t+1}-\tilde{H}_{u_{t+1}}^{\intercal}k_{\mu_{t+1}}+\tilde{B}_{t+1}^{\intercal}k_{\lambda_{t+1}}\end{bmatrix}.$

From the above, it can be seen that the entire matrix inverse $M_{t}^{-1}$
does not need to be computed for any stage $t$ (other than the terminal stage
$T$), and the factorization presented here allows computation of the entire
GFNE trajectory and associated multipliers very efficiently. In particular,
the overall computational complexity of solving this system is
$O(T\cdot((N+1)\cdot(n+m))^{2}\cdot(n+1))$ time due to the dominating cost of
at each stage solving the system of equations of the form $P_{t}^{1}W_{t}$,
where $(P_{t}^{1})^{-1}$ is a square matrix of width no greater than
$(N+1)\cdot(n+m)$, and $W_{t}$ is some matrix with $n+1$ columns.

After computing the terms Eq. 35 for all stages $t$ using the procedure above,
the resultant GFNE trajectory and associated multipliers can be extracted:

(39) $\displaystyle x_{1}^{*}$ $\displaystyle:=\hat{x}_{1},$ $\displaystyle
u_{s}^{*}$ $\displaystyle:=K_{s}x_{s}^{*}+k_{s},$ $\displaystyle
s\in\mathbf{T},$ $\displaystyle\mu_{s}$
$\displaystyle:=K_{\mu_{s}}x_{s}^{*}+k_{\mu_{s}},$ $\displaystyle
s\in\mathbf{T},$ $\displaystyle\lambda_{s}$
$\displaystyle:=K_{\lambda_{s}}x_{s}^{*}+k_{\lambda_{s}},$ $\displaystyle
s\in\mathbf{T},$ $\displaystyle\psi_{s}$
$\displaystyle:=K_{\psi_{s}}x_{s-1}^{*}+k_{\psi_{s}},$ $\displaystyle
s\in\mathbf{T_{2}},$ $\displaystyle x_{s+1}^{*}$
$\displaystyle:=A_{s}x_{s}^{*}+B_{s}u_{s}^{*}+c_{s},\ \ $ $\displaystyle
s\in\mathbf{T},$ $\displaystyle\mu_{T+1}$
$\displaystyle:=K_{\mu_{T+1}}x_{T}+k_{\mu_{T+1}}.$

##  4 Inequality-Constrained LQ Games

We now extend the basic results presented in Section 3 on the computation of
GFNE for equality-constrained LQ games, to the computation of GFNE for
inequality-constrained LQ games. The approach we take here is that of an
active-set method, analogous to active-set methods for quadratic programming
(see, e.g. [17]).

Consider a dynamic game among $N$ players over $T$ stages, with linear
dynamics described by Eq. 20, and quadratic cost functionals Eq. 22. Assume
that each player is also subject to linear equality constraints of the form
Eq. 26, along with linear inequality constraints of the form

(40) $\displaystyle 0$ $\displaystyle\leq
G_{x_{t}}^{i}x_{t}+G_{u_{t}^{1}}^{i}u_{t}^{1}+...+G_{u_{t}^{N}}^{i}u_{t}^{N}+g_{t}^{i},\
\ t\in\mathbf{T}$ $\displaystyle 0$ $\displaystyle\leq
G_{x_{T+1}}^{i}x_{T+1}+g_{T+1}^{i},$

for matrices $G_{x_{t}}^{i}\in\mathbb{R}^{b_{t}^{i}\times n}$,
$G_{u_{t}^{j}}^{i}\in\mathbb{R}^{b_{t}^{i}\times m_{t}^{j}}$, and vectors
$g_{t}^{i}\in\mathbb{R}^{b_{t}^{i}}$, where $b_{t}^{i}$ is the dimension of
the inequality constraint imposed on player $i$ at stage $t\in\mathbf{T^{+}}$.
As in Section 2, we associate multipliers
$\gamma_{t}^{i}\in\mathbb{R}^{b_{t}^{i}}$, $t\in\mathbf{T^{+}}$ with these
constraints for each player $i\in\mathbf{N}$. Assume that a solution to the
system Eq. 11 exists for this game at stage $t=1$, and that strict
complementarity holds for the conditions Eq. 11 for the subgame starting at
every $t\in\mathbf{T}$ along any solution.

The method we present for computing a GFNE of this game is an adaptation of
Algorithm 16.3 in [17] to the current setting. Under the strict
complementarity assumption (which ensures differentiability of the policies
$\pi_{t}$ along the solution), we have that at any GFNE solution, some subset
of the constraints Eq. 40 associated with strictly positive multipliers hold
with equality at the solution. If the set of active constraints along some
solution were known in advance, we could consider all active constraints as
equality constraints, ignore all inactive constraints, and solve for the
resultant equality-constrained game using the method presented in Section 3.
In general the set of active constraints along a solution is obviously unknown
in advance. The active-set method we propose accounts for this by iteratively
solving for the unique GFNE solution for different guesses of the active
constraint set, and uses dual variable information to update the guess of the
active set. In the remainder of this section we describe the proposed method.
The presentation of this section is based off of section 16.5 in [17], with
necessary modifications made to account for the multiplayer feedback setting
considered here.

The method begins with a feasible initialization for the game (defined by the
linear dynamics Eq. 20, equality constraints Eq. 26, and inequality
constraints Eq. 40, and the quadratic cost functionals Eq. 22). We denote the
set of all primal variables associated with the game at the $k$th iteration of
the method by $\mathbf{X}_{k}:=[x_{(1:T+1),k},u_{(1:T),k}]$. Also associated
with the $k$th iteration of the algorithm is the working set $\mathcal{W}_{k}$
which denotes the set of constraints which are treated with equality at the
$k$th iteration. The working set $\mathcal{W}_{k}$ always contains all of the
equality constraints Eq. 26. The working set $\mathcal{W}_{1}$ is taken to be
a subset of the constraints active along the initialization $\mathbf{X}_{1}$.

Given an iterate $\mathbf{X}_{k}$ and working set $\mathcal{W}_{k}$, we find a
step $\mathbf{P}_{k}:=[p_{x_{1:T+1}},p_{u_{1:T}}]$ is to move $\mathbf{X}_{k}$
to the GFNE associated with the working set of equality constraints in
$\mathcal{W}_{k}$. Specifically, the problem to be solved at each iteration is
the GFNE problem for the equality-constrained LQ game defined by each player’s
stage-wise cost functionals

(41) $\displaystyle l^{i}_{t,k}(p_{x_{t}},p_{u_{t}})$
$\displaystyle:=\frac{1}{2}\bigg{(}\begin{bmatrix}p_{x_{t}}\\\
p_{u_{t}}\end{bmatrix}^{\intercal}\begin{bmatrix}Q_{t}^{i}&S_{t}^{i\intercal}\\\
S_{t}^{i}&R_{t}^{i}\end{bmatrix}\begin{bmatrix}p_{x_{t}}\\\
p_{u_{t}}\end{bmatrix}+2\begin{bmatrix}p_{x_{t}}\\\
p_{u_{t}}\end{bmatrix}^{\intercal}\begin{bmatrix}q_{t,k}^{i}\\\
r_{t,k}^{i}\end{bmatrix}\bigg{)},\ \ $ $\displaystyle t\in\mathbf{T}$
$\displaystyle q_{t,k}^{i}$
$\displaystyle:=Q_{t}^{i}x_{t,k}+S_{t}^{i\intercal}u_{t,k}+q_{t}^{i},\ $
$\displaystyle t\in\mathbf{T},$ $\displaystyle r_{t,k}^{i}$
$\displaystyle:=S_{t}^{i}x_{t,k}+R_{t}^{i}u_{t,k}+r_{t}^{i},$ $\displaystyle
t\in\mathbf{T},$ $\displaystyle l^{i}_{T+1,k}(p_{x_{T+1}})$
$\displaystyle:=\frac{1}{2}\bigg{(}p_{x_{T+1}}^{\intercal}Q_{T+1}^{i}p_{x_{T+1}}+2p_{x_{T+1}}^{\intercal}q_{T+1,k}^{i}\bigg{)},$
$\displaystyle q_{T+1,k}^{i}$
$\displaystyle:=Q_{T+1}^{i}x_{T+1,k}+q_{T+1}^{i},$

the dynamics

(42)
$p_{x_{t+1}}=A_{t}p_{x_{t}}+B_{t}^{1}p_{u_{t}^{1}}+...+B_{t}^{N}p_{u_{t}^{N}},\
\ t\in\mathbf{T},$

and the linear equality constraints

(43) $\displaystyle 0$
$\displaystyle=H_{(x_{t},k)}^{i}p_{x_{t}}+H_{(u_{t}^{1},k)}^{i}p_{u_{t}^{1}}+...+H_{(u_{t}^{N},k)}^{i}p_{u_{t}^{N}},\
\ t\in\mathbf{T}$ $\displaystyle 0$
$\displaystyle=H_{(x_{T+1},k)}^{i}p_{x_{T+1}}.$

Above, the matrices $H^{i}_{(x_{t},k)}$ and $H^{i}_{(u_{t}^{j},k)}$ are
defined to be the set of active equality constraint coefficients corresponding
to $\mathcal{W}_{k}$:

(44) $H^{i}_{(x_{t},k)}:=\left[\begin{array}[]{c}H^{i}_{x_{t}}\\\
\hline\cr\vdots\\\
\\{G_{x_{t}}^{i,j}\\}_{(t,i,j)\in\mathcal{W}_{k}\cap\mathcal{I}}\\\
\vdots\end{array}\right],H_{(u_{t},k)}^{i}:=\left[\begin{array}[]{c}H^{i}_{u_{t}}\\\
\hline\cr\vdots\\\
\\{G_{u_{t}}^{i,j}\\}_{(t,i,j)\in\mathcal{W}_{k}\cap\mathcal{I}}\\\
\vdots\end{array}\right].$

Here, $\mathcal{W}_{k}\cap\mathcal{I}$ is the index set of all active
inequality constraints, and $G_{x_{t}}^{i,j}$ is the $j$th row of the matrix
$G_{x_{t}}^{i}$.

Associated with the constraints Eq. 43 are multipliers $\mu_{(t,k)}^{i}$,
defined as

(45) $\mu_{(t,k)}^{i}:=\left[\begin{array}[]{c}\mu_{t}^{i}\\\
\hline\cr\vdots\\\
\\{\gamma_{t}^{i,j}\\}_{(t,i,j)\in\mathcal{W}_{k}\cap\mathcal{I}}\\\
\vdots\end{array}\right]$

where $\gamma_{t}^{i,j}$ is the $j$th element of $\gamma_{t}^{i}$.

After solving for $\mathbf{P}_{k}$, the GFNE of the resultant equality-
constrained LQ game, $\mathbf{X}_{k}+\mathbf{P}_{k}$ is the GFNE for the
equality-constrained LQ game defined by Eq. 20, Eq. 22, Eq. 26, and the active
constraints Eq. 40 in $\mathcal{W}_{k}\cap\mathcal{I}$. However, it may be
that $\mathbf{X}_{k}+\mathbf{P}_{k}$ is infeasible with respect to the entire
set of inequality constraints Eq. 40. Therefore we instead find the point
$\mathbf{X}_{k}+\beta_{k}\mathbf{P}_{k}$, where

(46) $\displaystyle\beta_{k}:=$ $\displaystyle\max_{\beta\in[0,1]}\beta$
$\displaystyle\text{s.t. }\mathbf{X}_{k}+$
$\displaystyle\beta\mathbf{P}_{k}\text{ feasible w.r.t.
\lx@cref{creftype~refnum}{eq:linear_ineq_constraints}}.$

The optimization in Eq. 46 is a linear program, and $\beta_{k}$ can be
computed exactly and efficiently. When $\beta_{k}<1$, it implies that there is
an inequality constraint not considered in the working set which must be
accounted for. When this is the case, the iterate $\mathcal{X}_{k+1}$ is
updated to the point $\mathbf{X}_{k}+\beta_{k}\mathbf{P}_{k}$, and the working
set is updated to include the blocking constraint. If instead, $\beta_{k}=1$,
then the point $\mathbf{X}_{k}+\mathbf{P}_{k}$ both is a GFNE solution for the
working set and is feasible with respect to all equality and inequality
constraints. All that is left to check is whether the constraints
$\mu_{(t,k)}^{i,j}>0$ for all $j>a_{t}^{i}$, meaning the complementarity
conditions in Eq. 11 are satisfied, and therefore a solution satisfying the
entire set of conditions Eq. 11 for the inequality-constrained problem has
been found. If some multiplier associated with the inequality constraints in
the working set $\mathcal{W}_{k}$ is negative444The multipliers cannot be zero
by the strict complementarity assumption made., then the corresponding
constraint is to be dropped from the working set at the next iteration. Unlike
the the convex quadratic programming setting, where forming
$\mathcal{W}_{k+1}$ by dropping a constraint associated with a negative
multiplier in the set $\mathcal{W}_{k}\cap\mathcal{I}$ and setting
$\mathbf{X}_{k+1}=\mathbf{X}_{k}+\mathbf{P}_{k}$, the update
$\mathbf{P}_{k+1}$ does not necessarily move away from the dropped constraint
boundary. In such situations, the procedure fails to make progress, since the
value of $\beta_{k+1}$ in Eq. 46 will be $0$. In practice these conditions can
be treated by dropping a different constraint (also associated with a negative
multiplier) from the working set. If no other constraints are associated with
negative multipliers, a GFNE does not exist in the vicinity of the iterate,
and failure is declared. The full procedure is stated in Algorithm 1.

Algorithm 1 Active Set Inequality Constrained LQ Game GFNE Solver

1: Start with $\mathbf{X}_{1}$ feasible w.r.t. Eq. 20, Eq. 26, Eq. 40

2: Initialize $\mathcal{W}_{1}$ to be subset of active inequality constraints
along $\mathbf{X}_{1}$

3: for k=1,2,3,… do

4: Solve equality-constrained LQ GFNE defined by Eq. 41, Eq. 42, Eq. 43, and
denote the solution as $\mathbf{P}_{k}$

5: if $\mathbf{P}_{k}==\mathbf{0}$ then

6: Extract multipliers $\mu_{(t,k)}^{i}$, $\psi_{t}^{i}$, $\lambda_{t}^{i}$,
using Eq. 39

7: if $\mu_{(t,k)}^{i,j}>0,\ \forall j>a_{t}^{i}$ {Inequality constraint
multipliers} then

8: return $\mathbf{X}_{k}$,

9: else

10:
$(t_{m},i_{m},j_{m})\leftarrow\underset{(t,i,j)\in\mathcal{W}_{k}\cap\mathcal{I}}{\text{argmin}}\mu_{(t,k)}^{i,j}$

11: $\mathbf{X}_{k+1}\leftarrow\mathbf{X}_{k}$

12:
$\mathcal{W}_{k+1}\leftarrow\mathcal{W}_{k}\setminus\\{(t_{m},i_{m},j_{m})\\}$

13: end if

14: else

15: Find largest $\beta_{k}\in[0,1]$ such that
$\mathbf{X}_{k}+\beta_{k}\mathbf{P}_{k}$ is feasible w.r.t. Eq. 40

16: $\mathbf{X}_{k+1}\leftarrow\mathbf{X}_{k}+\beta_{k}\mathbf{P}_{k}$

17: if $\beta_{k}<1$ then

18: $(t_{b},i_{b},j_{b})\leftarrow$ index of blocking inequality constraint
not already in $\mathcal{W}_{k}\cap\mathcal{I}$

19: if $(t_{b},i_{b},j_{b})==(t_{m},i_{m},j_{m})$ {Blocking index is
previously dropped index} then

20: Choose other blocking constraint or declare failure

21: else

22: $\mathcal{W}_{k+1}\leftarrow\mathcal{W}_{k}\cup(t_{b},i_{b},j_{b})$

23: end if

24: else

25: $\mathcal{W}_{k+1}\leftarrow\mathcal{W}_{k}$

26: end if

27: end if

28: end for

##  5 Nonlinear Games

We now present a method for computing GFQNE solutions to general dynamic
games. In particular, we outline a procedure for finding a solution to the
conditions Eq. 14 for games defined by the dynamics Eq. 1, cost functionals
Eq. 2, and constraints Eqs. 3a and 3b. We assume that all functions appearing
in the conditions Eq. 14 are continuously twice differentiable, with the
exception of the implicitly defined policies. The procedure leverages the
method for computing solutions to inequality-constrained LQ games presented in
Section 4 and Algorithm 1, and generally is inspired by Sequential Quadratic
Programming methods for non-convex numerical optimization (see e.g. [17],
Chapter 18).

The foundation of this approach is in the observation that a Newton-style
method can be used to finding a solutions to the conditions Eq. 14, where each
iteration involves solving for a GFNE for the locally approximate LQ game
formed around the current iterate. Considering first the case in which the
game does not include any inequality constraints, computing a search direction
using Newton’s method on the conditions Eq. 14 at $t=1$ can be seen to be
equivalent to computing a search direction by solving an LQ approximation of
the game. In the inequality-constrained case, search directions can be found
by solving an inequality-constrained LQ approximation, analogous to the method
in [17].

In particular, we propose an iterative method for finding solutions to the
conditions Eq. 14. Throughout this section, iterations are again indexed by
$k=1,2,3,...$, as they were in the method for computing inequality-constrained
LQ games in Section 4. Here, let the current iterate of the primal and dual
game variables at iteration $k$ be denoted as

(47) $\displaystyle\mathbf{X}_{k}$
$\displaystyle:=[x_{(1:T+1),k},u_{(1:T),k}],$
$\displaystyle\mathbf{\Lambda}_{k}$
$\displaystyle:=[\lambda_{(1:T),k},\mu_{(1:T+1),k},\gamma_{(1:T+1),k},\psi_{(2:T),k}]$

Assume some initialization of all variables $\mathbf{X}_{1}$ and
$\mathbf{\Lambda}_{1}$. Then for each iteration $k$, a search direction
$\mathbf{P}_{k}$ is found by solving the inequality-constrained LQ game formed
as follows. Let the dynamics Eq. 20 for the approximate game at the $k$th
iteration be defined by the terms

(48) $\displaystyle A_{t,k}$
$\displaystyle:=\nabla_{x}f_{t}(x_{t,k},u_{t,k}),$ $\displaystyle B^{i}_{t,k}$
$\displaystyle:=\nabla_{u^{i}}f_{t}(x_{t,k},u_{t,k}),$ $\displaystyle c_{t,k}$
$\displaystyle:=f_{t}(x_{t,k},u_{t,k})-x_{t+1,k}.$

Similarly, let the equality and inequality constraint terms in Eqs. 26 and 40
be defined as

(49) $\displaystyle H_{x_{t},k}^{i}$
$\displaystyle:=\nabla_{x}h_{t}^{i}(x_{t,k},u_{t,k}),\ \ $ $\displaystyle
G_{x_{t},k}^{i}:=\nabla_{x}g_{t}^{i}(x_{t,k},u_{t,k}),$ $\displaystyle
H_{u_{t}^{i},k}^{i}$
$\displaystyle:=\nabla_{u^{i}}h_{t}^{i}(x_{t,k},u_{t,k}),\ \ $ $\displaystyle
G_{u_{t}^{i},k}^{i}:=\nabla_{u^{i}}g_{t}^{i}(x_{t,k},u_{t,k}),$ $\displaystyle
h_{t,k}^{i}$ $\displaystyle:=h_{t}^{i}(x_{t,k},u_{t,k}),\ \ $ $\displaystyle\
\ g_{t,k}^{i}:=g_{t}^{i}(x_{t,k},u_{t,k}).$

Finally, let the cost functional coefficients in Eq. 22 for stages
$t\in\mathbf{T}$ be defined as

(50) $\displaystyle Q_{t,k}^{i}$
$\displaystyle:=\nabla^{2}_{x,x}l_{t}^{i}(x_{t,k},u_{t,k})+(\nabla^{2}_{x,x}f_{t})^{\intercal}\lambda_{t,k}^{i}-(\nabla^{2}_{x,x}h_{t}^{i})^{\intercal}\mu_{t,k}^{i}-(\nabla^{2}_{x,x}g_{t}^{i})^{\intercal}\gamma_{t,k}^{i},$
$\displaystyle S_{t,k}^{i}$
$\displaystyle:=\nabla^{2}_{u,x}l_{t}^{i}(x_{t,k},u_{t,k})+(\nabla^{2}_{u,x}f_{t})^{\intercal}\lambda_{t,k}^{i}-(\nabla^{2}_{u,x}h_{t}^{i})^{\intercal}\mu_{t,k}^{i}-(\nabla^{2}_{u,x}g_{t}^{i})^{\intercal}\gamma_{t,k}^{i},$
$\displaystyle R_{t,k}^{i}$
$\displaystyle:=\nabla^{2}_{u,u}l_{t}^{i}(x_{t,k},u_{t,k})+(\nabla^{2}_{u,u}f_{t})^{\intercal}\lambda_{t,k}^{i}-(\nabla^{2}_{u,u}h_{t}^{i})^{\intercal}\mu_{t,k}^{i}-(\nabla^{2}_{u,u}g_{t}^{i})^{\intercal}\gamma_{t,k}^{i},$
$\displaystyle q_{t,k}^{i}$
$\displaystyle:=\nabla_{x}l_{t}^{i}(x_{t,k},u_{t,k}),$ $\displaystyle
r_{t,k}^{i}$ $\displaystyle:=\nabla_{u}l_{t}^{i}(x_{t,k},u_{t,k}).$

The solution to this inequality-constrained LQ game at each iteration $k$
yields the search direction $\mathbf{P}_{k}$ and multipliers
$\bar{\mathbf{\Lambda}}_{k+1}$. To ensure progress towards a solution of the
conditions Eq. 14, a line-search procedure is invoked. We seek a parameter
$\alpha_{k}\in[0,1]$ such that the iterates

(51) $\displaystyle\mathbf{X}_{k+1}$
$\displaystyle:=\mathbf{X}_{k}+\alpha_{k}\mathbf{P}_{k},$
$\displaystyle\mathbf{\Lambda}_{k+1}$
$\displaystyle:=\mathbf{\Lambda}_{k}+\alpha_{k}(\bar{\mathbf{\Lambda}}_{k+1}-\mathbf{\Lambda}_{k})$

make maximal progress towards satisfying the conditions Eq. 14, with respect
to an appropriate merit function. Because the game setting involves multiple
players, a decrease in the objective of all players’ objectives cannot be
guaranteed. Therefore the merit function we consider is simply the residual
squared norm of the conditions Eq. 14. In particular, define the merit
function to search over as the following:

(52) $\displaystyle\mathbf{M}(\mathbf{X},\mathbf{\Lambda}):=$
$\displaystyle\sum_{i\in\mathbf{N}}\sum_{s\in\mathbf{T}}\ $
$\displaystyle\left\|\nabla_{u_{s}^{i}}\bigg{[}l_{s}^{i}+f_{s}^{\intercal}\lambda_{s}^{i}-h_{s}^{i\intercal}\mu_{s}^{i}-g_{s}^{i^{\intercal}}\gamma_{s}^{i}\bigg{]}\right\|_{2}^{2}+$
$\displaystyle\sum_{i\in\mathbf{N}}\sum_{s\in\mathbf{T_{2}}}\ $
$\displaystyle\left\|\nabla_{x_{s}}\bigg{[}l_{s}^{i}-\lambda_{s-1}^{i}+f_{s}^{\intercal}\lambda_{s}^{i}-h_{s}^{i^{\intercal}}\mu_{s}^{i}-g_{s}^{i\intercal}\gamma_{s}^{i}\bigg{]}+\tilde{\nabla}_{x_{s}}\hat{\pi}_{s}^{-i\intercal}\psi_{s}^{i}\right\|_{2}^{2}+$
$\displaystyle\sum_{i\in\mathbf{N}}\sum_{s\in\mathbf{T_{2}}}\ $
$\displaystyle\left\|\nabla_{u^{-i}_{s}}\bigg{[}l_{s}^{i}+f_{s}^{\intercal}\lambda_{s}^{i}-h_{s}^{i^{\intercal}}\mu_{s}^{i}-g_{s}^{i\intercal}\gamma_{s}^{i}-\psi_{s}^{i}\bigg{]}\right\|_{2}^{2}+$
$\displaystyle\sum_{i\in\mathbf{N}}\ $
$\displaystyle\left\|\nabla_{x_{T+1}}\bigg{[}l_{T+1}^{i}-\lambda_{T}^{i}-h_{T+1}^{i^{\intercal}}\mu_{T+1}^{i}-g_{T+1}^{i\intercal}\gamma_{T+1}^{i}\bigg{]}\right\|_{2}^{2}+$
$\displaystyle\sum_{s\in\mathbf{T}}\ $
$\displaystyle\left\|x_{s+1}-f_{s}(x_{s},u_{s})\right\|_{2}^{2}+$
$\displaystyle\sum_{i\in\mathbf{N}}\Big{(}\sum_{s\in\mathbf{T}}\ $
$\displaystyle\left\|h_{s}^{i}(x_{s},u_{s})\right\|_{2}^{2}+\left\|h_{T+1}^{i}(x_{T+1})\right\|_{2}^{2}\Big{)}+$
$\displaystyle\sum_{i\in\mathbf{N}}\Big{(}\sum_{s\in\mathbf{T}}\ $
$\displaystyle\left\|\min(g_{s}^{i}(x_{s},u_{s}),0)\right\|_{2}^{2}+\left\|\min(g_{T+1}^{i}(x_{T+1}),0)\right\|_{2}^{2}\Big{)}+$
$\displaystyle\sum_{i\in\mathbf{N}}\sum_{s\in\mathbf{T^{+}}}\ $
$\displaystyle\left\|\min(\mu_{s}^{i},0)\right\|_{2}^{2}+|(g_{s}^{i})^{\intercal}\mu_{s}^{i}|.$

Recall that $\mathbf{T}_{2}:=\\{2,...,T\\}$. Then $\alpha_{k}$ is defined as:

(53)
$\displaystyle\alpha_{k}:=\min_{\alpha\in[0,1]}\mathbf{M}(\mathbf{X}_{k}+\alpha\mathbf{P}_{k},\mathbf{\Lambda}_{k}+\alpha(\bar{\mathbf{\Lambda}}_{k+1}-\mathbf{\Lambda}_{k})).$

Algorithm 2 GFQNE Solver for Nonlinear Games

1: Set convergence tolerance $\epsilon>0$

2: Start with initial $\mathbf{X}_{1}$, $\mathbf{\Lambda}_{1}$

3: for $k$=1,2,3,…,$k_{max}$ do

4: Solve inequality-constrained LQ GFNE defined by Eq. 48, Eq. 49, Eq. 50, and
denote the solution and corresponding multipliers as $\mathbf{P}_{k}$,
$\bar{\mathbf{\Lambda}}_{k+1}$

5: Find $\alpha_{k}$ according to Eq. 53 and Eq. 52 via backtracking line-
search

6: if $\alpha_{k}==0$ then

7: Return failure

8: end if

9: $\mathbf{X}_{k+1}\leftarrow\mathbf{X}_{k}+\alpha_{k}\mathbf{P}_{k}$

10:
$\mathbf{\Lambda}_{k+1}\leftarrow\mathbf{\Lambda}_{k}+\alpha_{k}(\bar{\mathbf{\Lambda}}_{k+1}-\mathbf{\Lambda}_{k})$

11: if $\mathbf{M}(\mathbf{X}_{k+1},\mathbf{\Lambda}_{k+1})<\epsilon$ then

12: Return $\mathbf{X}_{k+1},\mathbf{\Lambda}_{k+1}$ and break

13: end if

14: end for

The choice of merit function need not be as defined in Eq. 52. Any positive-
valued function which evaluates to 0 if and only if the arguments constitute a
solution to Eq. 14 is acceptable. In the line-search procedure Eq. 53 using
any such merit function, it is necessary in general to evaluate the policy
quasi-gradients at the candidate point $\mathbf{X}_{k}+\alpha\mathbf{P}_{k}$,
$\mathbf{\Lambda}_{k}+\alpha(\bar{\mathbf{\Lambda}}_{k+1}-\mathbf{\Lambda}_{k}))$
for general $\alpha$. However, recall that these terms are implicitly defined,
and in general require solving the approximate LQ game defined at the
candidate point to evaluate them. This makes the evaluation of Eq. 53 very
expensive. Therefore, in practice, we find it acceptable in most cases to
replace the policy quasi-gradients appearing in Eq. 52 corresponding to the
candidate point, with the quasi-gradients corresponding to the point
$\mathbf{X}_{k},\mathbf{\Lambda}_{k}$, which are evaluated in the computation
of the search direction $\mathbf{P}_{k}$. Also, even with the reuse of the
policy quasi-gradients, the minimization in Eq. 53 cannot be carried out
exactly. In practice, a backtracking line-search satisfying a sufficient
decrease condition is used instead.

Algorithm 2 gives the full algorithm for computing solutions for nonlinear
games. It is important to note that the proposed algorithm is not guaranteed
to converge to a GFQNE solution. Due to the omission of second-order
information of the policies $\hat{\pi}_{t}$ in the definition of the matrices
$Q_{t,k}^{i}$, it is not possible to guarantee that the resultant solution to
the LQ game is a descent direction for the proposed merit function. In such a
case, failure to converge is reported, as stated in Algorithm 2. Despite the
possibility of failure, we find in practice that the proposed method is
effective at generating search directions which enable progress with respect
to Eq. 52.

##  6 Example

(a) $\sigma_{polite}=0$

(b) $\sigma_{polite}=5$

Figure 1: Snapshots of the resultant GFQNE solutions found to the example in Section 6, when excluding (a) and including (b) the politeness term in player $1$’s objective. Major Iteration |  Minor Iteration |  Working Set Indices | Comment | $\alpha_{k}$ | $\mathbf{M}(\mathbf{X}_{k+1},\mathbf{\Lambda}_{k+1})$
---|---|---|---|---|---
1 | F1 | {} |  |  |
| F2 | {(101,2)} |  |  |
| F3 | {(101,1),(101,2)} |  |  |
| 1 | {(101,1),(101,2)} |  |  |
| 2 | {(101,2)} |  |  |
| 3 | {(101,1),(101,2)} | Cycle | 1 | 96.25
2 | F1 | {(101,2)} |  |  |
| F2 | {(101,1),(101,2)} |  |  |
| 1 | {(101,1),(101,2)} |  |  |
| 2 | {(101,2)} |  |  |
| 3 | {(101,1),(101,2)} | Cycle | 1 | 55.65
3 | F1 | {(101,2)} |  |  |
| 1 | {(101,2)} | Solution | 1 | 0.221
4 | F1 | {(101,2)} |  |  |
| 1 | {(101,2)} | Solution | 1 | 2.3e-5
Total Time |  Total LQ Solves | Solve Time |  Function Eval Time |  |
5.14 | 17 | 0.97 | 4.17 |  |
Table 1: Algorithm iterate information when using Algorithm 2 (Major
Iterations) and Algorithm 1 (Minor Iterations) to compute a GFQNE to the
example in Section 6, when $\sigma_{polite}=5$ (Fig. 1(b)). Here
$\mathbf{M}(\mathbf{X}_{k+1},\mathbf{\Lambda}_{k+1})$ is the merit function
value after performing a line search in the direction of $\mathbf{P}_{k}$ in
Algorithm 2. In each major iteration of this solve, $\alpha_{k}=1$, i.e., no
backtracking was necessary during line search. Here, minor iterations labeled
“F$\Box$” indicate equality-constrained LQ solves used to search for a
feasible initial solution to the inequality-constrained LQ game associated
with the major iteration. Detections of cycles indicate that the removal of a
constraint associated with a negative multiplier did not move the iterate
associated with Algorithm 1 away from the dropped constraint boundary (20). In
these cases, the iterate is accepted and the algorithm continues with the next
major iteration.

We now demonstrate the methodologies so far presented on a practical example.
Consider a game describing a driving scenario involving an autonomous vehicle
and two other vehicles on a freeway. Here $N=3$, and $T=100$ denotes the
number of discrete time-points in the trajectory game. Let the game dynamics
be defined as the concatenation of the independent dynamics of each vehicle in
the game. We assume that each vehicle follows simple unicycle dynamics;
specifically:

(54) $x_{t+1}^{i}=\begin{bmatrix}[l]x_{t+1}^{i,1}\\\ x_{t+1}^{i,2}\\\
x_{t+1}^{i,3}\\\
x_{t+1}^{i,4}\end{bmatrix}=f_{t}^{i}(x_{t}^{i},u_{t}^{i})=\begin{bmatrix}[l]x_{t}^{i,1}+\Delta\cdot
x_{t}^{i,3}\cos(x_{t}^{i,4})\\\ x_{t}^{i,2}+\Delta\cdot
x_{t}^{i,3}\sin(x_{t}^{i,4})\\\ x_{t}^{i,3}+\Delta\cdot u_{t}^{i,1}\\\
x_{t}^{i,4}+\Delta\cdot u_{t}^{i,2}\end{bmatrix},\hskip
14.22636pti\in\mathbf{N}.$

Here $\Delta$ represents some small sampling time. The vehicle state
dimensions denote, in order, the longitudinal (along-lane) position, lateral
(across-lane) position, speed in the direction of the vehicle heading, and the
vehicle heading in radians. The control dimensions denote, in order, the
vehicle acceleration and the angular velocity. The dynamics for the entire
game state are then given as:

(55) $x_{t+1}:=\begin{bmatrix}f_{t}^{1}(x_{t}^{1},u_{t}^{1})\\\
f_{t}^{2}(x_{t}^{2},u_{t}^{2})\\\
f_{t}^{3}(x_{t}^{3},u_{t}^{3})\end{bmatrix}=f_{t}(x_{t},u_{t}),\
t\in\mathbf{T}.$

Players $2$ and $3$ both aim to minimize acceleration, angular velocity, and
deviation from desired speed, while staying in-lane. Player $3$ also desires
to avoid collisions with player $1$. Player $1$ aims to complete a lateral
lane change while minimizing its own acceleration, angular velocity, and
deviation from its desired speed, while avoiding collision with player $3$.
Player 1 also attempts to minimize the objective of player $2$ in addition to
its own objective. Fig. 1 depicts this game. The players’ objective and
constraints are described as follows:

(56) $\displaystyle 0=h_{T+1}^{1}(x_{T+1}):=x^{1,2}_{T+1}+2,$ $\displaystyle
0=h_{T+1}^{2}(x_{T+1}):=x^{2,2}_{T+1}+2,$ $\displaystyle
0=h_{T+1}^{3}(x_{T+1}):=x^{3,2}_{T+1}-2,$ $\displaystyle 0\leq
g_{t}^{1}(x_{t}):=\left\|\begin{matrix}x_{t}^{1,1}-x_{t}^{3,1}\\\
x_{t}^{1,2}-x_{t}^{3,2}\end{matrix}\right\|_{2}-d_{min},\ \
t\in\mathbf{T^{+}},$ $\displaystyle 0\leq
g_{t}^{2}(x_{t}):=\left\|\begin{matrix}x_{t}^{2,1}-x_{t}^{1,1}\\\
x_{t}^{2,2}-x_{t}^{1,2}\end{matrix}\right\|_{2}-d_{min},\ \
t\in\mathbf{T^{+}},$ (57) $\displaystyle
L^{1}(x,u)=\Big{(}\sum_{t=1}^{T}\sigma_{1}\left\|u_{t}^{1}\right\|_{2}^{2}+\sigma_{2}(x_{t}^{1,2}+2)^{2}+\sigma_{3}(x_{t}^{1,3}-v_{goal}^{1})^{2}\Big{)}+\sigma_{polite}L^{2}(x,u),$
$\displaystyle
L^{2}(x,u)=\sum_{t=1}^{T}\sigma_{1}\left\|u_{t}^{2}\right\|_{2}^{2}+\sigma_{2}(x_{t}^{2,2}+2)^{2}+\sigma_{3}(x_{t}^{2,3}-v_{goal}^{2})^{2},$
$\displaystyle
L^{3}(x,u)=\sum_{t=1}^{T}\sigma_{1}\left\|u_{t}^{3}\right\|_{2}^{2}+\sigma_{2}(x_{t}^{3,2}-2)^{2}+\sigma_{3}(x_{t}^{3,3}-v_{goal}^{3})^{2},$

The initial state is defined to be
$\hat{x}_{1}:=[0,2,1,0,-10,-2,1.5,0,30,2,0.75,0]^{\intercal}$. The lateral
centers of the left and right lanes are $-2$ and $2$, respectively. The
constant $d_{min}$ is the minimum separation distance from vehicle centers
needed to avoid collision, which in this example is $3.3$. The parameters
$\sigma_{\\{1,2,3\\}}$ scale the relative weights between objective terms, and
are $\sigma_{1}=10,\ \sigma_{2}=0.2,\text{ and }\sigma_{3}=10$. The desired
speeds of the three players are $v_{goal}^{1}=1$, $v_{goal}^{2}=1.5$, and
$v_{goal}^{3}=0.75$. The term $\sigma_{polite}$ is the politeness coefficient
and weights how much player $1$ cares about interfering with player $2$’s
objective. We consider two variants, with $\sigma_{polite}=0$ and
$\sigma_{polite}=5$. This example is similar to games explored in [15].
Visualizations of the GFQNE solutions for the two variants are given in Fig.
1, and computation details for the $\sigma_{polite}=5$ case are given in Table
1 (details for the case $\sigma_{polite}=0$ are omitted for brevity).

##  7 Conclusion

In this paper, we presented a non-parametric, implicit policy formulation for
generalized feedback Nash equilibrium problems. We developed efficient
solution methods for the equality-constrained and inequality-constrained
Linear-Quadratic (LQ) cases and the general nonlinear case. To the best of our
knowledge, these comprise the first solution methods for finding Feedback Nash
Equilibria for both LQ and nonlinear games with general constraints. Dynamic
games have numerous applications; we demonstrate the utility of our method in
a trajectory planning setting for a lane-changing autonomous vehicle.

Future work should consider other solution methods for the general game which
build upon our solution to the equality-constrained LQ game. In particular,
penalty methods and interior point methods may also be competitive.
Furthermore, the results presented should be extended to cases in which strict
complementarity does not hold. Necessary conditions based on sub-differentials
could be used in such cases. It is also important to further develop a deeper
theoretical understanding of the “policy quasi-gradient” approximation and its
implications on convergence to local solutions. Finally, a high-performance,
optimized implementation of our method will facilitate its use in practical
applications by other researchers and practitioners.

## References

  * [1] T. Başar and G. J. Olsder, Dynamic noncooperative game theory, SIAM, 1998.
  * [2] S. L. Cleac’h, M. Schwager, and Z. Manchester, Algames: A fast solver for constrained dynamic games, arXiv preprint arXiv:1910.09713, (2019).
  * [3] B. Di and A. Lamperski, Newton’s method and differential dynamic programming for unconstrained nonlinear dynamic games, in 2019 IEEE 58th Conference on Decision and Control (CDC), IEEE, 2019, pp. 4073–4078.
  * [4] B. Di and A. Lamperski, Local first-order algorithms for constrained nonlinear dynamic games, in 2020 American Control Conference (ACC), IEEE, 2020, pp. 5358–5363.
  * [5] C. Dutang, Existence theorems for generalized nash equilibrium problems: An analysis of assumptions, Journal of Nonlinear Analysis and Optimization, 4 (2013), pp. 115–126.
  * [6] F. Facchinei, A. Fischer, and V. Piccialli, Generalized nash equilibrium problems and newton methods, Mathematical Programming, 117 (2009), pp. 163–194.
  * [7] F. Facchinei and C. Kanzow, Generalized nash equilibrium problems, Annals of Operations Research, 175 (2010), pp. 177–211.
  * [8] J. F. Fisac, E. Bronstein, E. Stefansson, D. Sadigh, S. S. Sastry, and A. D. Dragan, Hierarchical game-theoretic planning for autonomous vehicles, in International Conference on Robotics and Automation (ICRA), IEEE, 2019, pp. 9590–9596.
  * [9] D. Fridovich-Keil, E. Ratner, L. Peters, A. D. Dragan, and C. J. Tomlin, Efficient iterative linear-quadratic approximations for nonlinear multi-player general-sum differential games, in 2020 IEEE International Conference on Robotics and Automation (ICRA), IEEE, 2020, pp. 1475–1481.
  * [10] D. Fridovich-Keil, V. Rubies-Royo, and C. J. Tomlin, An iterative quadratic method for general-sum differential games with feedback linearizable dynamics, in 2020 IEEE International Conference on Robotics and Automation (ICRA), IEEE, 2020, pp. 2216–2222.
  * [11] H. V. Henderson and S. R. Searle, On deriving the inverse of a sum of matrices, Siam Review, 23 (1981), pp. 53–60.
  * [12] J. Herrera de la Cruz, B. Ivorra, and Á. M. Ramos, An algorithm for solving a class of multiplayer feedback-nash differential games, Mathematical Problems in Engineering, 2019 (2019).
  * [13] Y. Kim and M. C. Ferris, Solving equilibrium problems using extended mathematical programming, Mathematical programming computation, 11 (2019), pp. 457–501.
  * [14] G. Kossioris, M. Plexousakis, A. Xepapadeas, A. de Zeeuw, and K.-G. Mäler, Feedback nash equilibria for non-linear differential games in pollution control, Journal of Economic Dynamics and Control, 32 (2008), pp. 1312–1331.
  * [15] F. Laine, D. Fridovich-Keil, C.-Y. Chiu, and C. Tomlin, Multi-hypothesis interactions in game-theoretic motion planning, 2020, https://arxiv.org/abs/2011.06047.
  * [16] T.-T. Lu and S.-H. Shiou, Inverses of 2$\times$ 2 block matrices, Computers & Mathematics with Applications, 43 (2002), pp. 119–129.
  * [17] J. Nocedal and S. Wright, Numerical optimization, Springer Science & Business Media, 2006.
  * [18] P. V. Reddy and G. Zaccour, Feedback nash equilibria in linear-quadratic difference games with constraints, IEEE Transactions on Automatic Control, 62 (2017), pp. 590–604, https://doi.org/10.1109/TAC.2016.2555879.
  * [19] P. V. Reddy and G. Zaccour, Open-loop and feedback nash equilibria in constrained linear–quadratic dynamic games played over event trees, Automatica, 107 (2019), pp. 162–174.
  * [20] A. Tanwani and Q. Zhu, Feedback nash equilibrium for markov jump games under differential-algebraic constraints with application to robust control, in 2018 IEEE Conference on Decision and Control (CDC), 2018, pp. 1124–1129, https://doi.org/10.1109/CDC.2018.8619628.
  * [21] A. Tanwani and Q. Zhu, Feedback nash equilibrium for randomly switching differential-algebraic games, IEEE Transactions on Automatic Control, (2019).
  * [22] Z. Wang, R. Spica, and M. Schwager, Game theoretic motion planning for multi-robot racing, in Robotics: Science and Systems 2018, 09 2018.