









\section{Introduction}
\input{secs/1-intro.tex}
\input{secs/1fig-natural}
\input{secs/1sec-contributions}

\section{Preliminaries}
\label{sec:setup}
\input{secs/2-setup.tex}
\input{secs/2fig-qnr}

\section{Stability of $2$-player scalar games}
\label{sec:main}
\input{secs/3-mainresults.tex}
\input{secs/3sec-insights}

\section{Certificates for Stability of Game Dynamics}
\label{sec:certificates}
\subsection{Stability: Uniform Learning Rates}
\label{sec:learningrates}
\input{secs/3sec-uniform.tex}
\subsection{Stability: Non-Uniform Learning Rates}
\label{sec:learningrates}
\input{secs/3sec-nonuniform.tex}

\section{An Illustrative Example}
\label{sec:examples}
\input{secs/conf/5-ex.tex}

\section{Conclusion}
\label{sec:conclusion}
\input{secs/6-conclusion}






\subsection{Game-Theoretic Preliminaries}
A $2$-player \emph{continuous game} 
$\mc G = (\cost_1, \cost_2)$ 
is a collection of  costs 
defined on $X=X_1\times X_2$
where player (agent)
$i \in \mc I=\{1,2\}$ 
has cost $f_i:X\to \mb{R}$. In this paper, the results apply to games with sufficiently smooth costs $\cost_i\in C^r(
X,
\mb{R})$ for some $r\geq 0$.
Agent $i$'s set of feasible actions 
is the $\dimm_i$-dimensional precompact set
$X_i \subseteq \mb R^{\dimm_i}$. The notation $x_{-i}$ denotes the action of player $i$'s competitor; 
that is, $x_{-i}=x_j$ where $j\in \mc{I}\backslash\{i\}$.\footnote{For 2-player games, $x_{-1} = x_2$ and $x_{-2} = x_1$.}

The most common and arguably natural notion of an equilibrium in continuous games is due to  Nash~\cite{nash1951non}.
\begin{definition}[Local Nash equilibrium] A joint action profile $x=(x_1,x_2)\in W_1\times W_2\subset X_1\times X_2$ is a local Nash equilibrium on $W_1\times W_2$ if, for each player $i\in\mc{I}$,
$f_i(x_i,x_{-i})\leq f_i(x_i^\prime,x_{-i})$, $\forall x_i^\prime \in W_i$.
\end{definition}
A local Nash equilibrium can equivalently be defined as in terms of best response maps: $x_i\in \arg\min_{y}f_i(y,x_{-i})$.  
From this perspective, local optimality conditions for players' optimization problems give rise to the notion of a differential Nash equilibrium~\cite{ratliff2013characterization,ratliff2016characterization}; non-degenerate differential Nash are known to be generic and structurally stable amongst local Nash equilibria in sufficiently smooth games~\cite{ratliff2014allerton}. Let $D_if_i$ denote the derivative of $f_i$ with respect to $x_i$ and, analogously, let $D_i(D_if_i)\equiv D_i^2f_i$ be player $i$'s individiaul Hessian.
\begin{definition}
\label{def:nash}
For continuous game $\mc{G}=(\cost_1, \cost_2)$ where $\cost_i \in C^2(X_1 \times X_2,\R)$,
 a joint action profile $(x_1,x_2) \in X_1 \times X_2$ is a 
 \emph{differential Nash equilibrium}
 if 
 $D_if_i(x_1, x_2) = 0$ and $D_i^2f_i(x_1,x_2)> 0$ for each $i\in \mc{I}$.
\end{definition}
A differential Nash equilibrium is a strict local Nash equilibrium \cite[Thm.~1]{ratliff2013characterization}. Furthermore, the conditions $D_if_i(x)=0$ and $D_i^2f_i(x)\geq 0$ are necessary for a local Nash equilibrium \cite[Prop.~2]{ratliff2013characterization}.

