#  Linear convergence in time-varying generalized Nash equilibrium problems

Mattia Bianchi, Emilio Benenati, Sergio Grammatico  Emilio Benenati and Sergio
Grammatico are with the the Delft Center for Systems and Control, TU Delft,
The Netherlands. Mattia Bianchi is with the Automatic Control Laboratory, ETH
Zürich, Switzerland. E-mail addresses: {e.benenati<EMAIL_ADDRESS><EMAIL_ADDRESS>This work was supported by the ERC under research project
COSMOS (802348).

###### Abstract

We study generalized games with full row rank equality constraints and we
provide a strikingly simple proof of strong monotonicity of the associated KKT
operator. This allows us to show linear convergence to a variational
equilibrium of the resulting primal-dual pseudo-gradient dynamics. Then, we
propose a fully-distributed algorithm with linear convergence guarantee for
aggregative games under partial-decision information. Based on these results,
we establish stability properties for online GNE seeking in games with time-
varying cost functions and constraints. Finally, we illustrate our findings
numerically on an economic dispatch problem for peer-to-peer energy markets.

##  I Introduction

Generalized Nash equilibrium (GNE) problems arise in many multi-agent
applications, where the agents are coupled not only because of their
conflicting objectives, but also via shared constraints –operational limits of
the system, that the agents should respect. Among others, GNE seeking is used
in energy markets [1], radio communication [2] and formation control [3]
problems.

The networked structure of these applications naturally calls for distributed
solution methods. In fact, part of the recent literature focuses on semi-
decentralized GNE seeking algorithms [4, 5, 6], where the agents update their
decision locally, with the help of a coordinator that gathers and broadcasts
information over the systems (a setup also named full-information scenario).
Other works [7, 8, 9, 10] deal with applications where the agents can only
rely on fully-distributed peer-to-peer communication and local data. In this
so-called partial-decision information scenario, the agents compensate for the
lack of global knowledge by estimating the unknown quantities and by embedding
consensus dynamics in their local decision processes.

In both scenarios, to cope with the presence of coupling constraints and to
distribute the computation among the agents, one should resort to Lagrangian
reformulations. In fact, all the references above leverage primal-dual pseudo-
gradient algorithms, aimed at solving the Karush–Kuhn–Tucker (KKT) optimality
conditions of the GNE problem.

In general, primal-dual algorithms fails to achieve linear convergence, even
for the class of strongly-monotone generalized games [4]. Importantly,
together with linear convergence, some crucial input-to-state stability (ISS)
properties of pseudo-gradient iterations are also not guaranteed. This lack of
robustness is a critical issue for methods in the partial-decision information
scenario, where convergence should be ensured despite the estimation error. To
overcome this complication, vanishing step sizes can be used to drive the
error to zero [11], at the price of slow convergence. Alternatively, several
fixed-step algorithms for GNE seeking were derived based on operator-theoretic
methods and on the use of preconditioning [8, 9, 12, 7]. Unfortunately, this
approach comes with important limitations, such as extending the analysis to
time-varying setups.

For instance, there is no available fixed-step fully-distributed method to
solve GNE problems when the agents can only exchange information over
switching communication networks (while methods are available for games
without coupling constraints [13, 14]). Furthermore, in many decision
processes with real-world applications, the cost functions of the agents and
the system constraints can vary over time [15], for instance in cognitive
radio networks and demand response in smart grids [16]. In such domains,
linearly convergent algorithms become particularly desirable, as the solver
needs to quickly update its solution in response to changes in the
environment. Despite its practical relevance, there are very few works that
study the online GNE problem. The paper [17] proposes a regularized algorithm,
which only achieves inexact convergence, and which is not fully-distributed.
Instead, the authors of [18] develop an algorithm for the partial-decision
information scenario, but that achieves sublinear regret only when the
solution is asymptotically constant and for diminishing step sizes.

Contribution: In this paper we study generalized games with full row rank
coupling equality constraints –as those arising in resource allocation and
transportation problems [19], where demand-matching [10] and flow [1]
constraints are ubiquitous. For the first time, we show that, in this setup,
linear convergence to a GNE can be achieved via primal-dual dynamics, both for
the full- and partial-decision information scenario. Thanks to this result, we
can also adapt the dynamics to online equilibrium seeking in time-varying
games. Here we focus on the prominent class of aggregative games [4], for its
desirable scalability properties, but the analysis carries over to generally-
coupled costs. We summarize the novelties of our work as follows:

  1. 1.

We provide a simple, constructive proof of the strong monotonicity of the KKT
operator in games with full-row rank equality coupling constraints. As a
consequence, we show linear convergence to a GNE of the pseudo-gradient
ascent-descent method (Section III);

  2. 2.

We design a linearly convergent algorithm for GNE seeking in partial-decision
information, via a tracking technique [11] that avoids the need for slack
variables. Our proof is based on a change of coordinates and a small gain
argument: due to its generality, the argument also applies to the case of
(Q-connected) time-varying communication graphs (Section IV);

  3. 3.

We exploit our linear convergence results to study the tracking properties of
the proposed methods with respect to the solution of a game with time-varying
costs and constraints. In particular, for the fully-distributed algorithm, we
show that the extra error induced in the dynamic tracking procedure does not
jeopardize stability (Section V).

Notation: $\boldsymbol{0}_{n}$ (${\boldsymbol{1}}_{n}$) denotes the vector of
dimension $n$ with all elements equal to $0$ ($1$); $I_{n}$ the identity
matrix of dimension $n$; the subscripts are omitted when there is no
ambiguity. If $A$ is symmetric,
$\uplambda_{\textnormal{min}}(A)=\uplambda_{1}(A)\leq\dots\leq\uplambda_{n}(A)=:\uplambda_{\textnormal{max}}(A)$
denote its eigenvalues. $\otimes$ denotes the Kronecker product.
$\mathop{\hbox{\rm diag}}(A_{1},\dots,A_{N})$ denotes the block diagonal
matrix with $A_{1},\dots,A_{N}$ on its diagonal;
$\mathrm{col}\left(x_{1},\ldots,x_{N}\right)=[x_{1}^{\top}\ldots
x_{N}^{\top}]^{\top}$. For a positive definite symmetric matrix $P\succ 0$,
$\langle x,y\rangle_{P}=x^{\top}Py$ denotes the $P$-weighted inner product,
$\|x\|_{P}$ the corresponding norm; we omit the subscript if $P=I$. An
operator $\mathcal{F}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ is
($\mu$-strongly) monotone in $\mathcal{H}_{P}$ if, for any
$x,y\in\mathbb{R}^{n}$,
$\langle\mathcal{F}(x)-\mathcal{F}(y),x-y\rangle_{P}\geq
0(\geq\mu\|x-y\|_{P}^{2})$; is contractive in $\mathcal{H}_{P}$ if it is
Lipschitz with constant smaller than 1, i.e., for some $\ell<1$ and for any
$x,y\in\mathbb{R}^{n}$,
$\|\mathcal{F}(x)-\mathcal{F}(y)\|_{P}\leq\ell\|x-y\|_{P}$; we omit the
indication “in $\mathcal{H}_{P}$” if $P=I$. If $\mathcal{F}$ is
differentiable, $D\mathcal{F}$ denotes its Jacobian.

##  II Mathematical setup

We consider a set of agents, $\mathcal{I}\coloneqq\\{1,\ldots,N\\}$, where
each agent $i\in\mathcal{I}$ shall choose its decision variable (i.e.,
strategy) $x_{i}\in\mathbb{R}^{n_{i}}$. Let
$x\coloneqq\mathrm{col}((x_{i})_{i\in\mathcal{I}})\in\mathbb{R}^{n}$ denote
the stacked vector of all the agents’ decisions, with $\textstyle
n\coloneqq\sum_{i=1}^{N}n_{i}$. The goal of each agent $i\in\mathcal{I}$ is to
minimize its objective function $J_{i}(x_{i},x_{-i})$, which depends on both
the local variable $x_{i}$ and on the decision variables of the other agents
$x_{-i}\coloneqq\mathrm{col}((x_{j})_{j\in\mathcal{I}\backslash\\{i\\}})$.
Furthermore, the feasible decisions of each agent depends on the action of the
other agents via affine equality coupling constraints. Specifically, the
feasible set is $\mathcal{X}\coloneqq\left\\{x\in\mathbb{R}^{n}\mid
Ax=b\right\\}$, where $A\coloneqq\left[A_{1},\ldots,A_{N}\right]$ and
$b\coloneqq\sum_{i=1}^{N}b_{i}$, $A_{i}\in\mathbb{R}^{m\times n_{i}}$ and
$b_{i}\in\mathbb{R}^{m}$ being locally available information. The game is then
represented by the inter-dependent optimization problems:

$\displaystyle(\forall i\in\mathcal{I})\ \mathop{\rm
min}_{y_{i}\in\mathbb{R}^{{n_{i}}}}\;J_{i}(y_{i},x_{-i})\quad\text{s.t.}\
(y_{i},x_{-i})\in\mathcal{X}.$ (1)

The technical problem we consider here is the computation of a GNE, namely a
set of decisions that simultaneously solve all the optimization problems in
(1).

###### Definition 1

A collective strategy
$x^{\star}=\operatorname{col}\left((x_{i}^{\star}\right)_{i\in\mathcal{I}})$
is a generalized Nash equilibrium if, for all $i\in\mathcal{I}$,
$J_{i}\left(x_{i}^{\star},x_{-i}^{\star}\right)\leq\inf\\{J_{i}\left(y_{i},x_{-i}^{\star}\right)\mid(y_{i},x_{-i}^{\star})\in\mathcal{X}\\}.$
$\square$

Next, we postulate some standard regularity and convexity assumptions for the
constraint sets and cost functions.

######  Assumption 1 (Convexity)

In (1), $\mathcal{X}$ is non-empty. For each $i\in\mathcal{I}$, $J_{i}$ is
continuous and $J_{i}\left(\cdot,x_{-i}\right)$ is convex and continuously
differentiable for every $x_{-i}$. $\square$

As common in the literature [20], [4], among all the GNEs, we focus on the
subclass of variational GNEs (v-GNEs) [2, Def. 3.11], which are more
economically justifiable, as well as computationally tractable [21]. Under
Assumption 1 and defining the pseudo-gradient mapping of the game

$\displaystyle
F(x)\coloneqq\operatorname{col}\left((\nabla_{\\!x_{i}}J_{i}(x_{i},x_{-i}))_{i\in\mathcal{I}}\right),$
(2)

$x^{\star}$ is a v-GNE of the game in (1) if and only if there exists a dual
variable $\lambda^{\star}\in\mathbb{R}^{m}$ such that the following KKT
conditions are satisfied [2, Th. 4.8]:

Let us restrict our attention to strongly monotone games.

######  Assumption 2 (Strong monotonicity)

The game mapping $F$ in (2) is $\mu_{F}$-strongly monotone and
$\ell_{F}$-Lipschitz continuous, for some $\mu_{F}$, $\ell_{F}>0$. $\square$

The strong monotonicity of $F$ is sufficient to ensure existence and
uniqueness of a v-GNE [22, Th. 2.3.3]; it implies strong convexity of each
function $J_{i}(\cdot,x_{-i})$ for any fixed $x_{-i}$, but not joint convexity
of the function $J_{i}(\cdot)$. We emphasize that strong monotonicity is a
very common condition for algorithms with linear convergence. In addition, we
make the following assumption.

######  Assumption 3 (Full rank constraints)

$A$ is full row rank. $AA^{\top}\geq{\mu_{A}}I$, $\|A\|\leq\ell_{A}$ for some
scalars $\mu_{A},\ell_{A}>0$. $\square$

Assumption 3 postulates that there are no redundant constraints (or
equivalently that redundant constraints are removed). This condition is well
known in duality theory and optimization, as it ensures the uniqueness of dual
solutions (as it can be inferred by (II)).

###  II-A Aggregative games

For ease of presentation, we will specialize our results to the prominent
class of aggregative games111Similar results would hold for generally-coupled
games. We note that, in principle, one could set $\sigma(x)=x$ by opportunely
choosing the functions $\phi_{i}$’s in (3), which arises in a variety of
engineering applications, e.g., network congestion control and demand-side
management [23]. In particular, we assume that the cost function $J_{i}$ of
each agent $i$ depends only on the local decision $x_{i}$ and on an
aggregation value

$\displaystyle\sigma(x)=\frac{1}{N}\sum\phi_{i}(x_{i}),$ (3)

where $\phi_{i}:\mathbb{R}^{n_{i}}\rightarrow\mathbb{R}^{q}$ is a local
function of agent $i$. In short, overloading the function $J_{i}$ with some
abuse of notation, we also write

$\displaystyle J_{i}(x_{i},x_{-i})=J_{i}(x_{i},\sigma(x)).$ (4)

###### Assumption 4

For each $i\in\mathcal{I}$, the function $\phi_{i}$ in (3) is continuously
differentiable and $\ell_{\sigma}$-Lipschitz continuous. $\square$

##  III Linear convergence in generalized games

We start by showing that the KKT operator is strongly monotone, in a suitable
norm, under Assumptions 2 and 3.

###### Lemma 1

Let $\omega\coloneqq\mathrm{col}(x,\lambda)$. The operator

$\displaystyle\omega\mapsto\mathcal{A}(\omega)=\begin{bmatrix}F(x)+A^{\top}\lambda\\\
-Ax+b\end{bmatrix}$ (5)

is $\mu_{\mathcal{A}}$-strongly monotone in $\mathcal{H}_{P}$, for some
$P\succ 0$ and $\mu_{\mathcal{A}}>0$. $\square$

###### Proof:

For some $0<\nu<\ell_{A}$, let

$\displaystyle P=\begin{bmatrix}I&\nu A^{\top}\\\ \nu A&I\end{bmatrix}\succ
0.$ (6)

For any $x,x^{\star}\in\mathbb{R}^{n}$ and
$\lambda,\lambda^{\star}\in\mathbb{R}^{m}$, we have

$\displaystyle\hphantom{{}={}}\langle\mathcal{A}(\omega)-\mathcal{A}(\omega^{\star}),\omega-\omega^{\star}\rangle_{P}$
$\displaystyle=\langle F(x)-F(x^{\star}),x-x^{\star}\rangle$
$\displaystyle\hphantom{{}={}}+\nu\langle
F(x)-F(x^{\star}),A^{\top}(\lambda-\lambda^{\star})\rangle$
$\displaystyle\hphantom{{}={}}+\cancel{\langle
A^{\top}(\lambda-\lambda^{\star}),x-x^{\star}\rangle}$
$\displaystyle\hphantom{{}={}}+\nu\langle
A^{\top}(\lambda-\lambda^{\star}),A^{\top}(\lambda-\lambda^{\star})\rangle$
$\displaystyle\hphantom{{}={}}-\nu\langle
A(x-x^{\star}),A(x-x^{\star})\rangle$
$\displaystyle\hphantom{{}={}}-\cancel{\langle
A(x-x^{\star}),\lambda-\lambda^{\star}\rangle}$
$\displaystyle\geq(\mu_{F}-\nu\ell_{A}^{2})\|x-x^{\star}\|^{2}$
$\displaystyle\hphantom{{}={}}-\nu\ell_{F}\ell_{A}\|x-x^{\star}\|\|\lambda-\lambda^{\star}\|$
$\displaystyle\hphantom{{}={}}+\nu\mu_{A}\|\lambda-\lambda^{\star}\|^{2}$

which is positive definite for
$0<\nu<\frac{4\mu_{F}\mu_{A}}{\ell_{F}^{2}\ell_{A}^{2}+{4}\mu_{A}\ell_{A}^{2}}$.
The conclusion follows by equivalence of norms. ∎

Based on Lemma 1 we can prove linear convergence of classic primal-dual
iterations.

######  Theorem 1 (GNE seeking in full-decision information)

Let Assumptions 1-3 hold and
$\ell_{\mathcal{A}}:=(\ell_{F}+\ell_{A}){\sqrt{\frac{\uplambda_{\max}(P)}{\uplambda_{\mathop{\rm
min}}(P)}}}$. For any
$0<\alpha<\frac{2\mu_{\mathcal{A}}}{\ell_{\mathcal{A}}^{2}}$ and any initial
condition $(x^{0},\lambda^{0})$, the iteration

$\displaystyle x^{k+1}$
$\displaystyle=x^{k}-\alpha\left(F(x^{k})+A^{\top}\lambda^{k}\right)$ (7a)
$\displaystyle\lambda^{k+1}$
$\displaystyle=\lambda^{k}+\alpha\left(Ax^{k}-b\right)$ (7b)

converges linearly to the unique solution
$\omega^{\star}=(x^{\star},\lambda^{\star})$ of the KKT conditions in (II):
for all $k\in\mathbb{N}$

$\displaystyle\begin{split}\|\omega^{k+1}-\omega^{\star}\|^{2}_{P}\leq\rho\|\omega^{k}-\omega^{\star}\|^{2}_{P},\end{split}$
(8)

where $\rho=1-{2}\alpha\mu_{\mathcal{A}}+\alpha^{2}\ell_{\mathcal{A}}^{2}<1$.
$\square$

###### Proof:

By Lemma 1,
$\|\omega-\alpha\mathcal{A}(\omega)-(\omega^{\star}-\alpha\mathcal{A}(\omega^{\star}))\|_{P}=\|\omega-\omega^{\star}\|^{2}_{P}-2{\alpha}\langle\mathcal{A}(\omega)-\mathcal{A}(\omega^{\star}),\omega-\omega^{\star}\rangle_{P}+\alpha^{2}\|\mathcal{A}(\omega)-\mathcal{A}(\omega^{\star})\|_{P}^{2}\leq\rho\|\omega-\omega^{\star}\|^{2}_{P}$,
and the conclusion follows because (7) can be rewritten as
$\omega^{k+1}=\omega^{k}-\alpha\mathcal{A}(\omega^{k})$. ∎

For the case of aggregative games, (7a) can be implemented in a semi-
decentralized way, as in Algorithm 1.

Algorithm 1 Semi-decentralized GNE seeking

Iterate to convergence: for all $k\in\mathbb{N}$,

  * •

Each $i\in\mathcal{I}$: receive $\lambda^{k}$, $\sigma^{k}$ from coordinator;
update

$\displaystyle x_{i}^{k+1}$
$\displaystyle=x_{i}^{k}-\alpha\left(\nabla_{x_{i}}J_{i}(x_{i}^{k},{\sigma^{k}})+A_{i}^{\top}{\lambda}^{k}\right)$

  * •

Coordinator: receive
$\\{\phi_{i}({x_{i}}^{k+1}),A_{i}x_{i}^{k}-b_{i}\\}_{i\in\mathcal{I}}$; update

$\displaystyle\lambda^{k+1}$
$\displaystyle=\lambda^{k}+\alpha\textstyle\sum_{i\in\mathcal{I}}(A_{i}x_{i}^{k}-b_{i}),$
$\displaystyle\sigma^{k+1}$
$\displaystyle=\textstyle\frac{1}{N}\sum_{i\in\mathcal{I}}\phi_{i}(x_{i}^{k+1})$

##  IV Partial-decision information

In this section, we consider aggregative games in the so called-partial-
decision information scenario, where there is no central coordinator, and the
agents can only exchange information via peer-to-peer communication over a
communication graph $\mathcal{G}=(\mathcal{I},\mathcal{E})$, with weight
matrix $W\in\mathbb{R}^{N\times N}$, and $w_{i,j}\coloneqq[W]_{i,j}>0$ if and
only if $(j,i)$ belongs to the set of edges
$\mathcal{E}\subseteq\mathcal{I}\times\mathcal{I}$.

######  Assumption 5 (Communication)

The graph $\mathcal{G}$ is strongly connected. The weight matrix $W$
satisfies:

  * •

Double stochasticity:
${\boldsymbol{1}}^{\top}W={\boldsymbol{1}}^{\top},W{\boldsymbol{1}}=W{\boldsymbol{1}}$;

  * •

Self-loops: $w_{i,i}>0$ for all $i\in\mathcal{I}$.

We denote
$\theta\coloneqq\|W-\frac{1}{N}{\boldsymbol{1}}{\boldsymbol{1}}^{\top}\|<1$.
$\square$

To remedy the lack of global knowledge, we let each agent $i\in\mathcal{I}$
keep:

  * •

$\boldsymbol{\sigma}_{i}\in\mathbb{R}^{q}$: estimate of the aggregation
$\sigma(x)$;

  * •

$\boldsymbol{\lambda}_{i}\in\mathbb{R}^{m}$: estimate of the dual variable
$\lambda$;

  * •

$\boldsymbol{r}_{i}\in\mathbb{R}^{m}$: estimate of the residual $Ax-b$;

  * •

$z_{i}\in\mathbb{R}^{m}$: additional dual variable.

Our proposed dynamics are illustrated in Algorithm 2, where

$\displaystyle\boldsymbol{F}_{i}(x_{i},\boldsymbol{\sigma}_{i})\coloneqq\nabla_{x_{i}}J_{i}(x_{i},\boldsymbol{\sigma}_{i})+\frac{1}{N}[D\phi_{i}(x_{i})]^{\top}\nabla_{\boldsymbol{\sigma}_{i}}J_{i}(x_{i},\boldsymbol{\sigma}_{i}).$
(9)

Algorithm 2 Fully-distributed GNE seeking

Initialization: choose $\alpha>0$ as in Theorem 2; for all $i\in\mathcal{I}$,
set $x_{i}^{0}\in\mathbb{R}^{n_{i}}$,
$\boldsymbol{\sigma}_{i}^{0}=\phi_{i}(x_{i}^{0})$,
$z_{i}^{0}\in\mathbb{R}^{m}$, $\boldsymbol{\lambda}_{i}^{0}=z_{i}^{0}$,
$\boldsymbol{r}_{i}^{0}=A_{i}x_{i}^{0}-b_{i}$.
Iterate to convergence: for all $k\in\mathbb{N}$, for all $i\in\mathcal{I},$

  * •

Local variables update:

$\displaystyle x_{i}^{k+1}$
$\displaystyle=x_{i}^{k}-\alpha\left(\boldsymbol{F}_{i}(x_{i},\boldsymbol{\sigma}_{i}^{k})+A_{i}^{\top}\boldsymbol{\lambda}_{i}^{k}\right)$
$\displaystyle z_{i}^{k+1}$ $\displaystyle=z_{i}^{k}+\alpha
N\boldsymbol{r}_{i}^{k}$

  * •

Tracking: Agent $i$ exchanges the variables
$(\boldsymbol{\sigma}_{i},\boldsymbol{\lambda}_{i},\boldsymbol{r}_{i})$ with
its neighbors, and does

$\displaystyle\boldsymbol{\sigma}_{i}^{k+1}$
$\displaystyle=\sum_{j\in\mathcal{N}_{i}}w_{i,j}\boldsymbol{\sigma}_{j}^{k}+\phi_{i}(x_{i}^{k+1})-\phi_{i}(x_{i}^{k})$
$\displaystyle\boldsymbol{r}_{i}^{k+1}$
$\displaystyle=\sum_{j\in\mathcal{N}_{i}}w_{i,j}\boldsymbol{r}_{j}^{k}+A_{i}x_{i}^{k+1}-A_{i}x_{i}^{k}$
$\displaystyle\boldsymbol{\lambda}_{i}^{k+1}$
$\displaystyle=\sum_{j\in\mathcal{N}_{i}}w_{i,j}\boldsymbol{\lambda}_{j}^{k}+z_{i}^{k+1}-z_{i}^{k}$

Let us define
$\boldsymbol{\sigma}=\mathrm{col}((\boldsymbol{\sigma}_{i})_{i\in\mathcal{I}})$,
$\boldsymbol{r}=\mathrm{col}((\boldsymbol{r}_{i})_{i\in\mathcal{I}})$,
$\boldsymbol{\lambda}=\mathrm{col}((\boldsymbol{\lambda}_{i})_{i\in\mathcal{I}})$
and the extended game mapping

$\displaystyle\boldsymbol{F}(x,\boldsymbol{\sigma})\coloneqq\mathrm{col}((\boldsymbol{F}_{i}(x_{i},\boldsymbol{\sigma}_{i}))_{i\in\mathcal{I}}).$
(10)

Note that $\boldsymbol{F}(x,{\boldsymbol{1}}\otimes\sigma(x))=F(x)$.
Furthermore, let

$\displaystyle\bar{\boldsymbol{\lambda}}$
$\displaystyle=\textstyle\frac{1}{N}\sum_{i\in\mathcal{I}}\boldsymbol{\lambda}_{i},\quad\tilde{\boldsymbol{\lambda}}=\boldsymbol{\lambda}-{\boldsymbol{1}}\otimes\bar{\boldsymbol{\lambda}}$
(11a) $\displaystyle\bar{\boldsymbol{\sigma}}$
$\displaystyle=\textstyle\frac{1}{N}\sum_{i\in\mathcal{I}}\boldsymbol{\sigma}_{i},\quad\tilde{\boldsymbol{\sigma}}=\boldsymbol{\sigma}-{\boldsymbol{1}}\otimes\bar{\boldsymbol{\sigma}}$
(11b) $\displaystyle\bar{\boldsymbol{r}}$
$\displaystyle=\textstyle\frac{1}{N}\sum_{i\in\mathcal{I}}\boldsymbol{r}_{i},\quad\tilde{\boldsymbol{r}}=\boldsymbol{r}-{\boldsymbol{1}}\otimes\bar{\boldsymbol{r}}.$
(11c)

The following lemma shows an invariance property typical of tracking dynamics
as those in Algorithm 2.

###### Lemma 2

For all $k\in\mathbb{N}$, it holds that
$\bar{\boldsymbol{\lambda}}^{k}=\frac{1}{N}\textstyle\sum_{i\in\mathcal{I}}z_{i}^{k}$,
$\bar{\boldsymbol{r}}^{k}=\frac{1}{N}\textstyle\sum_{i\in\mathcal{I}}(A_{i}x_{i}^{k}-b_{i})$,
$\bar{\boldsymbol{\sigma}}^{k}=\sigma(x^{k})$. $\square$

###### Proof:

Via induction, by the initialization and double stochasticity of $W$. ∎

To study the convergence of Algorithm 2, we first need the following crucial
reformulation.

###### Lemma 3

The iteration in Algorithm 2 is equivalent to

$\displaystyle\begin{aligned} \begin{bmatrix}x^{k+1}\\\
\bar{\boldsymbol{\lambda}}^{k+1}\end{bmatrix}\\!\\!=\\!\underbrace{\boldsymbol{\xi}^{k}-\alpha\mathcal{A}(\boldsymbol{\xi}^{k})}_{\coloneqq\mathcal{B}_{1}(\boldsymbol{\xi}^{k})}+\\!\underbrace{\left[\begin{smallmatrix}\\!\alpha\left(\boldsymbol{F}(x^{k},\boldsymbol{\sigma}^{k})-\boldsymbol{F}(x^{k},{\boldsymbol{1}\otimes}\bar{\boldsymbol{\sigma}}^{k})+\boldsymbol{A}^{\top}\tilde{\boldsymbol{\lambda}}^{k}\right)\\!\\\
\boldsymbol{0}\end{smallmatrix}\right]}_{\coloneqq\mathcal{B}_{2}(\boldsymbol{\omega}^{k})}\\\
\begin{bmatrix}\tilde{\boldsymbol{\sigma}}^{k+1}\\\
\tilde{\boldsymbol{r}}^{k+1}\\\
\tilde{\boldsymbol{\lambda}}^{k+1}\end{bmatrix}=\underbrace{\begin{bmatrix}\boldsymbol{W}\tilde{\boldsymbol{\sigma}}^{k}\\\
\boldsymbol{W}\tilde{\boldsymbol{r}}^{k}\\\
\boldsymbol{W}\tilde{\boldsymbol{\lambda}}^{k}\end{bmatrix}}_{\coloneqq\mathcal{B}_{3}(\boldsymbol{\chi}^{k})}+\underbrace{\begin{bmatrix}\tilde{\Pi}\mathrm{col}((\phi_{i}(x_{i}^{k+1})-\phi_{i}(x_{i}^{k}))_{i\in\mathcal{I}})\\\
\tilde{\Pi}\mathrm{col}((A_{i}(x_{i}^{k+1}-x_{i}^{k}))_{i\in\mathcal{I}})\\\
\alpha
N\tilde{\boldsymbol{r}}^{k}\end{bmatrix}}_{\coloneqq\mathcal{B}_{4}(\boldsymbol{\omega}^{k})}\\\\[-6.99997pt]
\end{aligned}$ (12)

where $\boldsymbol{\omega}=(\boldsymbol{\xi},\boldsymbol{\chi})$,
$\boldsymbol{\xi}=(x,\bar{\boldsymbol{\lambda}})$,
$\boldsymbol{\chi}=(\tilde{\boldsymbol{\sigma}},\tilde{\boldsymbol{r}},\tilde{\boldsymbol{\lambda}})$,
and $\tilde{\Pi}\coloneqq
I-(\frac{1}{N}{\boldsymbol{1}}{\boldsymbol{1}}^{\top})\otimes I_{N}$,
$\boldsymbol{W}=W\otimes I$,
${\boldsymbol{A}=\mathrm{diag}((A_{i})_{i\in\mathcal{I}})}$: the sequence
$(x^{k},\boldsymbol{\sigma}^{k},\boldsymbol{r}^{k},\boldsymbol{\lambda}^{k})_{k\in\mathbb
N}$ generated by Algorithm 2 and the sequence
$(x^{k},\tilde{\boldsymbol{\sigma}}^{k}+{\boldsymbol{1}}\otimes\sigma(x^{k}),\tilde{\boldsymbol{r}}^{k}+{\boldsymbol{1}}\otimes(Ax^{k}-b),\bar{\boldsymbol{\lambda}}^{k}+\tilde{\boldsymbol{\lambda}}^{k})_{k\in\mathbb
N}$ generated by (12) coincide. $\square$

###### Proof:

The update of $\boldsymbol{\chi}$ follows by noting that
$\tilde{\boldsymbol{\sigma}}=\tilde{\Pi}\boldsymbol{\sigma}$,
$\tilde{\boldsymbol{r}}=\tilde{\Pi}\boldsymbol{r}$,
$\tilde{\boldsymbol{\lambda}}=\tilde{\Pi}\boldsymbol{\lambda}$ and
$\tilde{\Pi}\boldsymbol{W}\tilde{\Pi}=\boldsymbol{W}\tilde{\Pi}$. Then, the
proof follows by definition of $\mathcal{A}$, by using Lemma 2, and finally by
noting that
$\boldsymbol{F}(x^{k},{\boldsymbol{1}}\otimes\bar{\boldsymbol{\sigma}}^{k})=F(x^{k})$
by Lemma 2. Note that
$\boldsymbol{\sigma}=\tilde{\boldsymbol{\sigma}}+{\boldsymbol{1}}\otimes\sigma(x)$
and $\boldsymbol{r}=\tilde{\boldsymbol{r}}+\frac{1}{N}\otimes(Ax-b)$, which
allows us to eliminate the variables $\bar{\boldsymbol{\sigma}}$ and
$\bar{\boldsymbol{r}}$ in the iteration, and similarly for $z_{i}$, since
$\bar{\boldsymbol{\lambda}}^{k+1}=\bar{\boldsymbol{\lambda}}^{k}+\frac{1}{N}\sum_{i\in\mathcal{I}}(z_{i}^{k+1}-z_{i}^{k})=\bar{\boldsymbol{\lambda}}^{k}+\frac{1}{N}\sum_{i\in\mathcal{I}}(\alpha
N\boldsymbol{r}_{i}^{k})=\bar{\boldsymbol{\lambda}}^{k}+\alpha(Ax^{k}-b)$ by
Lemma 2. ∎

######  Theorem 2 (GNE seeking in partial-decision information)

Let Assumptions 1-5 hold. Then, there exists $\alpha_{\max}>0$ such that, for
all $0<\alpha<\alpha_{\max}$, the iteration in (12) converges linearly to
$\boldsymbol{\omega}^{\star}=(\boldsymbol{\xi}^{\star},\boldsymbol{0})$, with
$\boldsymbol{\xi}^{\star}=(x^{\star},\lambda^{\star})$: for all
$k\in\mathbb{N}$

$\displaystyle V(\boldsymbol{\omega}^{k+1})\leq\eta
V(\boldsymbol{\omega}^{k}),$ (13)

where

$\displaystyle
V(\boldsymbol{\omega})\coloneqq\textstyle\frac{1}{2}\|\boldsymbol{\xi}-\boldsymbol{\xi}^{\star}\|_{P}^{2}+\|\boldsymbol{\chi}\|^{2}$
(14)

for some $\eta<1$. $\square$

###### Proof:

Note that the operator $\mathcal{B}_{3}$ in (12) is a contraction by
Assumption 5, definition of $\boldsymbol{\chi}$ and (11); instead
$\mathcal{B}_{1}$ is a contraction for $\alpha$ small enough as in Theorem 1.
Moreover, the mappings $\mathcal{B}_{2}$ and $\mathcal{B}_{3}$ are Lipschitz
continuous with constant proportional to the step size $\alpha$, by the
assumptions. Therefore, with Lemma 1 and the reformulation in (12) in place,
the proof can be carried out via standard small-gain arguments, and is hence
only sketched here. By the Cauchy–Schwarz inequality, we can bound

$\displaystyle\hphantom{{}={}}\|\mathcal{B}_{1}(\boldsymbol{\xi}^{k})+\mathcal{B}_{2}(\boldsymbol{\omega}^{k})-\boldsymbol{\xi}^{\star}\|_{P}$
$\displaystyle\leq\begin{multlined}(1-{2}\alpha\mu_{\mathcal{A}}+\alpha^{2}\ell_{\mathcal{A}}^{2})\|\boldsymbol{\xi}^{k}-\boldsymbol{\xi}^{\star}\|^{2}_{P}\\\
+\alpha\ell_{1}\|\boldsymbol{\xi}^{k}-\boldsymbol{\xi}^{\star}\|_{P}\|\boldsymbol{\chi}^{k}\|+\alpha^{2}\ell_{2}\|\boldsymbol{\chi}^{k}\|^{2},\end{multlined}(1-{2}\alpha\mu_{\mathcal{A}}+\alpha^{2}\ell_{\mathcal{A}}^{2})\|\boldsymbol{\xi}^{k}-\boldsymbol{\xi}^{\star}\|^{2}_{P}\\\
+\alpha\ell_{1}\|\boldsymbol{\xi}^{k}-\boldsymbol{\xi}^{\star}\|_{P}\|\boldsymbol{\chi}^{k}\|+\alpha^{2}\ell_{2}\|\boldsymbol{\chi}^{k}\|^{2},$

and

$\displaystyle\hphantom{{}={}}\|\mathcal{B}_{3}(\boldsymbol{\chi}^{k})+\mathcal{B}_{4}(\boldsymbol{\omega}^{k})\|^{2}$
$\displaystyle\leq\begin{multlined}\theta\|\boldsymbol{\chi}^{k}\|^{2}+\alpha\ell_{3}\|\boldsymbol{\xi}^{k}-\boldsymbol{\xi}^{\star}\|_{P}\|\boldsymbol{\chi}^{k}\|+\alpha\ell_{4}\|\boldsymbol{\chi}^{k}\|^{2}\\\
+\alpha^{2}\ell_{5}\|\boldsymbol{\xi}^{k}-\boldsymbol{\xi}_{1}^{\star}\|_{P}^{2}+\alpha^{2}\ell_{6}\|\boldsymbol{\chi}^{k}\|^{2},\end{multlined}\theta\|\boldsymbol{\chi}^{k}\|^{2}+\alpha\ell_{3}\|\boldsymbol{\xi}^{k}-\boldsymbol{\xi}^{\star}\|_{P}\|\boldsymbol{\chi}^{k}\|+\alpha\ell_{4}\|\boldsymbol{\chi}^{k}\|^{2}\\\
+\alpha^{2}\ell_{5}\|\boldsymbol{\xi}^{k}-\boldsymbol{\xi}_{1}^{\star}\|_{P}^{2}+\alpha^{2}\ell_{6}\|\boldsymbol{\chi}^{k}\|^{2},$

where $\ell_{1},\ell_{2},\ell_{3},\ell_{4},\ell_{5},\ell_{6}>0$ are parameters
independent of $\alpha$. Therefore, for the norm $V$ in (14) we have

$\displaystyle\hphantom{{}={}}V(\boldsymbol{\omega}^{k+1})=\left[\begin{smallmatrix}\|\boldsymbol{\xi}^{k+1}-\boldsymbol{\xi}^{\star}\|_{P}\\\
\|\boldsymbol{\chi}^{k+1}\|\end{smallmatrix}\right]^{\top}\left[\begin{smallmatrix}\|\boldsymbol{\xi}^{k+1}-\boldsymbol{\xi}^{\star}\|_{P}\\\
\|\boldsymbol{\chi}^{k+1}\|\end{smallmatrix}\right]$
$\displaystyle\leq\left[\begin{smallmatrix}\|\boldsymbol{\xi}^{k}-\boldsymbol{\xi}^{\star}\|_{P}\\\
\|\boldsymbol{\chi}^{k}\|\end{smallmatrix}\right]^{\top}M\left[\begin{smallmatrix}\|\boldsymbol{\xi}^{k}-\boldsymbol{\xi}^{\star}\|_{P}\\\
\|\boldsymbol{\chi}^{k}\|\end{smallmatrix}\right]$
$\displaystyle\leq\uplambda_{{\max}}(M)V(\boldsymbol{\omega}^{k}),$

where

$\displaystyle
M\coloneqq\begin{bmatrix}1-{2}\alpha\mu_{\mathcal{A}}+\alpha^{2}(\ell_{\mathcal{A}}+\ell_{5})&\alpha\frac{1}{2}(\ell_{1}+\ell_{3})\\\\[10.00002pt]
\alpha\frac{1}{2}(\ell_{1}+\ell_{3})&\theta+\alpha\ell_{4}+\alpha^{2}({\ell_{2}+}\ell_{6})\end{bmatrix}$

and $\uplambda_{\max}(M)=\|M\|<1$ for small enough $\alpha>0$. ∎

Note that, for the special case $A={\boldsymbol{1}}^{\top}$, a linearly
convergent continuous-time method for GNE seeking in partial-decision
information was studied in [10]. Yet, to our knowledge, Theorem 2 is the first
result to ensure linear convergence in the case of more general general full-
rank constraints. Due to space limitations, we do not derive here an explicit
expression for $\alpha_{\max}$ and $\eta$ (or $\mu_{\mathcal{A}}$ in Lemma 1).

###### Remark 1

The proof of Theorem 1 directly applies to the case of a time-varying graph
with weight matrix $W^{k}$, provided that Assumption 5 holds for each
$k\in\mathbb{N}$. With some modification, the argument can be extended also to
the case of doubly stochastic graphs that are not strongly connected at each
step, but such that $\|W^{kQ}W^{kQ+1}\dots
W^{(k+1)Q}-\frac{1}{N}{\boldsymbol{1}}{\boldsymbol{1}}^{\top}\|\leq\theta<1$,
for a $Q>0$ and all ${k\in\mathbb{N}}$. $\square$

##  V Equilibrium tracking in time-varying games

We now consider the case where the game in (1) varies over time at a rate such
that we can not assume a time-scale separation between the game evolution and
the GNE seeking iterations. For each time index $t\in\mathbb{N}$, the agents
acquire a new instance of the game:

$\displaystyle(\forall i\in\mathcal{I})\ \mathop{\rm
min}_{y_{i}\in\mathbb{R}^{{n_{i}}}}\;J^{t}_{i}(y_{i},x_{-i})\quad\text{s.t.}\
(y_{i},x_{-i})\in\mathcal{X}^{t}.$ (15)

We consider the case when the constraints of the game vary only in their
affine part, that is, $\mathcal{X}^{t}:=\\{x\in\mathbb{R}^{n}|Ax=b^{t}\\}$,
and Assumptions 1–3 hold for each $t$. The games in (15) define a primal-dual
GNE pair sequence $(\omega^{\star}_{t})_{t\in\mathbb{N}}$, corresponding to
the zero set of the KKT operators $(\mathcal{A}_{t})_{t\in\mathbb{N}}$ defined
for all $t$ as in (II), with $F,b$ replaced respectively by
$F^{t}:=\mathrm{col}((\nabla_{x_{i}}J_{i}^{t})_{i\in\mathcal{I}})$ and
$b^{t}$. The GNE sequence is unique for each $t$ following the strong
monotonicity of $\mathcal{A}_{t}$ and [24, Ex. 22.12]. As the rate at which
the problem varies is comparable to the agents’ computation time, the agents
can only compute an approximation of the GNE at time $t$ before they are
presented with a new instance of the problem. The goal of the agents is then
to find a sequence $(\omega^{t})_{t\in\mathbb{N}}$ which asymptotically tracks
relatively well the GNE sequence. We formulate the following assumption, which
is standard in the literature of online optimization [25, Assm. 1], [15, Eq.
9] and is verified, for example, for games affected by a bounded process noise
in the linear constraints [17, Lemma 5].

###### Assumption 6

For some $\delta\geq 0$, it holds that the solution $\omega_{t}^{\star}$ of
the game in (15) satisfies

$\sup_{t\in\mathbb N}\|\omega^{\star}_{t+1}-\omega^{\star}_{t}\|\leq\delta.$

Assumption 6 implies that the solution at time $t$ is an approximate solution
for the problem at time $t+1$. Given an estimate of the solution at time
$\omega^{t-1}$ for some time step $t$, we then propose to compute $\omega^{t}$
by performing $K$ iterations of the iteration in (7), warm-started at
$\omega^{t}$, that is:

$\displaystyle y^{t,0}$ $\displaystyle=\omega^{t-1}$ (16a) $\displaystyle
y^{t,k+1}$ $\displaystyle=y^{t,k}-\alpha\mathcal{A}_{t}(y^{t,k})$
$\displaystyle\text{for}~{}k=0,...,K-1$ (16b) $\displaystyle\omega^{t}$
$\displaystyle=y^{K},$ (16c)

where $(y^{t,k})_{k\in\\{1,...,K\\}}$ are auxiliary variables. The following
lemma shows that, for an appropriately chosen step size, the proposed
algorithm tracks the GNE trajectory up to an asymptotic error which depends on
$\delta$ and $K$.

###### Theorem 3

For any $0<\alpha<\frac{2\mu_{\mathcal{A}}}{\ell_{\mathcal{A}}^{2}}$,
$\omega^{0}$, $K\in\mathbb{N}_{>0}$, the sequence
$(\omega^{t})_{t\in\mathbb{N}}$ generated by the iteration in (16) satisfies

$\limsup_{t\rightarrow\infty}\|\omega^{t}-\omega^{\star}_{t}\|_{P}\leq\frac{\rho^{K/2}}{1-\rho^{K/2}}\delta\sqrt{\uplambda_{\text{max}}(P)}.$
(17)

where $\rho$ is as in Theorem 1. $\square$

###### Proof:

Following Theorem 1, for $\alpha\leq
2\frac{\mu_{\mathcal{A}}}{\ell_{\mathcal{A}}^{2}}$,

$\|\omega^{t}-\omega_{t}^{\star}\|_{P}\leq\rho^{K/2}\|\omega^{t-1}-\omega_{t}^{\star}\|_{P}.$

From the latter, the triangle inequality and the fact
$\|z\|^{2}_{P}\leq\uplambda_{\text{max}}(P)\|z\|^{2}$ for all $z$:

$\displaystyle\|\omega^{t}-\omega_{t}^{\star}\|_{P}$
$\displaystyle\leq\rho^{K/2}\|\omega^{t-1}-\omega_{t-1}^{\star}\|_{P}+\rho^{K/2}\|\omega_{t}^{\star}-\omega_{t-1}^{\star}\|_{P}$
$\displaystyle\leq\rho^{K/2}\|\omega^{t-1}-\omega_{t-1}^{\star}\|_{P}+\rho^{K/2}\delta\sqrt{\uplambda_{\text{max}}(P)}.$

Iterating the latter $t$ times, we obtain

$\displaystyle\|\omega^{t}-\omega_{t}^{\star}\|_{P}$
$\displaystyle\leq\rho^{Kt/2}\|\omega^{0}-\omega_{0}^{\star}\|_{P}+\sum_{\tau=1}^{t}\rho^{K\tau/2}\delta\sqrt{\uplambda_{\text{max}}(P)}.$

Since $\rho^{K/2}<1$, the thesis follows by the convergence of the geometric
sequence. ∎

Let us now turn our attention to the time-varying counterpart of the partial-
decision information setup described in Section IV. Again, we consider
aggregative games in the form

$J^{t}_{i}(x_{i},x_{-i})=J^{t}_{i}(x_{i},\sigma^{t}(x))$

where $\sigma^{t}(x):=\frac{1}{N}\sum_{i\in\mathcal{I}}\phi_{i}^{t}(x_{i})$
and we postulate that $\phi_{i}^{t}$ satisfies Assumption 4 for all $t$. As in
Section IV, we augment the state of each agent with an estimate of
$\sigma^{t}(x)$, of the dual variable and of the residual $Ax-b^{t}$. For
every $t$, denote
$\boldsymbol{\omega}^{\star}_{t}=(\omega_{t}^{\star},\boldsymbol{0})$, where
$\omega_{t}^{\star}=(x^{\star}_{t},\lambda^{\star}_{t})$ is a primal-dual
solution of the game at time $t$ and the vector of zeros represents the target
estimation error. We then define the reference trajectory as
$(\boldsymbol{\omega}_{t}^{\star})_{t\in\mathbb{N}}$. At each time-step, we
propose to appropriately re-initialize the dynamic tracking of the estimated
variables and, in the spirit of the iteration in (16), to apply a finite
number of iterations of Algorithm 2. The resulting method is illustrated in
Algorithm 3. We obtain the following counterpart of Lemma 2 for the re-
initialized dynamic tracking.

Algorithm 3 Time-varying fully-distributed GNE seeking

Initialization: choose $\alpha>0$ as in Theorem 2; for all $i\in\mathcal{I}$,
set $x_{i}^{0}\in\mathbb{R}^{n_{i}}$,
$\boldsymbol{\sigma}_{i}^{0}=\boldsymbol{0}$, $z_{i}^{0}\in\mathbb{R}^{m}$,
$\boldsymbol{\lambda}_{i}^{0}=z_{i}^{0}$,
$\boldsymbol{r}_{i}^{0}=A_{i}x_{i}^{0}$, $b_{i}^{0}=\boldsymbol{0}$,
$\phi_{i}^{0}(\cdot)=\boldsymbol{0}$.
Iteration: at time $t\in\mathbb{N}_{>0}$, for each agent $i\in\mathcal{I}$,

  1. 1.

Acquire $J_{i}^{t}$, $\phi_{i}^{t}$, $b_{i}^{t}$

  2. 2.

Re-initialize $\hat{x}_{i}^{t,0}=x_{i}^{t-1}$,
$\hat{z}_{i}^{t,0}=z_{i}^{t-1}$,
$\hat{\boldsymbol{\sigma}}_{i}^{t,0}={\boldsymbol{\sigma}}_{i}^{t-1}-\phi^{t-1}_{i}(x_{i}^{t-1})+\phi^{t}_{i}(x_{i}^{t-1})$,
$\hat{\boldsymbol{r}}_{i}^{t,0}=\boldsymbol{r}_{i}^{t-1}+b_{i}^{t}-b_{i}^{t-1}$,
$\hat{\boldsymbol{\lambda}}_{i}^{t,0}={\boldsymbol{\lambda}}_{i}^{t-1}$

  3. 3.

For all $k\in\\{0,...,K-1\\}$, for all $i\in\mathcal{I}:$

     * •

Local variables update:

$\displaystyle\hat{x}_{i}^{t,k+1}$
$\displaystyle=\hat{x}_{i}^{t,k}-\alpha\left(\boldsymbol{F}^{t}_{i}(\hat{x}_{i}^{t,k},\hat{\boldsymbol{\sigma}}_{i}^{t,k})+A_{i}^{\top}\hat{\boldsymbol{\lambda}}_{i}^{t,k}\right)$
$\displaystyle\hat{z}_{i}^{t,k+1}$ $\displaystyle=\hat{z}_{i}^{t,k}+\alpha
N\hat{\boldsymbol{r}}_{i}^{t,k}$

     * •

Estimation update: Agent $i$ exchanges the variables
$(\hat{\boldsymbol{\sigma}}_{i}^{t,k},\hat{\boldsymbol{\lambda}}^{t,k}_{i},\hat{\boldsymbol{r}}^{t,k}_{i})$
with its neighbors, and updates

$\displaystyle\hat{\boldsymbol{\sigma}}_{i}^{t,k+1}$
$\displaystyle=\sum_{j\in\mathcal{N}_{i}}w_{i,j}\hat{\boldsymbol{\sigma}}_{j}^{t,k}+\phi^{t}_{i}(\hat{x}_{i}^{t,k+1})-\phi^{t}_{i}(\hat{x}_{i}^{t,k})$
$\displaystyle\hat{\boldsymbol{r}}_{i}^{t,k+1}$
$\displaystyle=\sum_{j\in\mathcal{N}_{i}}w_{i,j}\hat{\boldsymbol{r}}_{j}^{t,k}+A_{i}\hat{x}_{i}^{t,k+1}-A_{i}\hat{x}_{i}^{t,k}$
$\displaystyle\hat{\boldsymbol{\lambda}}_{i}^{t,k+1}$
$\displaystyle=\sum_{j\in\mathcal{N}_{i}}w_{i,j}\hat{\boldsymbol{\lambda}}_{j}^{t,k}+\hat{z}_{i}^{t,k+1}-\hat{z}_{i}^{t,k}$

  4. 4.

Set $x_{i}^{t}=\hat{x}_{i}^{t,K}$, $z_{i}^{t}=\hat{z}_{i}^{t,K}$,
$\boldsymbol{\sigma}_{i}^{t}=\hat{\boldsymbol{\sigma}}_{i}^{t,K}$,
$\boldsymbol{r}_{i}^{t}=\hat{\boldsymbol{r}}_{i}^{t,K}$,
$\boldsymbol{\lambda}_{i}^{t}=\hat{\boldsymbol{\lambda}}_{i}^{t,K}$

###### Lemma 4

For all $t\in\mathbb{N}$,
$\bar{\boldsymbol{\lambda}}^{t}=\sum_{i\in\mathcal{I}}({z}_{i}^{t})$, it holds
that
$\bar{\boldsymbol{r}}^{t}=\sum_{i\in\mathcal{I}}(A_{i}{x}_{i}^{t}-b_{i}^{t})$,
$\bar{\boldsymbol{\sigma}}^{t}=\sigma^{t}({x}^{t})$. $\square$

###### Proof:

Let for some $t$:

$\displaystyle\bar{\boldsymbol{r}}^{t}=\tfrac{1}{N}\textstyle\sum_{i\in\mathcal{I}}A_{i}{x}_{i}^{t}-b_{i}^{t}.$
(18)

From the update step 4) and the re-initialization step 2), we obtain
${x}_{i}^{t}=\hat{x}_{i}^{t,K}=\hat{x}_{i}^{t+1,0}$ and

