# An inexact-penalty method for GNE seeking in games with dynamic agents

Andrew R. Romano and Lacra Pavel  This work was supported by NSERC Alliance
and Huawei. A. R. Romano and L. Pavel are with ECE Department, University of
Toronto, Canada<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We consider a network of autonomous agents whose outputs are actions in a game
with coupled constraints. In such network scenarios, agents seeking to
minimize coupled cost functions using distributed information while satisfying
the coupled constraints. Current methods consider the small class of multi-
integrator agents using primal-dual methods. These methods can only ensure
constraint satisfaction in steady-state. In contrast, we propose an inexact
penalty method using a barrier function for nonlinear agents with equilibrium-
independent passive dynamics. We show that these dynamics converge to an
$\varepsilon$-GNE while satisfying the constraints for all time, not only in
steady-state. We develop these dynamics in both the full-information and
partial-information settings. In the partial-information setting, dynamic
estimates of the others’ actions are used to make decisions and are updated
through local communication. Applications to optical networks and velocity
synchronization of flexible robots are provided.

##  I Introduction

Game theory has become a widely used tool in the control of multi-agent
systems, having found many areas of applications such as in power control of
communication networks [1] and formation control for robotics [2]. In a
generalized game, the relevant equilibrium is the generalized Nash
equilibrium, or GNE. At a GNE, each agent (player) is minimizing its own,
coupled cost-function subject to the constraints, given that the other agents’
actions remain fixed. Many GNE seeking algorithms assume that each agent has
full-information of the others’ actions and/or each has has no inherent
dynamics. These are restrictive assumptions in many control applications as
information my be distributed among agents who must communicate with another
and agents may have inherent dynamics, e.g., a group of mobile robots. Any GNE
seeking agorithm that is applied in these scenarios must deal with these two
issues. Recently, NE seeking with partial-decision information has been
considered for networks of dynamic agents (multi-integrator, LTI) [3]-[4], but
most existing results are restricted to games with decoupled constraints.
Considering games with coupled constraints, results exist for integrator
agents, e.g., [5] in discrete-time and [6]-[7] in continuous-time and for
multi-integrator agents in continuous-time [8]. Semi-decentralized methods
have also been considered [9] as well as partial-information on the dual
variables only [10]. However, existing methods, such as primal-dual methods,
ensure that the coupled constraints are satisfied in steady-state only. These
algorithms are not applicable in real-world applications where the constraints
must be satisfied for all time, e.g., sensor networks [11], demand-side
management in smart-grids [12], or optical networks [13].

In this paper, we investigate an inexact-penalty based dynamics for GNE
seeking with passive agents in networks. These dynamics can ensure that the
coupled constraints are satisfied for all time, not just in steady-state.
Moreover, this approach allows for the extension from the full-decision
information setting to the partial-information one.

Penalty methods, using exact penalty functions, have been used in GNE seeking
algorithms [14]-[15]. In our work, in order to enforce constraint
satisfaction, the penalty function takes the form of a barrier function that
prevents each agent’s action from exiting the interior of the constraint set.
Related to our work, [16] considers NE seeking in potential games with virtual
couplings used to satisfy connectivity constraints for all time. Compared to
[16], we allow for arbitrary convex inequality constraints in non-potential
games. As far as we are aware, there do not exist any general GNE seeking
methods that can ensure constraint satisfaction for all time.

Contributions.  Interior point methods are a much used tool in convex
optimization [17]. We propose using the log-barrier function on the coupled
inequality constraints as our inexact penalty function. The GNE problem is
then converted into an NE problem whose costs go to infinity at the boundary
of the constraint set. We consider GNE seeking using this new set of penalized
cost functions for nonlinear agents with a class of equilibrium-independent
passive (EIP) dynamics. The benefit of considering these agents is two-fold.
First, we are able to capture versions of a variety of already known NE
seeking algorithms. Secondly, we are able to consider certain types of dynamic
agents. For the full-information case a gradient based feedback is used. In
partial information setting, we instead use a Laplacian based feedback, [18],
for the case where agents have full knowledge of the constraint information.

In both these cases, assuming that the initial conditions satisfy the
constraints, we show that the resulting action trajectories also satisfy the
constraints for all time. Additionally, we extend these results to cases where
the agents do not have full-information about the constraints, but must
communicate in order to get it using a two-time scale approach.

A preliminary version of this work appeared in [19] concerning systems with
LTI passive dynamics. Only cases with full-information of the constraint info
are treated therein.

This paper is organized as follows: In Section II, we provide the necessary
background information on invariance, passivity and graph theory. In Section
III, we formulate the inexact penalized GNE problem. In Section IV, we provide
a GNE seeking strategy for agents’ with EIP dynamics under full-information of
the others’ actions. In Section V, these results are extended to the case of
partial action information but full-knowledge of the constraint. Section VI
considers a fully-distributed algorithm based on a two-time scale approach.
Sections VII and VIII provide applications to optical networks and velocity
synchronization respectively.

_Notations_ : Let $\mathbb{R}$ and $\mathbb{R}_{\geq 0}$denote the real
numbers and non-negative real numbers, respectively. Given
$x,y\in\mathbb{R}^{n}$, $x\top y$ denotes their inner product. Let
$\|\cdot\|:\mathbb{R}^{n}\rightarrow\operatorname{Re}_{\geq 0}$ denote the
Euclidean norm and $\|\cdot\|:\mathbb{R}^{n}\rightarrow\mathbb{R}_{\geq 0}$
its induced matrix norm. Given a set $\mathcal{X}\subset\mathbb{R}^{n}$,
$\|\cdot\|_{\mathcal{X}}:\mathbb{R}^{n}\rightarrow\operatorname{Re}_{\geq 0}$
denotes the Euclidean point-to-set distance. Given a function
$\phi:\mathbb{R}^{n}\rightarrow\mathbb{R}$ and a vector field
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$, $L_{f}\phi=\nabla\phi^{\top}f$ is
the Lie-derivative of $\phi$ along $f$.

##  II Background

###  II-A Positive- and Output-Positive-Invariance

Consider a system with dynamics given by

$\displaystyle\begin{split}\dot{x}&=f(x)\\\ y&=h(x)\end{split}$ (1)

where $x\in\mathbb{R}^{n}$ and $y\in\mathbb{R}^{m}$ and
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ is locally Lipschitz. The
following are some standard results concerning positive-invariance of sets
from, e.g., [20].

###### Definition 1

A set $\mathcal{X}\subset\mathbb{R}^{n}$ is called positively-invariant for
(1) if for all $x(0)\in\mathcal{X}$, $x(t)\in\mathcal{X}$ for all $t\geq 0$.

###### Definition 2

A set $\mathcal{Y}\subset\mathbb{R}^{m}$ is called output-positively-invariant
(1) if $y(0)\in\mathcal{Y}$ implies that $y(t)\in\mathcal{Y}$ for all $t\geq
0$.

###### Definition 3

The Bouligand tangent cone of the set $\mathcal{X}$ at $x$ is
$T_{\mathcal{X}}(x)=\\{v\in\mathbb{R}^{n}:\lim\inf_{t\rightarrow
0^{+}}\frac{\|x+tv\|_{\mathcal{X}}}{t}=0\\}$

###### Definition 4

(Definition 4.9 [20]) Let $\mathcal{O}$ be an open set. A set
$S\subset\mathcal{O}$ is a practical set if

  1. 1.

$S$ is defined by a finite set of inequalities

$\displaystyle S=\\{x\in\mathbb{R}^{n}:h_{k}(x)\leq 0,k=1,\dots,r\\}$

where $h_{k}(x)$ are continuously differentiable functions defined on
$\mathcal{O}$.

  2. 2.

For all $x\in S$, there exists $z$ such that

$\displaystyle h_{k}(x)+\nabla h_{k}(x)^{\top}z<0,\quad\forall\ k$

  3. 3.

There exists a Lipschitz continuous vector field $f_{0}(x)$ such that for all
$x\in\partial S$,

$\displaystyle L_{f_{0}}h_{k}<0,\quad\forall\ k\ \operatorname{s.t.}\
h_{k}(x)=0$

###### Lemma 1

A closed set $\mathcal{X}\subset\mathbb{R}^{n}$ is positively-invariant if and
only if $f(x)\in T_{\mathcal{X}}(x)$ for all $x\in\mathcal{X}$.

###### Lemma 2

Let $S\\!\subset\\!\mathcal{O}$ be a practical set. Then for all
$x\\!\in\\!\partial S$,

$\displaystyle T_{S}(x)=\\{z\in\mathbb{R}^{n}:L_{z}h_{k}(x)\leq 0,\forall\ k\
\operatorname{s.t.}\ h_{k}(x)=0\\}.$

###  II-B Passivity and Observability

The following is from [21]. Consider a system

$\displaystyle\Xi:\begin{cases}\dot{x}=f(x)+Gu\\\ y=h(x)\end{cases}$ (2)

where $G$ is full column-rank. Let $\mathcal{E}_{\Xi}$ denote the set of
assignable equilibria of (2), and given $\bar{x}\in\mathcal{E}_{\Xi}$, let
$\bar{u}=k_{u}(\bar{x}):=-(G^{\top}G)^{-1}G^{\top}f(\bar{x})$ and
$\bar{y}=h(\bar{x})$ be the equilibrium input and output.

###### Definition 5

The system (2) is _equilibrium-independent passive_ if, for every equilibrium
$\bar{x}$, there exists a continuously-differentiable storage function
$V^{\bar{x}}:\mathbb{R}^{n}\rightarrow\mathbb{R}_{\geq 0}$ such that

$\displaystyle\nabla
V^{\bar{x}}(x)^{\top}(f(x)+Gu)\leq(y-\bar{y})^{\top}(u-\bar{u})$ (3)

where $\bar{u}$ and $\bar{y}$ are the steady-state input and output at
$\bar{x}$. A set of storage functions
$\\{V^{\bar{x}}(x),\bar{x}\in\mathcal{E}_{\Xi}\\}$ satisfying (3) is an _EIP
storage function family_.

###### Definition 6

The system (2) is _equilibrium-independent observable_ if, for every
$\bar{x}\in\mathcal{E}_{\Xi}$ with associated equilibrium input/output vectors
$\bar{u}=k_{u}(\bar{x})$ and $\bar{y}=h(\bar{x})$, no trajectory of
$\dot{x}=f(x)+G\bar{u}$ can remain within the set
$\\{x\in\mathbb{R}^{n}:h(x)=\bar{y}\\}$ other than the equilibrium trajectory
$x(t)=\bar{x}$.

###### Lemma 3

If the system (2) is equilibrium-independent observable then for a given
equilibrium I/O pair $(\bar{u},\bar{y})$, there is exactly one
$\bar{x}\in\mathcal{E}_{\Sigma}$ satisfying $\bar{u}=k_{u}(\bar{x})$ and
$\bar{y}=h(\bar{x})$.

###  II-C Graph Theory

The following is from [22]. An undirected graph
$\mathcal{G}=(\mathcal{I},\mathcal{E})$ is a set of vertices,
$\mathcal{I}=\\{1,\dots,N\\}$, and edges,
$\mathcal{E}\subset\mathcal{I}\times\mathcal{I}$. $(i,j)\in\mathcal{E}$ means
that vertex $j$ can receive information from vertex $i$. Let $\mathcal{G}$ be
assumed to be undirected so that $(i,j)\in\mathcal{E}$ if and only if
$(j,i)\in\mathcal{E}$ for all $i,j\in\mathcal{I}$. The adjacency matrix
$\boldsymbol{A}=[a_{ij}]\in\mathbb{R}^{N\times N}$ of $\mathcal{G}$ is defined
by $a_{ij}=1$ if $(j,i)\in\mathcal{E}$ and $a_{ij}=0$ otherwise. Since
$\mathcal{G}$ is undirected $\boldsymbol{A}=\boldsymbol{A}^{\top}$.
$\mathcal{G}$ is connected if given any $i,j\in\mathcal{I}$, there is a path
connecting them. Let $\mathcal{N}_{i}$ denote the neighbours of vertex $i$ and
let $D=\operatorname{diag}(|\mathcal{N}_{i}|)_{i\in\mathcal{I}}$. The
Laplacian of $\mathcal{G}$ is defined as $L=D-\boldsymbol{A}$.