Learning processes in games, and their study, arose as one of the explanations for how players grapple with one another in seeking an equilibrium~\cite{fudenberg1998theory}. In the case of sufficiently smooth games, gradient-based learning is a natural learning rule for myopic players%
\footnote{A mypoic player effectively believes it cannot influence its opponent's future behavior, and reacts only to local information about its cost.}.



\subsection{Gradient-based Learning as a Dynamical System %
}
At time $\kk$, 
a myopic agent $i$
updates its current action $x_i(\kk)$ by following the gradient of its
individual cost $\obj_i$
given the decisions of its competitors $x_{-i}$.
The synchronous adaptive process that arises is the discrete-time 
dynamical system
\begin{equation}
    \x_i(\kk+1) =x_{i}(\kk)-\gamma_i D_if_i(x_i(\kk),x_{-i}(\kk))
    \label{eq:gradientplay}
\end{equation} for each $i\in \mc{I}$ where $D_if_i$ is the gradient of player $i$'s cost with respect to $x_i$ and $\gamma_i$ is player $i$'s learning rate. 

\paragraph{Stability}
Recall that a matrix $A$ is called Hurwitz if its spectrum lies in the open left-half complex plane $\mb{C}_-^\circ$. Furthermore, we often say such a matrix is \emph{stable} in particular when $A$ corresponds to the dynamics of a linear system $\dot{x}=Ax$ or the linearization of a nonlinear system around a fixed point of the dynamics.\footnote{The Hartman-Grobman theorem~\cite{sastry1999nonlinear} states that around any hyperbolic fixed point of a nonlinear system, there is a neighborhood on which the nonlinear system is stable if the spectrum of Jacobian lies in $\mb{C}_-^\circ$.}  

It is known that \eqref{eq:gradientplay} will converge locally asymptotically to a differential Nash equilibrium if the local linearization is a contraction~\cite{chasnov2019convergence}. 
Let 
\eqnn{g(x)=(D_1f_1(x),D_2f_2(x))
\label{eq:gameform}}
be the vector of individual gradients and let $Dg(x)$ be its Jacobian---i.e., the \emph{game Jacobian}. Further, let $\sigma_p(A)\subset\mb{C}$
denote the \emph{point spectrum} (or \emph{spectrum}) of the matrix $A$, and $\rho(A)$ its \emph{spectral radius}. 
Then, $x$ is \emph{locally exponentially stable} if and only if $\rho(I-\Gamma Dg(x))<1$, where $\Gamma=\mathrm{blockdiag}(\gamma_1 I_{\dimm_1},\gamma_2I_{\dimm_2})$
is a diagonal matrix and $I_{\dimm_i}$ is the identity matrix of dimension $\dimm_i$. 
The map $I-\Gamma Dg(x)$ is the local linearization of \eqref{eq:gradientplay}. 
Hence, to study stability (and, in turn, convergence) properties it is useful to analyze the spectrum of not only the map $I-\Gamma Dg(x)$ but also $Dg(x)$ itself. 

For instance, when $\gamma=\gamma_1=\gamma_2$, the spectral mapping theorem
tells us that $\rho(I-\gamma Dg(x))=\max_{\lambda\in \sigma_p(Dg(x))}|1-\gamma \lambda|$ so that understanding the spectrum of $Dg(x)$ is imperative for understanding convergence of the discrete time update. On the other hand, when $\gamma_1\neq \gamma_2$, we write the local linearization as $I-\gamma_1\Learnrate Dg(x)$ where $\Learnrate=\mathrm{blockdiag}(I_{\dimm_1},\tau I_{\dimm_2})$ and $\tau=\gamma_2/\gamma_1$ is the learning rate ratio. 
Again, via the spectral mapping theorem, when $I-\gamma_1\Learnrate Dg(x)$ is a contraction for different choices of learning rate $\gamma_1$ is determined by the spectrum of $\Learnrate Dg(x)$.
Hence, given a \emph{fixed point}  $\fixedpoint{x}$ (i.e., $g(\fixedpoint{x})=0$), we study the stability properties of the limiting continuous time dynamical system---i.e., $\dot{x}=-g(x) $ when $\gamma_1=\gamma_2$ and $\dot{x}=-\Learnrate g(x)$ otherwise. From here forward, we will simply refer to the system $\dot{x}=-\Learnrate g(x)$ and point out when $\Learnrate=I_{d_1+d_2}$ if not clear from context. 




















\paragraph{Partitioning the Game Jacobian} Let 
$\fixedpoint{x}=(\fixedpoint{x}_1,\fixedpoint{x}_2)$ 
be a joint action profile such that 
$g(\fixedpoint{x})=0$.
Towards better understanding the spectral properties of $Dg(\fixedpoint{x})$ (respectively, $\Learnrate Dg(\fixedpoint{x})$), we 
partition~$Dg(\fixedpoint{x})$ into blocks:
\eqnn{%
 J(x)=
  \bmat{%
  -D_1^2\cost_1(\fixedpoint{\xx}) & 
  -D_{12}\cost_1(\fixedpoint{\xx}) \\
  -D_{21}\cost_2(\fixedpoint{\xx}) & 
  -D_{2}^2\cost_2(\fixedpoint{\xx})
 }
 =
 \bmat{\Aa & \Bb \\
  \Cc & \Dd}.
 \label{eq:game-jacobian}
}
A differential Nash equilibrium (the second order conditions of which are sufficient for a local Nash equilibrium) is such that 
$\Aa<0$ and
$\Dd<0$. On the other hand, as noted above, $J$ is Hurwitz or stable if its point spectrum $\sigma_p(J)\subset \mb{C}_-^\circ$. 
Moreover,
since the diagonal blocks are symmetric,
$\J$ is 
similar to the matrix 
in Fig~\ref{fig:blockdiag2p}.
For the remainder of the paper, 
we will study the $Dg$ at a given
fixed point $\fixedpoint{x}$ as defined in~\eqref{eq:game-jacobian}.
\begin{figure}[ht]
  \begin{minipage}[c]{0.4\columnwidth}
    \input{figs/blockdiag2p.tex}
  \end{minipage}\hfill
  \begin{minipage}[c]{0.59\columnwidth}
    \caption{\emph{Similarity}: the game Jacobian in~\eqref{eq:game-jacobian} 
    is similar to a matrix with diagonal block-diagonals.
    }
  \label{fig:blockdiag2p}
  \end{minipage}
\end{figure}



\paragraph{Classes of Games} Different classes of games can be characterized via $J$.   For instance,  a 
 \emph{zero-sum game}, where $\cost_1\equiv -\cost_2$, is such that $J_{12}=-J_{21}^\top$. On the other hand, %
 a game
 $\mc G = (\cost_1, \cost_2)$
 is a \emph{potential game} if and only if
 $D_{12}f_1 \equiv D_{21}f_2^\top$~\cite[Thm.~4.5]{monderer1996potential}, 
 which implies that $J_{12}=J_{21}^\top$.
 
 


\subsection{Spectrum of Block Matrices}
\label{sec:qnr}
One useful tool for characterizing the spectrum of a block operator matrix is the numerical range and quadratic numerical range, both of which 
contain the operator's spectrum~\cite{tretter2008spectral} and therefore all of its eigenvalues.
The \emph{numerical range} of $\J$ is defined by
\eqn{
   \NR(\J)=\{
\langle \J z,z\rangle:\ 
z\in \mb{C}^{\dimm_1+\dimm_2},\ %
\|z\|_2=1\}, 
}
and is convex. 
Given a block operator $J$,
let
\begin{equation}
\J_{v,w}=\bmat{\langle \J_{11}v,v\rangle & \langle\J_{12}w,v\rangle\\ \langle\J_{21}v,w\rangle & \langle\J_{22}w,w\rangle} 
\label{eq:jvw}
\end{equation}
where $v\in \mb{C}^{\dimm_1}$ and $w\in \mb{C}^{\dimm_2}$.
The \emph{quadratic numerical range} of $\J$,
defined by
\eqnn{
\NR^2(\J)=\bigcup_{v\in \mc{S}_1, w\in \mc{S}_2 }\sigma_p(\J_{v,w}),
\label{eq:qnr}}
is the union of the spectra of~\eqref{eq:jvw}
 where $\sigma_p(\cdot)$ denotes the (point) spectrum 
 of its argument 
 and $\mc{S}_i=\{z\in \mb{C}^{\dimm_i}:\ \|z\|_2=1\}$.
It is, in general, a non-convex subset of $\mb C$.
The quadratic numerical range~\eqref{eq:qnr}
is equivalent to the set of solutions of 
the characteristic polynomial
\eqnn{%
  \eig^2 
  &- \eig(\langle \Aa v,v\rangle  
  + \langle \Dd w,w\rangle ) 
  + \langle \Aa v,v\rangle\langle \Dd w,w\rangle  \\
  &- \langle \Bb v,w\rangle \langle \Cc w,v\rangle  = 0
  \label{eq:characteristic-polynomial}
}
for  $v\in \mc{S}_1$ and $w\in \mc{S}_2$. We use the notation $\langle \J x,y\rangle=\conjugate{x} \J y$ 
to denote the inner product. Note that $\NR^2(\J)$ is a subset of $\NR(\J)$ and, as previously noted, contains $\sigma_p(\J)$.
Albeit non-convex, $\NR^2(\J)$ provides a tighter characterization of the spectrum\footnote{There are numerous computational approaches for estimating the numerical ranges $\NR(\cdot)$ and $\NR^2(\cdot)$ (see, e.g., \cite[Sec. 6]{langer2001new}).}.







\begin{example}
Consider the game Jacobian of the zero-sum game $(f,-f)$ defined by 
cost $f:\R^2\times\R^2 \to \R$,
\[\cost(x,y)=-\tfrac{1}{2}x_1^2+\tfrac{5}{2}x_2^2+7y_1x_1-3y_2x_2-2y_1^2-6y_2^2.\]
The numerical range, quadratic numerical range, spectrum and diagonal entries of $\J$, defined using the origin as the fixed point,
are plotted in Fig.~\ref{fig:qnum-toy}. 
In this example, the origin is not 
a differential Nash equilibrium since $D^2_1f_1(0,0)$ is indefinite, yet it is an exponentially stable equilibrium of $\dot{x}=-g(x)$ since all the eigenvalues of $J$ are all negative.
\label{ex:qnum-toy}
\end{example}





Observing that the quadratic numerical range for a block $2\times 2$ matrix $J$ derived from a game on a finite dimensional Euclidean space reduces to characterizing the spectrum of $2\times 2$ matrices, 
we first characterize stability properties of scalar $2$-player continuous games. 







\subsection{Jacobian Decomposition: $2\times2$ case}

Consider 
the decomposition of a $\R^{2\times 2}$ game Jacobian
\begin{equation}
 \label{eq:2x2:decomp}
J(x)=\bmat{a & b \\ c & d}  
= \bmat{\gG & -\kK \\ \kK & \gG} + \bmat{\fF & \pP \\ \pP & -\fF} 
\end{equation}
where $\gG=\frac{1}{2}(a+d)$, $\fF=\frac{1}{2}(a-d)$, $\pP =\frac{1}{2}(b+c)$, $\kK=\frac{1}{2}(c-b)$.
Let 
$\trace(J)$ be its trace,
$\det(J)$ be its determinant, and 
$\disc(J)$ be the discriminant of its characteristic polynomial%
.\footnote{
The characteristic polynomial 
of $J$ is 
$\lambda \mapsto \det(J-\lambda I)$ and its discriminant is $\trace(J)^2 - 4\det(J)$ for $J \in \R^{2\times 2}$.
}
Several directly verifiable 
quantities 
are stated. 
\begin{statement}
\label{main-statement}
Given a matrix $\J \in \mb R^{2\times 2}$
and its 
spectrum $\sigma_p(J)=\{\eig_1, \eig_2\}$, 
the above decomposition gives rise to the following conditions:  
\begin{align*}
\trace(\J) & = 
\lambda_1 + \lambda_2 = 
a+d
=
2
\gG, \\
\det\big(\J\big) & = 
\lambda_1\lambda_2 = ad-bc 
 = (\gG^2 + \kK^2) - (\fF^2 + \pP^2),
\\
\disc\big(\J\big) 
&= 
(\lambda_1 + \lambda_2)^2 - 4\lambda_1 \lambda_2
 = 
4(\fF^2 + \pP^2 - \kK^2), \\
\lambda_{1,2} & =
\tfrac{1}{2}\big(
 \trace(\J) \mp
 \sqrt{\disc(J)}
\big)
=
\gG \mp 
\sqrt{\fF^2 + \pP^2 - \kK^2}.
\end{align*}
\end{statement}

 The change of coordinates from $(a,b,c,d)$ to $(m,h,p,z)$
in Statement~\ref{main-statement} 
provides 
 important insights into linear vector fields and, in particular, to games.
The stability of vector field $\dot x = Jx$ is given by the trace and determinant conditions.
\begin{proposition} %
\label{prop:stability}
The matrix $\J \in \mathbb{R}^{2 \times 2}$ is stable if and only if $\gG^2 + \kK^2 > \fF^2 + \pP^2$ and
$\gG < 0$.
\end{proposition}
\begin{proof}
Statement \ref{main-statement} and direct computation show that these conditions are equivalent to $\lambda_1 + \lambda_2 < 0$ and $\lambda_1\lambda_2 >0$, 
well-known conditions for stability of $2\times 2$ systems (illustrated in Fig.~\ref{fig:tracedet:tracedet}).
\end{proof}


















 



\subsection{Discussion of Decomposition}
\label{sec:insights}





The purpose of the decomposition into the alternative coordinates
is to geometrically---and thus
more directly---assess the conditions for stability of a differential Nash equilibrium. 
\ifsixpages
In particular,
the conditions for a fixed point of the game dynamics to be a differential Nash equilibrium
are $a<0$ and $d < 0$,
or equivalently,
$\gG < -|\fF|$,
which are represented 
by the left-shaded regions in Fig.~\ref{fig:gkfp:labels}--\ref{fig:gkfp:stable&nash}.
Moreover,
the conditions for a fixed point of the game dynamics to be stable (i.e., for $\sigma_p(J)\subset \mb{C}_-^\circ$) are $m<0$ and 
$m^2 + z^2 > h^2 + p^2$,
which are visible only
when using the decomposition
in Fig.~\ref{fig:gkfp:stable&nash}.
\else
 
 
\paragraph{Relationship to complex plane}
Fig.~\ref{fig:eigs} 
plots the coordinates of
$\gG,\kK,\fF,\pP$
relative to each other
to illustrate
the decomposition in
Statement~\ref{main-statement}.
If 
$\fF=0, \pP=0$, 
then the eigenvalues of $\J$ are $\lambda_{1,2} = \gG \mp \kK i$. Fig.~\ref{fig:eigs:complex} corresponds to a plot of eigenvalues in the complex plane.
Stability is given by the familiar open-left half plane condition: $\spec(\J) \subset \mathbb{C}_-^\circ$.  
If $\fF\neq 0$ or $\pP \neq 0$ 
a circular region in the center of the plane
expands the values of $\gG,\kK$ 
for which the eigenvalues of the matrix are purely real.
Fig.~\ref{fig:eigs:gkfp} shows
that
the eigenvalues are purely real if and only if
$\kK^2 \leq \fF^2 + \pP^2$.



 
 
\paragraph{Effect of rotation in game vector fields} 


Note the similarity between \eqref{eq:2x2:decomp} and the well-known symmetric/skew-symmetric (Helmholtz) decomposition

\begin{equation}
 \label{eq:2x2:helmholtz}
J(x)=\bmat{a & b \\ c & d}  
= \bmat{\gG + h & p\\ p & m-h} + \bmat{0 & -z \\ z & 0}. 
\end{equation}
Assuming that $m < 0$, from Proposition \ref{prop:stability} we can see that increasing 
the rotational component of the Jacobian helps stability.  Increasing the relative magnitude of $p$, the non-rotational interaction term hurts stability.  If there is no rotational component, ie. $J$ is symmetric, $p$'s negative impact on stability can be seen directly from the Schur complement\footnote{%
The Schur complements of the matrix in~\eqref{eq:game-jacobian} 
are $J_{11}-J_{12}J_{22}^{-1}J_{21}$ (where $J_{22}$ is invertible) and $J_{22}-J_{21}J_{11}^{-1}J_{12}$ (where $J_{11}$ is invertible).}. In this case $J$ is stable iff $J < 0$ and thus stability requires that both the diagonals and the Schur complement are negative: $a<0$, $d<0$, and $a-p^2d^{-1}<0$.  If $d<0$, increasing $p$ can only increase the Schur complement.  












 \begin{figure}[t]
 \input{figs/eigs.tex}
 \label{fig:eigs}