$\displaystyle\tfrac{1}{N}\textstyle\sum_{i\in\mathcal{I}}\hat{\boldsymbol{r}}_{i}^{t+1,0}$
$\displaystyle=\bar{\boldsymbol{r}}^{t}-\tfrac{1}{N}\textstyle\sum_{i\in\mathcal{I}}(b_{i}^{t+1}-b_{i}^{t})$
$\displaystyle\overset{\eqref{eq:lem:invariance_2:1}}{=}\tfrac{1}{N}\textstyle\sum_{i\in\mathcal{I}}(A_{i}\hat{x}_{i}^{t+1,0}-b_{i}^{t+1}).$

Then, by Lemma 2,
$\frac{1}{N}\sum_{i\in\mathcal{I}}\hat{\boldsymbol{r}}_{i}^{t+1,K}=\tfrac{1}{N}\textstyle\sum_{i\in\mathcal{I}}A_{i}\hat{x}_{i}^{t+1,K}-b_{i}^{t+1}$.
From the latter and the update step 4),

$\bar{\boldsymbol{r}}^{t+1}=\tfrac{1}{N}\textstyle\sum_{i\in\mathcal{I}}\hat{\boldsymbol{r}}^{t+1,K}=\tfrac{1}{N}\textstyle\sum_{i\in\mathcal{I}}A_{i}{x}_{i}^{t+1}-b_{i}^{t+1}.$