##  III Problem Formulation

In this work, we consider a set of $N$ agents (players)
$\mathcal{I}=\\{1,\dots,N\\}$ in a generalized game. Each agent controls its
action $y_{i}\in\mathbb{R}^{m_{i}}$ and attempts to minimize a cost function
$\mathcal{J}_{i}$ subject to shared, (possibly) coupled inequality constraints
$g(y)\leq 0$, $g:\mathbb{R}^{m}\rightarrow\mathbb{R}^{p}$, where
$y=\operatorname{col}(y_{i})_{i\in\mathcal{I}}\in\mathbb{R}^{m}$,
$m=\sum_{i\in\mathcal{I}}m_{i}$. This gives the following for each
$i\in\mathcal{I}$:

$\displaystyle\begin{split}\min_{y_{i}}\quad&\mathcal{J}_{i}(y_{i},y_{-i})\\\
\operatorname{s.t.}\quad&g(y)\leq 0\end{split}$ (4)

where $y_{-i}=\operatorname{col}(y_{1},\dots,y_{i-1},y_{i+1},\dots,y_{N})$,
all agents actions except for agent $i$’s.

###### Definition 7

A _generalized Nash equilibrium_ (GNE) of (4) is a strategy profile $y^{*}$
satisfying

$\displaystyle
y_{i}^{*}\in\operatorname*{arg\,min}_{z_{i}}\mathcal{J}_{i}(z_{i},y^{*}_{-i})\
\text{s.t.}\ g(z_{i},y^{*}_{-i})\leq 0,\quad\forall i\in\mathcal{I}$

###### Assumption 1

The cost function of each agent, $\mathcal{J}_{i}(y_{i},y_{-i})$, is convex
and continuously-differentiable in $y_{i}$, for each fixed $y_{-i}$, $g(y)$ is
component-wise convex and $C^{2}$ in $y$, either all $g_{\ell}(y)$ are affine
or at least one $g_{\ell}(y)$ is strictly-convex, where $g_{\ell}(y)$ is the
$\ell^{\text{th}}$ component of $g(y)$, and the feasible set
$\Omega=\\{y\in\mathbb{R}^{m}:g(y)\leq 0\\}$ is non-empty, convex, compact and
satisfies Slater’s constraint qualification.

Let the stacked vector of partial gradients of all cost functions, called the
pseudo-gradient, be denoted as

$\displaystyle
F(y):=\operatorname{col}(\nabla_{i}\mathcal{J}_{i}(y_{i},y_{-i}))_{i\in\mathcal{I}},$
(5)

where
$\nabla_{i}\mathcal{J}_{i}(y_{i},y_{-i})\\!=\\!\frac{\partial\mathcal{J}_{i}(y_{i},y_{-i})}{\partial
y_{i}}^{\top}\\!$.

A specific type of GNE is the so-called variational-GNE (vGNE). Under
Assumption 1, from Theorem 4.8 in [23], $y^{*}$ is a vGNE if and only if there
exist a dual variable $\lambda^{*}\in\mathbb{R}^{p}$ such that the KKT
conditions hold:

$\displaystyle\begin{split}&F(y^{*})+\sum_{\ell=1}^{p}\lambda_{\ell}^{*}\nabla
g_{\ell}(y^{*})=0\\\ &\lambda_{\ell}^{*}\geq 0\\\ &-g_{\ell}(y^{*})\geq
0,\qquad\forall\ell=1,\dots,p\\\
&-\lambda_{\ell}^{*}g_{\ell}(y^{*})=0\end{split}$ (6)

A vGNE has the interpretation of no price-discrimination among the agents,
that is, all agents are penalized equally for constraint violation.

###### Assumption 2

The pseudo-gradient $F(y)$ is Lipschitz continuous, i.e.,
$\|F(y)-F(y^{\prime})\|\leq\theta_{1}\|y-y^{\prime}\|$ for $\theta_{1}>0$, for
all $y,y^{\prime}\in\mathbb{R}^{m}$, and is either

  1. a)

strictly-monotone, i.e.,
$(y\\!-\\!y^{\prime})^{\top}\\!(F(y)\\!-\\!F(y^{\prime}))\\!\\!>0$ for all
$y\neq y^{\prime}\in\mathbb{R}^{m}$, or

  2. b)

strongly-monotone, i.e.,
$(y\\!-\\!y^{\prime})^{\top}\\!(F(y)\\!-\\!F(y^{\prime}))\\!\geq\\!\frac{\mu}{2}\\!\|y\\!-\\!y^{\prime}\|^{2}$
for $\mu>0$ and for all $y,y^{\prime}\in\mathbb{R}^{m}$.

Assumptions 1 and 2 are standard assumptions that guarantee existence and
uniqueness of a vGNE and are commonly used to show convergence, see, e.g., [5]
or [8]. Under Assumptions 1 and 2, by Cor. 2.2.5 and Thm. 2.3.3 from [24], the
GNE problem (4) has a unique variational-GNE.

Our goal is to design a GNE seeking algorithm in continuous-time that
satisfies the constraint $g(y)\leq 0$ for all time. Inspired by interior-point
methods, we consider solving problem (4) using inexact penalty functions.
Thus, consider transforming the GNE problem into an NE seeking problem given
by the following set of unconstrained programs:

$\displaystyle\min_{y_{i}}\quad$
$\displaystyle\mathcal{J}_{i}(y_{i},y_{-i})+\phi(y),\quad\forall
i\in\mathcal{I}$ (7)

where $\phi(y)$ is the so-called log-barrier function

$\displaystyle\phi(y)=\begin{cases}-\rho\sum_{\ell=1}^{p}\log(-g_{\ell}(y)),\quad&g(y)<0\\\
+\infty,&\text{else}\end{cases}$ (8)

where $\rho>0$. Note that under Assumption 1, $\phi(y)$ is strictly-convex and
$C^{2}$ in $y$ on $\operatorname{int}\Omega=\\{y\in\mathbb{R}^{m}:g(y)<0\\}$
and thus $\nabla\phi(y)$ is locally Lipschitz on $\operatorname{int}\Omega$.

Under Assumptions 1-2, by Cor. 4.3 from [25] and Thm. 3 from [26], the NE
problem (7) has a unique solution $y^{*}$. Moreover, $y^{*}$ satisfies

$\displaystyle F(y^{*})+\nabla\phi(y^{*})=0$ (9)

where $\nabla\phi$ is the gradient of $\phi$. Following from Section 11.2.2 in
[17], since $\phi(y)$ is the log-barrier function, (9) becomes

$\displaystyle F(y^{*})+\sum_{\ell=1}^{p}\frac{\rho}{-g_{\ell}(y^{*})}\nabla
g_{\ell}(y^{*})=0$

By letting $\lambda_{\ell}^{*}(\rho):=\frac{\rho}{-g_{\ell}(y^{*})}$, we get
the following conditions

$\displaystyle F(y^{*})+\sum_{\ell=1}^{p}\lambda_{\ell}^{*}(\rho)\nabla
g_{i}(y^{*})=0$ $\displaystyle\lambda_{\ell}^{*}(\rho)\geq 0$ $\displaystyle-
g_{\ell}(y^{*})\geq 0,\qquad\quad\forall l=1,p$
$\displaystyle-\lambda_{\ell}^{*}(\rho)g_{\ell}(y^{*})=\rho$

and as $\rho\\!\rightarrow\\!0$, we recover (6). Thus the NE of (7) is an
approximate vGNE of (4). Moreover, it is an $\varepsilon$-GNE of (4).

###### Definition 8

A _generalized_ $\varepsilon$-_Nash equilibrium_ ($\varepsilon$-GNE) of (4) is
a strategy profile $y^{*}$ satisfying

$\displaystyle\mathcal{J}_{i}(y^{*}_{i},y^{*}_{-i})\\!\leq\\!\inf_{y_{i}}\\{\mathcal{J}_{i}(y_{i},y_{-i}^{*})\\!+\\!\varepsilon:g(y_{i},y_{-i}^{*})\\!\leq\\!0\\},\,\,\forall
i\in\mathcal{I}$

for $\varepsilon>0$. When $\varepsilon=0$, $y^{*}$ is a GNE. Moreover, if the
dual variables are the same for each agent, we call $y^{*}$ an
$\varepsilon$-vGNE.

###### Lemma 4

The NE of (7) is an $\varepsilon$-vGNE of (4) with $\varepsilon=p\rho$.

###### Proof:

Consider the dual function, $h_{i}$, of (4) for agent $i$ evaluated at the NE
of $\eqref{eq:NE}$ $y^{*}$ and $\lambda^{*}(\rho)$ as above,

$\displaystyle h_{i}(\lambda^{*}(\rho))$
$\displaystyle=\mathcal{J}_{i}(y_{i}^{*},y_{-i}^{*})+\sum_{\ell=1}^{p}\lambda_{\ell}^{*}(\rho)g_{\ell}(y^{*})$
$\displaystyle=\mathcal{J}_{i}(y_{i}^{*},y_{-i}^{*})-p\rho$

By properties of the dual function, Section 5.1.3 in [17],

$\displaystyle\mathcal{J}_{i}(y_{i}^{*},y_{-i}^{*})-p\rho\leq\inf_{y_{i}}\\{\mathcal{J}_{i}(y_{i},y_{-i}^{*}):g(y_{i},y_{-i}^{*})\leq
0\\}$

Therefore,

$\displaystyle\mathcal{J}_{i}(y_{i}^{*},y_{-i}^{*})\leq\inf_{y_{i}}\\{\mathcal{J}_{i}(y_{i},y_{-i}^{*})+p\rho:g(y_{i},y_{-i}^{*})\leq
0\\}$

Since this holds for all $i\in\mathcal{I}$, $y^{*}$ is an $\varepsilon$-GNE of
(4) with $\varepsilon=p\rho$. Moreover, the dual variables,
$\lambda_{\ell}^{*}(\rho)$ are the same for all agents. Therefore $y^{*}$ is
an $\varepsilon$-vGNE. ∎

##  IV Full-Information Gradient Feedback

We consider GNE seeking for a class of passive nonlinear agents with dynamics
of the form

$\displaystyle\mathcal{P}_{i}:\begin{cases}\dot{x}_{i}=f_{i}(x_{i})+G_{i}u_{i}\\\
y_{i}=G_{i}^{\top}\nabla V_{i}(x_{i}).\end{cases}$ (10)

where $x_{i}\in\mathbb{R}^{n_{i}}$ is the state of agent $i$,
$u_{i}\in\mathbb{R}^{m_{i}}$ is agent $i$’s input, and the output
$y_{i}\in\mathbb{R}^{m_{i}}$ of $\mathcal{P}_{i}$ is the action of agent $i$.
In this section, we assume that each agent $i$ has full-knowledge of all other
agents’ actions, $y_{-i}$, but no knowledge of their states, $x_{j}$, or cost
functions, $\mathcal{J}_{j}$, for $j\neq i$. This is what we call the
_full-(decision) information_ case.

###### Assumption 3

$\mathcal{P}_{i}$ satisfies the following:

  1. a)

$f_{i}(x_{i})$ is Lipschitz continuous,

  2. b)

(10) is equilibrium independent observable,

  3. c)

$G_{i}$ is full column-rank,

  4. d)