\end{figure}


\begin{figure}[t]
\input{figs/tracedet.tex}
\caption{\emph{Visualization of~\autoref{prop:stability}}: $\dot y = \J(x) y$ is \tightcolorbox{mygreen!80!white}{stable}
 $\Longleftrightarrow\ \det(J) > 0$ and $\trace(J) < 0$.
}
\label{fig:tracedet}
\end{figure}


 


\subsection{Types of Games}


The decomposition also provides a natural classification of 2-player scalar games into four types based on specific coordinates being zero, as illustrated in Fig.~\ref{fig:gametype}.
 

\paragraph{Potential games ($z=0$)}
    The point $(\gG, \kK)$ lives on the horizontal axis 
   in Fig.~\ref{fig:gametype:k0},
   thus stable fixed points are a subset of Nash equilibria.  Since $z = 0$, Proposition \ref{prop:stability} indicates that increasing $p$, the interaction term between the players, and increasing $h$, the difference in curvature between the two players both only hurt stability. 
   
 
   

\paragraph{Zero-sum games ($p=0$)}
   The point $(\fF , \pP)$ lives on the horizontal axis
   in 
   Fig.~\ref{fig:gametype:p0},
   thus all Nash equilibria are stable, but not all stable fixed points are Nash.
   The magnitude of the interaction term $\kK$ helps stability and may make a fixed point stable even if it is not Nash.  
   \ifsixpages
   Intuitively, a strong enough interaction term can cause a player which is at its action under the Nash equilibrium with stronger negative curvature to pull another player with weaker positive curvature toward a fixed point even if that point is a local 
   maximum %
   for the weaker player. 
   \fi