The result then follows by induction and similarly for
$\bar{\boldsymbol{\sigma}}^{t}$ and $\bar{\boldsymbol{\lambda}}^{t}$. ∎

The re-inizialization of the dynamic tracking introduces an additional error
term in the solution tracking, which requires the following technical
assumption on the time variation of the functions
$(\phi_{i}^{t})_{t\in\mathbb{N}}$:

###### Assumption 7

For some $\delta_{\phi}>0$, it holds that

$\sup_{x,t}\|\mathrm{col}(\phi_{i}^{t}(x_{i})-\phi_{i}^{t+1}(x_{i}))_{i\in\mathcal{I}}\|\leq\delta_{\phi}.$

$\square$

###### Theorem 4

Let
${\boldsymbol{\omega}}^{t}=\mathrm{col}(x^{t},\bar{\boldsymbol{\lambda}}^{t},\tilde{\boldsymbol{\sigma}}^{t},\tilde{\boldsymbol{r}}^{t},\tilde{\boldsymbol{\lambda}}^{t}).$
There exists $\alpha_{\text{max}}$ such that, for every
$0<\alpha<\alpha_{\text{max}}$, the sequence
$(\boldsymbol{\omega}^{t})_{t\in\mathbb{N}}$ generated by Algorithm 3
satisfies