there exists a map $\pi_{i}:\mathbb{R}^{m_{i}}\rightarrow\mathbb{R}^{n_{i}}$
that solves the regulator equations for any $\bar{y}_{i}\in\mathbb{R}^{m_{i}}$

$\displaystyle 0$ $\displaystyle=f_{i}(\pi_{i}(\bar{y}_{i}))$ $\displaystyle
0$ $\displaystyle=G_{i}^{\top}\nabla V_{i}(x_{i})-\bar{y}_{i},$

i.e., any $\bar{y}_{i}\in\mathbb{R}^{m_{i}}$ is an equilibrium output of (10)
with equilibrium input $\bar{u}_{i}=0$.

  5. e)

$V_{i}(x_{i})$ is a strongly convex function with $\nabla V_{i}(x_{i})$
Lipschitz continuous and the mapping $-f_{i}\circ\nabla V_{i}^{-1}$ is
monotone.

###### Remark 1

Under Assumption 3, by Corollary 3.6 in [21], (10) is equilibrium-independent
passive with storage function family
$\\{V^{\bar{x}}(x),\bar{x}\in\mathcal{E}_{\mathcal{P}_{i}}\\}$, where

$\displaystyle V_{i}^{\bar{x}_{i}}(x_{i}):=V_{i}(x_{i})-V(\bar{x}_{i})-\nabla
V_{i}(\bar{x}_{i})^{\top}(x_{i}-\bar{x}_{i}).$

Three examples of systems that can meet Assumption 3 are:

  1. i)

Integrators

$\displaystyle\dot{y}_{i}=u_{i},$ (11)

  2. ii)

PI controllers in cascade with certain stable linear systems

$\displaystyle\begin{split}&\dot{x}_{i}=\begin{bmatrix}-v_{i}I&k_{i}I\\\
0&0\end{bmatrix}x_{i}+\begin{bmatrix}I\\\ I\end{bmatrix}u_{i}\\\
&y_{i}=\begin{bmatrix}I&0\end{bmatrix}x_{i},\end{split}$ (12)

where $0<k_{i}<v_{i}$, and

By stacking the plant dynamics (10), we get

$\displaystyle\mathcal{P}:\begin{cases}\dot{x}=f(x)+Gu\\\ y=G^{\top}\nabla
V(x).\end{cases}$ (13)

where $x\\!=\\!\operatorname{col}(x_{i})_{i\in\mathcal{I}}$,
$u\\!=\\!\operatorname{col}(u_{i})_{i\in\mathcal{I}}$,
$y\\!=\\!\operatorname{col}(y_{i})_{i\in\mathcal{I}}$,
$f(x)\\!=\\!\operatorname{col}(f_{i}(x_{i}))_{i\in\mathcal{I}}$,
$G\\!=\\!\operatorname{blkdiag}(G_{i})_{i\in\mathcal{I}}$ and $\nabla
V\\!=\\!\operatorname{col}(\nabla V_{i}(x_{i}))_{i\in\mathcal{I}}$.

###### Remark 2

It can be easily verified that (13) satisfies

  1. a)

$f(x)$ is Lipschitz continuous,

  2. b)

(13) is equilibrium-independent observable,

  3. c)

$G$ is full column-rank,

  4. d)

the map $\pi:\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$,
$\pi(x)=\operatorname{col}(\pi_{i}(x_{i}))_{i\in\mathcal{I}}$ solves the
regulator equations for any $\bar{y}\in\mathbb{R}^{m}$

$\displaystyle 0$ $\displaystyle=f(\pi(\bar{y}))$ $\displaystyle 0$
$\displaystyle=G^{\top}\nabla V(x)-\bar{y},$

i.e., any $\bar{y}\in\mathbb{R}^{m}$ is a steady-state output of (10) with
steady-state input $\bar{u}=0$.

  5. e)

(13) is equilibrium independent observable with strongly convex storage
function family

$\displaystyle V^{\bar{x}}(x):=V(x)-V(\bar{x})-\nabla
V(\bar{x})^{\top}(x-\bar{x})$

where $V(x)=\sum_{i\in\mathcal{I}}V_{i}(x_{i})$.

We consider solving GNE seeking (4) for (13) by converting the problem into
(7). In the full-(decision) information case, we consider a static partial-
gradient feedback. Thus, agent $i$ with $\mathcal{P}_{i}$ (10) takes

$\displaystyle u_{i}=-\nabla_{i}\mathcal{J}_{i}(y)-\nabla_{i}\phi(y).$ (14)

where $\nabla_{i}\phi(y)=\frac{\partial\phi(y)}{\partial y_{i}}^{\top}$. For
all agents, from $\mathcal{P}$ (13) with $u\\!=-\\!F(y)-\nabla\phi(y)$, this
leads to an overall stacked dynamics,

$\displaystyle\Sigma:\begin{cases}\dot{x}=f(x)-G(F(y)+\nabla\phi(y))=:q(x)\\\
y=G^{\top}\nabla V(x)\end{cases}$ (15)

###### Remark 3

In the absence of constraints (no penalty), the dynamics (15) capture a number
of previously investigated NE seeking algorithms. If each $\mathcal{P}_{i}$ is
taken to be an integrator (11), then gradient-play

$\displaystyle\Sigma:\quad\dot{y}+F(y)=0$

is recovered [18]. If instead, each $\mathcal{P}_{i}$ is governed by (12),
then the dynamics become the following second-order method investigated in the
optimization literature

$\displaystyle\Sigma:\quad\ddot{y}+\Big{(}\mathcal{V}+\frac{\partial
F(y)}{\partial y}\Big{)}\dot{y}+KF(y)=0$

where $\mathcal{V}=\operatorname{blkdiag}(v_{i}I)_{i\in\mathcal{I}}$ and
$K=\operatorname{blkdiag}(k_{i}I)_{i\in\mathcal{I}}$. See, e.g., [27]-[28].

Next, we investigate the behaviour of (15) and show that not only do the
solutions converge to an equilibrium corresponding to the output being the NE,
but that the solutions satisfy the output constraints for all time. First, we
investigate the equilibria of (15).

###### Lemma 5

Under Assumptions 1, 2 and 3, $x^{*}=\pi(y^{*})$ is the unique equilibrium
point of (15) with $y^{*}$ as in (9), the NE of (7) and $\varepsilon$-vGNE of
(4).

###### Proof:

See Appendix -A. ∎

In order to show that the constraints are satisfied for all time, we look at
positive-invariance of sub-level sets of the form
$S\\!=\\!\\{x\\!\in\\!\mathbb{R}^{n}:V^{x^{*}}(x)\\!-\\!c\\!\leq\\!0,\phi^{x^{*}}(x)\\!-\\!d\\!\leq\\!0\\}$
for $c,d>0$, where $x^{*}\\!=\\!\pi(y^{*})$ and
$\phi^{x^{*}}(x)\\!:=\\!\phi(G^{\top}\nabla V(x))\\!-\\!\phi(G^{\top}\nabla
V(x^{*}))\\!-\\!\nabla\phi(G^{\top}\nabla V(x^{*}))^{\top}(G^{\top}\nabla
V(x)\\!-\\!G^{\top}\nabla V(x^{*}))$, related to the Bregman divergence of
$\phi(y)$. The interior of these sets corresponds to the output satisfying the
constraints. The following lemma shows that $S$ is a practical set.

###### Lemma 6

Under Assumption 3, $S=\\{x\in\mathbb{R}^{n}:V^{x^{*}}(x)-c\leq
0,\phi^{x^{*}}(x)-d\leq 0\\}$ is a compact, practical set for all $c,d>0$.

###### Proof:

See Appendix -B. ∎

###### Remark 4

With LTI agents as in [19], sets of the form $S$ are convex with non-empty
interior. Thus practicality follows trivially. In potential games, as in [16],
the sublevel sets of the potential function are positively invariant under
gradient feedback and thus constraint satisfaction also follows trivially.

###### Lemma 7

Under Assumptions 1, 2(a) and 3, the set
$\operatorname{int}\Omega=\\{y:g(y)<0\\}$ is output-positively-invariant for
the dynamics (15). That is, for all $x(0)$ such that
$y(0)\in\operatorname{int}\Omega$, $y(t)\in\operatorname{int}\Omega$ for all
$t\geq 0$, i.e., the output constraints are satisfied for all time.

###### Proof:

We show that for each $x(0)$ such that $y(0)=G^{\top}\nabla V(x(0))$, there
exists $c,d>0$ such that $x(0)\in S=\\{x\in\mathbb{R}:V^{x^{*}}(x)-c\leq
0\\}\cap\\{x\in\mathbb{R}:\phi^{x^{*}}(x)-d\leq 0\\}$, where $x^{*}$ as in
Lemma 5, and $S$ is positively invariant.

First, consider the Lie derivatives of $V^{x^{*}}(x)$ and $\phi^{x^{*}}(x)$ on
$\partial S$ along the solutions of (15). There are two cases:

  1. 1.

$V^{x^{*}}(x)=c$ and $\phi^{x^{*}}(x)\leq d$

In this case, we consider the Lie derivative of $V^{x^{*}}$ along the
solutions of (15). By equilibrium-independent passivity of (13), we have

$\displaystyle
L_{q}V^{x^{*}}\leq-(y\\!-\\!y^{*})^{\top}u=-(y\\!-\\!y^{*})^{\top}(F(y)\\!+\\!\nabla\phi(y)).$

Using (9), $F(y)$ monotone and $\phi(y)$ convex, we have

$\displaystyle L_{q}V^{x^{*}}$
$\displaystyle\leq-(y\\!-\\!y^{*})^{\top}(F(y)\\!-\\!F(y^{*})+\nabla\phi(y)\\!-\\!\nabla\phi(y^{*}))$
$\displaystyle\leq 0.$

  2. 2.

$V^{x^{*}}\leq c$ and $\phi^{x^{*}}(x)=d$

We take the Lie derivative of $\phi^{x^{*}}(x)$ along the solutions of (15),
giving

$\displaystyle L_{q}\phi^{x^{*}}=$
$\displaystyle(\nabla\phi(y)\\!-\\!\nabla\phi(y^{*}))^{\top}G^{\top}\nabla^{2}V(x)^{\top}[f(x)\\!-\\!G(F(y)$
$\displaystyle+\nabla\phi(y))]$ $\displaystyle=$
$\displaystyle(\nabla\phi(y)\\!-\\!\nabla\phi(y^{*}))^{\top}G^{\top}\nabla^{2}V(x)^{\top}[f(x)-f(x^{*})$
$\displaystyle-G(F(y)-F(y^{*})+\nabla\phi(y)-\nabla\phi(y^{*}))].$

By Assumption 3(c) and (e), $G^{\top}\nabla^{2}V(x)G\succeq\alpha I$ for some
$\alpha>0$. Then, we can get

$\displaystyle L_{q}\phi^{x^{*}}\leq$
$\displaystyle\|\nabla\phi(y)\\!-\\!\nabla\phi(y^{*})\|\Big{[}\|G^{\top}\nabla^{2}V(x)\|$
$\displaystyle\|f(x)\\!-\\!f(x^{*})\|+\|G^{\top}\nabla^{2}V(x)G\|$
$\displaystyle\|F(y)-F(y^{*})\|-\alpha\|\nabla\phi(y)-\nabla\phi(y^{*})\|\Big{]}.$

Since $V^{x^{*}}<c$ and $V^{x^{*}}$ strongly convex, we have $\|x-x^{*}\|\leq
c_{1}$, for some $c_{1}$. Since $f(x)$ and $\nabla V(x)$ are Lipschitz
continuous, we have $\|f(x)-f(x^{*})\|\leq\theta_{3}\|x-x^{*}\|$ and
$\|G^{\top}\nabla V^{2}(x)\|\leq\theta_{4}$, for some $\theta_{3},\theta_{4}$.
Since $F(y)$ is Lipschitz continuous, we have
$\|F(y)-F(y^{*})\|\leq\theta_{1}\|y-y^{*}\|\leq\theta_{1}\theta_{4}\|x-x^{*}\|\leq
c_{1}\theta_{1}\theta_{4}$. Therefore,