\paragraph{Hamiltonian games ($m=0$)} 
    The point $(\gG, \kK)$ lives on the vertical axis 
    in Fig.~\ref{fig:gametype:g0},
    thus no strict Nash equilibria can exist.  At best these games are marginally stable if $|\kK|$ is large enough relative to the magnitude of $(\fF , \pP)$.

\begin{figure}[h]
\input{figs/gkfp.tex}
\caption{%
\emph{Decomposition of a general scalar game.}
The rows vectors of $J$ are plotted in (a)
and the same matrix 
with a change of coordinates
is plotted in (b).
	\tightcolorbox{myblue!50!white}{Nash} regions 
	($m<-|h|$) and 
	\tightcolorbox{mygreen!80!white}{stability}
	regions ($m<0,m^2+z^2>h^2+p^2$) 
	are visible.
	Their set differences
	characterize the conditions for a stable non-Nash and unstable Nash equilibria.
}
\label{fig:gkfp}
 
 

\input{figs/gametypes.tex}
\caption{
\emph{Stability and Nash
for different
classes of games.}
(a) Potential games:
symmetric interaction term only hurts stability.
(b) Zero-sum games: rotation can compensate for unhappy player.
(c) Hamiltonian games: players have
zero total curvature, $a+d=0$. 
(d) Matching curvature, $a=d$: there are no stable non-Nash equilibria.
}
\label{fig:gametype}


 \input{figs/gkfp_rates}
 \caption{%
 \emph{Time-scale separation affects stability.}
 The learning rate ratio $\tau=\learnrate_2/\learnrate_1>0$ affects the stability of the game dynamics.
 The factor
 $\beta = \tfrac{\tau - 1}{\tau + 1}$
 expands or shrinks the region for stability.  The condition $m < 0$ becomes $m < \beta h$. Note that $-1 \leq \beta \leq 1$ for $\tau \geq 0$. 
 \ifsixpages
 For $\beta \to \pm 1$,
 the region's vertical boundary 
 approaches $\pm h$.
 \fi
 }
 \label{fig:rates}
 \end{figure}
 

\paragraph{Matching-curvature games, ($h=0$)}
The point $(\fF , \pP)$ lives on the vertical axis 
in Fig.~\ref{fig:gametype:f0}, 
so any stable point is also a Nash. 
Any fixed point with $a,d$ having the same sign can be rescaled to have matching curvature $\learnrate_1 a=\learnrate_2 d$ by a choice of non-uniform learning rates $\learnrate_1,\learnrate_2>0$. 




