remarkRemark assumptionAssumption hypothesisHypothesis claimClaim Constrained
Feedback Stackelberg Equilibria Li, Sojoudi, Tomlin, and Fridovich-Keil

# The Computation of Approximate Feedback Stackelberg Equilibria in Multi-
player Nonlinear Constrained Dynamic Games††thanks:  This is a preprint
manuscript. This work was supported by the DARPA Assured Autonomy and ANSR
programs, the NASA ULI program in Safe Aviation Autonomy, and the ONR Basic
Research Challenge in Multibody Control Systems. D. Fridovich-Keil was
supported by the National Science Foundation under Grant No. 2211548.

Jingqi Li University of California, Berkeley<EMAIL_ADDRESS>Somayeh
Sojoudi22footnotemark: 2 Claire Tomlin22footnotemark: 2 David Fridovich-Keil
The University of Texas at Austin

###### Abstract

Solving feedback Stackelberg games with nonlinear dynamics and coupled
constraints, a common scenario in practice, presents significant challenges.
This work introduces an efficient method for computing local feedback
Stackelberg policies in multi-player general-sum dynamic games, with
continuous state and action spaces. Different from existing (approximate)
dynamic programming solutions that are primarily designed for unconstrained
problems, our approach involves reformulating a feedback Stackelberg dynamic
game into a sequence of nested optimization problems, enabling the derivation
of Karush–Kuhn–Tucker (KKT) conditions and the establishment of a second-order
sufficient condition for local feedback Stackelberg policies. We propose a
Newton-style primal-dual interior point method for solving constrained linear
quadratic (LQ) feedback Stackelberg games, offering provable convergence
guarantees. Our method is further extended to compute local feedback
Stackelberg policies for more general nonlinear games by iteratively
approximating them using LQ games, ensuring that their KKT conditions are
locally aligned with those of the original nonlinear games. We prove the
exponential convergence of our algorithm in constrained nonlinear games. In a
feedback Stackelberg game with nonlinear dynamics and (nonconvex) coupled
costs and constraints, our experimental results reveal the algorithm’s ability
to handle infeasible initial conditions and achieve exponential convergence
towards an approximate local feedback Stackelberg equilibrium.

###### keywords:

Feedback Stackelberg equilibrium, dynamic games, mathematical programming

49K99, 68Q25, 91A25

##  1 Introduction

Dynamic game theory [1] provides tools for analyzing strategic interactions in
multi-agent systems. It has broad applications in control [10], biology [25],
and economics [17]. A well-known equilibrium concept in dynamic game theory is
the _Nash equilibrium_ [36], where players pursue strategies that are
unilaterally optimal, and players make decisions simultaneously. However, this
may not apply to a broad class of games where a decision hierarchy exists,
such as lane-merging in highway driving [52], predator-prey competition in
biology [3], and retail markets in economics [29]. These games could be more
naturally formulated as _Stackelberg games_ [47], where players act
sequentially in a predefined order. For such games, the _Stackelberg
equilibrium_ is the appropriate equilibrium concept.

The precise formulation of Stackelberg equilibria depends on the information
structure [1]. For instance, in scenarios where players lack access to the
current game state, one can compute an _open-loop Stackelberg equilibrium_
(OLSE). At such an equilibrium, players’ decisions depend on the initial state
of a game and followers’ decisions are influenced by the leaders’. When
players also have access to state information and their prior players’
actions, it becomes appropriate to compute a _feedback Stackelberg
equilibrium_ (FSE), where each player’s decision is contingent upon the
current state and the actions of preceding players. One advantage of FSE over
OLSE is its sub-game perfection, meaning that decision policies remain optimal
for future stages, even if the state is perturbed at an intermediate stage.
This feature is particularly beneficial in scenarios with feedback
interactions among players, such as in lane merging during highway driving
[44] and human-robot interactions [14]. In these situations, the sub-game
perfection of FSE makes it a more suitable equilibrium concept than OLSE, as
it allows players to adjust their decisions based on the current state
information.

Though FSE is conceptually appealing, computing it poses significant
challenges [18, 49, 50, 32]. Previous research has extensively explored the
FSE problem in finite dynamic games, characterized by a finite number of
states and actions [42, 1, 45, 23, 2, 48]. In contrast, infinite dynamic
games–those with an infinite number of states and actions–have mostly been
considered within the framework of linear quadratic (LQ) games, featuring
linear dynamics and stage-wise quadratic costs [15, 1, 12, 46, 20]. The
computation of FSE for more general nonlinear games is more challenging than
for LQ games. A naive application of existing dynamic programming solutions in
finite dynamic games necessitates gridding the continuous state and action
spaces, often leading to computational intractability [6]. Recent works [34,
51] have proposed using approximate dynamic programming to compute an
approximate FSE for input-affine systems. Additionally, several iterative
linear-quadratic (LQ) approximation approaches have been proposed in [21, 35],
but they lack convergence guarantees.

Moreover, existing approaches are ill-suited for handling coupled equality and
inequality constraints on players’ states and decisions, which frequently
arise in safety-critical applications such as autonomous driving [43] and
human-robot interaction [22]. For instance, existing iterative LQ game solvers
[21, 35] cannot be directly integrated with the primal log barrier penalty
method [39] to incorporate these constraints. The most relevant studies, such
as [33, 13, 31], focus on computing OLSE in games under linear constraints.
This paper aims to bridge this gap in the literature.

Our contributions are threefold: (1) We first reformulate the $N$-player
feedback Stackelberg equilibrium problem, characterized by $N$ players making
sequential decisions over time, into a sequence of nested optimization
problems. This reformulation enables us to derive the Karush–Kuhn–Tucker (KKT)
conditions for the feedback Stackelberg equilibrium and to propose a second-
order sufficient condition for the local feedback Stackelberg policy. (2)
Using these results, we propose a Newton-style primal-dual interior point
(PDIP) algorithm for computing a local feedback Stackelberg equilibrium for LQ
games. Under certain regularity conditions, we show the convergence of our
algorithm to a local feedback Stackelberg equilibrium. (3) Finally, we propose
an efficient PDIP method for computing an approximate local feedback
Stackelberg equilbirium for more general nonlinear games under (nonconvex)
coupled equality and inequality constraints. Theoretically, we characterize
the approximation error of our method, and show the exponential convergence
under certain conditions. Empirically, we validate our algorithm in a highway
lane merging scenario, demonstrating its ability to tolerate infeasible
initializations and efficiently converge to an approximate local feedback
Stackelberg equilibrium in constrained nonlinear games.

##  2 Related Works

Closely related to the feedback Stackelberg equilibrium (FSE), the feedback
Nash equilibrium (FNE) has been extensively studied, for example, in [5, 1,
40, 24]. Our work builds upon [24], where the authors proposed KKT conditions
for constrained FNE. However, the FNE KKT conditions in [24] fail to hold true
for FSE due to the decision hierarchy in FSE. In our work, we introduce a set
of new KKT conditions for FSE. Another key difference is that we adopt the
primal-dual interior point method for solving LQ and nonlinear games, whereas
[24] considers the active-set method. In general, the former has polynomial
complexity, but the latter has exponential complexity [16]. Moreover, we are
able to prove the exponential convergence of our algorithm under certain
conditions. However, there is no such convergence proof in [24].

As highlighted in the literature, e.g., [1, 46, 34, 28, 51], the dominant
approach to computing unconstrained FSE is using (approximate) dynamic
programming. LQ games can be solved efficiently via exact dynamic programming;
however, in more general nonlinear cases the value function could be hard to
compute and, in general, has no analytical solution [34]. Compared with those
works, our approach could be considered as computing an efficient local
approximation of the value function along the state trajectory under the FSE
policy instead of approximating the value function everywhere as in [34].

Finally, to further motivate our work, we discuss whether the FSE could be
approximated well by a feedback Nash equilibrium or an open-loop Stackelberg
equilibrium. As suggested by [23], the FSE could coincide with the FNE in
repeated matrix games. However, we show a counter-example in Appendix A.1 that
the FSE could be arbitrarily different from the FNE in LQ games. Moreover,
there is a recent trend of approximating feedback policies via receding
horizon open-loop policies [26, 53], where an open-loop policy is re-solved at
each time for future steps. However, we show in another counter-example in
Appendix A.2 that the trajectory under the feedback Stackelberg policy and the
one under the receding horizon open-loop Stackelberg policy could be quite
different, even if there is no state perturbation. Thus, it is essential to
develop specific tools for computing the feedback Stackelberg equilibrium.

##  3 Constrained Feedback Stackelberg Games

In this section, we introduce the formulation of constrained feedback
Stackelberg games. We formulate the problem by extending the $N$-player
feedback Stackelberg games [15] to its constrained setting. We denote by
$\mathbb{N}$ and $\mathbb{R}$ the sets of natural numbers and real numbers,
respectively. Given $j,k\in\mathbb{N}$, we denote by
$\mathbf{I}_{j}^{k}=\\{j,j+1,\dots,k\\}$ if $j\leq k$ and $\emptyset$
otherwise. Let $T\in\mathbb{N}$ be the time horizon over which the game is
played. At each time $t$, we denote by $x_{t}$ and
$u_{t}^{i}\in\mathbb{R}^{m_{i}}$ the state of the entire game and the control
input of player $i$, respectively. We define
$u_{t}:=[u_{t}^{1},u_{t}^{2},\dots,u_{t}^{N}]\in\mathbb{R}^{m}$, with
$m:=\sum_{i=1}^{N}m_{i}$, to be the joint control input at time $t$. Moreover,
at each time $t$, players make decisions in the order of their indices. We
consider the time-varying dynamics

(1) $x_{t+1}=f_{t}(x_{t},u_{t}),$

where $f_{t}(x_{t},u_{t}):\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R}^{n}$
is assumed to be a twice differentiable function. Given a sequence of control
inputs ${\mathbf{u}}:=[u_{0},u_{1},\dots,u_{T}]\in\mathbb{R}^{Tm}$, we denote
by ${\mathbf{x}}:=[x_{0},x_{1},\dots,\allowbreak
x_{T+1}]\in\mathbb{R}^{(T+1)n}$ a state trajectory under dynamics (1).

At each time $t\in\mathbf{I}_{0}^{T}$, we denote the stage-wise cost of player
$i\in\mathbf{I}_{1}^{N}$ by
$\ell_{t}^{i}(x_{t},u_{t}):\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R}$,
and associate with each player a terminal cost,
$\ell_{T+1}^{i}(x_{T+1}):\mathbb{R}^{n}\to\mathbb{R}$. Each player
$i\in\mathbf{I}_{1}^{N}$ considers the following time-separable costs,

(2)
$J^{i}({\mathbf{x}},{\mathbf{u}})=\sum_{t=0}^{T}\ell_{t}^{i}(x_{t},u_{t})+\ell_{T+1}^{i}(x_{T+1}).\vspace{-0.5em}$

Moreover, let $n_{h,t}^{i}$ and $n_{g,t}^{i}$ be the number of equality and
inequality constraints held by player $i\in\mathbf{I}_{1}^{N}$ at time $t$,
respectively. We denote the equality and inequality constraint functions of
player $i$ by
$h_{t}^{i}(x_{t},u_{t}):\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R}^{n_{h,t}^{i}}$
and
$g_{t}^{i}(x_{t},u_{t}):\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R}^{n_{g,t}^{i}}$,
respectively. We specify the stage-wise equality and inequality constraints of
player $i\in\mathbf{I}_{1}^{N}$ as

(3) $\displaystyle 0=h_{t}^{i}(x_{t},u_{t}),\ 0\leq g_{t}^{i}(x_{t},u_{t}).$

At the terminal time $t=T+1$, we represent the equality and inequality
constraint functions of player $i\in\mathbf{I}_{1}^{N}$ by
$h_{T+1}^{i}(x_{T+1}):\mathbb{R}^{n}\to\mathbb{R}^{n_{h,T+1}^{i}}$ and
$g_{T+1}^{i}(x_{T+1}):\mathbb{R}^{n}\to\mathbb{R}^{n_{g,{T+1}}^{i}}$,
respectively. We consider the following equality and inequality constraints of
player $i\in\mathbf{I}_{1}^{N}$ at the terminal time,

(4) $0=h_{T+1}^{i}(x_{T+1}),\ 0\leq g_{T+1}^{i}(x_{T+1}).$

We remark that these definitions generate coupled dynamics and constraints
among different players at each time $t\in\mathbf{I}_{0}^{T+1}$. We consider
the following regularity assumption, following [24, 11]. The feasible set
$\mathcal{F}:=\\{x\in\mathbb{R}^{(T+1)n},u\in\mathbb{R}^{Tm}:h_{t}^{i}(x_{t},u_{t})=0,g_{t}^{i}(x_{t},u_{t})\geq
0,h_{T+1}^{i}(x_{T+1})=0,g_{T+1}^{i}(x_{T+1})\geq
0,x_{t+1}=f_{t}(x_{t},u_{t}),\forall
i\in\mathbf{I}_{1}^{N},t\in\mathbf{I}_{0}^{T}\\}$ is compact. The costs,
dynamics, equality and inequality constraints are twice differentiable and
bounded, but could be nonconvex in general.

###  3.1 Local Feedback Stackelberg Equilibria

In this subsection, we formalize the decision process of feedback Stackelberg
games. Before doing that, we introduce a few notations to compactly represent
different players’ control at different times. We define
$u_{t:t^{\prime}}^{i:i^{\prime}}:=\\{u_{\tau}^{j},\tau\in\mathbf{I}_{t}^{t^{\prime}},j\in\mathbf{I}_{i}^{i^{\prime}}\\}$.
In particular, we define $u_{t}^{1:i-1}:=\emptyset$ when $i=1$ and
$u_{t}^{i+1:N}:=\emptyset$ when $i=N$. We also denote by
$u_{t+1:T}^{1:i}:=\emptyset$ when $t=T$.

The policy of each player can be defined as follows. At the $t$-th stage,
since player 1 makes a decision first, its policy function
$\pi_{t}^{1}(x_{t}):\mathbb{R}^{n}\to\mathbb{R}^{m_{1}}$ depends only on the
state $x_{t}$. For players $i\in\mathbf{I}_{2}^{N}$, the policies are modeled
as
$\pi_{t}^{i}(x_{t},u_{t}^{1:i-1}):\mathbb{R}^{n}\times\mathbb{R}^{\sum_{j=1}^{i-1}m_{j}}\to\mathbb{R}^{m_{i}}$.
We will define the concept of _local feedback Stackelberg equilibria_ in the
remainder of this subsection.

At the terminal time $t=T+1$, we define the state-value functions for a player
$i\in\mathbf{I}_{1}^{N}$ as