$\displaystyle L_{q}\phi^{x^{*}}$
$\displaystyle\leq\|\nabla\phi(y)-\nabla\phi(y^{*})\|\Big{[}c_{1}\theta_{3}\theta_{4}+c_{1}\theta_{1}\theta_{4}^{2}\|G\|$
$\displaystyle\quad-\alpha\|\nabla\phi(y)-\nabla\phi(y^{*})\|\Big{]}$

By strict-convexity of $\phi^{x^{*}}(x)$, we have that
$\|\nabla\phi(y)-\nabla\phi(y^{*})\|\geq\frac{\phi^{x^{*}}(x)}{\|y-y^{*}\|}\geq\frac{d}{c_{1}\theta_{4}}$.
If we take $d\geq
d_{c}:=\frac{c_{1}\theta_{4}}{\alpha}[c_{1}\theta_{3}\theta_{4}+c_{1}\theta_{1}\theta_{4}^{2}\|G\|]$,
then $L_{q}V_{2}\leq 0$.

Since $S$ is a practical set by Lemma 6, by Lemma 2, $q(x)\in T_{S}(x)$ for
all $x\in\partial S$. In the interior of $S$, $q(x)\in
T_{S}(x)=\mathbb{R}^{n}$. Therefore, by Lemma 1, $S$ is positively invariant.
For all initial conditions $x(0)$ such that $y(0)\in\operatorname{int}\Omega$,
take $c\geq V^{x^{*}}(x(0))$ and $d\geq d_{c}$. Then $x(t)\in S$ for all
$t\geq 0$ and $y(t)\in\operatorname{int}\Omega$ for all $t\geq 0$ since for
all $x\in S$, $y=G^{\top}\nabla V(x)\in\operatorname{int}\Omega$. ∎

###### Theorem 1

Under Assumptions 1, 2(a) and 3, the equilibrium $x^{*}\\!=\\!\pi(y^{*})$ of
(15), where $y^{*}$ is the NE of (7) and $\varepsilon$-vGNE of (4), is
asymptotically stable. Moreover, if $y(0)\in\operatorname{int}\Omega$, then
the constraint $y(t)\in\Omega$ is satisfied for all $t\geq 0$.

###### Proof:

Take $V^{x^{*}}$ as the storage function of $\mathcal{P}$, where $x^{*}$ as in
Lemma 5. From equilibrium-independent passivity of (13), the derivative along
the solutions of (15) is

$\displaystyle\dot{V}^{x^{*}}$
$\displaystyle\leq-(y-y^{*})^{\top}u=-(y-y^{*})^{\top}(F(y)+\nabla\phi(y))$
$\displaystyle\leq-(y\\!-\\!y^{*})^{\top}(F(y)\\!-\\!F(y^{*})+\nabla\phi(y)\\!-\\!\nabla\phi(y^{*}))\leq
0$

and, by strict-monotonicity of $F(y)$ and convexity of $\phi(y)$, $\dot{V}=0$
if and only if $y=y^{*}$. By equilibrium independent observability of (10),
$x=x^{*}$ is asymptotically stable. By Lemma 7, if
$y(0)\in\operatorname{int}\Omega$, $y(t)\in\operatorname{int}\Omega$ for all
$t\geq 0$. ∎

##  V Partial-Information Gradient Feedback

Now, let’s assume that each agent has only partial-information of the actions
taken by the other players exchanged over an undirected, connected graph,
$\mathcal{G}_{c}$. For now, we assume that each agent has enough knowledge of
$g(y)$ in order to be able to compute its partial-gradient of the penalty
function exactly. This assumption is motivated by scenarios in which the
agents could have this knowledge:

  1. 1)

In the case of standard NE seeking, each agents constraints depend only on its
own action, i.e., $g(y)=\operatorname{col}(g_{1}(y_{1}),\dots,g_{M}(y_{M}))$,

  2. 2)

If each agent’s constraint set depends only on the actions of its neighbours
in the communication graph, $\mathcal{G}_{c}$, or

  3. 3)

If each agent can measure the constraint independently from the other agents.

In Section VI, we relax this assumption.

For the individual actions, assume that each agent $i$ maintains an estimate,
$\textbf{y}_{j}^{i}$, of the action of each agent $j$ and uses these to
evaluate the partial-gradient of its original cost function instead of the
true actions. Let
$\textbf{y}_{-i}^{i}:=\operatorname{col}(\textbf{y}_{1}^{i},\dots,\textbf{y}_{i-1}^{i},\textbf{y}_{i+1}^{i},\dots,\textbf{y}_{i-1}^{i})$
and
$\textbf{y}^{i}:=\operatorname{col}(\textbf{y}_{1}^{i},\dots,\textbf{y}_{i-1}^{i},y_{i},\textbf{y}_{i+1}^{i},\dots,\textbf{y}_{i-1}^{i})$.
Stacking the actions and estimates, we get
$\textbf{y}_{-i}:=\operatorname{col}(\textbf{y}_{-1}^{1},\dots,\textbf{y}_{-N}^{N})$,
the estimates only, and
$\textbf{y}:=\operatorname{col}(\textbf{y}^{1},\dots,\textbf{y}^{N})$, the
stacked actions and estimates. These actions and estimates are then be
exchanged over a communication graph, $\mathcal{G}_{c}$ with Laplacian $L$,
using a proportional consensus algorithm.

###### Assumption 4

The graph $\mathcal{G}_{c}$ is undirected and connected.

Let matrices $\mathcal{R}_{i}$, $\mathcal{S}_{i}$ for action and estimates
selection be,

$\displaystyle\begin{split}\mathcal{R}_{i}&:=\begin{bmatrix}0_{m_{i}\times
m_{<i}}&I_{m_{i}}&0_{m_{i}\times m_{>i}}\end{bmatrix}\\\
\mathcal{S}_{i}&:=\begin{bmatrix}I_{m_{<i}}&0_{m_{<i}\times
m_{i}}&0_{m_{<i}\times m_{>i}}\\\ 0_{m_{>i}\times m_{<i}}&0_{m_{>i}\times
m_{i}}&I_{m_{>i}}\end{bmatrix}\end{split}$ (16)

with $m_{<i}:=\sum_{j<i\ j,i\in\mathcal{I}}m_{j}$ and $m_{>i}:=\sum_{j>i\
j,i\in\mathcal{I}}m_{j}$. Note that $y_{i}=\mathcal{R}_{i}\textbf{y}^{i}$ and
$\textbf{y}_{-i}^{i}=\mathcal{R}_{i}\textbf{y}^{i}$.

Inspired by [18], instead of (14), we consider that each agent (10) uses the
following dynamic feedback

$\displaystyle\begin{split}\dot{\textbf{y}}_{-i}^{i}&=-\mathcal{S}_{i}\sum_{j\in\mathcal{N}_{i}}(\textbf{y}^{i}-\textbf{y}^{j})\\\
u_{i}&=-\nabla_{i}\mathcal{J}(y_{i},\textbf{y}^{i}_{-i})-\nabla_{i}\phi(y)-\mathcal{R}_{i}\sum_{j\in\mathcal{N}_{i}}(\textbf{y}^{i}-\textbf{y}^{j})\end{split}$
(17)

where $\textbf{L}=L\otimes I$ and $\nabla_{i}\phi(y)$ can be computed using
the information available to each agent. Note that (17) has a gradient-play
term (evaluated at estimates) and penalty term, as well as a dynamic
Laplacian-based estimate-consensus component $\textbf{y}_{-i}^{i}$ which, in
steady state, should bring all $\textbf{y}^{i}$ to consensus. We call the
stacked vector of partial gradients evaluated at estimates
$\textbf{F}(\textbf{y}):=\operatorname{col}(\nabla_{i}\mathcal{J}(y_{i},\textbf{y}^{i}_{-i}))_{i\in\mathcal{I}}$,
the extended-pseudo-gradient. Note that $\textbf{F}(\textbf{1}\otimes y)=F(y)$
for all $y\in\mathbb{R}^{m}$. By Lemma 3 from [8], under Assumption 2(b), the
extended pseudo-gradient is Lipschitz continuous,
$\|\textbf{F}(\textbf{y})-\textbf{F}(\textbf{y}^{\prime})\|\leq\theta_{2}\|\textbf{y}-\textbf{y}^{\prime}\|$
for all $\textbf{y},\textbf{y}^{\prime}\in\mathbb{R}^{M}$, $M=Nm$, for
$\mu\leq\theta_{2}\leq\theta_{1}$.

From (10) and (17), this gives overall stacked dynamics of

$\displaystyle\Sigma:\begin{cases}\dot{\textbf{y}}_{-i}=-\mathcal{S}\textbf{L}\textbf{y}=:\boldsymbol{f}_{1}(\textbf{x})\\\
\dot{x}=f(x)\\!-\\!G(\textbf{F}(\textbf{y})\\!+\\!\nabla\phi(y)\\!+\\!\mathcal{R}\textbf{L}\textbf{y})\\!=:\\!\boldsymbol{f}_{2}(\textbf{x})\\\
y=G^{\top}\nabla V(x)\end{cases}$ (18)

where $\textbf{x}=\operatorname{col}(\textbf{y}_{-i},x)$,
$\mathcal{R}=\operatorname{blkdiag}(\mathcal{R}_{i})_{i\in\mathcal{I}}$ and
$\mathcal{S}=\operatorname{blkdiag}(\mathcal{S}_{i})_{i\in\mathcal{I}}$. Let
$\boldsymbol{f}(\textbf{x}):=\operatorname{col}(\boldsymbol{f}_{1}(\textbf{x}),\boldsymbol{f}_{2}(\textbf{x}))$.
The unique equilibrium point of (18) is
$(\bar{\textbf{y}}_{-i},x^{*})=(\mathcal{S}\textbf{1}_{N}\otimes
y^{*},\pi(y^{*}))$, where $y^{*}$ is the NE of (7) and $\epsilon$-vGNE of (4).
We denote $\bar{\textbf{y}}=\textbf{1}_{N}\otimes y^{*}$.

###### Remark 5

It is important to note that in the extended space, F is not monotone which
was critical in the proof of Theorem 1. As such, we need to use different
analyses to examine the behaviour of (18).

###### Lemma 8

Under Assumptions 1, 2(b), 3 and 4,
$(\textbf{y}_{-i},x)=(\mathcal{S}\textbf{1}_{N}\otimes y^{*},\pi(x^{*}))$ is
the unique equilibrium of (18).

###### Proof:

See Appendix -C. ∎

We show output-positive invariance but showing positive invariance of the
sublevel sets of two functions:

$\displaystyle\textbf{V}^{\bar{\textbf{x}}}(\textbf{x})$
$\displaystyle:=\frac{1}{2}\|\textbf{y}_{-i}-\bar{\textbf{y}}_{-i}\|^{2}+V^{x^{*}}(x)$
$\displaystyle\boldsymbol{\phi}^{\bar{\textbf{x}}}(\textbf{x})$
$\displaystyle:=\phi^{x^{*}}(x)$

First, we show that the intersection of their sub-level sets forms a practical
set.

###### Lemma 9

Under Assumption 3,
$\textbf{S}=\\{\textbf{x}\in\mathbb{R}^{M-m+n}:\textbf{V}^{\bar{\textbf{x}}}(\textbf{x})-c\leq
0,\boldsymbol{\phi}^{\bar{\textbf{x}}}(\textbf{x})-d\leq 0\\}$ is a compact,
practical set for all $c,d>0$.