$\displaystyle\begin{split}\limsup_{t\rightarrow\infty}&\|\boldsymbol{\omega}^{t}-\boldsymbol{\omega}^{\star}_{t}\|_{Q}\leq\\\
&\tfrac{\eta^{K/2}}{1-\eta^{K/2}}\sqrt{\uplambda_{\text{max}}(Q)}((1+N\ell_{A})\delta+\delta_{\phi})\end{split}$
(19)

where $Q=\mathrm{diag}(P/2,I)$, for some $\eta\in(0,1)$. $\square$

###### Proof:

Following the same steps as in Lemma 3, the inner iteration (Step 3) of
Algorithm 3 is equivalent to the iteration in (12), where $\boldsymbol{F}$ and
$\phi_{i}$ are substituted by their time-varying counterpart. Now denote

$\displaystyle\psi^{t}=$
$\displaystyle\mathrm{col}(\boldsymbol{0},\boldsymbol{0},\mathrm{col}((\phi_{i}^{t}(x_{i}^{t})-\phi_{i}^{t-1}(x_{i}^{t}))_{i\in\mathcal{I}},$
$\displaystyle\mathrm{col}(b_{i}^{t}-b_{i}^{t-1})_{i\in\mathcal{I}},\boldsymbol{0}).$

From Assumptions 6, 7 and from $Ax_{t}^{\star}=b^{t}$,

$\displaystyle\begin{split}\|\psi^{t}\|&\leq\delta_{\phi}+\textstyle\sum_{i\in\mathcal{I}}\|b_{i}^{t}-b_{i}^{t-1}\|\\\
&\leq\delta_{\phi}+N\|b^{t}-b^{t-1}\|\leq\delta_{\phi}+N\ell_{A}\delta\end{split}$
(20)

From Theorem 2 and accounting for the re-initialization step, we find for
every $t$:

$\displaystyle\|\boldsymbol{\omega}^{t}-\boldsymbol{\omega}^{\star}_{t}\|_{Q}\leq\eta^{K/2}\|{\boldsymbol{\omega}}^{t-1}+\psi^{t}-\boldsymbol{\omega}^{\star}_{t}\|_{Q}$
(21)

for some $\eta\in(0,1)$. By the triangle inequality, Assumption 6 and (20),
and from the fact $\|z\|^{2}_{Q}\leq\uplambda_{\text{max}}(Q)\|z\|^{2}$, we
have

$\displaystyle\|{\boldsymbol{\omega}}_{t-1}+\psi_{t}-\boldsymbol{\omega}^{\star}_{t}\|_{Q}\leq\|{\boldsymbol{\omega}}_{t-1}-\boldsymbol{\omega}^{\star}_{t}\|_{Q}+\|\psi_{t}\|_{Q}$
$\displaystyle\leq\|{\boldsymbol{\omega}}_{t-1}-\boldsymbol{\omega}^{\star}_{t-1}\|_{Q}+\|\boldsymbol{\omega}^{\star}_{t}-\boldsymbol{\omega}^{\star}_{t-1}\|_{Q}+\|\psi_{t}\|_{Q}$
$\displaystyle\leq\|{\boldsymbol{\omega}}_{t-1}-\boldsymbol{\omega}^{\star}_{t-1}\|_{Q}+\sqrt{\uplambda_{\text{max}}(Q)}((1+N\ell_{A})\delta+\delta_{\phi}).$

By substituting the latter in (21) and by iterating the resulting inequality,
we obtain:

$\displaystyle\|\boldsymbol{\omega}_{t}-\boldsymbol{\omega}^{\star}_{t}\|_{Q}$
$\displaystyle\leq\eta^{Kt/2}\|{\boldsymbol{\omega}}_{0}-\boldsymbol{\omega}^{\star}_{0}\|_{Q}$
$\displaystyle+\textstyle\sum_{\tau=1}^{t}\eta^{Kt/2}\sqrt{\uplambda_{\text{max}}(Q)}((1+N\ell_{A})\delta+\delta_{\phi}).$

Then, as $\eta^{K/2}<1$, the result follows from the convergence of the
geometric series. ∎

###### Remark 2

Considering a time-varying matrix constraint $A_{t}$ (instead of $A$) would
generate some complications, as also the matrix wou (6) would be time-varying.
This case can be dealt by assuming a lower bound for $K$ in Theorems 3 and 4,
or under the extra assumption that $\bar{A}A_{t}^{\top}\geq\mu_{A}$ for a
matrix $\bar{A}$ and all ${k\in\mathbb{N}}$; but it is not discussed here.
$\square$

##  VI Numerical example1

††1https://github.com/bemilio/Simple_peer_to_peer

We demonstrate the proposed algorithms on a market clearing problem for a
peer-to-peer energy market model inspired by the one in [26]. We consider
$N=6$ prosumers that aim at determining their energy portfolio. At each time-
step $t$, the agents can either purchase power from a main energy operator,
produce it from a dispatchable energy source or trade it with their respective
neighbors over a randomly generated undirected graph
$\mathcal{G}^{\textrm{E}}$. Furthermore, the agents can exchange information
over an undirected connected communication graph $\mathcal{G}$. We denote for
each agent $i$ and each time-step $t$ the power purchased from the main
operator as $x^{\text{mg}}_{i,t}$, the produced power as $x^{\text{dg}}_{i,t}$
and the power that agent $i$ purchases from agent $j$ as
$x^{\text{tr}}_{i,j,t}$, $j\in\mathcal{N}_{i}^{\textrm{E}}$, with
$\mathcal{N}_{i}^{\textrm{E}}$ the set of neighbors of agent $i$ over
$\mathcal{G}^{\textrm{E}}$. As in [26], the energy price posed by the main
operator increases linearly with the aggregate power requested at the main
energy operator by a factor $c_{\text{mg}}>0$. Thus, by defining the
aggregative value

$\sigma^{\text{mg}}(x^{\text{mg}})=\textstyle\sum_{i\in\mathcal{I}}x^{\text{mg}}_{i},$

the cost incurred by each agent for purchasing energy from the operator is
$J^{\text{mg}}(x^{\text{mg}}_{i,t},\sigma^{\text{mg}}(x^{\text{mg}}_{t}))=c^{\text{mg}}\sigma^{\text{mg}}(x^{\text{mg}}_{t})x^{\text{mg}}_{i,t}$.
We consider quadratic cost on the power generation incurred by the agents [26,
Eq. 2], with the form
$J^{\text{dg}}_{i,t}(x^{\text{dg}}_{i,t})=c^{\text{dg}}(x^{\text{dg}}_{i,t}-x^{\text{dg,
ref}}_{i,t})^{2}$ where $x^{\text{dg, ref}}_{i,t}$ is the time-varying
scheduled setpoint of the dispatchable generators and $c^{\text{dg}}>0$. The
price (or revenue) of trading energy between peers is linear [26, Eq. 10], and
we assume that the agents incur a quadratic cost on the transactions for
utilizing the market, thus the total objective function related to the peer-
to-peer trading is given by
$J^{\text{tr}}((x^{\text{tr}}_{i,j,t})_{j\in\mathcal{N}_{i}^{\textrm{E}}})=\sum_{j\in\mathcal{N}_{i}}(c^{\text{tr}}x^{\text{tr}}_{i,j,t}+\kappa^{\text{tr}}(x^{\text{tr}}_{i,j,t})^{2})$.
We impose that the agents cannot sell power to the main operator and that, due
to physical limitations, the power generated by the dispatchable units must be
non-negative. As the formulation in (1) does not consider inequality
constraints, this is enforced by a Lipschitz continuous approximation of the
logarithmic barrier function

$J^{\text{bar}}(x^{\text{mg}}_{i,t},x^{\text{dg}}_{i,t})=\Gamma_{\gamma}(x^{\text{mg}}_{i,t})+\Gamma_{\gamma}(x^{\text{dg}}_{i,t}),$

where $\Gamma_{\gamma}(y):=\mathop{\rm min}(-\log(y),-\gamma
y+1-\log(1/\gamma))$ for $\gamma\gg 0$. The total cost incurred by each agent
is thus given by

$\displaystyle J_{i}^{t}(x_{i,t},x_{-i,t})$
$\displaystyle=J^{\text{mg}}(x^{\text{mg}}_{i,t},\sigma^{\text{mg}}(x_{t}^{\text{mg}}))+J^{\text{dg}}_{i,t}(x^{\text{dg}}_{i,t})$
$\displaystyle+J^{\text{tr}}((x^{\text{tr}}_{i,j,t})_{j\in\mathcal{N}_{i}^{\textrm{E}}})+J^{\text{bar}}(x^{\text{mg}}_{i,t},x^{\text{dg}}_{i,t}).$

Moreover, given a power demand $p_{i,t}^{\text{d}}$, the agents need to
satisfy the power balance equation [26, Eq. 1]

$\sum_{j\in\mathcal{N}_{i}^{\textrm{E}}}(x^{\text{tr}}_{i,j,t})+x^{\text{mg}}_{i,t}+x^{\text{dg}}_{i,t}=p_{i,t}^{\text{d}}.$
(22)

Figure 1: Convergence of Algorithm 2 for the day-ahead market clearing
problem. Figure 2: Tracking error of Algorithm 3 for the real-time market
clearing problem with respect to the day-ahead solution computed by $10^{5}$
iterations of Algorithm 2.  Figure 3: Constraint violation incurred by
Algorithm 3 for the real-time market clearing problem. The inequality
constraints enforced through the barrier function $J^{\text{bar}}$ are
observed to be always satisfied.

As the power balance constraints are local, we do not apply the dynamic
tracking method to the associated dual variables (i.e., dual variables are
managed locally, see [27, Rem. 2]). Instead, coupling constraints between the
agents decisions arises via trading reciprocity constraints [26, Eq. 8]:

$x_{i,j,t}^{\text{tr}}+x_{j,i,t}^{\text{tr}}=0.$ (23)

We first consider a time-invariant scenario and compute the day-ahead market
clearing solution over an entire day, with time-steps of 15 minutes: namely,
the cost of agent $i$ is given by $\sum_{t=1}^{T}J_{i}^{t}$, and the
constraints in (22)-(23) are imposed for all $t=1,2,\dots,T$, with $T=96$.
Figure 1 shows that, as expected, Algorithm 2 exhibits a linear convergence
rate with respect to the Lyapunov function in (14).

Then, we consider a real-time scenario. In particular, the agents only have
access to a prediction on their load demand and generation setpoint over the
coming quarter of an hour; hence the cost of agent $i$ at each time
$t=1,2,\dots,T$ is given by $J_{i}^{t}$. Note that the agents are in fact
faced with a time-varying generalized game as discussed in Section V, which we
address via Algorithm 3. The results are shown in Figure 2. Because of the
slow convergence (i.e., $\eta$ is close to $1$), $K=1$ results in a
significant tracking error; however, good performance is observed already for
$K=100$. Finally, in Figure 3, we show the constraint violation obtained by
the proposed method over the simulation horizon. As constraints are only
satisfied asymptotically, performing only a finite number of iterations per
time-step leads to a constraint violation, which as expected decreases with
$K$.

##  VII Conclusion

Strongly monotone GNE problems with full row rank equality coupling
constraints can be solved with linear convergence rate, both in semi-
decentralized and fully-distributed settings, via primal-dual algorithms. The
contractivity properties of the iterates also allow the tracking of the
solution sequence in time-varying games; in this online setting, the
asymptotic tracking accuracy can be increased by increasing the update
frequency.

As our results exploit the strong monotonicity of the KKT operator in a (non-
diagonally) weighted space, it is not clear how to embed projections in the
proposed methods, which is the main drawback of our approach. Future work
should hence focus on linear convergence in generalized games with local
constraints (and with inequality coupling constraints).

## References

  * [1] G. Belgioioso, W. Ananduta, S. Grammatico, and C. Ocampo-Martinez, “Operationally-safe peer-to-peer energy trading in distribution grids: A game-theoretic market-clearing mechanism,” IEEE Transactions on Smart Grid, vol. 13, no. 4, pp. 2897–2907, 2022.
  * [2] F. Facchinei and C. Kanzow, “Generalized Nash equilibrium problems,” Annals of Operations Research, vol. 175, pp. 177–211, 2010.
  * [3] W. Lin, C. Li, Z. Qu, and M. A. Simaan, “Distributed formation control with open-loop Nash strategy,” Automatica, vol. 106, pp. 266–273, 2019.
  * [4] G. Belgioioso and S. Grammatico, “Semi-decentralized generalized Nash equilibrium seeking in monotone aggregative games,” IEEE Transactions on Automatic Control, 2021.
  * [5] D. Paccagnan, B. Gentile, F. Parise, M. Kamgarpour, and J. Lygeros, “Nash and wardrop equilibria in aggregative games with coupling constraints,” IEEE Transactions on Automatic Control, vol. 64, no. 4, pp. 1373–1388, 2019.
  * [6] E. Benenati, W. Ananduta, and S. Grammatico, “On the optimal selection of generalized Nash equilibria in linearly coupled aggregative games,” in 2022 IEEE 61st Conference on Decision and Control (CDC), 2022, pp. 6389–6394.
  * [7] D. Gadjov and L. Pavel, “Single-timescale distributed GNE seeking for aggregative games over networks via forward–backward operator splitting,” IEEE Transactions on Automatic Control, vol. 66, no. 7, pp. 3259–3266, 2021.
  * [8] L. Pavel, “Distributed GNE seeking under partial-decision information over networks via a doubly-augmented operator splitting approach,” IEEE Transactions on Automatic Control, vol. 65, no. 4, pp. 1584–1597, 2020.
  * [9] M. Bianchi, G. Belgioioso, and S. Grammatico, “Fast generalized Nash equilibrium seeking under partial-decision information,” Automatica, vol. 136, p. 110080, 2022.
  * [10] Z. Deng and X. Nian, “Distributed generalized Nash equilibrium seeking algorithm design for aggregative games over weight-balanced digraphs,” IEEE Transactions on Neural Networks and Learning Systems, vol. 30, no. 3, pp. 695–706, 2019.
  * [11] G. Belgioioso, A. Nedić, and S. Grammatico, “Distributed generalized Nash equilibrium seeking in aggregative games on time-varying networks,” IEEE Transactions on Automatic Control, vol. 66, no. 5, pp. 2061–2075, 2021.
  * [12] Y. Huang and J. Hu, “Distributed solution of GNEP over networks via the Douglas-Rachford splitting method,” in 2021 60th IEEE Conference on Decision and Control (CDC), 2021, pp. 3110–3116.
  * [13] M. Bianchi and S. Grammatico, “Fully distributed Nash equilibrium seeking over time-varying communication networks with linear convergence rate,” IEEE Control Systems Letters, vol. 5, pp. 499–504, 2021.
  * [14] D. Gadjov and L. Pavel, “Distributed Nash equilibrium seeking resilient to adversaries,” in 2021 60th IEEE Conference on Decision and Control (CDC), 2021, pp. 191–196.
  * [15] E. Dall’Anese, A. Simonetto, S. Becker, and L. Madden, “Optimization and learning with information streams: Time-varying algorithms and applications,” IEEE Signal Processing Magazine, vol. 37, no. 3, pp. 71–83, 2020.
  * [16] T. Li, G. Peng, Q. Zhu, and T. Başar, “The confluence of networks, games, and learning a game-theoretic framework for multiagent decision making over networks,” IEEE Control Systems Magazine, vol. 42, no. 4, pp. 35–67, 2022\.
  * [17] Y. Su, F. Liu, Z. Wang, S. Mei, and Q. Lu, “Online distributed tracking of generalized Nash equilibrium on physical networks: Closing the loop via measurement feedback,” Autonomous Intelligent Systems, vol. 1, no. 1, p. 6, 2021.
  * [18] K. Lu, G. Li, and L. Wang, “Online distributed algorithms for seeking generalized Nash equilibria in dynamic environments,” IEEE Transactions on Automatic Control, vol. 66, no. 5, pp. 2289–2296, 2021.
  * [19] O. Stein and N. Sudermann-Merx, “The noncooperative transportation problem and linear generalized Nash games,” European Journal of Operational Research, vol. 266, no. 2, pp. 543–553, 2018.
  * [20] F. Parise, B. Gentile, and J. Lygeros, “A distributed algorithm for almost-Nash equilibria of average aggregative games with coupling constraints,” IEEE Transactions on Control of Network Systems, vol. 7, no. 2, pp. 770–782, 2020.
  * [21] A. A. Kulkarni and U. V. Shanbhag, “On the variational equilibrium as a refinement of the generalized Nash equilibrium,” Automatica, vol. 48, no. 1, pp. 45 – 55, 2012.
  * [22] F. Facchinei and J. Pang, Finite-dimensional variational inequalities and complementarity problems. Springer New York, 2007.
  * [23] S. Grammatico, “Dynamic control of agents playing aggregative games with coupling constraints,” IEEE Transactions on Automatic Control, vol. 62, no. 9, pp. 4537–4548, 2017.
  * [24] H. H. Bauschke and P. L. Combettes, Convex analysis and monotone operator theory in Hilbert spaces. Springer New York, 2017, vol. 2011.
  * [25] A. Simonetto, E. Dall’Anese, S. Paternain, G. Leus, and G. B. Giannakis, “Time-varying convex optimization: Time-structured algorithms and applications,” Proceedings of the IEEE, vol. 108, no. 11, pp. 2032–2048, 2020.
  * [26] G. Belgioioso, W. Ananduta, S. Grammatico, and C. Ocampo-Martinez, “Energy management and peer-to-peer trading in future smart grids: A distributed game-theoretic approach,” in 2020 European Control Conference (ECC), 2020, pp. 1324–1329.
  * [27] M. Bianchi and S. Grammatico, “Continuous-time fully distributed generalized Nash equilibrium seeking for multi-integrator agents,” Automatica, vol. 129, p. 109660, 2021.