(5) $V_{T+1}^{i}(x_{T+1}):=\left\\{\begin{aligned}
&\ell_{T+1}^{i}(x_{T+1})&&\textrm{if
}\left\\{\begin{subarray}{c}0=h_{T+1}^{i}(x_{T+1})\\\ 0\leq
g_{T+1}^{i}(x_{T+1})\end{subarray}\right.\\\
&\infty&&\textrm{else.}\end{aligned}\right.$

At time $t\leq T$, we first construct the state-action-value function for the
$N$-th player:

(6) $Z_{t}^{N}(x_{t},u_{t}^{1:N-1},u_{t}^{N}):=\left\\{\begin{aligned}
&\ell_{t}^{N}(x_{t},u_{t})+V_{t+1}^{N}(x_{t+1})&&\textrm{if
}\left\\{\begin{subarray}{c}0=x_{t+1}-f_{t}(x_{t},u_{t})\\\
0=h_{t}^{N}(x_{t},u_{t})\\\ 0\leq
g_{t}^{N}(x_{t},u_{t})\end{subarray}\right.\\\
&\infty&&\textrm{else.}\end{aligned}\right.$

Given $(x_{t},u_{t}^{1:N-1})$, there could be multiple $u_{t}^{N}$ minimizing
$Z_{t}^{N}(x_{t},u_{t}^{1:N-1},u_{t}^{N})$. We define $\pi_{t}^{N}$ by picking
an arbitrary minimizer $u_{t}^{N*}$,

(7)
$\pi_{t}^{N*}(x_{t},u_{t}^{1:N-1}):=u_{t}^{N*}\in\arg\min_{\tilde{u}_{t}^{N}}Z_{t}^{N}(x_{t},u_{t}^{1:N-1},\tilde{u}_{t}^{N}).$

We then construct the state-action-value function of player
$i\in\mathbf{I}_{2}^{N-1}$,

(8) $Z_{t}^{i}(x_{t},u_{t}^{1:i-1},u_{t}^{i}):=\left\\{\begin{aligned}
&\ell_{t}^{i}(x_{t},u_{t})+V_{t+1}^{i}(x_{t+1})&&\textrm{if
}\left\\{\begin{subarray}{c}0=x_{t+1}-f_{t}(x_{t},u_{t})\\\
0=h_{t}^{i}(x_{t},u_{t})\\\ 0\leq g_{t}^{i}(x_{t},u_{t})\\\
u_{t}^{j}=\pi_{t}^{j*}(x_{t},u_{t}^{1:j-1}),\
j\in\mathbf{I}_{i+1}^{N}\end{subarray}\right.\\\
&\infty&&\textrm{else,}\end{aligned}\right.$

and its policy

(9)
$\pi_{t}^{i*}(x_{t},u_{t}^{1:i-1}):=u_{t}^{i*}\in\arg\min_{\tilde{u}_{t}^{i}}Z_{t}^{i}(x_{t},u_{t}^{1:i-1},\tilde{u}_{t}^{i}).$

We finally construct the state-action-value function of the first player:

(10) $Z_{t}^{1}(x_{t},u_{t}^{1}):=\left\\{\begin{aligned}
&\ell_{t}^{1}(x_{t},u_{t})+V_{t+1}^{1}(x_{t+1})&&\textrm{if
}\left\\{\begin{subarray}{c}0=x_{t+1}-f_{t}(x_{t},u_{t})\\\
0=h_{t}^{1}(x_{t},u_{t})\\\ 0\leq g_{t}^{1}(x_{t},u_{t})\\\
u_{t}^{j}=\pi_{t}^{j*}(x_{t},u_{t}^{1:j-1}),\
j\in\mathbf{I}_{2}^{N}\end{subarray}\right.\\\
&\infty&&\textrm{else,}\end{aligned}\right.$

and its policy

(11)
$\pi_{t}^{1*}(x_{t}):=u_{t}^{1*}\in\arg\min_{\tilde{u}_{t}^{1}}Z_{t}^{1}(x_{t},\tilde{u}_{t}^{1}).$

We define the state-value function of player $i\in\\{1,2,\dots,N\\}$ at time
$t\leq T$ as

(12) $\displaystyle V_{t}^{i}(x_{t})=$ $\displaystyle
Z_{t}^{i}(x_{t},u_{t}^{1*},\dots,u_{t}^{i*}),$

where $u_{t}^{j*}=\pi_{t}^{j*}(x_{t},u_{t}^{1:(j-1)*}),\forall
j\in\mathbf{I}_{1}^{i}$.

We formally define the local generalized feedback Stackelberg policies as
follows.

######  Definition 3.1 (Local Feedback Stackelberg Policies [1]).

Let $\\{\pi_{t}^{i*}\\}_{t=0,i=1}^{T,N}$ be a set of policies, and define
$({\mathbf{x}}^{*},{\mathbf{u}}^{*})$ to be a state and control trajectory
under the policies $\\{\pi_{t}^{i*}\\}_{t=0,i=1}^{T,N}$, i.e.,

(13) $\displaystyle x_{t+1}^{*}=f_{t}(x_{t}^{*},u_{t}^{*}),\
u_{t}^{i*}=\pi_{t}^{i*}(x_{t}^{*},u_{t}^{1:(i-1)*}),\ \forall
t\in\mathbf{I}_{0}^{T},\ i\in\mathbf{I}_{1}^{N}.$

We say that $({\mathbf{x}}^{*},{\mathbf{u}}^{*})$ is a local feedback
Stackelberg equilibrium trajectory. Moreover, the set of policies
$\\{\pi_{t}^{i*}\\}_{t=0,i=1}^{T,N}$ is called a set of local feedback
Stackelberg policies if there exists an $\epsilon>0$ such that, for all
$t\in\mathbf{I}_{0}^{T}$,

(14) $\displaystyle Z_{t}^{1}(x_{t}^{*},\tilde{u}_{t}^{1})$ $\displaystyle\geq
Z_{t}^{1}(x_{t}^{*},u_{t}^{1*}),$ $\displaystyle\ \vdots$ $\displaystyle
Z_{t}^{N}(x_{t}^{*},u_{t}^{1*},\dots,u_{t}^{(N-1)*},\tilde{u}_{t}^{N})$
$\displaystyle\geq
Z_{t}^{N}(x_{t}^{*},u_{t}^{1*},\dots,u_{t}^{(N-1)*},u_{t}^{N*})$

for all $\tilde{u}_{t}^{1}\in\\{u:\|u-u_{t}^{1*}\|_{2}\leq\epsilon\\}$,
$\dots$, and $\tilde{u}_{t}^{N}\in\\{u:\|u-u_{t}^{N*}\|_{2}\leq\epsilon\\}$.

The above definition encapsulates the traditional approach to computing
feedback Stackelberg policies. This involves optimizing over state-action-
value functions, which are obtained by integrating other players’ policies
into each player’s problem and then recording the overall costs.

######  Remark 3.2 (Existence of Local Feedback Stackelberg Policies).

In general, it is difficult to establish a sufficient condition for the
existence of a feedback Stackelberg policy [7]. The main difficulty is that
the decision problem of each player is nested within that of other players. It
must be solved hierarchically. For example, the existence of feedback
Stackelberg policies [30] of a player $i\in\mathbf{I}_{1}^{N-1}$ is related to
the topological properties of the set of policies of players
$j\in\mathbf{I}_{i+1}^{N}$. Even if all the players’ costs are convex, the
feedback Stackelberg policy of player $N$ at the terminal time could be lower
semi-continuous. Subsequently, the cost of player $(N-1)$ could become upper
semi-continuous when substituting in the $N$-th player’s policy into the
$(N-1)$-th player’s cost. Since there may not exist a solution when minimizing
an upper semi-continuous function, there may not exist a feedback Stackelberg
policy for player $(N-1)$. However, if we can show that the policy of each
player is always continuous in the state and prior players’ controls and the
continuous costs are defined on a compact domain, then there exist feedback
Stackelberg equilibria [1].

We will now proceed to characterize the feedback Stackelberg policies in
greater detail in the subsequent section.

##  4 Necessary and Sufficient Conditions for Local Feedback Stackelberg
Policies

We show in the following theorem that the dynamic programming problem, as
described in Definition 3.1, can be reformulated as a sequence of nested
constrained optimization problems. In this reformulation, the policies for
other players are integrated as constraints within the problem of each player
$i$, instead of being directly substituted into the costs for computing state-
action-value functions, as is typical in traditional optimal control
literature. This approach enables us to establish KKT conditions for feedback
Stackelberg games in the latter part of this subsection.

######  Theorem 4.1.

Under Assumption 3, a set of policies $\pi:=\\{\pi_{t}^{i}\\}_{t=0,i=1}^{T,N}$
constitutes a set of local feedback Stackelberg policies if for all players
$i\in\mathbf{I}_{1}^{N}$, at all times $t\in\mathbf{I}_{0}^{T}$, its policy
$\pi_{t}^{i}$ satisfies

(15a)
$\displaystyle\pi_{t}^{i}(x_{t},u_{t}^{1:i-1})=\tilde{u}_{t}^{i}\in\underset{u_{t}^{i}}{\arg}\min_{\begin{subarray}{c}u_{t}^{i:N}\\\
u_{t+1:T}^{1:N}\\\ x_{t+1:T+1}\end{subarray}}$
$\displaystyle\sum_{\tau=t}^{T}\ell_{\tau}^{i}(x_{\tau},u_{\tau})+\ell_{T+1}^{i}(x_{T+1})$
(15b) s.t. $\displaystyle
0=u_{\tau}^{j}-\pi_{\tau}^{j}(x_{\tau},u_{\tau}^{1:j-1}),$
$\displaystyle\tau\in\mathbf{I}_{t+1}^{T},j\in\mathbf{I}_{1}^{N}\setminus\\{i\\}$
(15c) $\displaystyle 0=u_{t}^{j}-\pi_{t}^{j}(x_{t},u_{t}^{1:j-1}),$
$\displaystyle j\in\mathbf{I}_{i+1}^{N}$ (15d) $\displaystyle
0=x_{\tau+1}-f_{\tau}(x_{\tau},u_{\tau}),$
$\displaystyle\tau\in\mathbf{I}_{t}^{T}$ (15e) $\displaystyle
0=h_{\tau}^{i}(x_{\tau},u_{\tau}),\ 0\leq g_{\tau}^{i}(x_{\tau},u_{\tau}),$
$\displaystyle\tau\in\mathbf{I}_{t}^{T}$ (15f) $\displaystyle
0=h_{T+1}^{i}(x_{T+1}),\ 0\leq g_{T+1}^{i}(x_{T+1})$

where we drop (15c) when $i=N$, and we drop (15b) when $t=T$. The notation
$\arg_{u}\min_{u,v}$ represents that we minimize over $(u,v)$ but only return
$u$ as an output.

######  Proof 4.2.

The proof can be found in the Appendix.

In what follows, we will characterize the KKT conditions of the constrained
optimization problems in (15). Before doing that, we first introduce Lagrange
multipliers, which facilitate the formulation of Lagrangian functions for all
players.

Let $t\in\mathbf{I}_{0}^{T}$ and $i\in\mathbf{I}_{1}^{N}$. We denote by
$\lambda_{t}^{i}\in\mathbb{R}^{n}$ the Lagrange multiplier for the dynamics
constraint $0=x_{t+1}-f_{t}(x_{t},u_{t})$. Let $\mathbb{R}_{\geq 0}$ be the
set of non-negative real numbers. We define
$\mu_{t}^{i}\in\mathbb{R}^{n_{h,t}^{i}}$ and
$\gamma_{t}^{i}\in\mathbb{R}_{\geq 0}^{n_{g,t}^{i}}$ to be the Lagrange
multipliers for the constraints $0=h_{t}^{i}(x_{t},u_{t})$ and $0\leq
g_{t}^{i}(x_{t},u_{t})$, respectively. When $t\leq T$, the constrained problem
(15) of player $i<N$ considers the feedback interaction constraint
$0=u_{t}^{j}-\pi_{t}^{j}(x_{t},u_{t}^{1:j-1})$, $j\in\mathbf{I}_{i+1}^{N}$.
Thus, we associate those constraints with multipliers
$\psi_{t}^{i}:=[\psi_{t}^{i,i+1},\psi_{t}^{i,i+2},\dots,\psi_{t}^{i,N}]$,
where $\psi_{t}^{i,j}\in\mathbb{R}^{m_{i}}$. Moreover, when $t<T$, the
constrained problem (15) of a player $i\leq N$ includes the feedback
interaction constraints
$0=u_{\tau+1}^{j}-\pi_{\tau+1}^{j}(x_{\tau+1},u_{\tau+1}^{1:j-1})$, for
$\tau\geq t$ and $j\in\mathbf{I}_{1}^{N}\setminus\\{i\\}$. Thus, we associate
those constraints with multipliers
$\eta_{t}^{i}:=[\eta_{t}^{i,1},\dots,\eta_{t}^{i,i-1},\eta_{t}^{i,i+1},\allowbreak\dots,\eta_{t}^{i,N}]$,
where $\eta_{t}^{i,j}\in\mathbb{R}^{m_{j}}$. Finally, we simplify the notation
by defining
$\lambda_{t}:=[\lambda_{t}^{1},\lambda_{t}^{2},\dots,\lambda_{t}^{N}]$, and
define $\mu_{t}$, $\gamma_{t}$, $\eta_{t}$, and $\psi_{t}$ accordingly.

Subsequently, we define the Lagrangian functions of all the players. We first
consider player $i\in\mathbf{I}_{1}^{N}$,

(16) $\displaystyle
L_{t}^{i}(x_{t:t+1},u_{t:t+1},\lambda_{t},\mu_{t},\gamma_{t},\eta_{t},\psi_{t}):$
$\displaystyle=\ell_{t}^{i}(x_{t},u_{t})-\lambda_{t}^{i\top}(x_{t+1}-f_{t}(x_{t},u_{t}))$
$\displaystyle-\mu_{t}^{i\top}h_{t}^{i}(x_{t},u_{t})-\gamma_{t}^{i\top}g_{t}^{i}(x_{t},u_{t})$
$\displaystyle-\sum_{j\in\mathbf{I}_{i+1}^{N}}\psi_{t}^{i,j\top}(u_{t}^{j}-\pi_{t}^{j}(x_{t},u_{t}^{1:j-1}))$
$\displaystyle-\sum_{j\in\mathbf{I}_{1}^{N}\setminus\\{i\\}}\eta_{t}^{i,j^{\top}}(u_{t+1}^{j}-\pi_{t+1}^{j}(x_{t+1},u_{t+1}^{1:j-1}))$

where the right hand side terms represent player $i$’s cost, dynamics
constraint, equality and inequality constraints, and constraints encoding the
feedback interaction among players at the current and future time steps.

Furthermore, at the terminal time $t=T$, for player $i\in\mathbf{I}_{1}^{N}$,
we consider

(17) $\displaystyle
L_{T}^{i}(x_{T:T+1},u_{T},\lambda_{T},\mu_{T:T+1},\gamma_{T:T+1},\psi_{T}):$
$\displaystyle=\ell_{T}^{i}(x_{T},u_{T})+\ell_{T+1}^{i}(x_{T})$
$\displaystyle-\lambda_{T}^{i\top}(x_{T+1}-f_{T}(x_{T},u_{T}))$
$\displaystyle-\mu_{T}^{i\top}h_{T}^{i}(x_{T},u_{T})-\mu_{T+1}^{i\top}h_{T+1}^{i}(x_{T+1})$
$\displaystyle-\gamma_{T}^{i\top}g_{T}^{i}(x_{T},u_{T})-\gamma_{T+1}^{i\top}g_{T+1}^{i}(x_{T+1})$
$\displaystyle-\sum_{j\in\mathbf{I}_{i+1}^{N}}\psi_{T}^{i,j\top}(u_{T}^{j}-\pi_{T}^{j}(x_{T},u_{T}^{1:j-1}))$

where the right hand side terms represent player $i$’s costs, dynamics
constraint, equality and inequality constraints, and constraints encoding the
feedback interaction among players at the terminal time $T$. Note that there
is no more decision to be made at time $t=T+1$, and therefore, there is no
term representing the feedback interactions among players for future time
steps in (17), which is different from (16).

For all time steps $t\in\mathbf{I}_{0}^{T}$ and players
$i\in\mathbf{I}_{1}^{N}$, assuming the state $x_{t}$ is given and each player
$j<i$ has taken action $u_{t}^{j}$, we formulate the Lagrangian of the problem
(15) of player $i$ at the $t$-th stage as

(18) $\displaystyle\mathcal{L}_{t}^{i}($ $\displaystyle
x_{t:T+1},u_{t:T},\lambda_{t:T},\mu_{t:T+1},\gamma_{t:T+1},\eta_{t:T-1},\psi_{t:T}):=\sum_{\tau=t}^{T-1}L_{\tau}^{i}(x_{\tau:\tau+1},u_{\tau:\tau+1},$
$\displaystyle\lambda_{\tau},\mu_{\tau},\gamma_{\tau},\eta_{\tau},\psi_{\tau})+L_{T}^{i}(x_{T:T+1},u_{T},\lambda_{T},\mu_{T:T+1},\gamma_{T:T+1},\psi_{T})$

In what follows, we will propose KKT conditions for the nested constrained
optimization problem (15). We concatenate the KKT conditions of each player at
each time step, and we summarize the overall KKT conditions in the following
theorem.

######  Theorem 4.3 (Necessary Condition).

Under Assumption 3, let $({\mathbf{x}}^{*},{\mathbf{u}}^{*})$ be a local
feedback Stackelberg equilibrium trajectory. Suppose that the Linear
Independence Constraint Qualification (LICQ) [37] and strict complementarity
condition [9] are satisfied at $({\mathbf{x}}^{*},{\mathbf{u}}^{*})$.
Furthermore, suppose $\\{\pi_{t}^{i}\\}_{t=0,i=1}^{T,N}$ is a set of local
feedback Stackelberg policies and $\pi_{t}^{i}$ is differentiable around
$(x_{t}^{*},u_{t}^{1:(i-1)*})$, $\forall t\in\mathbf{I}_{0}^{T}$,
$i\in\mathbf{I}_{1}^{N}$. The KKT conditions of (15) can be formulated as, for
all $i\in\mathbf{I}_{1}^{N}$, $t\in\mathbf{I}_{0}^{T}$,

(19) $\displaystyle 0$
$\displaystyle=\nabla_{u_{t}^{i}}\mathcal{L}_{t}^{i}(x^{*}_{t:T+1},u^{*}_{t:T},\lambda_{t:T},\mu_{t:T+1},\gamma_{t:T+1},\eta_{t:T-1},\psi_{t:T})$
$\displaystyle 0$
$\displaystyle=\nabla_{x_{\tau}}\mathcal{L}_{t}^{i}(x^{*}_{t:T+1},u^{*}_{t:T},\lambda_{t:T},\mu_{t:T+1},\gamma_{t:T+1},\eta_{t:T-1},\psi_{t:T}),$
$\displaystyle\forall\tau\in\mathbf{I}_{t}^{T}$ $\displaystyle 0$
$\displaystyle=\nabla_{u_{t}^{j}}\mathcal{L}_{t}^{i}(x^{*}_{t:T+1},u^{*}_{t:T},\lambda_{t:T},\mu_{t:T+1},\gamma_{t:T+1},\eta_{t:T-1},\psi_{t:T}),$
$\displaystyle\forall j\in\mathbf{I}_{i+1}^{N}$ $\displaystyle 0$
$\displaystyle=\nabla_{u_{\tau}^{j}}\mathcal{L}_{t}^{i}(x^{*}_{t:T+1},u^{*}_{t:T},\lambda_{t:T},\mu_{t:T+1},\gamma_{t:T+1},\eta_{t:T-1},\psi_{t:T}),$
$\displaystyle\forall
j\in\mathbf{I}_{1}^{N}\setminus\\{i\\},\forall\tau\in\mathbf{I}_{t+1}^{T}$
$\displaystyle 0$
$\displaystyle=x^{*}_{\tau+1}-f_{\tau}(x^{*}_{\tau},u^{*}_{\tau}),$
$\displaystyle\forall\tau\in\mathbf{I}_{t}^{T}$ $\displaystyle 0$
$\displaystyle=h_{\tau}^{i}(x^{*}_{\tau},u^{*}_{\tau}),$
$\displaystyle\forall\tau\in\mathbf{I}_{t}^{T}$ $\displaystyle 0$
$\displaystyle\leq\gamma_{\tau}^{i}\perp
g_{\tau}^{i}(x^{*}_{\tau},u^{*}_{\tau})\geq 0,$
$\displaystyle\forall\tau\in\mathbf{I}_{t}^{T}$ $\displaystyle 0$
$\displaystyle=h_{T+1}^{i}(x^{*}_{T+1}),$ $\displaystyle 0$
$\displaystyle\leq\gamma_{T+1}^{i}\perp g_{T+1}^{i}(x^{*}_{T+1})\geq 0$

where $\perp$ represents the complementary slackness condition [9]. Then,
there exists Lagrange multipliers
${\boldsymbol{\lambda}}:=[\lambda_{t}]_{t=0}^{T}$,
${\boldsymbol{\mu}}:=[\mu_{t}]_{t=0}^{T}$,
${\boldsymbol{\gamma}}:=[\gamma_{t}]_{t=0}^{T}$,
${\boldsymbol{\eta}}:=[\eta_{t}]_{t=0}^{T-1}$, and
${\boldsymbol{\psi}}:=[\psi_{t}]_{t=0}^{T}$, such that (19) holds true.

######  Proof 4.4.

The proof can be found in the Appendix.

Constructing the KKT conditions in (19) requires the computation of policy
gradients, $\\{\nabla\pi_{t}^{i}\\}_{t=0,i=1}^{T,N}$, which appear in the
first four rows of (19). However, knowing the policy itself is not required,
as any solution satisfying the KKT conditions obeys the corresponding feedback
Stackelberg policy, as shown in the proof of Theorem 4.3. A key distinction
between (19) and the FNE KKT conditions in [24] lies in the accommodation of a
decision hierarchy among the $N$ players at each stage. This is reflected in
the terms
$-\sum_{j\in\mathbf{I}_{i+1}^{N}}\psi_{t}^{i,j\top}(u_{t}^{j}-\pi_{t}^{j}(x_{t},u_{t}^{1:j-1}))$
in the Lagrangian $\mathcal{L}_{t}^{i}$. Additionally, this decision hierarchy
differentiates the construction of the FSE KKT conditions from those of FNE.
We will outline a detailed procedure for constructing the FSE KKT conditions
in Sections 5 and 6, with an example provided in Appendix B.

Furthermore, we propose a sufficient condition for feedback Stackelberg
policies in the following theorem.

######  Theorem 4.5 (Sufficient Condition).

Suppose
$\\{{\mathbf{x}},{\mathbf{u}},{\boldsymbol{\lambda}},{\boldsymbol{\mu}},{\boldsymbol{\gamma}},{\boldsymbol{\eta}},{\boldsymbol{\psi}}\\}$
and its associated policies $\\{\pi_{t}^{i}\\}_{t=0,i=1}^{T,N}$ satisfy (19)
and there exists an $\epsilon>0$ such that, for all $i\in\mathbf{I}_{1}^{N}$,
$t\in\mathbf{I}_{0}^{T}$, and nonzero $\\{\Delta x_{T+1}\\}\bigcup\\{\Delta
x_{\tau},\Delta u_{\tau}\\}_{\tau=t}^{T}$ satisfying

(20) $\displaystyle 0=\Delta
u_{t}^{j}-\nabla\pi_{t}^{j}(x_{t},u_{t}^{1:j-1})\begin{bmatrix}\Delta x_{t}\\\
\Delta u_{t}^{1:j-1}\end{bmatrix},\forall j\in\mathbf{I}_{i}^{N}$
$\displaystyle 0=\Delta
u_{\tau}^{j}-\nabla\pi_{\tau}^{j}(x_{\tau},u_{\tau}^{1:j-1})\begin{bmatrix}\Delta
x_{\tau}\\\ \Delta u_{\tau}^{1:j-1}\end{bmatrix},\forall
j\in\mathbf{I}_{1}^{N},\forall\tau\in\mathbf{I}_{t+1}^{T}$ $\displaystyle
0=\Delta x_{\tau+1}-\nabla f_{\tau}(x_{\tau},u_{\tau})\begin{bmatrix}\Delta
x_{\tau}\\\ \Delta u_{\tau}\end{bmatrix},\forall\tau\in\mathbf{I}_{t}^{T}$
$\displaystyle 0=\nabla h_{\tau}^{j}(x_{\tau},u_{\tau})\begin{bmatrix}\Delta
x_{\tau}\\\ \Delta u_{\tau}\end{bmatrix},0=\nabla h_{T+1}^{j}(x_{T+1})\Delta
x_{T+1},\forall\tau\in\mathbf{I}_{0}^{T},\forall j\in\mathbf{I}_{1}^{N}$

we have $\sum_{i=1}^{N}\Bigg{[}\sum_{\tau=t}^{T}\begin{bmatrix}\Delta
x_{\tau}\\\ \Delta
u_{\tau}^{i}\end{bmatrix}^{\top}\nabla^{2}_{[x_{\tau},u_{\tau}^{i}]}L_{\tau}^{i}\begin{bmatrix}\Delta
x_{\tau}\\\ \Delta u_{\tau}^{i}\end{bmatrix}+\Delta
x_{T+1}^{\top}\nabla^{2}_{x_{T+1}}L_{T+1}^{i}\Delta x_{T+1}\Bigg{]}>0.$
Then, $\\{\pi_{t}^{i}\\}_{t=0,i=1}^{T,N}$ is a set of local feedback
Stackelberg policies and $({\mathbf{x}},{\mathbf{u}})$ constitutes a local
feedback Stackelberg equilibrium trajectory.

######  Proof 4.6.

The proof can be found in the Appendix.

######  Remark 4.7.

The gap between the necessity condition in Theorem 4.3 and the sufficiency
condition in Theorem 4.5 is due to the fact that a solution to (19) may not
necessarily be a feedback Stackelberg equilibrium, and that there exist
feedback Stackelberg equilibria where the cost functions possess zero second-
order gradients.

Theorems 4.3 and 4.5 establish conditions to certify whether a trajectory
$({\mathbf{x}},{\mathbf{u}})$ constitutes a feedback Stackelberg equilibrium
with a set of feedback Stackelberg policies
$\\{\pi_{t}^{i}\\}_{t=0,i=1}^{T,N}$. However, computing such policies
$\\{\pi_{t}^{i}\\}_{t=0,i=1}^{T,N}$ can be challenging. In the following
sections, we will discuss how to compute those policies. We will first compute
feedback policies for Linear Quadratic games and then extend the result to
nonlinear games.

##  5 Constrained Linear Quadratic Games

We consider the linear dynamics

(21)
$x_{t+1}=f_{t}(x_{t},u_{t})=A_{t}x_{t}+B_{t}^{1}u_{t}^{1}+\dots+B_{t}^{N}u_{t}^{N}+c_{t},\
t\in\mathbf{I}_{0}^{T},$

where $A_{t}\in\mathbb{R}^{n\times n}$,
$B_{t}^{i}\in\mathbb{R}^{n\times{m_{i}}}$ and $c_{t}\in\mathbb{R}^{n}$. We
denote by $B_{t}:=[B_{t}^{1},B_{t}^{2},\dots,B_{t}^{N}]$. The cost of the
$i$-th player is defined as

(22) $\displaystyle\ell_{t}^{i}(x_{t},u_{t})=$
$\displaystyle\frac{1}{2}\begin{bmatrix}x_{t}\\\
u_{t}\end{bmatrix}^{\top}\begin{bmatrix}Q_{t}^{i}&S_{t}^{i\top}\\\
S_{t}^{i}&R_{t}^{i}\end{bmatrix}\begin{bmatrix}x_{t}\\\
u_{t}\end{bmatrix}+q_{t}^{i\top}x_{t}+r_{t}^{i\top}u_{t},\
t\in\mathbf{I}_{0}^{T},$ $\displaystyle\ell_{T+1}^{i}(x_{T+1})=$
$\displaystyle\frac{1}{2}x_{T+1}^{\top}Q_{T+1}^{i}x_{T+1}+q_{T+1}^{i\top}x_{T+1},$

where symmetric matrices $Q_{t}^{i}\in\mathbb{R}^{n\times n}$ and
$R_{t}^{i}\in\mathbb{R}^{m\times m}$ are positive semidefinite and positive
definite, respectively. The off-diagonal matrix is denoted as
$S_{t}^{i}\in\mathbb{R}^{m\times n}$. In particular, we partition the
structure of $R_{t}^{i}$, $S_{t}^{i}$ and $r_{t}^{i}$ as follows

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

where $R_{t}^{i,j,k}$, $S_{t}^{i,j}$ and $r_{t}^{i}$ represent the cost terms
$u_{t}^{j\top}R_{t}^{i,j,k}u_{t}^{k}$, $u_{t}^{j\top}S_{t}^{i,j}x_{t}$ and
$r_{t}^{i,j^{\top}}u_{t}^{j}$ in $\ell_{t}^{i}(x_{t},u_{t})$. The linear
equality and inequality constraints are specified as,

(24) $\displaystyle
0=h_{t}^{i}(x_{t},u_{t})=H_{x_{t}}^{i}x_{t}+\sum_{j\in\mathbf{I}_{1}^{N}}H_{u_{t}^{j}}^{i}u_{t}^{j}+\bar{h}_{t}^{i},$
$\displaystyle t\in\mathbf{I}_{0}^{T}$ $\displaystyle 0\leq
g_{t}^{i}(x_{t},u_{t})=G_{x_{t}}^{i}x_{t}+\sum_{j\in\mathbf{I}_{1}^{N}}G_{u_{t}^{j}}^{i}u_{t}^{j}+\bar{g}_{t}^{i},$
$\displaystyle t\in\mathbf{I}_{0}^{T}$ $\displaystyle
0=h_{T+1}^{i}(x_{T+1})=H_{x_{T+1}}^{i}x_{T+1}+\bar{h}_{T+1}^{i},$
$\displaystyle 0\leq
g_{T+1}^{i}(x_{T+1})=G_{x_{T+1}}^{i}x_{T+1}+\bar{g}_{T+1}^{i}.$

###  5.1 Computing Policies and Constructing the KKT Conditions for LQ Games

In this subsection, we introduce a process for deriving policies and the KKT
conditions for LQ games. When we have linear inequality constraints, the
optimal policies of LQ games are generally piecewise linear functions of the
state [8, 24]. However, this makes them non-differentiable at the facets. In
our work, we propose to use the primal-dual interior point (PDIP) method [37]
to solve constrained LQ games. The benefits of using PDIP are its polynomial
complexity and tolerance of infeasible initializations. Critically, under
certain conditions, PDIP yields a local differentiable policy approximation to
the ground truth piecewise linear policy, as shown in the rest of this section
and an example in Appendix A.3.

To this end, we introduce a set of non-negative slack variables
$\\{s_{t}^{i}\\}_{t=0,i=1}^{T+1,N}$ such that we can rewrite the inequality
constraints as equality constraints for $t\in\mathbf{I}_{0}^{T+1}$ and
$i\in\mathbf{I}_{1}^{N}$,

(25) $\displaystyle g_{t}^{i}(x_{t},u_{t})-s_{t}^{i}=0,\
g_{T+1}^{i}(x_{T+1})-s_{T+1}^{i}=0.$

In this paper, we consider PDIP as a homotopy method as in [37]. Instead of
solving the mixed complementarity problem (19) directly, we seek solutions to
the homotopy approximation of the complementary slackness condition

(26) $\gamma_{t}^{i}\odot s_{t}^{i}=\rho\mathbf{1},\ s_{t}^{i}\geq 0,\
\gamma_{t}^{i}\geq 0$

where $\odot$ denotes the elementwise product and $\rho>0$ is a hyper-
parameter to be reduced to 0 gradually such that we recover the ground truth
solution when $\rho\to 0$. In the following section, we will construct the KKT
conditions where we replace the mixed complementarity condition with its
approximation (26). For each $\rho>0$, we denote its corresponding feedback
Stackelberg policy as $\\{{\pi_{t,\rho}^{i}}\\}_{t=0,i=1}^{T,N}$, if it
exists.

As shown in Theorem 4.3, the construction of the KKT conditions for player $i$
at stage $t$ requires the policy gradients of subsequent players at the
current stage and future stages. In what follows, we construct those KKT
conditions in reverse player order and backward in time.

####  5.1.1 Player $N$ at the $T$-th stage

Before constructing the KKT conditions, we first introduce the variables of
player $N$ at the terminal time $T$,
${\mathbf{z}}_{T}^{N}:=[u_{T}^{N},\lambda_{T}^{N},\mu_{T:T+1}^{N},\gamma_{T:T+1}^{N},\allowbreak
s_{T:T+1}^{N},x_{T+1}]$. As shown in Theorem 4.3, the KKT conditions of player
$N$ at time $T$ can be written as

(27)
$0=K_{T,\rho}^{N}({\mathbf{z}}_{T}^{N}):=\begin{bmatrix}\nabla_{u_{T}^{N}}L_{T}^{N}\\\
\nabla_{x_{T+1}}L_{T+1}^{N}\\\ x_{T+1}-f_{T}(x_{T},u_{T})\\\
h_{T}^{N}(x_{T},u_{T})\\\ h_{T+1}^{N}(x_{T+1})\\\
g_{T}^{N}(x_{T},u_{T})-s_{T}^{N}\\\ g_{T+1}^{N}(x_{T+1})-s_{T+1}^{N}\\\
\gamma_{T:T+1}^{N}\odot s_{T:T+1}^{N}-\rho\mathbf{1}\end{bmatrix},$

where the rows of $K_{T,\rho}^{N}({\mathbf{z}}_{T}^{N})$ represent the
stationarity conditions with respect to $u_{T}^{N}$ and $x_{T+1}$, dynamics
constraint, equality constraints, relaxed complementarity conditions, and
inequality constraints. To obtain a local policy and its policy gradient
around a ${\mathbf{z}}_{T}^{N}$ satisfying (27), we build a first-order
approximation to (27),

(28) $\nabla
K_{T,\rho}^{N}\cdot\Delta{\mathbf{z}}_{T}^{N}+\nabla_{[x_{T},u_{T}^{1:N-1}]}K_{T,\rho}^{N}\cdot\begin{bmatrix}\Delta
x_{T}\\\ \Delta
u_{T}^{1:N-1}\end{bmatrix}+K_{T,\rho}^{N}({\mathbf{z}}_{T}^{N})=0.$

If there is no solution $\Delta{\mathbf{z}}_{T}^{N}$ to (28), then we claim
there is no feedback Stackelberg policy. Suppose (28) has a solution
$\Delta{\mathbf{z}}_{T}^{N}$, then we can define $\Delta{\mathbf{z}}_{T}^{N}$
as

(29) $\displaystyle\Delta{\mathbf{z}}_{T}^{N}=\underbrace{-\big{(}\nabla
K_{T,\rho}^{N}\big{)}^{+}\cdot\Big{(}\nabla_{[x_{T},u_{T}^{1:N-1}]}K_{T,\rho}^{N}\cdot\begin{bmatrix}\Delta
x_{T}\\\ \Delta
u_{T}^{1:N-1}\end{bmatrix}+K_{T,\rho}^{N}({\mathbf{z}}_{T}^{N})\Big{)}}_{F_{T}^{N}(\Delta
x_{T},\Delta u_{T}^{1:N-1})},$

where $(\cdot)^{+}$ represents the pseudo-inverse and we denote
$\Delta{\mathbf{z}}_{T}^{N}$ as a function $F_{T}^{N}$ of $(\Delta
x_{T},\Delta u_{T}^{1:N-1})$. Since $\Delta u_{T}^{N}$ represents the first
$m_{N}$ entries of $\Delta{\mathbf{z}}_{T}^{N}$, we consider $\Delta
u_{T}^{N}$ as a function of $(\Delta x_{T},\Delta u_{T}^{1:N-1})$,

(30) $\displaystyle\Delta u_{T}^{N}=$ $\displaystyle-\big{[}\big{(}\nabla
K_{T,\rho}^{N}\big{)}^{+}\big{]}_{u_{T}^{N}}\cdot\Big{(}\nabla_{[x_{T},u_{T}^{1:N-1}]}K_{T,\rho}^{N}\cdot\begin{bmatrix}\Delta
x_{T}\\\ \Delta
u_{T}^{1:N-1}\end{bmatrix}+K_{T,\rho}^{N}({\mathbf{z}}_{T}^{N})\Big{)},$

where $\big{[}\big{(}\nabla K_{T,\rho}^{N}\big{)}^{+}\big{]}_{u_{T}^{N}}$
represents the rows of the matrix $\big{(}\nabla K_{T,\rho}^{N}\big{)}^{+}$
corresponding to the variable $u_{T}^{N}$, i.e., the first $m_{N}$ rows of the
matrix $\big{(}\nabla K_{T,\rho}^{N}\big{)}^{+}$.

Furthermore, for some $x\in\mathbb{R}^{n}$ and
$u^{1:N-1}\in\mathbb{R}^{\sum_{i=1}^{N-1}m_{i}}$, let $\Delta x_{T}=x-x_{T}$,
$\Delta u_{T}^{1:N-1}=u^{1:N-1}-u_{T}^{1:N-1}$ and $\Delta
u_{T}^{N}=u^{N}-u_{T}^{N}$. Substituting them into (30), we obtain a local
policy ${\tilde{\pi}_{T,\rho}^{N}}$ for player $N$ at time $T$,

(31) $\displaystyle u^{N}=$
$\displaystyle{\tilde{\pi}_{T,\rho}^{N}}(x,u^{1:N-1})$ $\displaystyle:=$
$\displaystyle u_{T}^{N}-\big{[}\big{(}\nabla
K_{T,\rho}^{N}\big{)}^{+}\big{]}_{u_{T}^{N}}\cdot\Big{(}\nabla_{[x_{T},u_{T}^{1:N-1}]}K_{T,\rho}^{N}\cdot\begin{bmatrix}x-x_{T}\\\
u^{1:N-1}-u_{T}^{1:N-1}\end{bmatrix}+K_{T,\rho}^{N}({\mathbf{z}}_{T}^{N})\Big{)}.$

Suppose that $\nabla K_{T,\rho}^{N}({\mathbf{z}}_{T}^{N})$ has a constant row
rank in an open set containing ${\mathbf{z}}_{T}^{N}$, then, by the constant
rank theorem [19], the policy ${\tilde{\pi}_{T,\rho}^{N}}$ of player $N$ at
time $T$ is locally differentiable with respect to $(x,u^{1:N-1})$, and its
gradient over $(x,u^{1:N-1})$ is

(32) $\displaystyle\begin{aligned}
\nabla{\tilde{\pi}_{T,\rho}^{N}}=&-\big{[}\big{(}\nabla
K_{T,\rho}^{N}\big{)}^{+}\big{]}_{u_{T}^{N}}\cdot\nabla_{[x_{T},u_{T}^{1:N-1}]}K_{T,\rho}^{N}.\end{aligned}$

In the following subsection, we construct the KKT conditions of a player $i<N$
at stage $T$.

####  5.1.2 Players $i<N$ at the $T$-th stage

For player $i<N$, assuming that ${\mathbf{z}}_{T}^{i+1}$ has been defined and
$\nabla\tilde{\pi}_{T,\rho}^{i+1}$ has been computed, we first introduce
variables

(33)
${\mathbf{y}}_{T}^{i}:=[u_{T}^{i},\psi_{T}^{i},\lambda_{T}^{i},\mu_{T:T+1}^{i},\allowbreak\gamma_{T:T+1}^{i},s_{T:T+1}^{i}]\textrm{
and }{\mathbf{z}}_{T}^{i}:=[{\mathbf{y}}_{T}^{i},{\mathbf{z}}_{T}^{i+1}].$

The KKT conditions of player $i$ at time $T$ is

(34)
$0=K_{T,\rho}^{i}({\mathbf{z}}_{T}^{i}):=\begin{bmatrix}\hat{K}_{T,\rho}^{i}({\mathbf{y}}_{T}^{i})\\\
K_{T,\rho}^{i+1}({\mathbf{z}}_{T}^{i+1})\end{bmatrix},\
\hat{K}_{T,\rho}^{i}({\mathbf{y}}_{T}^{i}):=\begin{bmatrix}\nabla_{u_{T}^{i}}L_{T}^{i}\\\
\nabla_{x_{T+1}}L_{T+1}^{i}\\\ \nabla_{u_{T}^{j}}L_{T}^{i},\forall
j\in\mathbf{I}_{i+1}^{N}\\\ h_{T}^{i}(x_{T},u_{T})\\\ h_{T+1}^{i}(x_{T+1})\\\
g_{T}^{i}(x_{T},u_{T})-s_{T}^{i}\\\ g_{T+1}^{i}(x_{T+1})-s_{T+1}^{i}\\\
\gamma_{T:T+1}^{i}\odot s_{T:T+1}^{i}-\rho\mathbf{1}\end{bmatrix},$

where the definition of $L_{T}^{i}$ involves the policy
${\pi_{T,\rho}^{i+1}}$, as shown in (17). Building a first-order approximation
to $0=K_{T,\rho}^{i}({\mathbf{z}}_{T}^{i})$, we have

(35) $\nabla
K_{T,\rho}^{i}\cdot\Delta{\mathbf{z}}_{T}^{i}+\nabla_{[x_{T},u_{T}^{1:i-1}]}K_{T,\rho}^{i}\cdot\begin{bmatrix}\Delta
x_{T}\\\ \Delta
u_{T}^{1:i-1}\end{bmatrix}+K_{T,\rho}^{i}({\mathbf{z}}_{T}^{i})=0.$

However, a drawback of PDIP is that the policy ${\pi_{T,\rho}^{i+1}}$ is
nonlinear in state $x_{T}$ and prior players’ controls $u_{T}^{1:i}$, as shown
in a simplified problem in Appendix A.3. The computation of $\nabla
K_{T,\rho}^{i}$ involves the evaluation of
$\nabla(\nabla_{u_{T}^{i}}L_{T}^{i})$, which requires the computation of
$\nabla(\eta_{T}^{i}\nabla\pi_{T,\rho}^{i+1})=\nabla\eta_{T}^{i}\cdot\nabla\pi_{T,\rho}^{i+1}+\eta_{T}^{i}\cdot\nabla^{2}\pi_{T,\rho}^{i+1}$.
Furthermore, to evaluate $\nabla^{2}\pi_{T,\rho}^{i+1}$, we need the
computation of $\nabla^{3}\pi_{T,\rho}^{i+2}$. In other words, the
construction of $\nabla K_{T,\rho}^{i}$ needs the evaluation of
$\nabla^{2}\pi_{T,\rho}^{i+1}$, $\nabla^{3}\pi_{T,\rho}^{i+2}$, …, and
$\nabla^{N-i+1}\pi_{T,\rho}^{N}$. The evaluation of high-order policy
gradients is challenging in practice [24] because there is no closed-form
solution to the KKT equation $0=K_{T,\rho}^{i+1}({\mathbf{z}}_{T}^{i+1})$.

We prove in Appendix A.3 that the high-order policy gradients could decay to
zero as $\rho\to 0$, when the ground truth policy is piecewise linear and
differentiable around $x_{T}$. Motivated by this observation, we propose to
approximate the nonlinear policy $\pi_{T,\rho}^{i+1}$ by its first-order
approximation $\tilde{\pi}_{T,\rho}^{i+1}$ in (31). With this approximation,
we have
$\nabla(\eta_{T}^{i}\nabla\tilde{\pi}_{T,\rho}^{i+1})=\nabla\eta_{T}^{i}\cdot\nabla\tilde{\pi}_{T,\rho}^{i+1}$.
We refer to this policy $\tilde{\pi}_{T,\rho}^{i+1}$ as a _quasi-policy_.

In the remainder of this section, we will always approximate the ground truth
nonlinear policy by quasi-policy when we define the KKT conditions.

Solving equation (35), we can obtain $\Delta{\mathbf{z}}_{T}^{i}$ and
$\nabla{\tilde{\pi}_{T,\rho}^{i}}$ as in (29) and (32), respectively. However,
by construction, the dimension of $\Delta{\mathbf{z}}_{T}^{i}$ is higher than
$\Delta{\mathbf{z}}_{T}^{i+1}$. Therefore, it is more expensive to compute
$(\nabla K_{T,\rho}^{i})^{+}$ than $(\nabla K_{T,\rho}^{i+1})^{+}$, and it is
worthwhile to reduce the complexity of computing $\Delta{\mathbf{z}}_{T}^{i}$
by leveraging the computation that we have done for
$\Delta{\mathbf{z}}_{T}^{i+1}$ and $\nabla\tilde{\pi}_{T,\rho}^{i+1}$. To this
end, by exploiting the structure
${\mathbf{z}}_{T}^{i}=[{\mathbf{y}}_{T}^{i},{\mathbf{z}}_{T}^{i+1}]$ in (33),
we can rewrite (35) as,

(36) $\left\\{\begin{aligned}
&\nabla\hat{K}_{T,\rho}^{i}\cdot\Delta{\mathbf{y}}_{T}^{i}+\nabla_{[x_{T},u_{T}^{1:i-1}]}\hat{K}_{T,\rho}^{i}\cdot\begin{bmatrix}\Delta
x_{T}\\\ \Delta
u_{T}^{1:i-1}\end{bmatrix}+\hat{K}_{T,\rho}^{i}({\mathbf{y}}_{T}^{i})=0\\\
&\nabla
K_{T,\rho}^{i+1}\cdot\Delta{\mathbf{z}}_{T}^{i+1}+\nabla_{[x_{T},u_{T}^{1:i}]}K_{T,\rho}^{i+1}\cdot\begin{bmatrix}\Delta
x_{T}\\\ \Delta
u_{T}^{1:i}\end{bmatrix}+K_{T,\rho}^{i+1}({\mathbf{z}}_{T}^{i+1})=0\end{aligned}\right.$

Observe that we have solved the second equation of (36) in Section 5.1.1. What
remains to be solved is the first equation in (36). We solve it as follows,

(37) $\displaystyle\Delta{\mathbf{y}}_{T}^{i}=$
$\displaystyle\underbrace{-\big{(}\nabla\hat{K}_{T,\rho}^{i}\big{)}^{+}\cdot\Big{(}\nabla_{[x_{T},u_{T}^{1:i-1}]}\hat{K}_{T,\rho}^{i}\cdot\begin{bmatrix}\Delta
x_{T}\\\ \Delta
u_{T}^{1:i-1}\end{bmatrix}+\hat{K}_{T,\rho}^{i}({\mathbf{y}}_{T}^{i})\Big{)}}_{\hat{F}_{T}^{i}(\Delta
x_{T},\Delta u_{T}^{1:i-1})},$ $\displaystyle\Delta u_{T}^{i}=$
$\displaystyle-\big{[}\big{(}\nabla\hat{K}_{T,\rho}^{i}\big{)}^{+}\big{]}_{u_{T}^{i}}\cdot\Big{(}\nabla_{[x_{T},u_{T}^{1:i-1}]}\hat{K}_{T,\rho}^{i}\cdot\begin{bmatrix}\Delta
x_{T}\\\ \Delta
u_{T}^{1:i-1}\end{bmatrix}+\hat{K}_{T,\rho}^{i}({\mathbf{y}}_{T}^{i})\Big{)},$
$\displaystyle\nabla{\tilde{\pi}_{T,\rho}^{i}}=$
$\displaystyle-\big{[}\big{(}\nabla\hat{K}_{T,\rho}^{i}\big{)}^{+}\big{]}_{u_{T}^{i}}\cdot\nabla_{[x_{T},u_{T}^{1:i-1}]}\hat{K}_{T,\rho}^{i}.$

Combining (37) and (29), we have

(38)
$\displaystyle\Delta{\mathbf{z}}_{T}^{i}=\begin{bmatrix}\Delta{\mathbf{y}}_{T}^{i}\\\
\Delta{\mathbf{z}}_{T}^{i+1}\end{bmatrix}=\begin{bmatrix}\hat{F}_{T}^{i}(\Delta
x_{T},\Delta u_{T}^{1:i-1})\\\ F_{T}^{i+1}(\Delta x_{T},\Delta
u_{T}^{1:i})\end{bmatrix}.$

Since $\Delta u_{T}^{i}$ is also a function of $(\Delta x_{T},\Delta
u_{T}^{1:i-1})$, as shown in (37), we can represent (38) compactly as
$\Delta{\mathbf{z}}_{T}^{i}=F_{T}^{i}(\Delta x_{T},\Delta u_{T}^{1:i-1})$.

As such, given that the KKT conditions of player $(i+1)$ at time $T$ have been
constructed, we have finished the construction of the KKT conditions for
player $i$ at time $T$, and we introduced a computationally efficient way to
compute $\nabla{\tilde{\pi}_{T,\rho}^{i}}$. We can derive the KKT conditions
and quasi-policy gradient of player $i<N$ at time $T$, sequentially, from
$i=N-1$ to $i=1$.

####  5.1.3 Player $N$ at a stage $t<T$

At a stage $t<T$, assuming that we have constructed the KKT conditions
$0=K_{t+1,\rho}^{1}({\mathbf{z}}_{t+1}^{1})$, we are ready to derive the KKT
conditions for player $N$ at time $t$. We first introduce the variable
${\mathbf{z}}_{t}^{N}:=[{\mathbf{y}}_{t}^{N},{\mathbf{z}}_{t+1}^{1}]$, with
${\mathbf{y}}_{t}^{N}:=[u_{t}^{N},\eta_{t}^{N},\lambda_{t}^{N},\mu_{t}^{N},\gamma_{t}^{N},\allowbreak
s_{t}^{N},x_{t+1}]$. We construct the KKT conditions of player $N$ at time $t$
as follows,

(39)
$0=K_{t,\rho}^{N}({\mathbf{z}}_{t}^{N}):=\begin{bmatrix}\nabla_{u_{t}^{N}}L_{t}^{N}\\\
\nabla_{x_{t+1}}L_{t}^{N}\\\ \nabla_{u_{t+1}^{j}}L_{t}^{N},\forall
j\in\mathbf{I}_{1}^{N}\setminus\\{i\\}\\\ x_{t+1}-f_{t}(x_{t},u_{t})\\\
h_{t}^{N}(x_{t},u_{t})\\\ g_{t}^{N}(x_{t},u_{t})-s_{t}^{N}\\\
\gamma_{t}^{N}\odot s_{t}^{N}-\rho\mathbf{1}\\\
K_{t+1,\rho}^{1}({\mathbf{z}}_{t+1}^{1})\end{bmatrix}.$

Building a first-order approximation to the above equation, we can obtain
quasi-policy gradient $\nabla{\tilde{\pi}_{t,\rho}^{N}}$ as in (37) when it
exists.

####  5.1.4 Players $i<N$ at a stage $t<T$

Suppose that we have constructed the KKT conditions for the $(i+1)$-th player
at the $t$-th stage, we are then ready to construct the KKT conditions for
player $i$ at the $t$-th stage. We introduce the variable
${\mathbf{z}}_{t}^{i}:=[{\mathbf{y}}_{t}^{i},{\mathbf{z}}_{t}^{i+1}]$ with
${\mathbf{y}}_{t}^{i}:=[u_{t}^{i},\psi_{t}^{i},\eta_{t}^{i},\lambda_{t}^{i},\mu_{t}^{i},\gamma_{t}^{i},s_{t}^{i}]$.
The KKT conditions of player $i$ at time $t$ is

(40)
$0=K_{t,\rho}^{i}({\mathbf{z}}_{t}^{i}):=\begin{bmatrix}\nabla_{u_{t}^{i}}L_{t}^{i}\\\
\nabla_{x_{t+1}}L_{t}^{i}\\\ \nabla_{u_{t}^{j}}L_{t}^{i},\forall
j\in\mathbf{I}_{i+1}^{N}\\\ \nabla_{u_{t+1}^{j}}L_{t}^{i},\forall
j\in\mathbf{I}_{1}^{N}\setminus\\{i\\}\\\ h_{t}^{i}(x_{t},u_{t})\\\
g_{t}^{i}(x_{t},u_{t})-s_{t}^{i}\\\ \gamma_{t}^{i}\odot
s_{t}^{i}-\rho\mathbf{1}\\\
K_{t,\rho}^{i+1}({\mathbf{z}}_{t}^{i+1})\end{bmatrix}.$

Building a first approximation to the above equation, we can obtain the quasi-
policy gradient $\nabla{\tilde{\pi}_{t,\rho}^{i}}$ as in (37), when it exists.

We observe that, by construction, the KKT conditions in (19) is equivalent to
$0=K_{0,\rho}^{1}({\mathbf{z}}_{0}^{1})$. To simplify notation, we define

(41) ${\mathbf{z}}:={\mathbf{z}}_{0}^{1},\ \
K_{\rho}({\mathbf{z}}):=K_{0,\rho}^{1}({\mathbf{z}}).$

The KKT conditions (19) can be represented compactly as
$0=K_{\rho}({\mathbf{z}})$. To more effectively illustrate the construction
process of KKT conditions described above, we have included detailed examples
of the KKT conditions for two-player LQ games in Appendix B as a reference.

Algorithm 1 Local Feedback Stackelberg Equilibrium via PDIP

0: $\\{f_{t}\\}_{t=0}^{T}$,
$\\{\ell_{t}^{i},h_{t}^{i},g_{t}^{i}\\}_{t=0,i=1}^{T+1,N}$, initial homotopy
parameter $\rho$, contraction rate $\sigma\in(0,1)$, parameters
$\beta\in(0,1)$ and $\kappa\in(0,1)$, tolerance $\epsilon$, initial solution
$\mathbf{z}_{\rho}^{(0)}:=[{\mathbf{x}}_{\rho}^{(0)},{\mathbf{u}}_{\rho}^{(0)},{\boldsymbol{\lambda}}_{\rho}^{(0)},{\boldsymbol{\mu}}_{\rho}^{(0)},{\boldsymbol{\gamma}}_{\rho}^{(0)},{\boldsymbol{\eta}}_{\rho}^{(0)},{\boldsymbol{\psi}}_{\rho}^{(0)},{\mathbf{s}}_{\rho}^{(0)}]$
with ${\mathbf{s}}_{\rho}^{(0)}>0$ and ${\boldsymbol{\gamma}}_{\rho}^{(0)}>0$

0: policies $\\{{\tilde{\pi}_{t,\rho}^{i}}\\}_{t=0,i=1}^{T,N}$, converged
solution $\mathbf{z}_{\rho}$

1: for $k^{\mathrm{out}}=1,2,\dots,k_{\mathrm{max}}^{\mathrm{out}}$ do

2: while the merit function
$\|K_{\rho}(\mathbf{z}_{\rho}^{(k)})\|_{2}>\epsilon$ do

3: construct the first-order approximation of the KKT conditions $0=\nabla
K_{\rho}\cdot\Delta\mathbf{z}_{\rho}+K_{\rho}(\mathbf{z}_{\rho}^{(k)})$

4: $\Delta\mathbf{z}_{\rho}\leftarrow-\big{(}\nabla K_{\rho}\big{)}^{+}\cdot
K_{\rho}(\mathbf{z}_{\rho}^{(k)})$

5: initialize the step size for line search, $\alpha\leftarrow 1$

6: while
$\|K_{\rho}(\mathbf{z}_{\rho}^{(k)}+\alpha\Delta\mathbf{z}_{\rho})\|_{2}>\kappa\|K_{\rho}(\mathbf{z}_{\rho}^{(k)})\|_{2}$
or
$\hat{{\mathbf{z}}}_{\rho}:=(\mathbf{z}_{\rho}^{(k)}+\alpha\Delta\mathbf{z}_{\rho})$
has a non-positive element in its sub-vector
$[\hat{{\mathbf{s}}}_{\rho},\hat{{\boldsymbol{\gamma}}}_{\rho}]$ do

7: $\alpha\leftarrow\beta\cdot\alpha$

8: end while

9: if $\alpha==0$ then

10: claim failure to find a feedback Stackelberg equilibrium

11: end if

12:
$\mathbf{z}_{\rho}^{(k+1)}\leftarrow\mathbf{z}_{\rho}^{(k)}+\alpha\Delta\mathbf{z}_{\rho}$

13: end while

14: $\rho\leftarrow\sigma\cdot\rho$

15: end for

16: construct $\\{{\tilde{\pi}_{t,\rho}^{i}}\\}_{t=0,i=1}^{T,N}$ as in (31)
and record $\mathbf{z}_{\rho}\leftarrow\mathbf{z}_{\rho}^{(k)}$.

17: return $\\{{\tilde{\pi}_{t,\rho}^{i}}\\}_{t=0,i=1}^{T,N}$,
$\mathbf{z}_{\rho}$

###  5.2 Primal-Dual Interior Point Algorithm and Convergence Analysis in
Constrained LQ Games

In this subsection, we propose the application of Newton’s method to compute
${\mathbf{z}}^{*}=[{\mathbf{x}}^{*},{\mathbf{u}}^{*},{\boldsymbol{\lambda}}^{*},{\boldsymbol{\mu}}^{*},{\boldsymbol{\gamma}}^{*},{\boldsymbol{\eta}}^{*},\allowbreak{\boldsymbol{\psi}}^{*},{\mathbf{s}}^{*}]$,
ensuring $0=K_{\rho}({\mathbf{z}}^{*})$. This approach guarantees that the
associated quasi-policies form a set of local FSE policies, provided that we
anneal the parameter $\rho$ to zero and the sufficient condition in Theorem
4.5 is satisfied. We formalize our method in Algorithm 1.

In Algorithm 1, we gradually decay the homotopy parameter $\rho$ to zero such
that $\lim_{\rho\to 0}\mathbf{z}_{\rho}$ recovers an FSE solution. For each
$\rho$, at the $k$-th iteration, we first construct the KKT conditions
$0=K_{\rho}({\mathbf{z}})$ along the trajectory $\mathbf{z}_{\rho}^{(k)}$. We
compute the Newton update direction $\Delta{\mathbf{z}}:=-(\nabla
K_{\rho})^{+}\cdot K_{\rho}(\mathbf{z}_{\rho}^{(k)})$. Since we aim at finding
a solution ${\mathbf{z}}^{*}$ to $0=K_{\rho}({\mathbf{z}}^{*})$, a natural
choice of merit function is $\|K_{\rho}({\mathbf{z}})\|_{2}$. Given this
choice of the merit function, we perform a line search to determine a step
size $\alpha$ and update
$\mathbf{z}_{\rho}^{(k+1)}=\mathbf{z}_{\rho}^{(k)}+\alpha\Delta{\mathbf{z}}$
until convergence. The converged solution is denoted as $\mathbf{z}_{\rho}$.
Subsequently, we steadily decay $\rho$ and repeat these Newton update steps.
We characterize how the magnitude of the KKT residual value
$\|K_{\rho}({\mathbf{z}})\|_{2}$ influences the convergence rate of Algorithm
1 when solving LQ games in the following result.

######  Theorem 5.1.

Under Assumption 3, let
${\mathcal{F}}_{z}:=\\{{\mathbf{z}}=[{\mathbf{x}},{\mathbf{u}},{\boldsymbol{\lambda}},{\boldsymbol{\mu}},{\boldsymbol{\gamma}},{\boldsymbol{\eta}},{\boldsymbol{\psi}},{\mathbf{s}}]:{\boldsymbol{\gamma}}\geq
0,{\mathbf{s}}\geq 0\\}$ be the solution set. We denote by $\nabla
K_{\rho}({\mathbf{z}})$ and ${\nabla^{*}}K_{\rho}({\mathbf{z}})$ the Jacobians
of the KKT conditions with and without considering quasi-policy gradients,
respectively. Suppose that $\nabla K_{\rho}({\mathbf{z}})$ is invertible and
there exist constants $D$ and $C$ such that

(42a) $\displaystyle\|(\nabla K_{\rho}({\mathbf{z}}))^{-1}\|_{2}\leq D,$
$\displaystyle\forall
i\in\mathbf{I}_{1}^{N},\forall{\mathbf{z}}\in{\mathcal{F}}_{z},$ (42b)
$\displaystyle\|{\nabla^{*}}K_{\rho}({\mathbf{z}})-{\nabla^{*}}K_{\rho}(\tilde{{\mathbf{z}}})\|_{2}\leq
C\|{\mathbf{z}}-\tilde{{\mathbf{z}}}\|_{2},$ $\displaystyle\forall
i\in\mathbf{I}_{1}^{N},\forall{\mathbf{z}},\tilde{{\mathbf{z}}}\in{\mathcal{F}}_{z}.\vspace{-0.4em}$

Let ${\hat{\alpha}}\in[0,1]$ be the maximum feasible stepsize for all
${\mathbf{z}}\in\mathcal{F}_{\mathbf{z}}$, i.e.,
${\hat{\alpha}}:=\max\\{\alpha\in[0,1]:{\mathbf{z}},{\mathbf{z}}+\alpha\Delta{\mathbf{z}}\in{\mathcal{F}}_{z}\\}$.
Moreover, suppose $\|{\nabla^{*}}K_{\rho}({\mathbf{z}})-\nabla
K_{\rho}({\mathbf{z}})\|_{2}\leq\delta$ for all
${\mathbf{z}}\in\mathcal{F}_{\mathbf{z}}$ and $D\cdot\delta<1$. Then, for all
${\mathbf{z}}\in\mathcal{F}_{z}$, there exists $\alpha\in[0,{\hat{\alpha}}]$
such that

  1. 1.

if $\|K_{\rho}({\mathbf{z}})\|_{2}>\frac{1-D\delta}{D^{2}C{\hat{\alpha}}}$,
then
$\|K_{\rho}({\mathbf{z}}+\alpha\Delta{\mathbf{z}})\|_{2}\leq\|K_{\rho}({\mathbf{z}})\|_{2}-\frac{(1-D\delta)^{2}}{2D^{2}C}$;

  2. 2.

if $\|K_{\rho}({\mathbf{z}})\|_{2}\leq\frac{1-D\delta}{D^{2}C{\hat{\alpha}}}$,
then
$\|K_{\rho}({\mathbf{z}}+\alpha\Delta{\mathbf{z}})\|_{2}\leq\big{(}1-\frac{1}{2}{\hat{\alpha}}(1-D\delta)\big{)}\cdot\|K_{\rho}({\mathbf{z}})\|_{2}$,
and we have exponential convergence.

######  Proof 5.2.

The proof can be found in the Appendix.

Theorem 5.1 suggests that, under certain conditions, the merit function
$\|K_{\rho}({\mathbf{z}})\|_{2}$ decays to zero exponentially fast, and
Algorithm 1 converges to a solution satisfying the KKT conditions considering
the quasi-policy gradients. The above analysis can be considered as an
extension of the classical PDIP convergence proof in [9] to constrained
feedback Stackelberg games where we consider feedback interaction constraints
$0=u_{t}^{i}-\tilde{\pi}_{t,\rho}^{i}(x_{t},u_{t}^{1:i-1})$ and the quasi-
policy gradients. The condition (42a) equates to establishing a lower bound
for the smallest nonzero singular value of $\nabla K_{\rho}({\mathbf{z}})$.
Practically, this can be achieved by adding a minor cost regularization term
to the KKT conditions [11]. Moreover, the constant $C$ in (42b) depends on the
maximum singular values of the Hessians of costs, the Jacobian of constraints,
and linear dynamics, which are all constant matricies in LQ games and can
therefore be upper bounded.

Given a $\rho>0$, a converged solution ${\mathbf{z}}_{\rho}$ renders
$K_{\rho}({\mathbf{z}}_{\rho})=0$. Note that the KKT conditions
$0=K_{\rho}({\mathbf{z}})$ reduce to the one in Theorem 4.3 when $\rho$ decays
to zero. As $\rho$ approaches zero, the solution ${\mathbf{z}}_{\rho}$, when
converged, recovers a solution to the KKT conditions in Theorem 4.3. When the
sufficient conditions in Theorem 4.5 are also satisfied, the quasi-policies
$\\{{\tilde{\pi}_{t,\rho}^{i}}\\}_{t=0,i=1}^{T,N}$ constitute a set of local
FSE policies.

##  6 From LQ Games to Nonlinear Games

In this section, we extend our solution for LQ games to feedback Stackelberg
games with nonlinear dynamics. Without loss of generality, each player could
have non-quadratic costs. Coupled nonlinear equality and inequality
constraints could also exist among players.

###  6.1 Iteratively Approximating Nonlinear Games via LQ Games by Aligning
Their KKT Conditions

In this subsection, we introduce a procedure which iteratively approximates
the constrained nonlinear games using constrained LQ games, and computes
approximate local feedback Stackelberg policies for the nonlinear games. These
LQ game approximations are designed to ensure that the first-order
approximations of their KKT conditions, expressed as $0=\nabla
K_{\rho}({\mathbf{z}})\cdot\Delta{\mathbf{z}}+K_{\rho}({\mathbf{z}})$, align
with those of the original nonlinear games, specifically considering the
inclusion of quasi-policies. Our approach differs from the existing iterative
LQ game approximation techniques [21, 35] for FSE policies, which linearize
the dynamics and quadraticize only the costs. In contrast, our method
linearizes the dynamics but quadraticizes the Lagrangian. This enables us to
utilize the convergence results for LQ games, as discussed in the previous
section, to analyze the convergence properties of our method in nonlinear
games. Consequently, our work provides the first iterative LQ game
approximation approach that has provable convergence guarantees for
constrained nonlinear feedback Stackelberg games.

In what follows, we introduce local LQ game approximations of the original
nonlinear game. Let ${\mathbf{z}}$ be a solution in the set $\mathcal{F}_{z}$.
We first define the following linear approximation of the dynamics and
constraints around ${\mathbf{z}}$, for all
$t\in\mathbf{I}_{0}^{T},i\in\mathbf{I}_{1}^{N}$,

(43) $\displaystyle A_{t}:=\nabla_{x}f_{t}(x_{t},u_{t}),$ $\displaystyle
B_{t}^{i}:=\nabla_{u_{t}^{i}}f_{t}(x_{t},u_{t}),$ $\displaystyle
c_{t}:=f_{t}(x_{t},u_{t})-x_{t+1},$ $\displaystyle
H_{x_{t}}^{i}:=\nabla_{x}h_{t}^{i},\
H^{i}_{u_{t}^{j}}:=\nabla_{u_{t}^{j}}h_{t}^{i},$ $\displaystyle
G_{x_{t}}^{i}:=\nabla_{x}g_{t}^{i},\
G^{i}_{u_{t}^{j}}:=\nabla_{u_{t}^{j}}g_{t}^{i},$ $\displaystyle\forall
j\in\mathbf{I}_{1}^{N},$
$\displaystyle\bar{h}_{t}^{i}:=h_{t}^{i}(x_{t},u_{t}),$
$\displaystyle\bar{g}_{t}^{i}:=g_{t}^{i}(x_{t},u_{t}),$ $\displaystyle
H_{x_{T+1}}^{i}:=\nabla_{x}h_{T+1}^{i},$ $\displaystyle
G_{x_{T+1}}^{i}:=\nabla_{x}g_{T+1}^{i},$
$\displaystyle\bar{h}_{T+1}^{i}:=h_{T+1}^{i}(x_{T+1}),$
$\displaystyle\bar{g}_{T+1}^{i}:=g_{T+1}^{i}(x_{T+1}).$

For each $i\in\mathbf{I}_{1}^{N}$ and $t\in\mathbf{I}_{0}^{T}$, we represent
the second order terms and cost-related terms in the Lagrangian
$\mathcal{L}_{t}^{i}$ as quadratic costs (22), with parameters defined as
follows,

(44) $\displaystyle Q_{t}^{i}:=$
$\displaystyle\nabla_{xx}^{2}\ell_{t}^{i}+(\nabla^{2}_{xx}f_{t})^{\top}\lambda_{t}^{i}-(\nabla_{xx}^{2}h_{t}^{i})^{\top}\mu_{t}^{i}-(\nabla_{xx}^{2}g_{t}^{i})^{\top}\gamma_{t}^{i},$
$\displaystyle S_{t}^{i}:=$
$\displaystyle\nabla_{ux}^{2}\ell_{t}^{i}+(\nabla_{ux}^{2}f_{t})^{\top}\lambda_{t}^{i}-(\nabla_{ux}^{2}h_{t}^{i})^{\top}\mu_{t}^{i}-(\nabla_{ux}^{2}g_{t}^{i})^{\top}\gamma_{t}^{i},$
$\displaystyle R_{t}^{i}:=$
$\displaystyle\nabla_{uu}^{2}\ell_{t}^{i}+(\nabla_{uu}^{2}f_{t})^{\top}\lambda_{t}^{i}-(\nabla_{uu}^{2}h_{t}^{i})^{\top}\mu_{t}^{i}-(\nabla_{uu}^{2}g_{t}^{i})^{\top}\gamma_{t}^{i},$
$\displaystyle Q_{T+1}^{i}:=$
$\displaystyle\nabla_{xx}^{2}\ell_{T+1}^{i}-(\nabla_{xx}^{2}h_{T+1}^{i})^{\top}\mu_{T+1}^{i}-(\nabla_{xx}^{2}g_{T+1}^{i})^{\top}\gamma_{T+1}^{i},$
$\displaystyle q_{t}^{i}:=$ $\displaystyle\nabla_{x}\ell_{t}^{i},\hskip
28.45274ptr_{t}^{i}:=\nabla_{u}\ell_{t}^{i},\hskip
28.45274ptq_{T+1}^{i}:=\nabla_{x}\ell_{T+1}^{i}.$

We can modify Algorithm 1 to address nonlinear games by applying an LQ game
approximation around the solution $\mathbf{z}_{\rho}^{(k)}$ in step 3 of
Algorithm 1 and formulate the resulting approximate KKT conditions
$0=K_{\rho}(\mathbf{z}_{\rho}^{(k)})$ defined with terms in (43) and (44).
Furthermore, this LQ game approximation is reiterated around
$\mathbf{z}_{\rho}^{(k)}+\alpha\Delta\mathbf{z}_{\rho}$ in step 6, when we
evaluate the merit function
$\|K_{\rho}(\mathbf{z}_{\rho}^{(k)}+\alpha\Delta\mathbf{z}_{\rho})\|_{2}$
during line search.

###  6.2 Quasi-Policies Approximation Error and Exponential Convergence
Analysis in Nonlinear Games

In the above solution procedure, we approximate the ground truth nonlinear
policies of nonlinear games by quasi-policies. However, different from LQ
games, the ground truth feedback Stackelberg policies for nonlinear games
could have nonzero high-order policy gradients. Thus, it is worthwhile to
characterize the error caused by the quasi-policy gradients. Essentially,
there are two error sources. The first type of error is due to the fact that
we have neglected high-order policy gradients when evaluating the KKT Jacobian
$\nabla K_{t,\rho}^{i}({\mathbf{z}})$, and the second form of error is how
these changes propagate into the expression of KKT conditions
$0=K_{t,\rho}^{i}({\mathbf{z}})$ for earlier players and stages. Suppose those
two error sources could be upper bounded; then, we can characterize their
impact on the policy gradients error in the following proposition.

######  Proposition 6.1.

Under Assumption 3, let ${\mathbf{z}}$ and $\tilde{\mathbf{z}}$ be two
elements in the solution set $\mathcal{F}_{z}$. We denote by
$\\{{\pi_{t,\rho}^{i}}\\}_{t=0,i=1}^{T,N}$ a set of policies around
${\mathbf{z}}$ and $\\{{\tilde{\pi}_{t,\rho}^{i}}\\}_{t=0,i=1}^{T,N}$ a set of
quasi-policies around $\tilde{\mathbf{z}}$, respectively. We denote by
$\\{K_{t,\rho}^{i}({\mathbf{z}})\\}_{t=0,i=1}^{T,N}$ and
$\\{K_{t,\rho}^{i*}({\mathbf{z}})\\}_{t=0,i=1}^{T,N}$ the KKT conditions with
and without quasi-policies, respectively. Let $i\leq N$ and $t\leq T$. Suppose
that the Jacobian matrices $\nabla K_{t,\rho}^{i}(\tilde{\mathbf{z}})$,
$\nabla K_{t,\rho}^{i*}(\tilde{\mathbf{z}})$ and $\nabla
K_{t,\rho}^{i*}({\mathbf{z}})$ are invertible. Let
$\epsilon_{{\mathbf{z}},\tilde{\mathbf{z}}}>0$ be an upper error bound such
that

(45) $\displaystyle\max\Big{\\{}$ $\displaystyle\|\nabla
K_{t,\rho}^{i}(\tilde{\mathbf{z}})-\nabla
K_{t,\rho}^{i*}(\tilde{\mathbf{z}})\|_{2},$ $\displaystyle\|\nabla
K_{t,\rho}^{i*}(\tilde{\mathbf{z}})-\nabla
K_{t,\rho}^{i*}({\mathbf{z}})\|_{2},$
$\displaystyle\|K_{t,\rho}^{i}(\tilde{\mathbf{z}})-K_{t,\rho}^{i}({\mathbf{z}})\|_{2},$
$\displaystyle\|K_{t,\rho}^{i}({\mathbf{z}})-K_{t,\rho}^{i*}({\mathbf{z}})\|_{2}\Big{\\}}\leq\epsilon_{{\mathbf{z}},\tilde{\mathbf{z}}}.$

Then, the error between the quasi-policy gradient and the policy gradient can
be bounded as follows,

(46) $\displaystyle\|\nabla\tilde{\pi}_{t,\rho}^{i}$
$\displaystyle(\tilde{\mathbf{z}})-\nabla\pi_{t,\rho}^{i}({\mathbf{z}})\|_{2}\leq\epsilon_{{\mathbf{z}},\tilde{\mathbf{z}}}\cdot\Big{(}2\|\nabla
K_{t,\rho}^{i*}({\mathbf{z}})^{-1}\|_{2}+$ $\displaystyle\big{(}\|\nabla
K_{t,\rho}^{i}(\tilde{\mathbf{z}})^{-1}\|_{2}+\|\nabla
K_{t,\rho}^{i*}({\mathbf{z}})^{-1}\|_{2}\big{)}\cdot\|\nabla
K_{t,\rho}^{i*}(\tilde{\mathbf{z}})^{-1}\|_{2}\|K_{t,\rho}^{i}(\tilde{\mathbf{z}})\|_{2}\Big{)}.$

######  Proof 6.2.

The proof can be found in Appendix.

Proposition 6.1 suggests that the error introduced by the quasi-policy
gradients is proportional to $\epsilon_{{\mathbf{z}},\tilde{\mathbf{z}}}$, as
described in (46). However, it is challenging to obtain an analytical bound
$\epsilon_{{\mathbf{z}},\tilde{\mathbf{z}}}$ because the evaluation of
$K_{t,\rho}^{i*}({\mathbf{z}})$ and $\nabla K_{t,\rho}^{i*}({\mathbf{z}})$
requires computing the high-order policy gradients. The above analysis only
provides a partial analysis for the policy gradient error introduced by the
quasi-policy gradients. In principle, it is possible that the quasi-policy
gradients could lead to a different feedback Stackelberg policy from the
ground truth feedback Stackelberg policy. However, it is intractable to
compute high-order policy gradients when we have a long horizon game. We
believe that the local feedback Stackelberg quasi-policy is the closest
computationally tractable approximation possible when we consider the first-
order policy approximation techniques.

Furthermore, we can leverage the sufficient condition of local FSE policies
and the convergence analysis in Theorem 5.1 to show that we will converge to a
local FSE policy of nonlinear games under certain conditions on the iterative
LQ approximations.

######  Theorem 6.3 (Exponential Convergence in Nonlinear Games).

Suppose that there exist constants $(D,C,\delta,{\hat{\alpha}})$, as defined
in Theorem 5.1, such that at each iteration $k$ of Algorithm 1, the
approximate LQ game defined in (43) and (44) satisfies the conditions of
Theorem 5.1. Then, for each $\rho>0$ and a sufficiently large $k$,
$\mathbf{z}_{\rho}^{(k)}$ converges exponentially fast to a solution
$\mathbf{z}_{\rho}$, which renders $\|K_{\rho}(\mathbf{z}_{\rho})\|_{2}=0$.
Moreover, if the limit $\hat{{\mathbf{z}}}:=\lim_{\rho\to 0}\mathbf{z}_{\rho}$
exists and Theorem 4.5, which provides a sufficient condition for local FSE
policies, holds true at $\mathbf{z}_{\rho}$ for all $\rho>0$, then quasi-
policies $\lim_{\rho\to 0}\\{{\tilde{\pi}_{t,\rho}^{i}}\\}_{t=0,i=1}^{T,N}$
are local FSE policies.

######  Proof 6.4.

The proof can be found in the Appendix.

##  7 Experiments

In this section, we consider a two-player feedback Stackelberg game modeling
highway driving111The source code is available at
https://github.com/jamesjingqili/FeedbackStackelbergGames.jl.git, where two
highway lanes merge into one and the planning horizon $T=20$. We associate
with each player a 4-dimensional state vector
$x_{t}^{i}=[p_{x,t}^{i},p_{y,t}^{i},v_{t}^{i},\theta_{t}^{i}]$, where
$(p_{x,t}^{i},p_{y,t}^{i})$ represents the $(x,y)$ coordinate, $v_{t}^{i}$
denotes the velocity, and $\theta_{t}^{i}$ encodes the heading angle of player
$i$ at time $t$. The joint state vector of the two players is denoted as
$x_{t}=[x_{t}^{1},x_{t}^{2}]$. Both players have nonlinear unicycle dynamics,
$\forall t\in\mathbf{I}_{0}^{T}$, $\forall i\in\\{1,2\\}$,

(47) $\displaystyle p_{x,t+1}^{i}=p_{x,t}^{i}+\Delta t\cdot
v_{t}^{i}\sin(\theta_{t}^{i}),$ $\displaystyle
p_{y,t+1}^{i}=p_{y,t}^{i}+\Delta t\cdot v_{t}^{i}\cos(\theta_{t}^{i}),$
$\displaystyle v_{t+1}^{i}=v_{t}^{i}+\Delta t\cdot a_{t}^{i},$
$\displaystyle\theta_{t+1}^{i}=\theta_{t}^{i}+\Delta t\cdot\omega_{t}^{i}.$

We consider the following cost functions, for all $t\in\mathbf{I}_{0}^{T}$,

(48)
$\ell_{t}^{1}(x_{t},u_{t})=10(p_{x,t}^{1}-0.4)^{2}+6(v_{t}^{1}-v_{t}^{2})^{2}+2\|u_{t}^{1}\|_{2}^{2},\ell_{t}^{2}(x_{t},u_{t})=\|\theta_{t}^{2}\|_{2}^{4}+2\|u_{t}^{2}\|_{2}^{2},$

and the terminal costs
$\ell_{T+1}^{1}(x_{T+1})=10(p_{x,T+1}^{1}-0.4)^{2}+6(v_{t}^{1}-v_{t}^{2})^{2}$
and $\ell_{T+1}^{2}(x_{T+1})=\|\theta^{2}_{T+1}\|_{2}^{4}$. Note that we
include a fourth-order cost term in player 2’s cost at each stage to model its
preference of small heading angle. We consider the following (nonconvex)
constraints encoding collision avoidance, driving on the road, and control
limits,

(49)
$\displaystyle\sqrt{\|p_{x,t}^{1}-p_{x,t}^{2}\|_{2}^{2}+\|p_{y,t}^{1}-p_{y,t}^{2}\|^{2}_{2}}-d_{\mathrm{safe}}\geq
0,$ $\displaystyle t\in\mathbf{I}_{0}^{T+1},$ $\displaystyle
p_{x,t}^{i}-p_{l}\geq 0,\hskip 22.76228ptp_{r}(p_{y,t}^{i},p_{x,t}^{i})\geq
0,\hskip 22.76228pt\|u_{t}\|_{\infty}\leq u_{\max},$ $\displaystyle
t\in\mathbf{I}_{0}^{T+1},i\in\\{1,2\\},$

where we define $p_{l}\in\mathbb{R}$ to be the left road boundary and denote
by $p_{r}(p_{x,t}^{i},p_{y,t}^{i})$ the distance between player $i$ and the
right road boundary curve. We also consider the following equality constraints
at the terminal time

(50) $\displaystyle v_{T+1}^{1}-v_{T+1}^{2}=0,\ \theta_{T+1}^{1}=0,$

where the two players aim to reach a consensus on their speeds, with player 1
maintaining its heading angle pointing forwards.

(a) $\rho=1$, $k=0$.

(b) $\rho=1$, $k=3$.

(c) $\rho=1$, $k=6$.

(d) $\rho=2^{-10}$, $k=10$.

Figure 1: Tolerance of an infeasible trajectory initialization and the
converged trajectories of two players. In Figure 1(a), we plot the initial
state trajectories of two players, where player 1’s trajectory is infeasible
because it violates the road boundary constraint. When $\rho=1$, we plot the
state trajectories in the third and the sixth iterations in Figure 1(b) and
Figure 1(c), respectively. They become feasible at the sixth iteration. In
Figure 1(d), we plot the converged solution, with $\rho=2^{-10}$.

(e) $\rho=1$.

(f) $\rho=2^{-1}$.

(g) $\rho=2^{-5}$.

(h) $\rho=2^{-10}$.

Figure 2: Convergence under different values of the homotopy parameter $\rho$
for 10 perturbed initial trajectories. The solid curve and the shaded area
denote the mean and the standard deviation, respectively.

The nominal initial states of two players are specified as
$x_{0}^{1}=[0.9,1.2,3.5,0.0]$ and $x_{0}^{2}=[0.5,0.6,3.8,0.0]$, respectively.
We randomly sample 10 initial states around $x_{0}=[x_{0}^{1},x_{0}^{2}]$
under a uniform distribution within the range of $-0.1$ to $0.1$. From each
sampled $\hat{x}_{0}$, we obtain an initial state trajectory
${\mathbf{x}}^{(0)}$ by simulating the nonlinear dynamics (47) with the
initial controls ${\mathbf{u}}^{(0)}=\mathbf{0}$. Set the initial slack
variables for the inequality constraints as ${\mathbf{s}}^{(0)}=\mathbf{1}$,
along with the corresponding Lagrange multipliers
${\boldsymbol{\gamma}}^{(0)}=\mathbf{1}$. We set all other Lagrange
multipliers
$\\{{\boldsymbol{\lambda}}^{(0)},{\boldsymbol{\mu}}^{(0)},{\boldsymbol{\eta}}^{(0)},{\boldsymbol{\psi}}^{(0)}\\}$
to zeros. Consequently, we have constructed an initial solution
${\mathbf{z}}^{(0)}=[{\mathbf{x}}^{(0)},{\mathbf{u}}^{(0)},{\boldsymbol{\lambda}}^{(0)},{\boldsymbol{\gamma}}^{(0)}{\boldsymbol{\mu}}^{(0)},{\boldsymbol{\eta}}^{(0)},{\boldsymbol{\psi}}^{(0)},{\mathbf{s}}^{(0)}]$.
We repeat this initialization trajectory defining process for different
sampled initial states $\hat{x}_{0}.$

As shown in Figure 1, although the right road boundary constraint is initially
violated by initialization ${\mathbf{z}}^{(0)}$, as the algorithm progresses,
subsequent iterates ${\mathbf{z}}^{(k)}$ become feasible. For each sampled
initial state $\hat{x}_{0}$, we employ Algorithm 1 with iterative LQ game
approximations to compute a local feedback Stackelberg equilibrium trajectory
and the associated local linear policies. The average performance is depicted
in Figure 2. For each $\rho$, the merit function value decreases as the
iterations continue. Furthermore, since the cost functions are strongly convex
with respect to each player’s controls and the Jacobian of the dynamics has
full rank, by Theorem 4.5, the state trajectory converges to an approximate
local feedback Stackelberg equilibrium as $\rho\to 0$.

##  8 Conclusions

In this paper, we considered general-sum feedback Stackelberg dynamic games
with coupled constraints among $N$ players. We proposed a primal-dual interior
point method to compute an approximate feedback Stackelberg equilibrium and
the associated policies for all players. To the best of the authors’
knowledge, this represents the first attempt to compute approximate local
feedback Stackelberg equilibria in both LQ games and nonlinear games under
general coupled equality and inequality constraints, within continuous state
and action spaces. We theoretically characterized the approximation error and
the exponential convergence of our algorithm. Numerical experiments suggest
that the proposed algorithm can tolerate infeasible initializations and
efficiently converge to a feasible equilibrium solution. Future research
should investigate the potential benefits of higher-order policy gradient
approximations. Additionally, extending our approach to stochastic feedback
dynamic games is also a promising future direction.

## Acknowledgments

We would like to thank Professor Lillian Ratliff and Professor Forrest Laine
for valuable discussions and comments. We used ChatGPT-4 [38] to check the
grammar in the Introduction and Related Works sections.

##  Appendix A Supplementary results

######  Proof A.1 (Proof of Theorem 4.1).

At the terminal time $t=T$, we observe that, for each player
$i\in\mathbf{I}_{1}^{N}$, the equation (15) can be rewritten as

$\displaystyle\tilde{u}_{T}^{i}\in\arg_{u_{T}^{i}}\min_{u_{T}^{i}}\Big{\\{}\min_{\begin{subarray}{c}u_{T}^{i+1:N}\\\
x_{T+1}\end{subarray}}$
$\displaystyle\ell_{T}^{i}(x_{T},u_{T})+V_{T+1}^{i}(x_{T+1})\Big{\\}}$ s.t.
$\displaystyle 0=u_{T}^{j}-\pi_{T}^{j}(x_{T},u_{T}^{1:j-1}),\
0=x_{T+1}-f_{T}(x_{T},u_{T})$ $\displaystyle j\in\mathbf{I}_{i+1}^{N}$
$\displaystyle 0=h_{T}^{i}(x_{T},u_{T}),\ 0\leq g_{T}^{i}(x_{T},u_{T})$
$\displaystyle 0=h_{T+1}^{i}(x_{T+1}),\ 0\leq g_{T+1}^{i}(x_{T+1})$

which implies
$\tilde{u}_{T}^{i}\in\arg_{u_{T}^{i}}\min_{u_{T}^{i}}Z_{T}^{i}(x_{T},u_{T}^{1:i-1},u_{T}^{i})$.
Moreover, for all $t\in\mathbf{I}_{0}^{T-1}$ and $i\in\mathbf{I}_{1}^{N}$, we
observe

$\displaystyle\tilde{u}_{t}^{i}\in\arg_{u_{t}^{i}}\min_{u_{t}^{i}}\Big{\\{}\min_{\begin{subarray}{c}u_{t}^{i+1:N}\\\
u_{t+1:T}^{1:N}\\\ x_{t+1:T+1}\end{subarray}}$
$\displaystyle\sum_{\tau=t}^{T}\ell_{\tau}^{i}(x_{\tau},u_{\tau})+\ell_{T+1}^{i}(x_{T+1})\Big{\\}}$
s.t. $\displaystyle 0=u_{t}^{j}-\pi_{t}^{j}(x_{t},u_{t}^{1:j-1})$
$\displaystyle j\in\mathbf{I}_{i+1}^{N}$ $\displaystyle
0=x_{\tau+1}-f_{\tau}(x_{\tau},u_{\tau})$
$\displaystyle\tau\in\mathbf{I}_{t}^{T}$ $\displaystyle
0=u_{\tau}^{j}-\pi_{\tau}^{j}(x_{\tau},u_{\tau}^{1:j-1})$
$\displaystyle\tau\in\mathbf{I}_{t+1}^{T},j\in\mathbf{I}_{1}^{N}\setminus\\{i\\}$
$\displaystyle 0=h_{\tau}^{i}(x_{\tau},u_{\tau}),\ 0\leq
g_{\tau}^{i}(x_{\tau},u_{\tau})$ $\displaystyle\tau\in\mathbf{I}_{t}^{T}$
$\displaystyle 0=h_{T+1}^{i}(x_{T+1}),\ 0\leq g_{T+1}^{i}(x_{T+1})$

The above can be further rewritten as

$\displaystyle\tilde{u}_{t}^{i}\in\arg_{u_{t}^{i}}\min_{u_{t}^{i}}\Big{\\{}\min_{\begin{subarray}{c}u_{t}^{i+1:N}\\\
x_{t+1}\end{subarray}}$
$\displaystyle\ell_{t}^{i}(x_{t},u_{t})+V_{t+1}^{i}(x_{t+1})\Big{\\}}$ s.t.
$\displaystyle 0=u_{t}^{j}-\pi_{t}^{j}(x_{t},u_{t}^{1:j-1}),\
0=x_{t+1}-f_{t}(x_{t},u_{t})$ $\displaystyle j\in\mathbf{I}_{i+1}^{N}$
$\displaystyle 0=h_{t}^{i}(x_{t},u_{t}),\ 0\leq g_{t}^{i}(x_{t},u_{t})$

It follows that
$\tilde{u}_{t}^{i}\in\arg_{u_{t}^{i}}\min_{u_{t}^{i}}Z_{t}^{i}(x_{t},u_{t}^{1:i-1},u_{t}^{i})$.
Therefore, the set of strategies $\\{\pi_{t}^{i}\\}_{t=0,i=1}^{T,N}$
constitutes a set of local feedback Stackelberg policies.

######  Proof A.2 (Proof of Theorem 4.3).

For a time $t\in\mathbf{I}_{0}^{T}$ and player $i\in\mathbf{I}_{1}^{N}$, we
set the gradient of $\mathcal{L}_{t}^{i}$ with respect to $u_{t}^{i}$ and
$x_{t}$ to be zero. This constitutes the first two rows of $\eqref{eq:KKT}$.
In addition, a player $i<N$ considers the feedback interaction constraints
$0=u_{t}^{j*}-\pi_{t}^{j}(x_{t}^{*},u_{1}^{1:j-1*})$, for
$j\in\mathbf{I}_{i+1}^{N}$. This constraint is implicitly ensured when we
include player $j$’s KKT conditions into player $i$’s KKT conditions. Thus, we
only need to ensure the gradient $\nabla_{u_{t}^{j}}\mathcal{L}_{t}^{i}$ to be
zero, when synthesizing player $i$’s KKT conditions. This corresponds to the
third row of (19). Moreover, at a time $t<T$, each player
$i\in\mathbf{I}_{1}^{N}$ needs to account for the feedback reaction from other
players at future steps. Again this constraint is implicitly ensured when we
define player $j$’s KKT conditions. We only need to additionally set the
gradient of $\mathcal{L}_{t}^{i}$ with respect to $u_{\tau}^{j}$ to be zero,
where $\tau\in\mathbf{I}_{t+1}^{T}$ and
$j\in\mathbf{I}_{1}^{N}\setminus\\{i\\}$. These correspond to the fourth row
of (19). Finally, we include the dynamics constraints, equality and inequality
constraints, and complementary slackness conditions in the last five rows of
(19).

######  Proof A.3 (Proof of Theorem 4.5).

We can check that the feasible set for the equality constraints of (20) is a
superset of the critical cone of the problem (19). By Theorem 12.6 in [37],
the solutions $(\mathbf{x},\mathbf{u})$ constitute a local feedback
Stackelberg equilibrium trajectory, and $\\{\pi_{t}^{i}\\}_{t=0,i=1}^{T,N}$ is
a set of local feedback Stackelberg policies.

######  Proof A.4 (Proof of Theorem 5.1).

By fundamental theorem of calculus, we have
$K_{\rho}({\mathbf{z}}+\alpha\Delta{\mathbf{z}})=K_{\rho}({\mathbf{z}})+\int_{0}^{1}{\nabla^{*}}K_{\rho}({\mathbf{z}}\allowbreak+\tau\alpha\Delta{\mathbf{z}})\alpha\Delta{\mathbf{z}}d\tau$,
and we have

(51)
$\displaystyle\|K_{\rho}({\mathbf{z}}+\alpha\Delta{\mathbf{z}})\|_{2}=\left\|K_{\rho}({\mathbf{z}})+\int_{0}^{1}{\nabla^{*}}K_{\rho}({\mathbf{z}}+\tau\alpha\Delta{\mathbf{z}})\alpha\Delta{\mathbf{z}}d\tau\right\|_{2}$
$\displaystyle\leq\|K_{\rho}({\mathbf{z}})+\alpha{\nabla^{*}}K_{\rho}({\mathbf{z}})\Delta{\mathbf{z}}\|_{2}+\left\|\int_{0}^{1}({\nabla^{*}}K_{\rho}({\mathbf{z}}+\tau\alpha\Delta{\mathbf{z}})-{\nabla^{*}}K_{\rho}({\mathbf{z}}))\alpha\Delta{\mathbf{z}}d\tau\right\|_{2}$

Substituting $\Delta{\mathbf{z}}$ into
$\|K_{\rho}({\mathbf{z}})+\alpha{\nabla^{*}}K_{\rho}({\mathbf{z}})\Delta{\mathbf{z}}\|_{2}$,
we have

(52) $\displaystyle\|K_{\rho}({\mathbf{z}})$
$\displaystyle+\alpha{\nabla^{*}}K_{\rho}({\mathbf{z}})\Delta{\mathbf{z}}\|_{2}=\|K_{\rho}({\mathbf{z}})-\alpha{\nabla^{*}}K_{\rho}({\mathbf{z}})(\nabla
K_{\rho}({\mathbf{z}}))^{-1}K_{\rho}({\mathbf{z}})\|_{2}$ $\displaystyle\leq$
$\displaystyle(1-\alpha)\|K_{\rho}({\mathbf{z}})\|_{2}+\alpha\|{\nabla^{*}}K_{\rho}({\mathbf{z}})-\nabla
K_{\rho}({\mathbf{z}})\|_{2}\|(\nabla
K_{\rho}({\mathbf{z}}))^{-1}\|_{2}\|K_{\rho}({\mathbf{z}})\|_{2}$
$\displaystyle\leq$
$\displaystyle(1-\alpha)\|K_{\rho}({\mathbf{z}})\|_{2}+\alpha\delta
D\|K_{\rho}({\mathbf{z}})\|_{2}=(1-\alpha(1-\delta
D))\|K_{\rho}({\mathbf{z}})\|_{2}$

Combining (52) and (51), we have

$\displaystyle\|$ $\displaystyle
K_{\rho}({\mathbf{z}}+\alpha\Delta{\mathbf{z}})\|_{2}$
$\displaystyle\leq(1-\alpha(1-\delta
D))\|K_{\rho}({\mathbf{z}})\|_{2}+\left\|\alpha\Delta{\mathbf{z}}\right\|_{2}\left\|\int_{0}^{1}\|\nabla^{*}K_{\rho}({\mathbf{z}}+\tau\alpha\Delta{\mathbf{z}})-\nabla^{*}K_{\rho}({\mathbf{z}})\|d\tau\right\|_{2}$
$\displaystyle\leq(1-\alpha(1-\delta
D))\|K_{\rho}({\mathbf{z}})\|_{2}+\frac{1}{2}\alpha^{2}D^{2}C\|K_{\rho}({\mathbf{z}})\|_{2}^{2}$

where the right hand side is minimized when
$\alpha^{*}=\frac{1-D\delta}{D^{2}C\|K_{\rho}({\mathbf{z}})\|_{2}}$. Suppose
$\|K_{\rho}({\mathbf{z}})\|_{2}>\frac{1-D\delta}{D^{2}C{\hat{\alpha}}}$, then
${\hat{\alpha}}>\frac{1-D\delta}{D^{2}C\|K_{\rho}({\mathbf{z}})\|_{2}}$ and we
have
$\|K_{\rho}({\mathbf{z}}+\alpha^{*}\Delta{\mathbf{z}})\|_{2}\leq\|K_{\rho}({\mathbf{z}})\|_{2}-\frac{(1-D\delta)^{2}}{2D^{2}C}$.

For the case
$\|K_{\rho}({\mathbf{z}})\|_{2}\leq\frac{1-D\delta}{D^{2}C{\hat{\alpha}}}$,
let $\alpha:={\hat{\alpha}}$. By
${\hat{\alpha}}D^{2}C\|K_{\rho}({\mathbf{z}})\|_{2}\leq 1-D\delta$, we have
$\|K_{\rho}({\mathbf{z}}+{\hat{\alpha}}\Delta{\mathbf{z}})\|_{2}\leq(1-\frac{1}{2}{\hat{\alpha}}(1-D\delta))\|K_{\rho}({\mathbf{z}})\|_{2}$.

######  Proof A.5 (Proof of Proposition 6.1).

By definition, we have

$\displaystyle\|$
$\displaystyle\nabla\tilde{\pi}_{t,\rho}^{i}(\tilde{\mathbf{z}})-\nabla\pi_{t,\rho}^{i}({\mathbf{z}})\|_{2}=\|\nabla
K_{t,\rho}^{i}(\tilde{\mathbf{z}})^{-1}K_{t,\rho}^{i}(\tilde{\mathbf{z}})-\nabla
K_{t,\rho}^{i*}({\mathbf{z}})^{-1}K_{t,\rho}^{i*}({\mathbf{z}})\|_{2}$
$\displaystyle=\|\nabla
K_{t,\rho}^{i}(\tilde{\mathbf{z}})^{-1}K_{t,\rho}^{i}(\tilde{\mathbf{z}})-\nabla
K_{t,\rho}^{i*}({\mathbf{z}})^{-1}K_{t,\rho}^{i*}({\mathbf{z}})$
$\displaystyle\hskip 28.45274pt+\nabla
K_{t,\rho}^{i*}(\tilde{\mathbf{z}})^{-1}K_{t,\rho}^{i}(\tilde{\mathbf{z}})-\nabla
K_{t,\rho}^{i*}(\tilde{\mathbf{z}})^{-1}K_{t,\rho}^{i}(\tilde{\mathbf{z}})$
$\displaystyle\hskip 28.45274pt+\nabla
K_{t,\rho}^{i*}({\mathbf{z}})^{-1}K_{t,\rho}^{i}(\tilde{\mathbf{z}})-\nabla
K_{t,\rho}^{i*}({\mathbf{z}})^{-1}K_{t,\rho}^{i}(\tilde{\mathbf{z}})$
$\displaystyle\hskip 28.45274pt+\nabla
K_{t,\rho}^{i*}({\mathbf{z}})^{-1}K_{t,\rho}^{i}({\mathbf{z}})-\nabla
K_{t,\rho}^{i*}({\mathbf{z}})^{-1}K_{t,\rho}^{i}({\mathbf{z}})\|_{2}$
$\displaystyle\leq\Big{(}\|\nabla
K_{t,\rho}^{i}(\tilde{\mathbf{z}})^{-1}-\nabla
K_{t,\rho}^{i*}(\tilde{\mathbf{z}})^{-1}\|_{2}+\|\nabla
K_{t,\rho}^{i*}(\tilde{\mathbf{z}})^{-1}-\nabla
K_{t,\rho}^{i*}({\mathbf{z}})^{-1}\|_{2}\Big{)}\|K_{t,\rho}^{i}(\tilde{\mathbf{z}})\|_{2}$
$\displaystyle\hskip
28.45274pt+\Big{(}\|K_{t,\rho}^{i}(\tilde{\mathbf{z}})-K_{t,\rho}^{i}({\mathbf{z}})\|_{2}+\|K_{t,\rho}^{i}({\mathbf{z}})-K_{t,\rho}^{i*}({\mathbf{z}})\|_{2}\Big{)}\|\nabla
K_{t,\rho}^{i*}({\mathbf{z}})^{-1}\|_{2}$
$\displaystyle\leq\epsilon_{{\mathbf{z}},\tilde{\mathbf{z}}}\Big{(}\|\nabla
K_{t,\rho}^{i}(\tilde{\mathbf{z}})^{-1}\|_{2}+\|\nabla
K_{t,\rho}^{i*}({\mathbf{z}})^{-1}\|_{2}\Big{)}\|\nabla
K_{t,\rho}^{i*}(\tilde{\mathbf{z}})^{-1}\|_{2}\|K_{t,\rho}^{i}(\tilde{\mathbf{z}})\|_{2}$
$\displaystyle\hskip
28.45274pt+2\epsilon_{{\mathbf{z}},\tilde{\mathbf{z}}}\|\nabla
K_{t,\rho}^{i*}({\mathbf{z}})^{-1}\|_{2}$

where the last line follows by applying Lemma A.6.

######  Lemma A.6.

Let $K$ and $\tilde{K}$ be two invertible matrices. Suppose
$\|K-\tilde{K}\|_{2}\leq\epsilon$, then we have
$\|K^{-1}-\tilde{K}^{-1}\|_{2}\leq\epsilon\|K^{-1}\|_{2}\cdot\|\tilde{K}^{-1}\|_{2}$.

######  Proof A.7 (Proof of Lemma A.6).

Define $\bar{K}:=K-\tilde{K}$. Applying the Woodbury matrix equality, we have
$\tilde{K}^{-1}=K^{-1}+K^{-1}\cdot\bar{K}\cdot\tilde{K}^{-1}$, and this
implies
$\|\tilde{K}^{-1}-K^{-1}\|\leq\epsilon\|K^{-1}\|\cdot\|\tilde{K}^{-1}\|$.

(a) Trajectories

(b) Feedback Stackelberg policy

(c) Receding-horizon open-loop Stackelberg policy

Figure 3: The trajectories under the receding horizon open-loop Stackelberg
equilibrium (RH-OLSE) policy and those under the FSE policy are quite
different, regardless of the initial conditions. For example, in the above
case, under the FSE policy, player 1 first moves towards the origin and then
player 2 follows. However, under the RH-OLSE policy, player 1 always stays at
its initial position, waiting for player 2 to approach.

(a) Zeroth order

(b) First order

(c) Second order

Figure 4: Visualization of the policy gradients of a constrained single-stage
Linear Quadratic Regulator problem under different values of $\rho$. The cost
is given by $(u_{0}-x_{0})^{2}$. The dynamics is defined as
$x_{1}=x_{0}+u_{0}$. We consider a constraint $u_{0}\geq 0$. The ground truth
piecewise linear policy is not differentiable at $x=0$. As $\rho\to 0$, the
policy obtained from PDIP and its first-order gradient closely approximate the
ground truth policy and its first-order gradient, for all nonzero states $x$.
Moreover, as shown in Figure 4, the high-order gradient of the PDIP policy
decays to zero as $\rho\to 0$, for all nonzero states $x$.

######  Proof A.8 (Proof of Theorem 6.3).

Observe that the first order-approximation of the KKT conditions for the local
LQ approximation coincides with the one for nonlinear games. By Theorem 5.1,
for each $\rho>0$,
$\lim_{k\to\infty}\|K_{\rho}(\mathbf{z}_{\rho}^{(k)})\|_{2}=0$, and we have
exponential convergence when
$k\geq\|K_{\rho}(\mathbf{z}_{\rho}^{(0)})\|_{2}/(\frac{1-D\delta}{D^{2}C{\hat{\alpha}}})$.
Moreover, by Theorem 4.5, for each $\rho>0$, the local policies
$\\{{\tilde{\pi}_{t,\rho}^{i}}\\}_{t=0,i=1}^{T,N}$ are local FSE policies. It
follows that $\lim_{\rho\to
0}\\{{\tilde{\pi}_{t,\rho}^{i}}\\}_{t=0,i=1}^{T,N}$ are local FSE policies as
well.

Figure 5: Players correctly exchange lanes under the FSE policy but keep far
away from each other under the FNE policy due to safety concern.

###  A.1 Comparing the FNE with the FSE

Consider a two-player lane exchanging problem with linear double integrator
dynamics $x_{t+1}=Ax_{t}+B^{1}u_{t}^{1}+B^{2}u_{t}^{2}$. Consider cost
functions
$c_{t}^{1}(x,u)=1.1(p_{t,x}^{1}-1)^{2}+(\theta_{t}^{1})^{2}+(v_{t}^{1}-1)^{2}-\frac{1}{2}((p_{t,x}^{2}-x_{t}^{5})^{2}+((p_{t,y}^{1}-p_{t,y}^{2})^{2})+4\|u_{t}^{1}\|^{2}_{2}$
and
$c_{t}^{2}(x,u)=1.1(p_{t,x}^{2}+1)^{2}+(\theta_{t}^{2})^{2}+(v_{t}^{2}-1)^{2}-\frac{1}{2}((p_{t,x}^{1}-p_{t,x}^{2})^{2}+(p_{t,y}^{1}-p_{t,y}^{2})^{2})+4\|u_{t}^{2}\|_{2}^{2}$.
Figure 5 suggests that the FSE is a more appropriate equilibrium concept than
the FNE when decision hierarchy exists.

###  A.2 A counter example that the receding horizon open-loop Stackelberg
equilibrium fails to approximate the FSE well

In this subsection, we consider the Example 1 of [27]. We show in Figure 3
that the receding-horizon open-loop Stackelberg policy could lead to a
trajectory quite different from the one under FSE. Therefore, it is crucial to
study the computation of FSE.

###  A.3 The decay of high-order policy gradients when we apply PDIP to solve
constrained LQ games

We validate the quasi-policy assumption in LQ games in Proposition A.9, and
include a simplified example in Figure 4.

######  Proposition A.9.

Under the same assumptions of Theorem 5.1, let $\rho>0$ and denote by
${\mathbf{z}_{\rho}^{*}}$ a converged solution to an LQ game under Algorithm 1
with considering high-order policy gradients. Let
$\\{{\pi_{t,\rho}^{i}}\\}_{t=0,i=1}^{T,N}$ be the converged policies. Suppose
that $\lim_{\rho\to 0}{\mathbf{z}_{\rho}^{*}}$ exists and we denote it by
${\mathbf{z}}^{*}$. Moreover, suppose that the ground truth FSE policies
$\\{\pi_{t}^{i}\\}_{t=0,i=1}^{T,N}$ are differentiable at
$({\mathbf{x}}^{*},{\mathbf{u}}^{*})$. Then, $\lim_{\rho\to
0}\|\nabla{\pi_{t,\rho}^{i}}-\nabla\pi_{t}^{i}\|_{2}=0$, and $\lim_{\rho\to
0}\|\nabla^{j}{\pi_{t,\rho}^{i}}\|_{2}=0,\forall
i\in\mathbf{I}_{1}^{N},t\in\mathbf{I}_{0}^{T}$, $j\geq 2$.

######  Proof A.10.

At time $t=T$, there is no policy gradient term in the $N$-th player’s KKT
conditions. Recall that $\nabla{\pi_{T,\rho}^{N}}=-[(\nabla
K_{T,\rho}^{N})^{-1}]_{u_{T}^{N}}\nabla_{[x_{T},u_{T}^{1:N-1}]}K_{T,\rho}^{N}$
and $\nabla\pi_{T}^{N}=-[(\nabla
K_{T}^{N})^{-1}]_{u_{T}^{N}}\nabla_{[x_{T},u_{T}^{1:N-1}]}K_{T}^{N}$. Since
$\lim_{\rho\to
0}\|K_{T,\rho}^{N}({\mathbf{z}_{T,\rho}^{N*}})-K_{T}^{N}({\mathbf{z}_{T}^{N*}})\|_{2}=0$,
we have pointwise convergence $\lim_{\rho\to
0}\|\nabla{\pi_{T,\rho}^{N}}-\nabla\pi_{T}^{N}\|_{2}=0$ almost everywhere. We
characterize those high-order quasi-policy gradients of ${\pi_{T,\rho}^{N}}$
as follows. We denote the map from ${\mathbf{z}_{T,\rho}^{N*}}$ to the $j$-th
order gradient of ${\pi_{T,\rho}^{N}}$ by an operator
${\mathcal{A}}_{T}^{N,j}:{\mathbf{z}_{T,\rho}^{N*}}\to\nabla^{j}{\pi_{T,\rho}^{N}}$.
Observe that $[(\nabla K_{T,\rho}^{N})^{-1}]_{u_{T}^{N}}$ can be considered as
the concatenation of a matrix inverse operator
${\mathcal{M}}:X\in\mathbb{R}^{n\times n}\to X^{-1}\in\mathbb{R}^{n\times n}$
and a linear operator ${\hat{\mathcal{M}}}:{\mathbf{z}_{T,\rho}^{N*}}\to\nabla
K_{T,\rho}^{N}$. Note that the matrix inverse is an infinitely differentiable
operator when $X$ is invertible and
$\nabla_{[x_{T},u_{T}^{1:N-1}]}K_{T,\rho}^{N}$ is a constant matrix. Thus, by
the chain rule [41], ${\pi_{T,\rho}^{N}}$ is infinitely differentiable, which
also implies that $\nabla^{j}{\pi_{T,\rho}^{N}}$ is continuous, $\forall j\geq
1$.

Since $\nabla K_{T,\rho}^{N}({\mathbf{z}_{T,\rho}^{N*}})$ is invertible at
${\mathbf{z}_{T,\rho}^{N*}}$ and ${\mathcal{A}}_{T}^{N,j}$, $\forall j\geq 1$,
is a continuous operator, there exists a compact set ${\mathcal{S}}$
containing ${\mathbf{z}_{T,\rho}^{N*}}$ such that $\nabla
K_{T,\rho}^{N}({\mathbf{z}}_{T}^{N})$ is invertible for all
${\mathbf{z}}_{T}^{N}\in{\mathcal{S}}$. By the compactness of ${\mathcal{S}}$
and the continuity of ${\mathcal{A}}_{T}^{N,j}$, we have that
${\mathcal{A}}_{T}^{N,j}$ is a uniformly continuous operator on
${\mathcal{S}}$. By Theorem 2 in [4], a uniformly continuous operator
preserves the pointwise convergence. Thus, $\lim_{\rho\to
0}\|\nabla^{j}{\pi_{T,\rho}^{N}}-\nabla^{j}\pi_{T}^{N}\|_{2}=0$. Since the
ground truth policy $\pi_{T}^{N}$ is piecewise linear and the high-order
gradients of $\pi_{T}^{N}$ vanish, we have $\lim_{\rho\to
0}\|\nabla^{j}{\pi_{T,\rho}^{N}}\|_{2}=0$, $\forall j>1$.

Subsequently, for player $i=N-1$, since $\lim_{\rho\to
0}\|\nabla{\pi_{T,\rho}^{N}}-\nabla\pi_{T}^{N}\|_{2}=0$, we have
$\lim_{\rho\to 0}\|\nabla K_{T}^{i}({\mathbf{z}_{T,\rho}^{i*}})-\nabla
K_{T}^{i}({\mathbf{z}_{T}^{i*}})\|_{2}=0$, which implies $\lim_{\rho\to
0}\|\nabla{\pi_{T,\rho}^{i}}-\nabla\pi_{T}^{i}\|_{2}=0$. A similar reasoning
as above yields that
$\lim_{\rho\to\infty}\|\nabla^{j}{\pi_{T,\rho}^{i}}-\nabla^{j}\pi_{T}^{i}\|_{2}=0$,
$\forall j>1$. Moreover, we can show that for all players $i<N-1$,
$\lim_{\rho\to
0}\|\nabla^{j}{\pi_{T,\rho}^{i}}-\nabla^{j}\pi_{T}^{i}\|_{2}=0$, $\forall
j\geq 1$. We continue this backward induction proof of $\lim_{\rho\to
0}\|\nabla^{j}{\pi_{t,\rho}^{i}}-\nabla^{j}\pi_{t}^{i}\|_{2}=0$, $\forall
j\geq 1$, for prior stages backwards in players decision order until $t=0$ and
$i=1$.

##  Appendix B KKT conditions for two-player LQ games

The KKT conditions $0=K_{T,\rho}^{2}({\mathbf{z}}_{T}^{2})$ of player $2$ at
time $T$ are

$\left\\{\begin{aligned}
0=&\Sigma_{j=1}^{2}R_{T}^{2,2,j}u_{T}^{j}+S_{T}^{2,2}x_{T}+r_{T}^{2,2}+B_{T}^{2\top}\lambda_{T}^{2}-G_{u_{T}^{2}}^{2\top}\gamma_{T}^{2}-H_{u_{T}^{2}}^{2\top}\mu_{T}^{2}\\\
0=&Q_{T+1}^{2}x_{T+1}+q_{T+1}^{2}-\lambda_{T}^{2}-G_{x_{T+1}}^{2\top}\gamma_{T+1}^{2}-H_{x_{T+1}}^{2\top}\mu_{T+1}^{2}\\\
0=&x_{T+1}-A_{T}x_{T}-B_{T}^{1}u_{T}^{1}-B_{T}^{2}u_{T}^{2}-c_{T}\\\
0=&H_{u_{T}^{2}}^{2}u_{T}^{2}+H_{x_{T}}^{2}x_{T}+H_{u_{T}^{1}}^{2}u_{T}^{1}+\bar{h}_{T}^{2}\\\
0=&H_{x_{T+1}}^{2}x_{T+1}+\bar{h}_{T+1}^{2}\\\ 0=&\gamma_{T:T+1}^{2}\odot
s_{T:T+1}^{2}-\rho\mathbf{1}\\\
0=&G_{u_{T}^{2}}^{2}u_{T}^{2}+G_{x_{T}}^{2}x_{T}+G_{u_{T}^{1}}^{2}u_{T}^{1}+\bar{g}_{T}^{2}-s_{T}^{2}\\\
0=&G_{x_{T+1}}^{2}x_{T+1}+\bar{g}_{T+1}^{2}-s_{T+1}^{2}\end{aligned}\right.$

We construct the KKT conditions $0=K_{T,\rho}^{1}({\mathbf{z}}_{T}^{1})$ of
player $1$ at time $T$:

$\left\\{\begin{aligned}
0=&\Sigma_{j=1}^{2}R_{T}^{1,1,j}u_{T}^{j}+S_{T}^{1,1}x_{T}+r_{T}^{1,1}+B_{T}^{1\top}\lambda_{T}^{1}-G_{u_{T}^{1}}^{1\top}\gamma_{T}^{1}-H_{u_{T}^{1}}^{1\top}\mu_{T}^{1}+(\nabla_{u_{T}^{1}}\pi_{T,\rho}^{2})^{\top}\psi_{T}^{1}\\\
0=&Q_{T+1}^{1}x_{T+1}+q_{T+1}^{1}-\lambda_{T}^{1}-G_{x_{T+1}}^{1\top}\gamma_{T+1}^{1}-H_{x_{T+1}}^{1\top}\mu_{T+1}^{1}\\\
0=&\Sigma_{j=1}^{2}R_{T}^{1,2,j}u_{T}^{j}+S_{T}^{1,2}x_{T}+r_{T}^{1,2}+B_{T}^{2\top}\lambda_{T}^{1}-G_{u_{T}^{2}}^{1\top}\gamma_{T}^{1}-H_{u_{T}^{2}}^{1\top}\mu_{T}^{1}-\psi_{T}^{1}\\\
0=&H_{u_{T}^{1}}^{1}u_{T}^{1}+H_{x_{T}}^{1}x_{T}+H_{u_{T}^{2}}^{1}u_{T}^{2}+\bar{h}_{T}^{1}\\\
0=&H_{x_{T+1}}^{1}x_{T+1}+\bar{h}_{T+1}^{1}\\\ 0=&\gamma_{T:T+1}^{1}\odot
s_{T:T+1}^{1}-\rho\mathbf{1}\\\
0=&G_{u_{T}^{1}}^{1}u_{T}^{1}+G_{x_{T}}^{1}x_{T}+G_{u_{T}^{2}}^{1}u_{T}^{2}+\bar{g}_{T}^{1}-s_{T}^{1}\\\
0=&G_{x_{T+1}}^{1}x_{T+1}+\bar{g}_{T+1}^{1}-s_{T+1}^{1}\\\
0=&K_{T,\rho}^{2}({\mathbf{z}}_{T}^{2})\end{aligned}\right.$

We construct the KKT conditions $0=K_{t,\rho}^{2}({\mathbf{z}}_{t}^{2})$ of
player $2$ at time $t<T$:

$\left\\{\begin{aligned}
0=&\Sigma_{j=1}^{2}R_{t}^{2,2,j}u_{t}^{j}+S_{t}^{2,2}x_{t}+r_{t}^{2,2}+B_{t}^{2\top}\lambda_{t}^{2}-G_{u_{t}^{2}}^{2\top}\gamma_{t}^{2}-H_{u_{t}^{2}}^{2\top}\mu_{t}^{2}\\\
0=&Q_{t+1}^{2}x_{t+1}+q_{t+1}^{2}-\lambda_{t}^{2}-G_{x_{t+1}}^{2\top}\gamma_{t+1}^{2}-H_{x_{t+1}}^{2\top}\mu_{t+1}^{2}\\\
&-A_{t+1}^{\top}\lambda_{t+1}^{2}+\Sigma_{j=1}^{2}S_{t+1}^{2,j}u_{t+1}^{j}+(\nabla_{x_{t+1}}\pi_{t+1,\rho}^{1})^{\top}\eta_{t}^{2}\\\
0=&\Sigma_{j=1}^{2}R_{t+1}^{2,1,j}u_{t+1}^{j}+S_{t+1}^{2,1}x_{t+1}+r_{t+1}^{2,1}+B_{t+1}^{1\top}\lambda_{t+1}^{2}-G_{u_{t+1}^{1}}^{2\top}\gamma_{t+1}^{2}-H_{u_{t+1}^{1}}^{2\top}\mu_{t+1}^{2}-\eta_{t}^{2}\\\
0=&x_{t+1}-A_{t}x_{t}-B_{t}^{1}u_{t}^{1}-B_{t}^{2}u_{t}^{2}-c_{t}\\\
0=&H_{u_{t}^{2}}^{2}u_{t}^{2}+H_{x_{t}}^{2}x_{t}+H_{u_{t}^{1}}^{2}u_{t}^{1}+\bar{h}_{t}^{2}\\\
0=&\gamma_{t}^{2}\odot s_{t}^{2}-\rho\mathbf{1}\\\
0=&G_{u_{t}^{2}}^{2}u_{t}^{2}+G_{x_{t}}^{2}x_{t}+G_{u_{t}^{1}}^{2}u_{t}^{1}+\bar{g}_{t}^{2}-s_{t}^{2}\\\
0=&K_{t+1,\rho}^{1}({\mathbf{z}}_{t+1}^{1})\end{aligned}\right.$

We construct the KKT conditions $0=K_{t,\rho}^{1}({\mathbf{z}}_{t}^{1})$ of
player $1$ at time $t<T$:

$\left\\{\begin{aligned}
0=&\Sigma_{j=1}^{2}R_{t}^{1,1,j}u_{t}^{j}+S_{t}^{1,1}x_{t}+r_{t}^{1,1}+B_{t}^{1\top}\lambda_{t}^{1}-G_{u_{t}^{1}}^{1\top}\gamma_{t}^{1}-H_{u_{t}^{1}}^{1\top}\mu_{t}^{1}+(\nabla_{u_{t}^{1}}\pi_{t,\rho}^{2})^{\top}\psi_{t}^{1}\\\
0=&Q_{t+1}^{1}x_{t+1}+q_{t+1}^{1}-\lambda_{t}^{1}-G_{x_{t+1}}^{1\top}\gamma_{t+1}^{1}-H_{x_{t+1}}^{1\top}\mu_{t+1}^{1}\\\
&-A_{t+1}^{\top}\lambda_{t+1}^{1}+\Sigma_{j=1}^{2}S_{t+1}^{1,j}u_{t+1}^{j}+(\nabla_{x_{t+1}}\pi_{t+1,\rho}^{2})^{\top}\eta_{t}^{1}\\\
0=&\Sigma_{j=1}^{2}R_{t}^{1,2,j}u_{t}^{j}+S_{t}^{1,2}x_{t}+r_{t}^{1,2}+B_{t}^{2\top}\lambda_{t}^{1}-G_{u_{t}^{2}}^{1\top}\gamma_{t}^{1}-H_{u_{t}^{2}}^{1\top}\mu_{t}^{1}-\psi_{t}^{1}\\\
0=&\Sigma_{j=1}^{2}R_{t+1}^{1,2,j}u_{t}^{j}+S_{t+1}^{1,2}x_{t+1}+r_{t+1}^{1,2}+B_{t+1}^{2\top}\lambda_{t+1}^{1}-G_{u_{t+1}^{2}}^{1\top}\gamma_{t+1}^{1}-H_{u_{t+1}^{2}}^{1\top}\mu_{t+1}^{1}-\eta_{t}^{1}\\\
0=&H_{u_{t}^{1}}^{1}u_{t}^{1}+H_{x_{t}}^{1}x_{t}+H_{u_{t}^{2}}u_{t}^{2}+\bar{h}_{t}^{1}\\\
0=&\gamma_{t}^{1}\odot s_{t}^{1}-\rho\mathbf{1}\\\
0=&G_{u_{t}^{1}}^{1}u_{t}^{1}+G_{x_{t}}^{1}x_{t}+G_{u_{t}^{2}}^{1}u_{t}^{2}+\bar{g}_{t}^{1}-s_{t}^{1}\\\
0=&K_{t,\rho}^{2}({\mathbf{z}}_{t}^{2})\end{aligned}\right.$

We continue the above construction process until $i=1$ and $t=0$.

## References

  * [1] T. Başar and G. J. Olsder, Dynamic noncooperative game theory, SIAM, 1999.
  * [2] Y. Bai, C. Jin, H. Wang, and C. Xiong, Sample-efficient learning of stackelberg equilibria in general-sum games, Advances in Neural Information Processing Systems, 34 (2021), pp. 25799–25811.
  * [3] L. Bakule and M. Straškraba, On structural control strategies in aquatic ecosystems, Ecological Modelling, 39 (1987), pp. 171–180.
  * [4] R. G. Bartle and J. T. Joichi, The preservation of convergence of measurable functions under composition, Proceedings of the American Mathematical Society, 12 (1961), pp. 122–126.
  * [5] T. Basar, On the uniqueness of the nash solution in linear-quadratic differential games, International Journal of Game Theory, 5 (1976), pp. 65–90.
  * [6] R. Bellman, Dynamic programming, tech. report, RAND CORP SANTA MONICA CA, 1956.
  * [7] A. Bensoussan, S. Chen, A. Chutani, S. P. Sethi, C. C. Siu, and S. C. Phillip Yam, Feedback stackelberg–nash equilibria in mixed leadership games with an application to cooperative advertising, SIAM Journal on Control and Optimization, 57 (2019), pp. 3413–3444.
  * [8] T. Besselmann, J. Lofberg, and M. Morari, Explicit MPC for LPV systems: Stability and optimality, IEEE Transactions on Automatic Control, 57 (2012), pp. 2322–2332.
  * [9] S. P. Boyd and L. Vandenberghe, Convex optimization, Cambridge university press, 2004.
  * [10] O. Chen and M. Ben-Akiva, Game-theoretic formulations of interaction between dynamic traffic control and dynamic traffic assignment, Transportation Research Record, 1617 (1998), pp. 179–188.
  * [11] R. Chinchilla, G. Yang, and J. P. Hespanha, Newton and interior-point methods for (constrained) nonconvex–nonconcave minmax optimization with stability and instability guarantees, Mathematics of Control, Signals, and Systems, (2023), pp. 1–41.
  * [12] E. Dockner, Differential games in economics and management science, Cambridge University Press, 2000.
  * [13] F. Fabiani, M. A. Tajeddini, H. Kebriaei, and S. Grammatico, Local stackelberg equilibrium seeking in generalized aggregative games, IEEE Transactions on Automatic Control, 67 (2021), pp. 965–970.
  * [14] P. Franceschi, N. Pedrocchi, and M. Beschi, Human–robot role arbitration via differential game theory, IEEE Transactions on Automation Science and Engineering, (2023).
  * [15] B. Gardner and J. Cruz, Feedback stackelberg strategy for m-level hierarchical games, IEEE Transactions on Automatic Control, 23 (1978), pp. 489–491.
  * [16] N. Goswami, S. K. Mondal, and S. Paruya, A comparative study of dual active-set and primal-dual interior-point method, IFAC Proceedings Volumes, 45 (2012), pp. 620–625.
  * [17] X. He, A. Prasad, S. P. Sethi, and G. J. Gutierrez, A survey of stackelberg differential game models in supply and marketing channels, Journal of Systems Science and Systems Engineering, 16 (2007), pp. 385–413.
  * [18] Y.-C. Ho, P. Luh, and R. Muralidharan, Information structure, stackelberg games, and incentive controllability, IEEE Transactions on Automatic Control, 26 (1981), pp. 454–460.
  * [19] R. Janin, Directional derivative of the marginal function in nonlinear programming, Springer, 1984.
  * [20] M. Jungers, Feedback strategies for discrete-time linear-quadratic two-player descriptor games, Linear Algebra and its Applications, 440 (2014), pp. 1–23.
  * [21] H. Khan and D. Fridovich-Keil, Leadership inference for multi-agent interactions, arXiv preprint arXiv:2310.18171, (2023).
  * [22] M. Kimmel and S. Hirche, Invariance control for safe human–robot interaction in dynamic environments, IEEE Transactions on Robotics, 33 (2017), pp. 1327–1342.
  * [23] D. Korzhyk, Z. Yin, C. Kiekintveld, V. Conitzer, and M. Tambe, Stackelberg vs. nash in security games: An extended investigation of interchangeability, equivalence, and uniqueness, Journal of Artificial Intelligence Research, 41 (2011), pp. 297–327.
  * [24] F. Laine, D. Fridovich-Keil, C.-Y. Chiu, and C. Tomlin, The computation of approximate generalized feedback nash equilibria, SIAM Journal on Optimization, 33 (2023), pp. 294–318.
  * [25] S. M. LaValle and S. Hutchinson, Game theory as a unifying structure for a variety of robot tasks, in Proceedings of 8th IEEE international symposium on intelligent control, IEEE, 1993, pp. 429–434.
  * [26] S. Le Cleac’h, M. Schwager, and Z. Manchester, ALGAMES: a fast augmented lagrangian solver for constrained dynamic games, Autonomous Robots, 46 (2022), pp. 201–215.
  * [27] J. Li, C.-Y. Chiu, L. Peters, S. Sojoudi, C. Tomlin, and D. Fridovich-Keil, Cost inference for feedback dynamic games from noisy partial state observations and incomplete trajectories, in Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, 2023, pp. 1062–1070.
  * [28] M. Li, J. Qin, and L. Ding, Two-player stackelberg game for linear system via value iteration algorithm, in 2019 IEEE 28th International Symposium on Industrial Electronics (ISIE), IEEE, 2019, pp. 2289–2293.
  * [29] T. Li and S. P. Sethi, A review of dynamic stackelberg game models, Discrete & Continuous Dynamical Systems-B, 22 (2017), p. 125.
  * [30] R. Lucchetti, F. Mignanego, and G. Pieri, Existence theorems of equilibrium points in stackelberg, Optimization, 18 (1987), pp. 857–866.
  * [31] M. Maljkovic, G. Nilsson, and N. Geroliminis, On finding the leader’s strategy in quadratic aggregative stackelberg pricing games, arXiv preprint arXiv:2304.11615, (2023).
  * [32] G. Martín-Herrán and S. J. Rubio, On coincidence of feedback and global stackelberg equilibria in a class of differential games, European Journal of Operational Research, 293 (2021), pp. 761–772.
  * [33] S. Mondal and P. V. Reddy, Linear quadratic stackelberg difference games with constraints, in 2019 18th European Control Conference (ECC), IEEE, 2019, pp. 3408–3413.
  * [34] T. Mylvaganam and A. Astolfi, Approximate solutions to a class of nonlinear stackelberg differential games, in 53rd IEEE Conference on Decision and Control, IEEE, 2014, pp. 420–425.
  * [35] K. Nakamura, Opinion-guided games: Strategic coordination through gradient-based opinion dynamics, (2023).
  * [36] J. Nash, Non-cooperative games, Annals of mathematics, (1951), pp. 286–295.
  * [37] J. Nocedal and S. J. Wright, Numerical optimization, Springer, 1999\.
  * [38] OpenAI, ChatGPT-4, 2023, https://openai.com/chatgpt.  [Software].
  * [39] L. Peters, D. Fridovich-Keil, C. J. Tomlin, and Z. N. Sunberg, Inference-based strategy alignment for general-sum differential games, in Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, 2020, pp. 1037–1045.
  * [40] P. V. Reddy and G. Zaccour, Feedback nash equilibria in linear-quadratic difference games with constraints, IEEE Transactions on Automatic Control, 62 (2016), pp. 590–604.
  * [41] W. Rudin et al., Principles of mathematical analysis, vol. 3, McGraw-hill New York, 1976.
  * [42] M. Simaan and J. B. Cruz Jr, Additional aspects of the stackelberg strategy in nonzero-sum games, Journal of Optimization Theory and Applications, 11 (1973), pp. 613–626.
  * [43] Z. Sun, M. Greiff, A. Robertsson, and R. Johansson, Feasibility and coordination of multiple mobile vehicles with mixed equality and inequality constraints, arXiv preprint arXiv:1809.05509, (2018).
  * [44] A. Talebpour, H. S. Mahmassani, and S. H. Hamdar, Modeling lane-changing behavior in a connected environment: A game theory approach, Transportation Research Procedia, 7 (2015), pp. 420–440.
  * [45] B. Tolwinski, A stackelberg solution of dynamic games, IEEE Transactions on Automatic Control, 28 (1983), pp. 85–93.
  * [46] K. G. Vamvoudakis, F. L. Lewis, M. Johnson, and W. E. Dixon, Online learning algorithm for stackelberg games in problems with hierarchy, in 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), IEEE, 2012, pp. 1883–1889.
  * [47] H. Von Stackelberg, The theory of the market economy: Oxford university press, 1952, (1952).
  * [48] K. Wang, L. Xu, A. Perrault, M. K. Reiter, and M. Tambe, Coordinating followers to reach better equilibria: End-to-end gradient descent for stackelberg games, in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, 2022, pp. 5219–5227.
  * [49] E. R. Weintraub, On the existence of a competitive equilibrium: 1930-1954, Journal of Economic Literature, 21 (1983), pp. 1–39.
  * [50] D. Xie, On time inconsistency: a technical issue in stackelberg differential games, Journal of Economic Theory, 76 (1997), pp. 412–430.
  * [51] K. Xu, X. Zhao, and X. Han, Adaptive dynamic programming for a class of two-player stackelberg differential games, in 2020 International Conference on System Science and Engineering (ICSSE), IEEE, 2020, pp. 1–6.
  * [52] J. H. Yoo and R. Langari, A stackelberg game theoretic driver model for merging, in Dynamic Systems and Control Conference, vol. 56130, American Society of Mechanical Engineers, 2013, p. V002T30A003.
  * [53] Y. Zhao and Q. Zhu, Stackelberg game-theoretic trajectory guidance for multi-robot systems with koopman operator, arXiv preprint arXiv:2309.16098, (2023).