###### Proof:

By letting $\textbf{G}=\operatorname{col}(0,G)$, we have that
$y=\textbf{G}^{\top}\nabla\textbf{V}(\textbf{x})$. Additionally, since
$\textbf{V}(\textbf{x})$ is strongly-convex in x, the proof follows almost
identically to the proof of Lemma 6, replacing $x$ with x, $G$ with G,
$V^{x^{*}}(x)$ with $\textbf{V}^{\bar{\textbf{x}}}(\textbf{x})$ and
$\phi^{x^{*}}(x)$ with $\boldsymbol{\phi}^{\bar{\textbf{x}}}(\textbf{x})$ and
is thus omitted for the sake of brevity. ∎

###### Lemma 10

Under Assumptions 1, 2(b), 3 and 4, if
$\mu(\lambda_{2}(L)-\theta_{2})>\theta_{2}^{2}$, then the set
$\operatorname{int}\Omega=\\{y:g(y)<0\\}$ is output-positively-invariant for
the dynamics (18). That is, for all $x(0)$ such that
$y(0)\in\operatorname{int}\Omega$, $y(t)\in\operatorname{int}\Omega$ for all
$t\geq 0$, i.e., the output constraints are satisfied for all time.

###### Proof:

We show that for all $c>0$, there exists $d_{c}$ such that for all $d\geq
d_{c}$, S is positively invariant for (18). Then, for all
$(\textbf{y}_{-i}(0),x(0))$ such that $y(0)\in\operatorname{int}\Omega$, we
have that $(\textbf{y}_{-i}(t),x(t))\in S_{c}^{d}$ for some $c,d>0$ and
$y(t)\in\operatorname{int}\Omega$ for all $t\geq 0$. The proof is similar to
that of Lemma 7, however the fact that F is not monotone complicates the
analysis.

First, consider the Lie derivatives of
$\textbf{V}^{\bar{\textbf{x}}}(\textbf{x})$ and
$\boldsymbol{\phi}^{\bar{\textbf{x}}}(\textbf{x})$ along the solutions of
(15). There are two cases to check:

  1. 1.

$\textbf{V}^{\bar{\textbf{x}}}(\textbf{x})=c$ and
$\boldsymbol{\phi}^{\bar{\textbf{x}}}(\textbf{x})\leq d$

In this case, we consider the Lie derivative of $V$ along the solutions of
(18). By equilibrium-independent passivity of (13), we get

$\displaystyle L_{\boldsymbol{f}}\textbf{V}^{\bar{\textbf{x}}}$
$\displaystyle\leq-(\textbf{y}_{-i}-\bar{\textbf{y}}_{-i})^{\top}\mathcal{S}\textbf{L}\textbf{y}-(y-y^{*})^{\top}u$
$\displaystyle\leq-(\textbf{y}_{-i}-\bar{\textbf{y}}_{-i})^{\top}\mathcal{S}\textbf{L}\textbf{y}$
$\displaystyle\quad-(y-y^{*})^{\top}(\textbf{F}(\textbf{y})+\nabla\phi(y)+\mathcal{R}\textbf{L}\textbf{y}).$

Since $\textbf{F}(\bar{\textbf{y}})=F(y^{*})$, $F(y^{*})+\nabla\phi(y^{*})=0$
and $\textbf{L}\bar{\textbf{y}}=0$, we have

$\displaystyle L_{\boldsymbol{f}}\textbf{V}^{\bar{\textbf{x}}}$
$\displaystyle\leq-(\textbf{y}_{-i}-\bar{\textbf{y}}_{-i})^{\top}\mathcal{S}\textbf{L}(\textbf{y}-\bar{\textbf{y}})$
$\displaystyle\quad-(y-y^{*})^{\top}(\textbf{F}(\textbf{y})-\textbf{F}(\bar{\textbf{y}})+\nabla\phi(y)-\nabla\phi(y^{*}))$
$\displaystyle\quad-(y-y^{*})^{\top}\mathcal{R}\textbf{L}(\textbf{y}-\bar{\textbf{y}}).$

By monotonicity of $\nabla\phi(y)$ and that
$\mathcal{R}^{\top}y+\mathcal{S}^{\top}\textbf{y}_{-i}\\!=\\!\textbf{y}$,

$\displaystyle L_{\boldsymbol{f}}\textbf{V}^{\bar{\textbf{x}}}$
$\displaystyle\\!\leq-\\!(\textbf{y}\\!-\\!\bar{\textbf{y}})^{\top}\textbf{L}(\textbf{y}\\!-\\!\bar{\textbf{y}})\\!-\\!(\textbf{y}\\!-\\!\bar{\textbf{y}})^{\top}\mathcal{R}^{\top}(\textbf{F}(\textbf{y})\\!-\\!\textbf{F}(\bar{\textbf{y}})).$
(19)

If $\mu(\lambda_{2}(L)-\theta_{2})>\theta_{2}^{2}$, then by Theorem 2 in [18],
we have that $L_{\boldsymbol{f}}\textbf{V}^{\bar{\textbf{x}}}\leq 0$.

  2. 2.

$\textbf{V}^{\bar{\textbf{x}}}(\textbf{x})\leq c$ and
$\boldsymbol{\phi}^{\bar{\textbf{x}}}(\textbf{x})=d$

In the second case, we take the Lie derivative of
$\boldsymbol{\phi}^{\bar{\textbf{x}}}(\textbf{x})$ along the solutions of
(15), giving

$\displaystyle L_{\boldsymbol{f}}\boldsymbol{\phi}^{\bar{\textbf{x}}}$
$\displaystyle=(\nabla\phi(y)-\nabla\phi(y^{*}))^{\top}G^{\top}\nabla^{2}V(x)[f(x)$
$\displaystyle\quad-G(\textbf{F}(\textbf{y})+\nabla\phi(y)+\mathcal{R}\textbf{L}\textbf{y})].$

By Assumption 3 (c) and (e), we have that
$G^{\top}\nabla^{2}V(x)G\succeq\alpha I$ for some $\alpha\\!>\\!0$. Then, we
get

$\displaystyle L_{\boldsymbol{f}}\boldsymbol{\phi}^{\bar{\textbf{x}}}$
$\displaystyle=(\nabla\phi(y)-\nabla\phi(y^{*}))^{\top}G^{\top}\nabla^{2}V(x)[f(x)-f(x^{*})$
$\displaystyle\quad-G(\textbf{F}(\textbf{y})-\textbf{F}(\bar{\textbf{y}})+\nabla\phi(y)-\nabla\phi(y^{*})$
$\displaystyle\quad+\mathcal{R}\textbf{L}(\textbf{y}-\bar{\textbf{y}}))]$
$\displaystyle\leq\|\nabla\phi(y)\\!-\\!\nabla\phi(y^{*})\|\Big{[}\|G^{\top}\nabla^{2}V(x)\|\|f(x)\\!-\\!f(x^{*})\|$
$\displaystyle\quad+\|G^{\top}\nabla^{2}V(x)\|\|G\|(\|\textbf{F}(\textbf{y})-\textbf{F}(\bar{\textbf{y}})\|$
$\displaystyle\quad+\|\mathcal{R}\textbf{L}\|\|\textbf{y}-\bar{\textbf{y}}\|)-\alpha\|\nabla\phi(y)-\nabla\phi(y^{*})\|\Big{]}.$

Using similar arguments to those in the proof of Lemma 7, there exists $d_{c}$
such that for all $d\geq d_{c}$
$L_{\boldsymbol{f}}\boldsymbol{\phi}^{\bar{\textbf{x}}}\leq 0$.

Then, by Lemmas 9 and 2 for all $\textbf{x}\in\partial\textbf{S}$,
$\boldsymbol{f}(\textbf{x})\in T_{\textbf{S}}(\boldsymbol{x})$ and for
$\textbf{x}\in\operatorname{int}\textbf{S}$,
$\boldsymbol{f}(\textbf{x})\in\mathbb{R}^{M-m+n}=T_{\textbf{S}}(\boldsymbol{x})$.
Therefore, S is positively invariant by Lemma 1. For all initial conditions
$x(0)$ such that $y(0)\in\operatorname{int}\Omega$, take $c\geq
V(\textbf{y}_{-i}(0),x(0))$ and $d\geq d_{c}$. Then
$\textbf{x}(t)\in\textbf{S}$ for all $t\geq 0$ and
$y(t)\in\operatorname{int}\Omega$ for all $t\geq 0$. ∎

###### Theorem 2

Under Assumptions 1, 2(b), 3 and 4, if
$\mu(\lambda_{2}(L)-\theta_{2})>\theta_{2}^{2}$, then the equilibrium
$(\bar{\textbf{y}}_{-i},x^{*})=(\mathcal{S}\textbf{1}_{N}y^{*},\pi(y^{*}))$ of
(18), where $y^{*}$ is the NE of (7) and $\varepsilon$-vGNE of (4), is
asymptotically stable. Moreover, if $y(0)\in\operatorname{int}\Omega$, then
the constraint $y(t)\in\Omega$ is satisfied for all $t\geq 0$.

###### Proof:

Consider the Lyapunov candidate function
$V=\frac{1}{2}\|\textbf{y}_{-i}-\bar{\textbf{y}}_{-i}\|^{2}+V^{x^{*}}(x)$,
where $x^{*}=\pi(y^{*})$ as in Lemma 8. Taking the derivative along the
solutions of (18) yields as in (19),

$\displaystyle\dot{V}\leq-(\textbf{y}-\bar{\textbf{y}})^{\top}\textbf{L}(\textbf{y}-\bar{\textbf{y}})-(\textbf{y}-\bar{\textbf{y}})^{\top}\mathcal{R}^{\top}(\textbf{F}(\textbf{y})-\textbf{F}(\bar{\textbf{y}}))\
$

By Theorem 2 in [18], if $\mu(\lambda_{2}(L)-\theta_{2})>\theta_{2}^{2}$,
$\dot{V}\leq 0$ and $\dot{V}=0$ if and only if $\textbf{y}=\bar{\textbf{y}}$.
By equilibrium independent observability,
$(\textbf{y}_{-i},x)=(\bar{\textbf{y}}_{-i},x^{*})$ is asymptotically stable.
By Lemma 10, if $y(0)\in\operatorname{int}\Omega$,
$y(t)\in\operatorname{int}\Omega$ for all $t\geq 0$. ∎

##  VI Fully-Distributed Constraint Information

Next, we consider a partial-information feedback with fully-distributed
constraint information. Accordingly, each agent maintains estimates of all
other agents’ actions which are exchanged over a communication graph in the
same manner as (17) and uses these and an auxiliary variable in place of its
own action to compute the gradient of the penalty function. In order to
maintain constraint satisfaction, the communication and action updates occur
on two different time-scales.

We consider the following feedback law for dynamics (10),

$\displaystyle\begin{split}\epsilon\dot{z}_{i}&=y_{i}-z_{i}\\\
\epsilon\dot{\textbf{y}}_{-i}^{i}&=-\mathcal{S}_{i}\sum_{j\in\mathcal{N}_{i}}(\textbf{y}^{i}-\textbf{y}^{j})\\\
u_{i}&=-k\Big{[}\nabla_{i}\mathcal{J}(y_{i},\textbf{y}^{i}_{-i})+\nabla_{i}\phi(z_{i},\textbf{y}^{i}_{-i})]\end{split}$
(20)

where $k>0$ is a parameter to be chosen. Stacking these together yields

$\displaystyle\Sigma:$ $\displaystyle\begin{cases}\epsilon\dot{z}=y-z\\\
\epsilon\dot{\textbf{y}}_{-i}=-\mathcal{S}\textbf{L}\mathcal{S}^{\top}\textbf{y}_{-i}-\mathcal{S}\textbf{L}\mathcal{R}^{\top}y\\\
\dot{x}=f(x)\\!-\\!kG(\textbf{F}(y,\textbf{y}_{-i})\\!+\\!\boldsymbol{\Psi}(z,\textbf{y}_{-i}))\\\
y=G^{\top}\nabla V(x)\end{cases}$ (21)

where $z=\operatorname{col}(z_{i})_{i\in\mathcal{I}}$ and
$\boldsymbol{\Psi}(z,\textbf{y}_{-i})=\operatorname{col}(\nabla_{i}\phi(z_{i},\textbf{y}^{i}_{-i}))_{i\in\mathcal{I}}$.

###### Assumption 5

For each $\mathcal{P}_{i}$, for every $\bar{x}_{i}$, $V_{i}^{\bar{x}}$
satisfies

$\displaystyle\underline{\omega}_{i}\|x_{i}-\bar{x}_{i}\|^{2}\leq
V_{i}^{\bar{x}_{i}}$
$\displaystyle\leq\bar{\omega}_{i}\|x_{i}-\bar{x}_{i}\|^{2}$
$\displaystyle(\nabla V_{i}^{\bar{x}_{i}})^{T}(f_{i}(x_{i})+G_{i}u_{i})$
$\displaystyle\leq-\alpha_{i}\|x_{i}-\bar{x}_{i}\|^{2}+\beta_{i}\|y_{i}-\bar{y}_{i}\|^{2}$
$\displaystyle\quad+(y_{i}-\bar{y}_{i})^{\top}(u_{i}-\bar{u}_{i})$

for $\alpha_{i},\beta_{i},\underline{\omega}_{i},\bar{\omega}_{i}>0$.

###### Assumption 6

For each $\mathcal{P}_{i}$, $f_{i}(x_{i})$ is $C^{2}$ in $x_{i}$ and $V(x)$ is
$C^{3}$. Additionally, $\textbf{F}(y)$ is $C^{2}$ in its arguments.

###### Remark 6

Assumption 5 strengthens the EIP of Assumption 3 and is related to strict-
passivity and output-to-state stability. It guarantees that $\bar{x}_{i}$ can
rendered exponentially stable by a suitable static output feedback.

###### Remark 7

Systems (11) and (12), which satisfy Assumption 3, also satisfy Assumption 5
for any $\beta_{i}>0$.

###### Lemma 11

Under Assumptions 1 and 2(b) through 6, for every $x(0)\in\mathbb{R}^{n}$ such
that $y(0)=G^{\top}\nabla V(x(0))\in\operatorname{int}\Omega$ and for every
$(z(0),\textbf{y}_{-i}(0))\in
R_{y}^{x(0)}:=\\{(z,\textbf{y}_{-i}):\|z-y(0)\|^{2}+\|\textbf{y}_{-i}-\mathcal{S}\textbf{1}_{N}\otimes
y(0)\|^{2}\leq\gamma\\}$, where $\gamma>0$ is such $R_{y}^{x(0)}$ is a compact
subset of
$\Omega_{\textbf{y}}:=\\{(z,\textbf{y}_{-i}):g_{\ell}(z_{i},\textbf{y}_{-i}^{i})<0,\forall\ell,i\\}$,
there exists $\epsilon^{*}>0$ and $k^{*}>0$ such that for all
$0<\epsilon<\epsilon^{*}$ and $k\geq k^{*}$, $y(t)\in\operatorname{int}\Omega$
for all $t\geq 0$.

###### Proof:

First, we freeze $\epsilon=0$ and analyze the behaviours of the reduced system
and boundary layer system separately. Consider the boundary layer system. On
the fast time-scale, by treating $y$ as fixed and the change of coordinates
$z\mapsto\tilde{z}:=z-y$,
$\textbf{y}_{-i}\mapsto\tilde{\textbf{y}}_{-i}:=\textbf{y}_{-i}-\mathcal{S}\textbf{1}_{N}\otimes
y$, it becomes

$\displaystyle\begin{split}\frac{d\tilde{z}}{d\tau}&=-\tilde{z}\\\
\frac{d\tilde{\textbf{y}}_{-i}}{d\tau}&=-\mathcal{S}\textbf{L}\mathcal{S}^{\top}\tilde{\textbf{y}}_{-i}\end{split}$
(22)

The is an asymptotically stable linear system and thus
$(\tilde{z},\tilde{\textbf{y}}_{-i})=(0,0)$ is an exponentially stable
equilibrium point of (22). Next, consider the reduced system (21). By treating
$(z,\textbf{y}_{-i})=(y,\mathcal{S}\textbf{1}_{N}\otimes y)$, the $x$ dynamics
(21) become

$\displaystyle\begin{split}\dot{x}&=f(x)-kG(F(y)+\nabla\phi(y))\\\
y&=G^{\top}\nabla V(x)\end{split}$ (23)

similar to (15).

Consider the Lyapunov candidate function $V^{x^{*}}:=V(x)-V(x^{*})-\nabla
V(x^{*})^{\top}(x-x^{*})$, where $x^{*}=\pi(y^{*})$. Taking the derivative
along the solutions of (23), by Assumption 5,

$\displaystyle\begin{split}\dot{V}&\leq-\alpha\|x-x^{*}\|^{2}+\beta\|y-y^{*}\|^{2}+(y-y^{*})^{\top}u\\\
&\leq-\alpha\|x-x^{*}\|^{2}+\beta\|y-y^{*}\|^{2}\\\
&\quad-(y-y^{*})^{\top}(F(y)-F(y^{*})+\nabla\phi(y)-\nabla\phi(y^{*}))\\\
&\leq-\alpha\|x-x^{*}\|^{2}+\beta\|y-y^{*}\|^{2}-\\!k\mu\|y-y^{*}\|^{2}\end{split}$
(24)

where $\alpha=\min\\{\alpha_{i}:i\in\mathcal{I}\\}$ and
$\beta=\max\\{\beta_{i}:i\in\mathcal{I}\\}$. The last inequality follows from
strong-monotonicity of $F(y)+\nabla\phi(y)$. If $k\geq
k^{*}:=\frac{\beta}{\mu}$, then $\dot{V}\leq-\alpha\|x-x^{*}\|^{2}$. Thus, by
Theorem 4.10 in [29], $x=x^{*}$ is an exponentially stable equilibrium of
(23).

Second, for $\Sigma$ (21), we must check properties of
$f_{1}(z,\textbf{y}_{-i},x):=\operatorname{col}(-z+G^{\top}\nabla
V(x),-\mathcal{S}\textbf{L}\mathcal{S}\textbf{y}_{-i}-\mathcal{S}\textbf{L}\mathcal{R}^{\top}G^{\top}\nabla
V(x))$ and
$f_{2}(z,\textbf{y}_{-i},x):=f(x)-kG(\textbf{F}(y,\textbf{y}_{-i})+\boldsymbol{\Psi}(z,\textbf{y}_{-i}))$.
$f_{1}$ is $C^{1}$ and Lipschitz continuous in $(z,\textbf{y}_{-i},x)$ since
$\nabla V(x)$ is Lipschitz continuous and $C^{1}$. Therefore on any compact
subset of $\mathbb{R}^{M}\times\Omega_{x}$,
$\Omega_{x}=\\{x\in\mathbb{R}^{n}:G^{\top}\nabla
V(x)\in\operatorname{int}\Omega\\}$, $f_{1}$ and its partial derivatives are
continuous and bounded. Under Assumptions 3 and 5, $f_{2}$ is $C^{1}$, locally
Lipschitz with locally Lipschitz partial derivatives. Therefore, $f_{2}$ and
its partial derivatives are continuous and bounded on any compact subset of
$\Omega_{\textbf{y}}\times\Omega_{x}$, where
$\Omega_{\textbf{y}}:=\\{(z,\textbf{y}_{-i}):\mathcal{R}_{i}^{\top}z_{i}+\mathcal{S}_{i}^{\top}\textbf{y}_{-i}^{i}\in\operatorname{int}\Omega,\forall
i\\}$. Additionally, under Assumption 3,
$h(x):=\operatorname{col}(G^{\top}\nabla
V(x),\mathcal{S}\textbf{1}_{N}\otimes(G^{\top}\nabla V(x)))$, $\frac{\partial
f_{1}}{\partial z}$ and $\frac{\partial f_{1}}{\partial\textbf{y}_{-i}}$ have
bounded first partial derivatives on any compact subset of
$\Omega_{\textbf{y}}\times\Omega_{x}$. Finally,

$\displaystyle\frac{\partial f_{2}(y,\textbf{1}_{N}\\!\otimes\\!y,x)}{\partial
x}\\!=\\!\frac{\partial f}{\partial x}\\!-\\!kG\Big{[}\frac{\partial
F}{\partial y}G^{\top}\nabla^{2}V\\!+\\!\frac{\partial^{2}\phi}{\partial
y^{2}}G^{\top}\nabla^{2}V\Big{]}$

Under Assumption 6, $\frac{\partial f_{2}(y,\textbf{1}\otimes y,x)}{\partial
x}$ is Lipschitz continuous on any compact subset of $\Omega_{x}$.

Therefore, by Theorem 11.2 in [29], for each $k\geq k^{*}$ and for each
compact subset $\bar{\Omega}\subset\Omega_{x}$, there exists
$\bar{\epsilon}>0$ such that for all $x(0)\in\bar{\Omega}$ and for all
$0<\epsilon<\bar{\epsilon}$ (21) has a unique solution $x(t)$ and
$(z(t),\textbf{y}_{-i}(t))$ and for some $\kappa_{1}>0$

$\displaystyle\|x(t)-\hat{x}(t)\|\leq\epsilon\kappa_{1}$

where $\hat{x}(t)$ is the solution to the reduced system. By Lemma 7,
$\Omega_{x}$ is positively invariant for the reduced system. Consider
$\kappa_{x}:=\inf_{t\geq 0}\|\hat{x}(t)\|_{\partial\Omega_{x}}$ and let
$\epsilon^{*}=\min\\{\bar{\epsilon},\frac{\kappa_{x}}{\kappa_{1}}\\}$. Then
for all $0<\epsilon<\epsilon^{*}$ we have that
$\|x(t)-\hat{x}(t)\|<\kappa_{x}$ and thus $x(t)\in\Omega_{x}$ and
$y(t)\in\operatorname{int}\Omega$ for all $t\geq 0$. ∎

###### Theorem 3

Under Assumptions 1 and 2(b) through 6, there exists $k^{*}>0$ and
$\epsilon^{**}>0$ such that for all $k\geq k^{*}$ and
$0<\epsilon<\epsilon^{**}$, the equilibrium
$(\bar{z},\bar{\textbf{y}}_{-i},x^{*})=(y^{*},\mathcal{S}\textbf{1}_{N}\otimes
y^{*},\pi(y^{*}))$ of (21), where $y^{*}$ is the NE of (7) and
$\varepsilon$-vGNE of (4), is exponentially stable. Moreover, for all $x(0)$
such that $y(0)\in\operatorname{int}\Omega$, for all
$(z(0),\textbf{y}_{-i}(0)\in R_{y}^{x(0)}$, the constraint $y(t)\in\Omega$ is
satisfied for all $t\geq 0$.

###### Proof:

Following from the proof of Lemma 11, if $k\geq k^{*}:=\frac{\beta}{\mu}$,
then $x=x^{*}$ is exponentially stable for the reduced system, (23).
$(\tilde{z},\tilde{\textbf{y}}_{-i})=(0,0)$ is exponentially stable for the
boundary-layer system, (22). Therefore, by Theorem 11.4 in [29], there exists
$\hat{\epsilon}>0$ such that for all $0<\epsilon<\hat{\epsilon}$,
$(z,\bar{\textbf{y}}_{-i},x^{*})=(y^{*},\mathcal{S}\textbf{1}_{N}\otimes
y^{*},x^{*})$ is an exponentially stable equilibrium of (21).

Moreover, by Lemma 11, for all $(z(0),\textbf{y}_{-i}(0),x(0))$ such that
$y(0)\in\operatorname{int}\Omega$ and $(z(0),\textbf{y}_{i}(0))\in
R_{y}^{x(0)}$, there exists $\epsilon^{*}>0$ such that the constraint
$y(t)\in\Omega$ is satisfied for all $t\geq 0$. Then take
$\epsilon^{**}=\min\\{\hat{\epsilon},\epsilon^{*}\\}$. ∎

##  VII OSNR Example

Consider an optical-signal-to-noise ratio (OSNR) model for wave division
multiplexing links with ten channels. Each channel chooses its transmission
power $y_{i}$ in order to maximize its signal-to-noise ratio. The link is
assumed to have a maximum transmission power, $P_{0}$. This leads to a game
given by the following set of optimization problems

$\displaystyle\begin{split}\min_{y_{i}}\quad&a_{i}y_{i}-b_{i}\ln\Big{(}1+c_{i}\frac{y_{i}}{n_{i}^{0}+\sum_{j\neq
i}\Gamma_{ij}y_{j}}\Big{)}\\\ \operatorname{s.t.}\quad&0\leq y_{i}\\\
&\textstyle{\sum_{j\in\mathcal{I}}}y_{j}\leq P_{0}\end{split}$ (25)

where $a_{i}>0$ is a pricing parameter, $b_{i}>0$, $\Gamma=[\Gamma]_{ij}$ is
the link system matrix and $n_{i}^{0}$ is the channel noise power, with
parameters as in [30]. We consider that each autonomous agent uses a fully-
distributed partial-information gradient-play scheme, with agent dynamics
given by (11) and (20). In order to get the action information, action
estimates are communicated over graph $\mathcal{G}_{c}$, Fig. 1.

$1$$10$$2$$3$$4$$5$$6$$7$$8$$9$ Figure 1: Communication graph,
$\mathcal{G}_{c}$, $\lambda_{2}=2.6158$

Fig. 2 shows transmission power, $y_{i}$, for each agent over time using
$v_{i}=1$, $k_{i}=\frac{1}{2}$ and $\rho=0.1$. Each agent always has positive
power and the total power usage on the link is less than the maximum, Fig. 3,
meaning the constraints are satisfied for all time.

Figure 2: Individual transmission powers, $y_{i}$ Figure 3: Total power usage,
$\sum_{i\in\mathcal{I}}y_{i}$

##  VIII Velocity Synchronization

Next, we consider a velocity synchronization problem for a group of flexible
mobile robots. Consider a group of five flexible mobile robots moving in a
line. Each robot is modelled as two masses connected by a non-linear spring,
with force $\psi_{i}(\cdot)$ and damper with coefficient $\gamma_{i}$. Let
$d_{i}$ denote robot $i$’s position, mass $M_{i}$, and $\eta_{i}$ the position
of its appendage, mass $m_{i}$. A force $u_{i}$ is applied to mass $M_{i}$.
Letting $x_{i}^{1}=d_{i}-\eta_{i}$, $x_{i}^{2}=\dot{d}_{i}$ and
$x_{i}^{3}=\dot{\eta}_{i}$, the dynamics of robot $i$ are given by

$\displaystyle\mathcal{P}_{i}:\begin{cases}\dot{x}_{i}^{1}=x_{i}^{2}-x_{i}^{3}\\\
M_{i}\dot{x}_{i}^{2}=-\psi_{i}(x_{i}^{1})-\eta_{i}(x_{i}^{2}-x_{i}^{3})+u_{i}\\\
m_{i}\dot{x}_{i}^{3}=\psi_{i}(x_{i}^{1})+\eta_{i}(x_{i}^{2}-x_{i}^{3})\\\
y_{i}=x_{i}^{2}\end{cases}$ (26)

It can be shown that if $\psi_{i}$ is strongly-monotone and Lipschitz
continuous and $\psi_{i}(0)=0$ , (26) satisfies Assumption 3 with
$V_{i}(x_{i})=\int_{0}^{x_{i}^{1}}\psi_{i}(x_{i}^{1})dx_{i}^{1}+\frac{M_{i}}{2}(x_{i}^{2})^{2}+\frac{m_{i}}{2}(x_{i}^{3})^{2}$.

We consider the following leader-follower problems:

$\displaystyle\begin{split}\min_{y_{i}}\quad&(y_{i}-y_{i-1})^{2}\\\
\operatorname{s.t.}\quad&(y_{i}-y_{i-1})^{2}\leq\delta_{i,\text{max}}^{2}\end{split}$
(27)

where $y_{0}:=v_{0}$, the reference velocity for the leader.

We simulate a group of five robots using the full-information feedback (14)
with $v_{0}=3$, $d_{i,\text{max}}=d_{\text{max}}=3$, $M_{i}=m_{i}=1$,
$\eta_{i}=1$, $\psi_{i}(x_{i}^{1})=-x_{i}^{1}-\text{atan}(x_{i}^{1})$ and
$\rho=0.1$. Figure 4 shows that the robots synchronize to $v_{0}=3$. Figure 5
shows that the velocity difference between neighbours never exceeds
$d_{\text{max}}$.

Figure 4: Velocities, $\dot{d}_{i}$, of the five robots Figure 5: Difference
in velocities between neighbours over time

##  IX Conclusions

In this paper, we present a novel approach to solving GNE problem using an
inexact penalty function on the inequality constraints that converts the GNE
seeking problem into an NE seeking problem. We then consider full- and
partial-information gradient-play feedbacks for dynamic agents with passive
dynamics. We prove both convergence to the NE and constraint satisfaction for
all time.

Future work will explore using a time-varying penalty function to guarantee
exact convergence to the vGNE. Additionally, we will consider other types of
agent dynamics and time-varying cost-functions and constraints.

###  -A Proof of Lemma 5

By Assumptions 1 and 2, $y^{*}$ is the unique point such that
$F(y^{*})\\!+\\!\nabla\phi(y^{*})\\!=\\!0$. Let $x^{*}\\!=\\!\pi(y^{*})$. By
Assumption 3 and (9),

$\displaystyle f(\pi(y^{*}))-G(F(y^{*})+\nabla\phi(y^{*}))=0$ (28)

therefore $x^{*}=\pi(y^{*})$ is an equilibrium point of (3). Now suppose there
is another equilibrium $\bar{x}$, we have

$\displaystyle 0$ $\displaystyle=f(\bar{x})-G(F(\bar{y})+\nabla\phi(\bar{y}))$
$\displaystyle\bar{y}$ $\displaystyle=G^{\top}\nabla V(\bar{x})$

Let $w=\nabla V(\bar{x})$ by strong-monotonicity of Lipschitz continuity of
$\nabla V$, $\nabla V$ is invertible. Thus, we have

$\displaystyle f(\nabla V^{-1}(w))=G(F(G^{\top}w)+\nabla\phi(G^{\top}w))$

Let $w^{*}=\nabla V(x^{*})$. From (28), we get

$\displaystyle f(\nabla V^{-1}(w))-f(\nabla V^{-1}(w^{*}))$
$\displaystyle\quad=G[F(G^{\top}w)\\!+\\!\nabla\phi(G^{\top}w)\\!-\\!F(G^{\top}w^{*})\\!-\\!\nabla\phi(G^{\top}w^{*})]$

Left multiplying by $(w-w^{*})^{\top}$ gives

$\displaystyle(w-w^{*})^{\top}[f(\nabla V^{-1}(w))-f(\nabla
V^{-1}(w^{*}))]=(w\\!-\\!w^{*})^{\top}G$
$\displaystyle\quad[F(G^{\top}w)\\!+\\!\nabla\phi(G^{\top}w)\\!-\\!F(G^{\top}w^{*})\\!-\\!\nabla\phi(G^{\top}w^{*})]$

By monotonicity of $F+\nabla\phi$ and of $-f\circ\nabla V^{-1}$, we have

$\displaystyle 0\geq(w-w^{*})^{\top}f(\nabla V^{-1}(w))-f(\nabla
V^{-1}(w^{*}))$
$\displaystyle=(w-w^{*})^{\top}G[F(G^{\top}w)\\!+\\!\nabla\phi(G^{\top}w)$
$\displaystyle\qquad-\\!F(G^{\top}w^{*})\\!-\\!\nabla\phi(G^{\top}w^{*})]\geq
0$

Then, by strict-monotonicity of $F$, $G^{\top}w=G^{\top}w^{*}$, implying
$\bar{y}=y^{*}$, NE of (7) and $\varepsilon$-vGNE of (4) by Lemma 4. Thus, by
Lemma 3, $\bar{x}=x^{*}$. Therefore, $x^{*}=\pi(y^{*})$ is the unique
equilibrium of (15).

###  -B Proof of Lemma 6

First, we show that
$S\subset\Omega_{x}:=\\{x\in\mathbb{R}^{n}:g(G^{\top}\nabla V(x))<0\\}$ is
compact. Note that $S=\\{x\in\mathbb{R}:V^{x^{*}}(x)-c\leq
0\\}\cap\\{x\in\mathbb{R}:\phi^{x^{*}}(x)-d\leq 0\\}$. Which is closed, since
both functions are continuous. Since, the first set is compact, the
intersection of the two is also compact.

Next, cf. Definition 4, Condition 2, we need to show that for all $x\in S$,
there exists $z\in\mathbb{R}^{n}$ such that $V^{x^{*}}(x)-c+\nabla
V^{x^{*}}(x)^{\top}z<0$ and
$\phi^{x^{*}}(x)-d+\nabla\phi^{x^{*}}(x)^{\top}z<0$. Now, consider $x\in S$.
There are four cases to be considered.

  1. 1.

$V^{x^{*}}(x)-c<0$, $\phi^{x^{*}}(x)-d<0$
In this case, the inequalities hold trivially for $z=0$.

  2. 2.

$V^{x^{*}}(x)-c<0$, $\phi^{x^{*}}(x)-d=0$
Let $z=-G\eta$, where $\eta=(\nabla\phi(G^{\top}\nabla
V(x))-\nabla\phi(G^{\top}\nabla V(x^{*}))$. Then

$\displaystyle V^{x^{*}}(x)-c+\nabla V^{x^{*}}(x)^{\top}z=$ $\displaystyle
V^{x^{*}}(x)-c-(\nabla V(x)-\nabla V(x^{*}))^{\top}G\eta<0$

by strict-convexity of $\phi$ and the fact that $G^{\top}\nabla V(x)\neq
G^{\top}\nabla V(x^{*})$ for all $x$ such that $\phi^{x^{*}}(x)=d$.
Additionally,

$\displaystyle\phi^{x^{*}}(x)-d+\nabla\phi^{x^{*}}(x)^{\top}z=-\eta^{\top}G^{\top}\nabla^{2}V(x)^{\top}G\eta<0$

by convexity of $\phi(y)$, strong-convexity of $V(x)$, full-column rank of $G$
and since $G^{\top}\nabla V(x)\neq G^{\top}\nabla V(x^{*})$ when
$\phi^{x^{*}}(x)>0$.

  3. 3.

$V^{x^{*}}(x)-c=0$, $\phi^{x^{*}}(G^{\top}\nabla V(x))-d<0$
Let $z=-a(\nabla V(x)-\nabla V(x^{*}))$, where
$0<a<\frac{d-\phi^{x^{*}}(x)}{|\nabla(\phi^{x^{*}}(x))^{\top}(\nabla
V(x)-\nabla V(x^{*}))|}$. This gives

$\displaystyle V^{x^{*}}(x)-c+\nabla V^{x^{*}}(x)^{\top}z=$
$\displaystyle-a(\nabla V(x)-\nabla V(x^{*}))^{\top}(\nabla V(x)-\nabla
V(x^{*}))<0$

by strong-convexity of $V(x)$. Furthermore,

$\displaystyle\phi^{x^{*}}(x)-d+\nabla\phi^{x^{*}}(x)^{\top}z=$
$\displaystyle\phi^{x^{*}}(x)-d-a\nabla\phi^{x^{*}}(x)^{\top}(\nabla
V(x)-\nabla V(x^{*}))$
$\displaystyle\leq\phi^{x^{*}}(x)-d+a|\nabla\phi^{x^{*}}(x)^{\top}(\nabla
V(x)-\nabla V(x^{*}))|<0$

  4. 4.

$V^{x^{*}}(x)-c=0$, $\phi^{x^{*}}(G^{\top}\nabla V(x))-d=0$
Let $z$ as in Case 2. Then $V^{x^{*}}(x)-c+\nabla V^{x^{*}}(x)^{\top}z<0$ and
$\phi^{x^{*}}(x)-d+\nabla\phi^{x^{*}}(x)^{\top}z<0$ as in Case 2.

Next, to show condition (3) in Definition 4, consider the vector field
$f_{0}(x)=(\phi^{x^{*}}(x)-d)(\nabla V(x)-\nabla V(x^{*}))-G\eta$, where
$\eta=(\nabla\phi(G^{\top}\nabla V(x))-\nabla\phi(G^{\top}\nabla V(x^{*}))$
and $a\in\mathbb{R}$, which is Lipschitz continuous on $S$ since
$S\subset\Omega_{x}$ is compact and $f_{0}$ is $C^{1}$ on $\Omega_{x}$. Here,
we need to check three cases

  1. 1.

$V^{x^{*}}(x)-c<0$, $\phi^{x^{*}}(x)-d=0$

$\displaystyle
L_{f_{0}}\phi^{x^{*}}=-\eta^{\top}G^{\top}\nabla^{2}V(x)G\eta<0$ (29)

by $\phi(x)$ strictly convex, $V(x)$ strongly-convex, rank of $G$ and that
$G^{\top}\nabla V(x)\neq G^{\top}\nabla V(x^{*})$ when $\phi^{x^{*}}(x)>0$.

  2. 2.

$V^{x^{*}}(x)-c=0$, $\phi^{x^{*}}(x)-d<0$

$\displaystyle L_{f_{0}}V^{x^{*}}=$ $\displaystyle(\phi^{x^{*}}(x)-d)\|\nabla
V(x)-\nabla V(x^{*})\|^{2}$ $\displaystyle-\\!(\nabla V(x)\\!-\\!\nabla
V(x^{*}))^{\top}G\eta<0$

by strong-convexity of $V(x)$, $\phi^{x^{*}}(x)<d$ and convexity of $\phi(y)$.

  3. 3.

$V^{x^{*}}(x)-c=0$, $\phi^{x^{*}}(x)-d=0$
We have $L_{f_{0}}\phi^{x^{*}}<0$ as in (29). Furthermore

$\displaystyle L_{f_{0}}V^{x^{*}}\\!=\\!$ $\displaystyle-\\!(\nabla
V(x)\\!-\\!\nabla V(x^{*}))^{\top}G\eta<0$

by $\phi(y)$ strictly-convex and $G^{\top}\nabla V(x)\neq G^{\top}\nabla
V(x^{*})$ when $\phi^{x^{*}}(x)>0$.

Therefore, by Definition 4, we have that $S$ is a practical set.

###  -C Proof of Lemma 8

First, we show that $(\mathcal{S}\textbf{1}_{N}\otimes y^{*},\pi(x^{*}))$ is
an equilibrium point of (15). At $(\mathcal{S}\textbf{1}_{N}\otimes
y^{*},\pi(x^{*}))$, $\textbf{y}=\textbf{1}_{N}\otimes y^{*}$. Thus, using the
fact that $\textbf{F}(\textbf{1}_{N}\otimes y)=F(y)$ for any $y$, (18) becomes

$\displaystyle\dot{\textbf{y}}_{-i}$
$\displaystyle=-\mathcal{S}\textbf{L}\textbf{1}_{N}\otimes y^{*}=0$
$\displaystyle\dot{x}$
$\displaystyle=f(\pi(x^{*}))\\!-\\!G(F(y^{*})\\!+\\!\nabla\phi(y^{*})\\!+\\!\mathcal{R}\textbf{L}\textbf{1}_{N}\otimes
y^{*})\\!=\\!0$

Therefore $(\mathcal{S}\textbf{1}_{N}\otimes y^{*},\pi(x^{*}))$ is an
equilibrium point of (18). Now, suppose there is another equilibrium point
$(\bar{\textbf{y}}_{-i},\bar{x})$. From (18),

$\displaystyle-\mathcal{S}\textbf{L}(\mathcal{S}^{\top}\bar{\textbf{y}}_{-i}-\mathcal{R}^{\top}\bar{y})=0$
(30) $\displaystyle
f(\bar{x})\\!-\\!G(\textbf{F}(\bar{\textbf{y}})\\!+\\!\nabla\phi(\bar{y})\\!+\\!\mathcal{R}\textbf{L}\bar{\textbf{y}})=0$
(31)

From (30), $\bar{\textbf{y}}_{-i}=\textbf{1}_{N}\otimes\bar{y}$. Using
$\textbf{F}(\textbf{1}_{N}\otimes\bar{y})=F(\bar{y})$, (31) becomes
$f(\bar{x})\\!-\\!G(F(\bar{y})+\nabla\phi(\bar{y}))=0$. Following the proof of
Lemma 5, $\bar{x}=\pi(x^{*})$ and $\bar{y}=y^{*}$.

## References

  * [1] T. Alpcan and T. Başar, _Distributed Algorithms for Nash Equilibria of Flow Control Games_. Birkhäuser Boston, 2005.
  * [2] W. Lin, Z. Qu, and M. A. Simaan, “Distributed game strategy design with application to multi-agent formation control,” in _Proc. of the 53rd IEEE CDC_ , Dec. 2014, pp. 433–438.
  * [3] M. Guo and C. De Persis, “Network games with dynamic players: Stabilization and output convergence to Nash equilibrium,” _arXiv e-prints arXiv:1912.00383_ , 2019.
  * [4] A. R. Romano and L. Pavel, “Dynamic NE seeking for multi-integrator networked agents with disturbance rejection,” _IEEE Transactions on Control of Networked Systems_ , vol. 7, no. 1, pp. 129–139, 2020.
  * [5] L. Pavel, “Distributed GNE seeking under partial-decision information over networks via a doubly-augmented operator splitting approach,” _IEEE Trans. Autom. Control_ , vol. 65, no. 4, pp. 1584–1597, 2020.
  * [6] K. Lu, G. Jing, and L. Wang, “Distributed algorithms for searching generalized Nash equilibrium of noncooperative games,” _IEEE Trans. Cybern._ , vol. 49, no. 6, pp. 2362–2371, June 2019.
  * [7] Y. Zou, B. Huang, Z. Meng, and W. Ren, “Continuous-time distributed nash equilibrium seeking algorithms for non-cooperative constrained games,” _Automatica_ , vol. 127, p. 109535, 2021.
  * [8] M. Bianchi and S. Grammatico, “Continuous-time fully distributed generalized Nash equilibrium seeking for multi-integrator agents,” _arXiv e-prints arXiv:1911.12266_ , 2019.
  * [9] C. De Persis and S. Grammatico, “Continuous-time integral dynamics for a class of aggregative games with coupling constraints,” _IEEE Trans. Autom. Control_ , vol. 65, no. 5, pp. 2171–2176, 2020.
  * [10] P. Yi and L. Pavel, “An operator splitting approach for distributed generalized Nash equilibria computation,” _Automatica_ , vol. 102, pp. 111 – 121, 2019.
  * [11] M. S. Stanković, K. H. Johansson, and D. M. Stipanović, “Distributed seeking of Nash equilibria with application to mobile sensor networks,” _IEEE Trans. Autom. Control_ , vol. 57, no. 4, pp. 904–919, Apr. 2012.
  * [12] A.-H. Mohsenian-Rad, V. W. Wong, J. Jatskevich, R. Schober, and A. Leon-Garcia, “Autonomous demand-side management based on game-theoretic energy consumption scheduling for the future smart grid,” _IEEE Trans. Smart Grid_ , vol. 1, no. 3, pp. 320–331, Dec. 2010.
  * [13] L. Pavel, “A noncooperative game approach to OSNR optimization in optical networks,” _IEEE Trans. Autom. Control_ , vol. 51, no. 5, pp. 848–852, May 2006.
  * [14] F. Facchinei and C. Kanzow, “Penalty methods for the solution of generalized Nash equilibrium problems,” _SIAM J. Optim._ , vol. 20, no. 5, pp. 2228–2253, 2010.
  * [15] M. Fukushima, “Restricted generalized Nash equilibria and controlled penalty algorithm,” _Computation Management Science_ , vol. 8, pp. 201–218, 2011\.
  * [16] F. Fabiani and A. Caiti, “Nash equilibrium seeking in potential games with double-integrator agents,” in _2019 18th ECC_ , 2019, pp. 548–553.
  * [17] S. Boyd and L. Vandenberghe, _Convex Optimization_. Cambridge University Press, 2004.
  * [18] D. Gadjov and L. Pavel, “A passivity-based approach to Nash equilibrium seeking over networks,” _IEEE Trans. Autom. Control_ , vol. 64, no. 3, pp. 1077–1092, 2019.
  * [19] A. R. Romano and L. Pavel, “GNE seeking in games with passive dynamic agents via inexact-penalty methods,” in _Proc. of the 59 th CDC_, Dec. 2020.
  * [20] F. Blanchini and S. Miani, _Set-Theoretic Methods in Control_ , 2nd ed. Birkhäuser, 2015.
  * [21] J. W. Simpson-Porco, “Equilibrium-independent dissipativity with quadratic supply rates,” _IEEE Trans. Autom. Control_ , vol. 64, no. 4, pp. 1440–1455, 2019.
  * [22] C. Godsil and G. Royle, _Algebraic Graph Theory_ , ser. Graduate Texts in Mathematics. Springer New York, 2001.
  * [23] F. Facchinei and C. Kanzow, “Generalized Nash equilibrium problems,” _Annals of Operations Research_ , pp. 177–211, 2010.
  * [24] F. Facchinei and J. S. Pang, _Finite-dimensional variational inequalities and complementarity problems_. Springer, 2007.
  * [25] T. Başar and G. J. Olsder, _Dynamic Noncooperative Game Theory_ , 2nd ed., ser. Classics in Applied Mathematics. SIAM, 1999.
  * [26] G. Scutari, F. Facchinei, J. S. Pang, and D. P. Pallomar, “Real and complex monotone communication games,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 7, pp. 400–409, Jul. 2014.
  * [27] H. Attouch, J. Peypouquet, and P. Redont, “A dynamical approach to an inertial forward-backward algorithm for convex minimization,” _SIAM Journal on Optimization_ , vol. 24, no. 1, pp. 232–256, 2014.
  * [28] R. I. Boţ and E. R. Csetnek, “A second-order dynamical system with Hessian-driven damping and penalty term associated to variational inequalities,” _Optimization_ , vol. 68, no. 7, pp. 1265–1277, 2019.
  * [29] H. K. Khalil, _Nonlinear Systems_ , 3rd ed. SIAM, 2002.
  * [30] F. Salehisadaghiani and L. Pavel, “Distributed Nash equilibrium seeking: A gossip-based algorithm,” _Automatica_ , vol. 72, pp. 209–216, 2016.