# An Efficient Distributed Nash Equilibrium Seeking with Compressed and Event-
triggered Communication

Xiaomeng Chen1 Wei Huo1 1X. Chen, W. Huo, Y. Wu and L. Shi are with the
Department of Electronic and Computer Engineering, Hong Kong University of
Science and Technology, Clear Water Bay, Kowloon, Hong Kong (email:
{xchendu,whuoaa, ywubj,eesling}@ust.hk). Yuchi Wu1 Subhrakanti Dey3 and Ling
Shi1 3 S. Dey is with the Department of Electrical Engineering, Uppsala
University, Box 65, 751 03 Uppsala, Sweden. (email:
subhrakanti.dey@angstrom.uu.se).

###### Abstract

Distributed Nash equilibrium (NE) seeking problems for networked games have
been widely investigated in recent years. Despite the increasing attention,
communication expenditure is becoming a major bottleneck for scaling up
distributed approaches within limited communication bandwidth between agents.
To reduce communication cost, an efficient distributed NE seeking (ETC-DNES)
algorithm is proposed to obtain an NE for games over directed graphs, where
the communication efficiency is improved by event-triggered exchanges of
compressed information among neighbors. ETC-DNES saves communication costs in
both transmitted bits and rounds of communication. Furthermore, our method
only requires the row-stochastic property of the adjacency matrix, unlike
previous approaches that hinged on doubly-stochastic communication matrices.
We provide convergence guarantees for ETC-DNES on games with restricted
strongly monotone mappings and testify its efficiency with no sacrifice on the
accuracy. The algorithm and analysis are extended to a compressed algorithm
with stochastic event-triggered mechanism (SETC-DNES). In SETC-DNES, we
introduce a random variable in the triggering condition to further enhance
algorithm efficiency. We demonstrate that SETC-DNES guarantees linear
convergence to the NE while achieving even greater reductions in communication
costs compared to ETC-DNES. Finally, numerical simulations illustrate the
effectiveness of the proposed algorithms.

Nash equilibrium seeking, information compression, event-triggered
communication, distributed networks, non-cooperative games

##  1 INTRODUCTION

Noncooperative games have been studied extensively primarily due to its wide
applications in a large variety of fields, such as congestion control in
traffic networks [1], charging/discharging of electric vechicles [2] and
demand-side management in smart grids [3]. As an important issue, Nash
equilibrium (NE) seeking has gained ever-increasing attention with the
emergence of multi-agent systems. Conceptually, NE represents a proposed
solution in multi-player non-cooperative games, where selfish players aim to
minimize their individual cost functions by making decisions based on the
actions of others.

A large body of works on NE seeking have been reported in the recent
literature (see e.g.[4, 5, 6] and references therein). Most of them assumed
that each player has access to the decisions of all other players,
necessitating a central coordinator to disseminate information across the
network. However, this full-decision information setting can be impractical in
certain scenarios [7]. Hence, distributed NE seeking algorithms have gained
considerable interest recently, where decentralized information sharing
protocols are employed to exchange local messages among players. In
distributed NE seeking algorithms, each agent is required to transmit
augmented states, which are combinations of real states and estimates, at each
iteration. This communication overhead can be particularly challenging in
games with numerous agents or in systems with limited communication
capacities, such as underwater vehicles and low-cost unmanned aerial vehicles.
Therefore, reducing communication costs while ensuring convergence to NE in
large-scale games is of paramount importance.

To alleviate the communication burden in distributed networks, a large number
of communication-efficient approaches have emerged. The key idea is to lessen
the amount of communication at each iteration. For example, a compressor is
usually adopted for agents to send compressed information that is encoded with
fewer number of bits. Recently, various information compression methods, such
as quantization and sparsification, have been utilized in decentralized
networks for distributed optimization and learning [8, 9, 10, 11, 12]. In the
context of non-cooperative games, Nekouei et al. [13] investigated the impact
of quantized communication on the behavior of NE seeking algorithms over fully
connected communication graphs. A continuous-time distributed NE seeking
algorithm with finite communication bandwidth is proposed by Chen et al. [14],
where a specific quantizer is used. In our previous work, we developed a
discrete-time distributed NE seeking algorithm (C-DNES) that employed general
compressors to compress information before transmission [15].

While compression effectively reduces the amount of information transmitted,
it does not reduce the number of communication rounds. In some instances, the
transmitted state may exhibit minimal changes between iterations, resulting in
a waste of communication resources. To address this issue, event-triggered
mechanisms have been introduced, drawing inspiration from distributed control
[16, 17] and extending to distributed optimization and games [18, 19, 20, 21,
22]. The core idea behind event-triggered scheme is that information is
transmitted only when an event occurs. In general, event condition is related
to the change of system states. While previous works primarily focused on
deterministic event-triggered schemes, recent research has demonstrated the
efficiency of stochastic event-triggered mechanisms in reducing communication
rounds for distributed systems [23]. Tsang et al. [24] extended deterministic
event triggers to stochastic versions for distributed optimization problems,
and Huo et al. [25] applied stochastic event-triggered methods to distributed
non-cooperative games in continuous time, proving convergence to the exact NE.

None of the above studies consider both the number of communication rounds and
the amount of information transmitted in distributed non-cooperative games. In
this paper, we introduce a communication-efficient NE seeking algorithm for
non-cooperative games in distributed systems where agents communicate over
unbalanced directed graphs. Our algorithm incorporates both compression and
event-triggered communication while operating under a much more general set of
assumptions than existing literature. At each communication round, prior to
transmitting local state information to neighboring agents, our approach
involves computing a deterministic or stochastic triggering condition. If the
condition is satisfied, the agent transmits a compressed value to its
neighbors. The main contributions of this paper are summarized as follows:

  1. 1.

We combine the compression approach with event-triggered (incorporating
infrequent communication) strategy to design a compressed event-triggered
distributed NE seeking algorithm, ETC-DNES, where agents initiate a compressed
information transmission controlled by a locally computable triggering event.
Compared with the compression approach in [14, 15] and the event-triggered
approach in [20, 21, 22], our proposed algorithm can save communication bits
and rounds simultaneously, which further reduce the communication cost among
the agents.

  2. 2.

We analyze the convergence performance of the proposed algorithm for games
with restricted strongly monotone mappings. The results show that ETC-DNES
achieves exact convergence asymptotically under the diminishing triggering
condition sequence (Theorem 1). We also prove that when the triggering
sequence is bounded by an exponential decay function, linear convergence is
established (Corollary 1).

  3. 3.

We further extend the event-triggered mechanism to a stochastic one, where a
random variable is introduced, and propose SETC-DENS to improve the algorithm
efficiency. We show that it can converge to the NE with linear convergent rate
(Theorem 2).

  4. 4.

The proposed strategies accommodate a broad class of compressors with bounded
relative compression error, encompassing commonly used compressors including
unbiased and biase but contractive compressors. Moreover, unlike previous
works [20, 21, 22] that require undirected communication graph, our proposed
strategy for communication-efficient NE seeking applies to both undirected and
directed graphs.

  5. 5.

In our simulation examples, we investigate various options for the event-
triggered conditions. The results demonstrate the remarkable efficiency of
both ETC-DNES and SETC-DNES in reducing the number of transmitted data.
Notably, these algorithms achieve reductions of up to a hundredfold in the
number of total transmitted bits.

Notations: In this paper, $\bm{1}\in\mathbb{R}^{n}$ represents the column
vector with each entry given by $1$. We denote $\bm{e}_{i}\in\mathbb{R}^{n}$
as the unit vector which takes zero except for the $i$-th entry that equals to
$1$. $\mathbb{R}_{++}$ denotes the set of all positive real numbers. The
spectral radius of matrix $\mathbf{A}$ is denoted by $\rho(\mathbf{A})$. The
smallest nonzero eigenvalue of a positive semidefinite matrix
$\mathbf{M}\succeq\mathbf{0}$ is denoted as
$\tilde{\lambda}_{\min}(\mathbf{M})$. Given a vector $\mathbf{x}$, we denote
its $i$-th element by $[\bm{x}]_{i}$. Given a matrix $\mathbf{A}$, we denote
its element in the $i$-th row and $j$-th column by $[\bm{A}]_{ij}$. Let
sgn($\cdot$) and $|\cdot|$ be the element-wise sign function and absolute
value function, respectively. We denote $||\mathbf{x}||$ and
$||\mathbf{X}||_{\text{F}}$ respectively as $l_{2}$ norm of vector
$\mathbf{x}$ and the Frobenius norm of matrix $\mathbf{X}$. We denote by
$\mathbf{A}\odot\mathbf{B}$, the Hadamard product of two matrices,
$\mathbf{A}$ and $\mathbf{B}$. In addition, $\bm{x}\preceq\bm{y}$ is denoted
as component-wise inequality between vectors $\bm{x}$ and $\bm{y}$. For a
matrix $\mathbf{A}\in\mathbb{R}^{n\times n}$, denote $\text{diag}(\mathbf{A})$
as its diagonal vector, i.e.,
$\text{diag}(\mathbf{A})=[[\bm{A}]_{11},\ldots,[\bm{A}]_{nn}]^{\top}$. For a
vector $\mathbf{a}\in\mathbb{R}^{n}$, denote $\text{Diag}(\mathbf{a})$ as the
diagonal matrix with the vector $\mathbf{a}$ on its diagonal. A matrix
$\mathbf{A}\in\mathbb{R}^{n\times n}$ is consensual if it has equal row
vectors. $U(a,b)$ denotes the uniform distribution over the interval $(a,b).$
Finally, “$\text{w.p.}1$” stands for “with probability $1$”.

##  2 PRELIMINARIES AND PROBLEM STATEMENT

###  2.1 Network Model

We consider a group of agents communicating with each other over a directed
graph $G\triangleq(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}=\\{1,2,3\ldots,n\\}$ denotes the agent set and
$\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$ denotes the edge set,
respectively. A communication link from agent $j$ to agent $i$ is denoted by
$(j,i)\in\mathcal{E}$, indicating that agent $j$ can send messages to agent
$i$. The agents who can send messages to node $i$ are denoted as in-neighbours
of agent $i$ and the set of these agents is denoted as
$\mathcal{N}_{i}^{-}=\\{j\in\mathcal{V}\mid(j,i)\in\mathcal{E}\\}$. The
adjacency matrix of the graph is denoted as $W=[w_{ij}]_{n\times n}$ with
$w_{ij}>0$ if $(i,j)\in\mathcal{E}$ or $i=j$, and $w_{ij}=0$ otherwise. The
graph $G$ is called strongly connected if there exists at least one directed
path from any agent $i$ to any agent $j$ in the directed graph with $i\neq j$.

###### Assumption 1

The directed graph $G\triangleq(\mathcal{V},\mathcal{E})$ is strongly
connected. Moreover, the adjacency matrix $W$ associated with $G$ is row-
stochastic, i.e., $\sum_{l=1}^{n}w_{il}=1,\forall i\in\mathcal{V}$.

###  2.2 Compressors

A stochastic compressor
$\mathcal{C}(\mathbf{x},\xi,C):\mathbb{R}^{d}\times\mathcal{Z}\times\mathbb{R}^{+}\rightarrow\mathbb{R}^{d}$
is a mapping that converts a $\mathbb{R}^{d}$-valued signal $\mathbf{x}$ to a
compressed one, where $C\geq 0$ is the desired compression ratio and
$\mathbf{\xi}$ is a random variable with range $\mathcal{Z}$. Note that the
realizations $\xi$ of the compressor $\mathcal{C}(.)$ are independent among
different agents and time steps. In other words, given a sequence
$\\{\mathbf{x}_{i,k}\\}$ for each agent $i\in\mathcal{V}$, and any time
iteration $k\geq 0$, the randomness $\xi_{i,k}$ with each usage of the
compressor $\mathcal{C}_{i,k}(\mathbf{x}_{i,k},\mathbf{\xi}_{i,k},C)$ is
i.i.d, where $\mathcal{C}_{i,k}(\cdot)$ denotes the compressor used by agent
$i$ at iteration $k$. For deterministic compressors, which can be treated as
special cases of the random ones, the random variable $\xi$ is not included,
and thus the notation reduces to $\mathcal{C}_{i,k}(\mathbf{x},C)$. For
stochastic compressors, the notation $\mathbb{E}_{\xi}$ is used to denote the
expectation over the inherent randomness in the stochastic compressor [26, 27,
28]. For deterministic compressors, the expected value operator will return
the deterministic argument. Hereafter, we drop $\xi,C$ and write
$\mathcal{C}_{i,k}(\mathbf{x})$ for notational simplicity.

As inspired by [8], in this paper, we consider a general class of stochastic
compressors that satisfy the following assumption.

###### Assumption 2

For any agent $i\in\mathcal{V}$ and any iteration $k\geq 0$, given all the
recorded history of data on the network $\mathcal{H}_{k}$, the compression
operator $\mathcal{C}_{i,k}$ satisfies

$\mathbb{E}_{\xi}[||\mathcal{C}_{i,k}(\mathbf{x})-\mathbf{x}||^{2}|\mathcal{H}_{k}]\leq
C||\mathbf{x}||^{2},\qquad\forall\mathbf{x}\in\mathbb{R}^{d},$ (1)

where $C\geq 0$ and the r-scaling of $\mathcal{C}_{i,k}$ satisfies

$\mathbb{E}_{\xi}[||\mathcal{C}_{i,k}(\mathbf{x})/r-\mathbf{x}||^{2}|\mathcal{H}_{k}]\leq(1-\delta)||\mathbf{x}||^{2},\qquad\forall\mathbf{x}\in\mathbb{R}^{d},$
(2)

where $\delta\in(0,1]$ and $r>0$.

The above class of compressors incorporate the widely used unbiased
compressors and biased but contractive compressors, such as stochastic
quantization [10] and Top-$k$ sparsification [11]. They also cover biased and
non-contractive compressors like the norm-sign compressor. In other words,
Assumption 2 is weaker than various commonly used assumptions for compressors
in the literature.

Some specific compressors satisfying 2 are give below.

Example 1 (Stochastic quantization):

The $b-$bit $q-$norm quantisation compressor is defined as follows:

$\mathcal{C}_{q}(\mathbf{x})=\frac{||\mathbf{x}||_{q}}{2^{b-1}}sgn(\mathbf{x})\odot\left\lfloor\frac{2^{b-1}|\mathbf{x}|}{||\mathbf{x}||_{q}}+\mathbf{u}\right\rfloor,$
(3)

where $\mathbf{u}$ is a random vector uniformly sampled from $[0,1]^{d}$,
which is independent of $\mathbf{x}$. It can be shown that the compressor is
unbiased and its compression variance has an upper bound which is linearly
proportional to the norm of the variables (see Theorem 3 in [10]). For
$q=\infty$, the compressor satisfies Assumption 2 with $C=d/4^{b}$.

Example 2 (Top-$k$ sparsification):

The largest $k$ coordinates in magnitude is selected among the vector
$\mathbf{x}$, i.e.,

$\mathcal{C}_{top}(\mathbf{x})=\mathbf{x}\odot\mathbf{e},$ (4)

where the elements of $\mathbf{x}$ is reordered as
$[\mathbf{x}]_{1}\geq[\mathbf{x}]_{2}\geq\cdots[\mathbf{x}]_{d}$ and
$\mathbf{e}$ satisfies $[\mathbf{e}]_{l}=1$ for $l\leq k$ and
$[\mathbf{e}]_{l}=0$ for $l>k$. This compressor is biased but contractive
since it meets Assumption 2 with $C=1-k/d<1$.

Example 3 (norm-sign) compressor:

The norm-sign compressor is defined as follow:

$\mathcal{C}(\mathbf{x})=||\mathbf{x}||_{q}sgn(\mathbf{x}),\quad q\geq 2.$ (5)

###### Remark 1

For the compressor defined in (5), we have the following compression constants
satisfying Assumption 2.

$\begin{matrix}C=d-1,&r=d,&\delta=\frac{1}{d}.\end{matrix}$

###  2.3 Problem Formulation

Consider a non-cooperative game in a multi-agent system of $n$ agents, where
each agent has an unconstrained action set $\Omega_{i}=\mathbb{R}$. Without
loss of generality, we assume that each agent’s decision variable is a scalar.
Let $J_{i}$ denote the cost function of the agent $i$. Then, the game is
denoted as $\Gamma(n,\\{J_{i}\\},\\{\Omega_{i}=\mathbb{R}\\})$. The goal of
each agent $i\in\mathcal{V}$ is to minimize its objective function
$J_{i}(x_{i},\mathbf{x_{-i}})$, which depends on both the local variable
$x_{i}$ and the decision variables of the other agents $\mathbf{x_{-i}}$. The
concept of NE is given below.

###### Definition 1

A vector
$\mathbf{x}^{\star}=[x_{1}^{\star},x_{2}^{\star},\ldots,x_{n}^{\star}]^{\top}$
is an NE if for any $i\in\mathcal{V}$ and $x_{i}\in\mathbb{R}$,
$J_{i}(x_{i}^{\star},\mathbf{x_{-i}}^{\star})\leq
J_{i}(x_{i},\mathbf{x_{-i}}^{\star}).$

We then make the following assumptions with respect to game $\Gamma$.

###### Assumption 3

For $i\in\mathcal{V}$, the cost function $J_{i}(x_{i},\mathbf{x_{-i}})$ is
strongly convex and continuously differentiable in $x_{i}$ for each fixed
$\mathbf{x_{-i}}$.

###### Definition 2

The mapping $\mathbf{F}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$, referred to
be the game mapping of $\Gamma(n,\\{J_{i}\\},\\{\Omega_{i}\\})$ is denoted as

$\mathbf{F(x)}\triangleq[\nabla_{1}J_{1}(x_{1},x_{-1}),\ldots,\nabla_{n}J_{n}(x_{n},x_{-n})]^{\top},$
(6)

where $\nabla_{i}J_{i}(x_{i},\mathbf{x_{-i}})=\frac{\partial
J_{i}(x_{i},\mathbf{x_{-i}})}{\partial x_{i}},\forall i\in\mathcal{V}$.

###### Assumption 4

The game mapping $\mathbf{F(x)}$ is restricted strongly monotone to any NE
$\mathbf{x}^{\star}$ with constant $\mu_{r}>0$, i.e.,

$\langle\mathbf{F(x)}-\mathbf{F(\mathbf{x}^{\star})},\mathbf{x}-\mathbf{\mathbf{x}^{\star}}\rangle\geq\mu_{r}||\mathbf{x-\mathbf{x}^{\star}}||^{2},\forall\mathbf{x}\in\mathbb{R}^{n}.$

###### Remark 2

In this paper, we relax the strongly monotone mapping condition in [4, 29, 30]
to a restricted one as Assumption 4. Thus, a wider variety of games are taken
into consideration.

###### Assumption 5

Each function $\nabla_{i}J_{i}(x_{i},\mathbf{x_{-i}})$ is Lipschitz continuous
in $x_{i}$ for every fixed $\mathbf{x_{-i}}$, i.e., $\exists L_{i}\geq 0$, we
have $\forall x_{i},y_{i},$

$|\nabla_{i}J_{i}(x_{i},\mathbf{x_{-i}})-\nabla_{i}J_{i}(y_{i},\mathbf{x_{-i}})|\leq
L_{i}|x_{i}-y_{i}|.$

Moreover, each function $\nabla_{i}J_{i}(x_{i},\mathbf{x_{-i}})$ is Lipschitz
continuous in $\mathbf{x_{-i}}$ for every fixed $x_{i}$, i.e., $\exists
L_{-i}\geq 0$, we have $\forall\mathbf{x_{-i}},\mathbf{y_{-i}},$

$||\nabla_{i}J_{i}(x_{i},\mathbf{x_{-i}})-\nabla_{i}J_{i}(x_{i},\mathbf{y_{-i}})||\leq
L_{-i}||\mathbf{x_{-i}}-\mathbf{y_{-i}}||.$

Assumption 5 is required for linear convergence of algorithms computing an
equilibrium point in variational inequalities [30, 31, 32].

In this paper, we are interested in distributed seeking of an NE in a game
$\Gamma(n,\\{J_{i}\\},\\{\Omega_{i}=\mathbb{R}\\})$ where Assumption 1,3,4 and
5 hold. Note that given Assumption 3 and 4, there exists an unique NE in the
game $\Gamma(n,\\{J_{i}\\},\\{\Omega_{i}=\mathbb{R}\\})$ [15] and it can be
can be alternatively characterized by using the first-order optimality
conditions. To be specific, $\mathbf{x}^{\star}\in\mathbb{R}^{n}$ is an NE if
and only if for all $x_{i}$, we have

$\langle\nabla
J_{i}(x_{i}^{\star},\mathbf{x_{-i}}^{\star}),x_{i}-x_{i}^{\star}\rangle\geq
0.$ (7)

To cope with incomplete information in a distributed network, we assume that
each agent maintains a local variable

$\mathbf{x}_{(i)}=[\tilde{x}_{(i)1},\ldots,\tilde{x}_{(i)i-1},x_{i},\tilde{x}_{(i)i+1},\ldots,\tilde{x}_{(i)n}]^{\top}\in\mathbb{R}^{n},$
(8)

which is his estimation of the joint action profile
$\mathbf{x}=[x_{1},x_{2},\ldots,x_{n}]^{\top}$, where
$\tilde{x}_{(i)j}\in\mathbb{R}$ denotes agent $i$’s estimate of $x_{j}$ and
$\tilde{x}_{(i)i}=x_{i}\in\mathbb{R}$. The objective of this work is to design
an efficient algorithm with compressed and event-triggered communication,
where each agents are able to find an NE in game $\Gamma$.

##  3 Event-triggered and Compressed Distributed NE Seeking Algorithm (ETC-
DNES)

In this section, we propose a distributed NE seeking algorithm with event-
triggered and compressed communication, where compressed information is
revealed to neighoring agent at each triggered time. An event-triggered
mechanism is designed to reduce the communication frequency. We show that the
proposed algorithm can converge to the optimal solution based on carefully
chosen event-triggering thresholds. Furthermore, we establish conditions under
which the algorithm exhibits linear convergence.

###  3.1 Algorithm Development

In this subsection, we introduce the ETC-DNES algorithm designed to seek NE in
game $\Gamma$, which is a distributed algorithm that carefully incorporates
the difference compression technique from [15] and event-triggered
communication mechanism into the conventional NE seeking algorithm from [30].
The detailed procedures of ETC-DNES are outlined in Algorithm 1 , and we
provide a summary of the notations used throughout the algorithm in Table 1.

Table 1: Descriptions of notations in Algorithm 1 Symbol | Description
---|---
$\mathbf{x}_{(i)}$ | Local estimate of the joint action profile
$\mathbf{\hat{x}}_{(i)}$ | Estimated version of $\mathbf{x}_{(i)}$
$\mathbf{\hat{x}}_{(i),w}$ | Weighted average of $\mathbf{\hat{x}}_{(i)}$
$\mathbf{h}_{i}$ | Reference point of $\mathbf{x}_{(i)}$
$\mathbf{h}_{i,w}$ | Weighted average of $\mathbf{h}_{i}$
$\mathbf{q}_{i}$ | Compressed value of $\mathbf{x}_{(i)}-\mathbf{h}_{i}$
$\mathbf{\tilde{q}}_{i}$ | Latest sent value
$\mathbb{I}_{i,k}$ | Triggering indicator
Algorithm 1 ETC-DNES: Event-triggered and Compressed Distributed Nash
Equilibrium Seeking Algorithm

Input: Stopping time $K$, gradient step-size $\eta$, consensus step-size
$\gamma$, scaling parameter $\alpha>0$, and initial values
$\mathbf{x}_{(i),0},\mathbf{h}_{i,0},\mathbf{\tilde{q}}_{i,-1}$
Output: $\mathbf{x}_{(i),k}$

1:for each agent $i\in\mathcal{V}$ do

2:
$\mathbf{h}_{i,w,0}=\sum\limits_{j\in\mathcal{N}_{i}}w_{ij}\mathbf{h}_{j,0}$

3:end for

4:for $k=0,1,2,\ldots,K-1$ do locally at each agent $i\in\mathcal{V}$

5: $\mathbf{q}_{i,k}=\mathcal{C}_{i,k}(\mathbf{x}_{(i),k}-\mathbf{h}_{i,k})$.

6: Run Algorithm 2 and obtain the triggering indicator $\mathbb{I}_{i,k}$

7: if $\mathbb{I}_{i,k}=1$, then

8: Send $\mathbf{q}_{i,k}$ to agent $l\in\mathcal{N}_{i}$ and set
$\mathbf{\tilde{q}}_{i,k}=\mathbf{q}_{i,k}$

9: else

10: Do not send and set $\mathbf{\tilde{q}}_{i,k}=\mathbf{\tilde{q}}_{i,k-1}$.

11: end if

12: $\mathbf{\hat{x}}_{(i),k}=\mathbf{h}_{i,k}+\mathbf{\tilde{q}}_{i,k}$

13:
$\mathbf{h}_{i,k+1}=(1-\alpha)\mathbf{h}_{i,k}+\alpha\mathbf{\hat{x}}_{(i),k}$

14: Let $\mathbf{\tilde{q}}_{j,k}=\mathbf{q}_{j,k}$ if receive
$\mathbf{q}_{j,k}$ from agent $j\in\mathcal{N}_{i}$. Otherwise, let
$\mathbf{\tilde{q}}_{j,k}=\mathbf{\tilde{q}}_{j,k-1}$

15:
$\mathbf{\hat{x}}_{(i),w,k}=\mathbf{h}_{i,w,k}+\sum_{j=1}^{n}w_{ij}\mathbf{\tilde{q}}_{j,k}$

16:
$\mathbf{h}_{i,w,k+1}=(1-\alpha)\mathbf{h}_{i,w,k}+\alpha\mathbf{\hat{x}}_{(i),w,k}$

17:
$\mathbf{x}_{(i),k+1}=\mathbf{x}_{(i),k}-\gamma(\mathbf{\hat{x}}_{(i),k}-\mathbf{\hat{x}}_{(i),w,k})-\gamma\eta\nabla_{i}J_{i}(\mathbf{x}_{(i),k})\mathbf{e}_{i}$

18:end for

Algorithm 2 Event-triggering Condition Calculating Algorithm at Each Agent

Input: Time iteration $k$, state value $\mathbf{q}_{i,k}$ and
$\mathbf{\tilde{q}}_{i,k-1}$, triggering thresholds $\\{\tau_{i,k}\\}_{k\geq
0}$
Output: $\mathbb{I}_{i,k}$

1:if $k=0$, then

2: $\mathbb{I}_{i,k}=1$

3:else

4: if $||\mathbf{q}_{i,k}-\mathbf{\tilde{q}}_{i,k-1}||\geq\tau_{i,k}$, then

5: $\mathbb{I}_{i,k}=1$

6: else

7: $\mathbb{I}_{i,k}=0$

8: end if

9:end if

Transmission of Compressed Value: In ETC-DNES, the transmission of information
occurs only when an event is triggered at iteration $k$, denoted as
$\mathbb{I}_{i,k}=1$. Instead of compressing the local variable
$\mathbf{x}_{(i)}$, we maintain an auxiliary variable $\mathbf{h}_{i}^{k}$,
acting as a reference point of $\mathbf{x}_{(i)}$, and compress the difference
$\mathbf{x}_{(i)}^{k}-\mathbf{h}_{i}^{k}$ (line 5 in Algorithm 2). This choice
serves to mitigate compression errors, as the error tends to vanish as the
reference point $\mathbf{h}_{i,k}$ converges to $\mathbf{x}_{(i),k}$. In
addition, each agent $i$ obtains a coarse representation of
$\mathbf{x}_{(i)}$, denoted as $\mathbf{\hat{x}}_{(i)}$, by assembling
$\mathbf{h}_{i}^{k}$ and the latest sent value from its neighbors,
$\mathbf{\tilde{q}}_{j},\forall j\in\mathcal{N}_{i}^{-}$ (line 12 in Algorithm
2). Then $\mathbf{h}_{i}^{k+1}$ is obtained as the weighted average of its
previous value $\mathbf{h}_{i}^{k}$ and $\mathbf{\hat{x}}_{(i)}^{k}$ with
mixing weight $\alpha$, indicating that $\mathbf{h}_{i}^{k}$ is tracking the
motions of $\mathbf{x}_{i}^{k}$ (line 13 in Algorithm 2). Moreover, the
variable $\mathbf{h}_{i,w}$ is a weighted averaged version of
$\mathbf{h}_{i}$, which can be regarded as a backup copy for the neighboring
information (line 16 in Algorithm 2). The introduction of this auxiliary
variable eliminates the need to store all the neighbors’ variable
$\mathbf{h}_{j}$.

Event-triggered Mechanism: To determine when messages should be sent to
neighboring agents, each agent executes Algorithm 2 to calculate the
triggering indicator at each time iteration. At the initial iteration, $k=0$,
the indicator $\mathbb{I}_{i,k}$ is set to 1, indicating that agents
automatically trigger transmissions at the start. For subsequent iterations,
$k\geq 1$, each agent evaluates the triggering condition (line 4 in Algorithm
2) to determine the triggering indicator’s value.

Specifically, agent $i$ transmits their current compressed value,
$\mathbf{q}_{i,k}$, to their neighbors and updates the latest sent value,
$\mathbf{\tilde{q}}_{i,k}$, to equal the transmitted value only if the
difference between the current compressed value and the latest sent value,
$||\mathbf{q}_{i,k}-\mathbf{\tilde{q}}_{i,k-1}||$, exceeds or equals a
predefined event-triggering threshold $\tau_{i,k}$. Otherwise, if the
difference is less than $\tau_{i,k}$, agent $i$ refrains from communication in
that round and retains the previous value as the latest sent value. Smaller
values of $\tau_{i,k}$ result in more frequent communication between agents.
When $\tau_{i,k}=0$ for every iteration, agents always transmit their
compressed value to neighbors, rendering ETC-DNES equivalent to C-DNES [15]
without event-triggering laws.

We make the following mild assumption for the event-triggering threshold in
ETC-DNES.

###### Assumption 6

The thresholds $\\{\tau_{i,k}\\}_{k\geq 0},\forall i\in\mathcal{N}$ satisfies

$\tau_{i,k}\geq 0,\qquad\lim\limits_{k\rightarrow\infty}\tau_{i,k}=0.$ (9)

Assumption 6 is a mild assumption satisfied by many sequences. For example,
the threshold can be chosen as a fraction form
$\tau_{i,k}=\frac{a_{i}}{(k+b_{i})^{2}}$ with $a_{i}>0,b_{i}>0$ or an
exponential form $\tau_{i,k}=C_{i}a_{i}^{k}$ with $C_{i}>0$ and $0<a_{i}<1$.

For the convenience of analysis, we define the event error as
$\mathbf{e}_{i,k}=\mathbf{q}_{i,k}-\mathbf{\tilde{q}}_{i,k}$ and denote the
compact form of action-profile estimates from all agents as

$\mathbf{X}=[\mathbf{x}_{(1)},\mathbf{x}_{(2)},\ldots,\mathbf{x}_{(n)}]^{\top}\in\mathbb{R}^{n\times
n},$

where the $i$th row is the estimation vector
$\mathbf{x}_{(i)},i\in\mathcal{V}$. Auxiliary variables of the agents in
compact form
$\mathbf{H},\mathbf{H}_{w},\mathbf{Q},\mathbf{\tilde{Q}},\mathbf{E},\mathbf{\hat{X}}$
and $\mathbf{\hat{X}}_{w}$ are defined similarly. At $k-$th iteration, their
values are denoted by
$\mathbf{X}_{k},\mathbf{H}_{k},\mathbf{H}_{w,k},\mathbf{Q}_{k},\mathbf{\tilde{Q}}_{k},\mathbf{E}_{k},\mathbf{\hat{X}}_{k}$
and $\mathbf{\hat{X}}_{w,k}$ , respectively.

Moreover, we define a diagonal matrix

$\mathbf{\tilde{F}}(\mathbf{X})\triangleq\text{Diag}(\nabla_{1}J_{1}(\mathbf{x}_{(1)}),\ldots,\nabla_{n}J_{n}(\mathbf{x}_{(n)}))\in\mathbb{R}^{n\times
n}.$

Algorithm 1 can be written in compact form as follows:

$\displaystyle\mathbf{Q}_{k}=\mathcal{C}_{k}(\mathbf{X}_{k}-\mathbf{H}_{k}),$
(10a)
$\displaystyle\mathbf{\hat{X}}_{k}=\mathbf{H}_{k}+\mathbf{Q}_{k}-\mathbf{E}_{k},$
(10b)
$\displaystyle\mathbf{\hat{X}}_{w,k}=\mathbf{H}_{w,k}+W(\mathbf{Q}_{k}-\mathbf{E}_{k}),$
(10c)
$\displaystyle\mathbf{H}_{k+1}=(1-\alpha)\mathbf{H}_{k}+\alpha\mathbf{\hat{X}}_{k},$
(10d)
$\displaystyle\mathbf{H}_{w,k+1}=(1-\alpha)\mathbf{H}_{w,k}+\alpha\mathbf{\hat{X}}_{w,k},$
(10e)
$\displaystyle\mathbf{X}_{k+1}=\mathbf{X}_{k}-\gamma(\mathbf{\hat{X}}_{k}-\mathbf{\hat{X}}_{w,k})-\gamma\eta\mathbf{\tilde{F}}(\mathbf{X}_{k}),$
(10f)

where $\mathbf{X}_{0}$ and $\mathbf{H}_{0}$ are arbitrary.

Note that after initialization $\mathbf{H}_{w,0}=W\mathbf{H}_{0}$, we have

$\displaystyle\mathbf{H}_{w,1}$
$\displaystyle=(1-\alpha)\mathbf{H}_{w,0}+\alpha(\mathbf{H}_{w,0}+W\mathbf{Q}_{0}-W\mathbf{E}_{0})$
(11) $\displaystyle=W\mathbf{H}_{0}+\alpha
W(\mathbf{\hat{X}}_{0}-\mathbf{H}_{0}+\mathbf{E}_{0})-\alpha W\mathbf{E}_{0}$
$\displaystyle=W[(1-\alpha)\mathbf{H}_{0}+\alpha\mathbf{\hat{X}}_{0}]=W\mathbf{H}_{1}.$

Hence, by induction, we obtain $\mathbf{H}_{w,k}=W\mathbf{H}_{k}$ and
$\mathbf{\hat{X}}_{w,k}=W\mathbf{\hat{X}}_{k}$ for all $k$. Then, the state
variable update in (10f) becomes

$\displaystyle\mathbf{X}_{k+1}$
$\displaystyle=\mathbf{X}_{k}-\gamma(\mathbf{\hat{X}}_{k}-W\mathbf{\hat{X}}_{k})-\gamma\eta\mathbf{\tilde{F}}(\mathbf{X}_{k})$
(12)
$\displaystyle=\mathbf{X}_{k}-\gamma\mathbf{F}_{a}(\mathbf{X}_{k})+\gamma(I-W)\mathbf{D}_{k},$

where
$\mathbf{F}_{a}(\mathbf{X}_{k})=(I-W)\mathbf{X}_{k}+\eta\mathbf{\tilde{F}}(\mathbf{X}_{k})$
denotes the augmented mapping [31] of game $\Gamma$,
$\mathbf{D}_{k}=\mathbf{X}_{k}-\mathbf{\hat{X}}_{k}$ denotes the compression
error for the decision variable.

###  3.2 Convergence Analysis

In this subsection, we analyze the convergence performance of ETC-DNES. Let
$\mathcal{F}_{k}$ be the $\sigma-$algebra generated by
$\\{\mathbf{D}_{0},\mathbf{D}_{1},\ldots,\mathbf{D}_{k-1}\\}$, and denote
$\mathbb{E}_{\xi}[\cdot|\mathcal{F}_{k}]$ as the conditional expectation given
$\mathcal{F}_{k}$. Now, we present the following lemmas.

###### Lemma 1

Suppose Assumption 6 holds. Under ETC-DNES, there holds

$\lim_{k\rightarrow\infty}||\mathbf{E}_{k}||^{2}_{\text{F}}=0\qquad\text{w.p.}1.$
(13)

######  Proof 3.1.

From the event-triggering condition in Algorithm 1, we can obtain that for all
realization of $\mathbf{q}_{i,k},\forall k\geq 0$, if
$||\mathbf{q}_{i,k+1}-\mathbf{\tilde{q}}_{i,k}||\geq\tau_{i,k+1}$, then
$||\mathbf{q}_{i,k+1}-\mathbf{\tilde{q}}_{i,k+1}||=0\leq\tau_{i,k+1}$.
Otherwise, $||\mathbf{q}_{i,k+1}-\mathbf{\tilde{q}}_{i,k}||<\tau_{i,k+1}$.
Since $\mathbf{\tilde{q}}_{i,k+1}=\mathbf{\tilde{q}}_{i,k}$ in such case, we
still have
$||\mathbf{q}_{i,k+1}-\mathbf{\tilde{q}}_{i,k+1}||\leq\tau_{i,k+1}$.

Recall that $\mathbf{q}_{i,0}=\mathbf{\tilde{q}}_{i,0}$, we can obtain
$||\mathbf{q}_{i,k}-\mathbf{\tilde{q}}_{i,k}||\leq\tau_{i,k},\forall k\geq 0$,
i.e., $||\mathbf{e}_{i,k}||\leq\tau_{i,k},\forall k\geq 0,i\in\mathcal{V}$.
Thus,

$||\mathbf{E}_{k}||^{2}_{\text{F}}=\sum_{i}^{n}||\mathbf{e}_{i,k}||^{2}\leq\sum_{i}^{n}\tau_{i,k}^{2}\qquad\text{w.p.}1.$

Given Assumption 6, we have $\lim_{k\rightarrow\infty}\tau_{i,k}=0,\forall
i\in\mathcal{N}$. Then we can obtain
$\lim_{k\rightarrow\infty}||\mathbf{E}_{k}||^{2}_{\text{F}}=0$ with
probability $1$.

######  Lemma 3.2.

Suppose Assumption 2 holds, the variables $\mathbf{X}_{k},\mathbf{H}_{k}$ are
measurable respect to $\mathcal{F}_{k}$. Furthermore, the following inequality
holds for ETC-DNES

$\mathbb{E}_{\xi}[||\mathbf{X}_{k}-\mathbf{\hat{X}}_{k}||^{2}_{\text{F}}\mid\mathcal{F}_{k}]\leq
2C||\mathbf{X}_{k}-\mathbf{H}_{k}||^{2}_{\text{F}}+2||\mathbf{E}_{k}||_{\text{F}}^{2}.$
(14)

######  Proof 3.3.

By expanding (10a)-(10f) recursively, $\mathbf{X}_{k}$ and $\mathbf{H}_{k}$
can be represented by linear combinations of $\mathbf{X}_{0},\mathbf{H}_{0}$
and random variables $\\{\mathbf{D}_{j}\\}_{j=0}^{k-1}$, i.e,
$\mathbf{X}_{k},\mathbf{H}_{k}$ are measurable respect to $\mathcal{F}_{k}$.
Moreover, from Equation (10b) and (1), we have

$\displaystyle\mathbb{E}_{\xi}[||\mathbf{X}_{k}-\mathbf{\hat{X}}_{k}||^{2}_{\text{F}}\mid\mathcal{F}_{k}]$
(15)
$\displaystyle=\mathbb{E}_{\xi}[||\mathbf{X}_{k}-\mathbf{H}_{k}-\mathcal{C}_{k}(\mathbf{X}_{k}-\mathbf{H}_{k})+\mathbf{E}_{k}||^{2}_{\text{F}}\mid\mathcal{F}_{k}]$
$\displaystyle\leq
2C||\mathbf{X}_{k}-\mathbf{H}_{k}||^{2}_{\text{F}}+2||\mathbf{E}_{k}||_{\text{F}}^{2}.$

The following lemma is crucial for establishing a linear system of
inequalities that bound
$\mathbb{E}_{\xi}[||\mathbf{X}_{k}-\mathbf{X}^{\star}||^{2}_{\text{F}}]$ and
$\mathbb{E}_{\xi}[||\mathbf{X}_{k}-\mathbf{H}_{k}||^{2}_{\text{F}}]$.

######  Lemma 3.4.

Given Assumptions 1–5, when $\alpha\in(0,\frac{1}{r}]$, the following linear
system of component-wise inequalities holds for ETC-DNES

$\mathbf{V}_{k+1}\leq\mathbf{A}\mathbf{V}_{k}+\mathbf{B}||\mathbf{E}_{k}||^{2}_{\text{F}},$
(16)

where

$\mathbf{V}_{k}=\begin{bmatrix}\mathbb{E}_{\xi}[||\mathbf{X}_{k}-\mathbf{X}^{\star}||^{2}_{\text{F}}]\\\
\mathbb{E}_{\xi}[||\mathbf{X}_{k}-\mathbf{H}_{k}||^{2}_{\text{F}}]\\\
\end{bmatrix},$ (17)

and the elements of transition matrix $\mathbf{A}=[a_{ij}]$ and
$\mathbf{B}=[b_{ij}]$ are respectively given by

$\displaystyle\mathbf{A}=\begin{bmatrix}c_{1}(1+L_{F}^{2}\gamma^{2}-2\mu_{F}\gamma)&c_{2}\gamma^{2}\\\
c_{3}\gamma^{2}L_{F}^{2}&c_{x}+c_{4}\gamma^{2}\\\ \end{bmatrix},$ (18)
$\displaystyle\mathbf{B}=\begin{bmatrix}c_{2}\gamma^{2}&c_{4}\gamma^{2}\end{bmatrix}^{\top},$

where
$c_{1}=\frac{2L_{F}^{2}-\mu_{F}^{2}}{2L_{F}^{2}-2\mu_{F}^{2}},c_{2}=\frac{2c_{1}||I-W||_{\text{F}}^{2}C}{c_{1}-1},c_{3}=\frac{4-2\alpha
r\delta}{\alpha
r\delta},c_{4}=2c_{3}C||(I-W)||^{2}_{\text{F}},c_{x}=\frac{2-\alpha
r\delta}{2}$.

######  Proof 3.5.

See Appendix 7.2.

######  Remark 3.6.

Lemma 3.4 shows that the behavior of the error vector $\mathbf{V}_{k}$ relies
on the transition matrix $\mathbf{A}$ as well as the additive error terms due
to the event-triggered communication.

The following theorem shows the convergence properties of ETC-DNES.

######  Theorem 3.7.

Let Assumptions 1–6 hold. When $\gamma=\mu_{F}/L_{F}^{2}$, the scaling
parameter $\alpha$ and gradient step-size satisfy

$\alpha\in(0,\frac{1}{r}],\quad\eta\leq\min\Big{\\{}\frac{2n}{\mu_{r}}\sqrt{\frac{1-c_{x}}{m_{1}}},\frac{\tilde{\lambda}_{\text{min}}(I-W)m_{2}^{2}}{L_{m}(m_{2}^{2}+1)}\Big{\\}},$
(19)

where
$m_{1}=\frac{c_{3}\epsilon_{1}}{||I-W||_{\text{F}}^{2}}+\frac{\epsilon_{2}}{4||I-W||_{\text{F}}^{2}}+\frac{c_{4}\epsilon_{2}}{||I-W||_{\text{F}}^{4}},m_{2}=-1+\sqrt{1+\frac{\mu_{r}^{2}}{4n^{2}L_{m}}\sqrt{\frac{m_{1}}{1-c_{x}}}}$,
the spectral radius of $\mathbf{A}$ is less than $1$. Thus, the NE-seeking
error
$\mathbb{E}_{\xi}[||\mathbf{X}^{k+1}-\mathbf{X}^{\star}||^{2}_{\text{F}}]$ and
the compression error
$\mathbb{E}_{\xi}[||\mathbf{X}^{k+1}-\mathbf{H}^{k+1}||^{2}_{\text{F}}]$ both
converge to $0$ under ETC-DNES.

######  Proof 3.8.

See Appendix 7.3.

######  Corollary 3.9.

Suppose Assumptions 1–6 hold and the algorithm parameters satisfy (19). If the
threshold sequence is chosen in an exponential form, i.e.,
$\tau_{i,k}=C_{i}p_{i}^{k}$ with $C_{i}>0$ and $0<p_{i}<1$, the error vector
$\mathbf{V}_{k}$ converges to $0$ linearly under Algorithm 1.

######  Proof 3.10.

See Appendix 7.4.

######  Remark 3.11.

Theorem 3.7 demonstrates the asymptotic convergence of each agent’s state to
the NE. In the compression-based method [15] without event-triggered
mechanism, the convergence rate is solely dependent on the spectral radius
$\rho(\mathbf{A})$. However, in our proposed algorithm that integrates both
event-triggering and compression, the upper bound of the error vector
$\mathbf{V}(k)$ in (16) indicates that the convergence rate depends on both
the threshold of the triggering condition and the spectral radius
$\rho(\mathbf{A})$. In general, the convergence rate of the event-triggered
algorithm is slower compared to its non-event-triggered counterpart due to
reduced information exchange. Nevertheless, Corollary 3.9 reveals that with a
suitably chosen triggering condition, the event-triggered algorithm can
achieve linear convergence to the optimal solution. Therefore, by judiciously
selecting the trigger condition’s threshold, the proposed event-triggered
method effectively reduces communication load without significantly impacting
the convergence rate in terms of its order.

######  Remark 3.12.

All the above results can be adopted for games with different dimensions of
the action sets. The scalar case is considered for the sake of notational
simplicity.

##  4 Stochastic Event-triggered and Compressed Distributed NE Seeking
Algorithm (SETC-DNES)

In this section, we introduce a stochastic event-triggered mechanism for
communication-efficient NE seeking. This mechanism incorporates a random
variable into the event-triggering condition, resulting in different
probabilities of triggering events based on local information. We demonstrate
that the proposed stochastic event-triggered and compressed distributed NE
seeking algorithm (SETC-DNES) achieves linear convergence to the NE.

Algorithm 3 Stochastic Event-triggering Condition Calculating Algorithm at
Each Agent

Input: Time iteration $k$, state value
$\mathbf{q}_{i,k},\mathbf{\tilde{q}}_{i,k-1},\mathbf{x}_{(i),k},\mathbf{h}_{i,k}$,
event-trigger parameter $\kappa>1$, $0<a<1$
Output: $\mathbb{I}_{i,k}$

1:if $k=0$, then

2: $\mathbb{I}_{i,k}=1$

3:else

4: Extract $\zeta_{i,k}\in(a,1)$ from an arbitrary stationary ergodic random
process

5: if
$\zeta_{i,k}>\kappa\exp(\frac{-||\mathbf{q}_{i,k}-\mathbf{\tilde{q}}_{i,k-1}||}{||\mathbf{x}_{(i),k}-\mathbf{h}_{i,k}||})$
then,

6: $\mathbb{I}_{i,k}=1$

7: else

8: $\mathbb{I}_{i,k}=0$

9: end if

10:end if

###  4.1 Algorithm Development

In this subsection, we extend the deterministic event-triggered mechanism from
Section 3 to a stochastic one. Given that SETC-DNES and ETC-DNES only differ
in the triggering calculation algorithm, we will not provide a detailed
overview of SETC-DNES. Instead, we present Algorithm 3 to illustrate the
stochastic event-triggered mechanism used in the compressed distributed NE
seeking algorithm.

Stochastic Event-triggered Mechanism: In Algorithm 3, a novel stochastic
event-triggered mechanism is proposed. The intuition behind the proposed
stochastic event-triggered method is to extend the deterministic one in
Section 3 by assigning a probability for each event, rather than triggering
whenever the defined event occurs.

Here is how it works: at each iteration $k\geq 1$, a random variable
$\zeta_{i,k}$ is drawn from a stationary ergodic random process with an
identical probability density function $f_{i,\zeta}$ for all agents
$i\in\mathcal{V}$. Then, each agent $i\in\mathcal{V}$ evaluates the triggering
condition (line 5 in Algorithm 3). If the condition is met, the triggering
indicator is set to $1$, and agent $i$ communicates the compressed value to
all its neighbors. Otherwise, no communication takes place at that iteration.

Differing from the event-triggering condition in Algorithm 2, which requires a
threshold $\tau_{i,k}$, this approach dispenses with the need for
$\tau_{i,k}$. Instead, agent $i$ calculates the ratio between
$||\mathbf{q}_{i,k}-\mathbf{\tilde{q}}_{i,k-1}||$ and
$||\mathbf{x}_{(i),k}-\mathbf{h}_{i,k}||$. Then, it compares $\zeta_{i,k}$
with
$\kappa\exp(-||\mathbf{q}_{i,k}-\mathbf{\tilde{q}}_{i,k-1}||/||\mathbf{x}_{(i),k}-\mathbf{h}_{i,k}||)$
to evaluate the triggering condition. Crucially, as
$||\mathbf{x}_{(i),k}-\mathbf{h}_{i,k}||$ diminishes over time (refer to
Section 4.2 for further details), it’s ensured that the probability of
communication increases monotonically with
$||\mathbf{q}_{i,k}-\mathbf{\tilde{q}}_{i,k-1}||$. This means that higher
probabilities of communication are assigned to more urgent cases corresponding
to larger values of $||\mathbf{q}_{i,k}-\mathbf{\tilde{q}}_{i,k-1}||$. To
provide an illustrative example, consider a scenario where $a=0.5$, and
$\zeta_{i,k}$ follows a uniformly distributed random process. In this case,
the probability of event occurrence, denoted as $P[\mathbb{I}_{i,k}=1]$, can
be expressed as
$0.5(1-\kappa\exp(-||\mathbf{q}_{i,k}-\mathbf{\tilde{q}}_{i,k-1}||/||\mathbf{x}_{(i),k}-\mathbf{h}_{i,k}||))$,
i.e., $P[\mathbb{I}_{i,k}=1]$ increases with the value of
$||\mathbf{q}_{i,k}-\mathbf{\tilde{q}}_{i,k-1}||$. In instances where
$\zeta_{i,k}$ remains a positive constant, the stochastic scheme transforms
into a deterministic one.

Note that except for the calculation of the triggering indicator, the state
update rule in SETC-DNES is identical to that in ETC-DNES. Consequently, the
compact form of SETC-DNES remains the same as ETC-DNES, as shown in Equations
(10).

###  4.2 Convergence Analysis

In this subsection, we analyze the convergence performance of SETC-DNES. We
first have the following inequality when $\mathbb{I}_{i,k}=0$ in SETC-DNES:

$||\mathbf{q}_{i,k}-\mathbf{\tilde{q}}_{i,k-1}||\leq(||\mathbf{x}_{(i),k}-\mathbf{h}_{i,k}||)(\ln\kappa-\ln\zeta_{i,k}).$
(20)

Given that $a<\zeta_{i,k}<1$, we can establish an upper bound for the event
error in SETC-DNES as follows:

$||\mathbf{E}_{k}||^{2}_{\text{F}}=\sum_{i}^{n}||\mathbf{e}_{i,k}||^{2}\leq\sum_{i}^{n}l^{2}(||\mathbf{x}_{(i),k}-\mathbf{h}_{i,k}||^{2})=l^{2}||\mathbf{X}_{k}-\mathbf{H}_{k}||^{2}_{\text{F}},$
(21)

where $l=\ln\kappa-\ln a$.

We now proceed to derive the following lemma, which will enable us to
establish a linear system of inequalities for bounding NE-seeking error and
compression error.

######  Lemma 4.13.

Given Assumption 1–5, when $\alpha\in(0,\frac{1}{r}]$, the following linear
system of component-wise inequalities holds for SETC-DNES,

$\mathbf{V}_{k+1}\leq\mathbf{C}\mathbf{V}_{k},$ (22)

where the elements of transition matrix $\mathbf{C}=[c_{ij}]$ are given by

$\mathbf{C}=\begin{bmatrix}c_{1}(1+L_{F}^{2}\gamma^{2}-2\mu_{F}\gamma)&c_{5}\gamma^{2}\\\
c_{3}\gamma^{2}L_{F}^{2}&c_{x}+c_{6}\gamma^{2}\end{bmatrix}$ (23)

with $c_{5}=c_{2}(l^{2}+1)$ and $c_{6}=c_{4}(l^{2}+1)$.

######  Proof 4.14.

Since SETC-DNES and ETC-DNES differ only in their event-triggering methods,
Lemma 3.4 also applies to SETC-DNES.

Bringing inequality (21) into inequality (16), we can obtain

$\displaystyle\mathbf{V}_{k+1}\leq\mathbf{A}\mathbf{V}_{k}+l^{2}\mathbf{B}||\mathbf{X}_{k}-\mathbf{H}_{k}||^{2}_{\text{F}}$
(24)
$\displaystyle=\begin{bmatrix}c_{1}(1+L_{F}^{2}\gamma^{2}-2\mu_{F}\gamma)&c_{2}\gamma^{2}\\\
c_{3}\gamma^{2}L_{F}^{2}&c_{x}+c_{4}\gamma^{2}\\\
\end{bmatrix}\mathbf{V}_{k}+\begin{bmatrix}0&l^{2}c_{2}\gamma^{2}\\\
0&l^{2}c_{4}\gamma^{2}\\\ \end{bmatrix}\mathbf{V}_{k}$
$\displaystyle=\begin{bmatrix}c_{1}(1+L_{F}^{2}\gamma^{2}-2\mu_{F}\gamma)&c_{2}\gamma^{2}+l^{2}c_{2}\gamma^{2}\\\
c_{3}\gamma^{2}L_{F}^{2}&c_{x}+c_{4}\gamma^{2}+l^{2}c_{4}\gamma^{2}\end{bmatrix}\mathbf{V}_{k}$
$\displaystyle=\mathbf{C}\mathbf{V}_{k}.$

The following theorem shows the convergence properties of SETC-DNES.

######  Theorem 4.15.

Suppose Assumption 1–5 hold, we take $\alpha\in(0,\frac{1}{r}]$, the consensus
step-size $\gamma=\mu_{L}/L_{F}^{2}$, and gradient step-size $\eta$ satisfying

$\eta\leq\min\Big{\\{}\frac{2n}{\mu_{r}}\sqrt{\frac{1-c_{x}}{m_{3}}},\frac{\tilde{\lambda}_{\text{min}}(I-W)m_{4}^{2}}{L_{m}(m_{4}^{2}+1)}\Big{\\}},$

where
$m_{3}=\frac{c_{3}\epsilon_{3}}{||I-W||_{\text{F}}^{2}}+\frac{\epsilon_{4}}{4||I-W||_{\text{F}}^{2}}+\frac{c_{4}(1+l^{2})\epsilon_{4}}{||I-W||_{\text{F}}^{4}},m_{4}=-1+\sqrt{1+\frac{\mu_{r}^{2}}{4n^{2}L_{m}}\sqrt{\frac{m_{3}}{1-c_{x}}}},\epsilon_{3}\geq\frac{4c_{2}(1+l^{2})}{L_{F}^{2}}\epsilon_{4}>0.$

Then the NE-seeking error
$\mathbb{E}_{\xi}[||\mathbf{X}^{k+1}-\mathbf{X}^{\star}||^{2}_{\text{F}}]$ and
the compression error
$\mathbb{E}_{\xi}[||\mathbf{X}^{k+1}-\mathbf{H}^{k+1}||^{2}_{\text{F}}]$ of
SETC-DNES both converge to $0$ at the linear rate
$\mathcal{O}(\rho(\mathbf{C})^{k})$ with $\rho(\mathbf{C})<1$ under SETC-DNES.

######  Proof 4.16.

The proof of Theorem 2 follows a similar structure to that of Theorem 1 and is
omitted here.

######  Remark 4.17.

Theorem 4.15 establishes the linear convergence of the proposed SETC-DNES
algorithm. As indicated in (21), the event error $\mathbf{E}_{k}$ is bounded
by the differences between $\mathbf{X}_{k}$ and $\mathbf{H}_{k}$.
Consequently, the convergence rate is independent of any specific assumptions
regarding the event-triggering condition and relies solely on the spectral
radius $\rho(\mathbf{C})$. Therefore, Theorem 4.15 effectively demonstrates
the well-posedness of the proposed SETC-DNES algorithm.

##  5 SIMULATIONS

In this section, we provide numerical results to validate our theoretical
results and compare our proposed communication-efficient algorithms with
existing methods.

Network. We consider a randomly generated directed communication network with
$n=50$ agents. The weight matrix $W$ is

$[W]_{ij}=\begin{cases}1/(\max_{i\in V}\mathcal{|N|}_{i}),&\mbox{if
$j\in\mathcal{N}_{i}^{-}$;}\\\
1-\sum_{j\in\mathcal{N}_{i}^{-}}w_{ij},&\mbox{if $j=i$;}\\\
0,&\mbox{Otherwise.}\end{cases}$ (25)

Task. The connectivity control game defined in [33] is considered, where the
sensors in the network try to find a tradeoff between the local objective,
e.g., source seeking and positioning and the global objective, e.g.,
maintaining connectivity with other sensors. The cost function of sensor $i$
is defined as $J_{i}(\mathbf{x})=l_{i}^{c}(x_{i})+l_{i}^{g}(\mathbf{x})$,
where $l_{i}^{c}(x_{i})=x_{i}^{\top}r_{ii}x_{i}+x_{i}^{\top}r_{i}+b_{i}$,
$l_{i}^{g}(\mathbf{x})=\sum\limits_{j\in S_{i}}c_{ij}||x_{i}-x_{j}||^{2}$,
$S_{i}\subseteq V$ and $x_{i}=[x_{i1},x_{i2}]^{\top}\in\mathbb{R}^{2}$ denotes
the position of sensor $i$, and $r_{ii},r_{i},b_{i},c_{ij}>0$ are constants.
The parameters are set as $r_{ii}=\begin{bmatrix}i&0\\\
0&i\end{bmatrix},r_{i}=\begin{bmatrix}i&i\end{bmatrix}^{\top},b_{i}=i$ and
$c_{ij}=1,\forall i,j\in V$. Furthermore, there is $S_{i}=\\{i+1\\}$ for
$i\in\\{1,2,\ldots,49\\}$ and $S_{50}=\\{1\\}$. The unique Nash equilibrium of
the game is $x^{\star}_{ij}=-0.5$ for $i\in\\{1,2,\ldots,50\\},j\in\\{1,2\\}$.
Meanwhile, $\mathbf{x}_{(i),0}$ are randomly generated in $[0,1]^{100}$,
$\mathbf{h}_{i,0}=\mathbf{0}$.

Figure 1: Residual v.s. number of iterations for different algorithms.

Compressor. For information compression, we implement the stochastic
quantization compressor with $b=2$ and $q=\infty$ in (3) for all agents at
each iteration. As pointed out in [12], transmitting this compressed message
needs $(b+1)d+l$ bits if a scalar can be transmitted with $l$ bits while
maintaining sufficient precision. In contrast, each agent sends $dl$ bits at
each triggered iteration when implementing NE seeking algorithm without
compression. In this simulation, we choose $l=32$.

Algorithms. We compare ETC-DNES with different triggering thresholds and SETC-
DNES to C-DNES [15], which is the current state-of-the-art in compressed NE
seeking, and event-triggered NE seeking without compression [22]. All the
hyper-parameters used in the experiment are tuned manually and given in TABLE
2.

Table 2: Parameter settings for different algorithms Algorithm | Value
---|---
C-DNES [15] | $\eta=0.01,\gamma=0.5,\alpha=0.05$
Event-triggered NE [22] |  $\eta=0.01,\tau_{k}=10/k^{1.1}$ (suggested by [22])
ETC-DNES-1 | $\eta=0.01,\gamma=0.5,\alpha=0.05,\tau_{k}=10/k^{1.1}$
ETC-DNES-2 | $\eta=0.01,\gamma=0.5,\alpha=0.05,\tau_{k}=50\times 0.99^{k}$
SETC-DNES | $\eta=0.01,\gamma=0.5,\alpha=0.05,$
| $\zeta_{i,k}\sim U(0.5,1),\kappa=1.5$
Table 3: A comparison on the residuals and averaged trigger times by stopping the algorithms at $k=5000$. Rate is calculated as averaged trigger times divided by total times Algorithm | Residual | Averaged trigger times | Rate
---|---|---|---
Event-triggered NE [22] | 0.0319 | 1509.4 | $30.2\%$
ETC-DNES-1 | 0.0162 | 1551.3 | $31.0\%$
ETC-DNES-2 | 0.0024 | 3027.4 | $60.5\%$
SETC-DNES | 0.0022 | 2101.2 | $42.0\%$

Results. We use the normalized residual
$\mathcal{R}=\frac{||\mathbf{X}_{k}-\mathbf{X}^{\star}||_{\text{F}}}{||\mathbf{X}_{0}-\mathbf{X}^{\star}||_{\text{F}}}$
to measure the performance of each algorithm. We plot the convergence of the
residual concerning both the number of iterations and the total bits
transmitted for the various algorithm and triggering conditions combinations,
all initialized with the same initial conditions. These results are shown in
Fig. 1 and Fig. 3, respectively. Moreover, the effectiveness of different
triggering condition is illustrated in Fig. 2 and a comparison of the total
transmitted bits required by different algorithms to reach $\mathcal{R}\leq
0.01$ is provided in Fig. 4. Here are some key observations:

  * •

From Fig. 1, we can see that proposed communication-efficient algorithm with
different triggering conditions all converge to the NE of the game. Moreover,
ETC-DNES-2 and SETC-DNES achieve a similar linear convergence rate as C-DNES
without event trigger [15].

  * •

The effectiveness of different triggering conditions is depicted in Fig. 2,
clearly demonstrating a reduction in communication rounds when event-triggered
mechanisms are employed. Regarding execution efficiency, a comprehensive
comparison is provided in Table 3. This comparison includes algorithm
residuals, the averaged trigger times across all agents, and communication
rates for each algorithm at the time iteration $k=5000$. Notably, ETC-DNES-1
excels in significantly reducing the number of communication rounds, although
it does come at the expense of a slightly larger residual. It’s important to
note that while ETC-DNES-2 achieves a small residual, it does so at the cost
of a larger number of communication rounds. In contrast, SETC-DNES manages to
simultaneously achieve a small residual and a low communication rate, making
it a compelling choice for efficient distributed Nash equilibrium seeking.

  * •

From Fig. 3 we can see that our communication-efficient algorithms converge
faster than event-triggered NE and C-DNES when comparing their performances
based on the total number of bits that agents communicate, which shows the
effectiveness of our proposed algorithms. Notably, it can be seen in Fig. 4
that, SETC-DNES distinguishes itself by achieving the lowest communication
cost among all the algorithms, utilizing only $1.24\%$ of the bits required by
event-triggered NE (without compression) to reach a specified accuracy of the
algorithm.

(a)

(b)

(c)

(d)

Figure 2: Triggering instants for different algorithms with event-triggered
communication. (a) event-triggered NE [22]; (b) ETC-DNES-1; (c) ETC-DNES-2;
(d) SETC-DNES. Figure 3: Residual v.s. number of total transmitted bits for
different algorithms. Figure 4: Total transmitted bits of different algorithms
to obtain $\mathcal{R}\leq 0.01$.

##  6 CONCLUSION AND FUTURE WORK

In this paper, we have studied the problem of distributed Nash equilibrium
seeking over directed networks with constrained communication. A novel
compressed event-triggered distributed NE seeking approach (ETC-DNES) is
proposed to save communication, where a compressed information is exchanged
among neighboring agents only when an event condition is satisfied. ETC-DNES
can guarantee the exact convergence to the NE using a diminishing triggering
threshold sequence, and linear convergence can be achieved under certain
conditions. To further improve the algorithm efficiency, we present a
stochastic event-triggered mechanism for compressed NE seeking algorithm
(SETC-DNES) and also prove its linear convergent property. Simulation examples
demonstrate the effectiveness of the proposed communication-efficient
algorithms for directed graphs, with SETC-DNES outperforming ETC-DNES in terms
of total number of transmitted bits while achieving a small error. Future
works may focus on the extensions to time-varying networks. Distributed NE
seeking with constrained action space can also be considered.

##  7 APPENDIX

###  7.1 Supporting Lemmas

The following lemmas are useful in the proofs.

######  Lemma 7.18.

(Lemma 7 in [8]) For any $\mathbf{U,V}\in\mathbb{R}^{n\times n}$, the
following inequality is satisfied:

$||\mathbf{U}+\mathbf{V}||^{2}\leq\tau^{\prime}||\mathbf{U}||^{2}+\frac{\tau^{\prime}}{\tau^{\prime}-1}||\mathbf{V}||^{2},$
(26)

where $\tau^{\prime}>1$. Moreover, for any
$\mathbf{U}_{1},\mathbf{U}_{2},\mathbf{U}_{3}\in\mathbb{R}^{n\times n}$, we
have
$||\mathbf{U}_{1}+\mathbf{U}_{2}+\mathbf{U}_{3}||^{2}\leq\tau_{1}||\mathbf{U}_{1}||^{2}+\frac{2\tau_{1}}{\tau_{1}-1}(||\mathbf{U}_{2}||^{2}+||\mathbf{U}_{3}||^{2})$
and $||\mathbf{U}_{1}+\mathbf{U}_{2}+\mathbf{U}_{3}||^{2}\leq
3||\mathbf{U}_{1}||^{2}+3||\mathbf{U}_{2}||^{2}+3||\mathbf{U}_{3}||^{2}$.

######  Lemma 7.19.

(Lemma 3.1 in [34]) Suppose that $0<\beta<1$ and let $\zeta_{k}\geq 0$ be a
scalar sequence. If $\lim_{k\rightarrow\infty}\zeta_{k}=0$, then

$\lim_{k\rightarrow\infty}\sum\limits_{r=0}^{k}\beta^{k-r}\zeta_{r}=0.$

######  Lemma 7.20.

(Lemma 2 in [35]) Let $\\{a_{k}\\}$ be a sequence such that
$a_{k}=C_{a}\gamma^{k}$, where $C_{a}>0$ and $0<\gamma<1$. Then for
$0<\theta<1$,

$\sum\limits_{r=0}^{k}a_{r}\theta^{k-r}<C\mu^{k},$

where $\max\\{\gamma,\theta\\}<\mu<1$ and $C$ is a positive constant.

######  Lemma 7.21.

(Lemma 1 in [31]) Given Assumption 5, the augmented mapping $\mathbf{F}_{a}$
of game $\Gamma(n,\\{J_{i}\\},\\{\Omega_{i}\\})$ is Lipschitz continuous with
$L_{F}=\eta L_{m}+||I-W||_{\text{F}}$, where
$L_{m}=\max_{i}\\{\sqrt{L_{i}^{2}+L_{-i}^{2}}\\}$.

######  Lemma 7.22.

(Lemma 3 in [31]) Given Assumption 1, 4 and 5, the augmented mapping
$\mathbf{F}_{a}$ of game $\Gamma(n,\\{J_{i}\\},\\{\Omega_{i}\\})$ is
restricted strongly monotone to any NE matrix
$\mathbf{X}^{\star}=\mathbf{1}(\mathbf{x}^{\star})^{\top}$ with the constant
$\mu_{F}=\min\\{b_{1},b_{2}\\}>0$, where
$b_{1}=\eta\mu_{r}/2n,b_{2}=(\beta^{2}\tilde{\lambda}_{\text{min}}(I-W)/(\beta^{2}+1))-\eta^{2}L_{m}$
and $\beta$ is a positive constant such that
$\beta^{2}+2\beta=\frac{\mu_{r}}{2n\eta L_{m}}$.

###  7.2 Proof of Lemma 3.4

We derive two inequalities in terms of NE-seeking error and compression error,
respectively.

NE-seeking error:

Based on Proposition 1 in [31] , we conclude that
$\mathbf{X}^{\star}=\mathbf{X}^{\star}-\gamma\mathbf{F}_{a}(\mathbf{X}^{\star}),\forall\gamma>0$.

Thus, we can obtain

$\displaystyle||\mathbf{X}_{k+1}-\mathbf{X}^{\star}||_{\text{F}}^{2}$ (27)
$\displaystyle\leq||\mathbf{X}_{k}-\gamma\mathbf{F}_{a}(\mathbf{X}_{k})+\gamma(I-W)\mathbf{D}_{k}-\mathbf{X}^{\star}+\gamma\mathbf{F}_{a}(\mathbf{X}^{\star})||_{\text{F}}^{2}$
$\displaystyle\leq
c_{1}||\mathbf{X}_{k}-\gamma\mathbf{F}_{a}(\mathbf{X}_{k})-\mathbf{X}^{\star}+\gamma\mathbf{F}_{a}(\mathbf{X}^{\star})||_{\text{F}}^{2}$
$\displaystyle+\frac{c_{1}}{c_{1}-1}\gamma^{2}||I-W||_{\text{F}}^{2}||\mathbf{D}_{k}||_{\text{F}}^{2},$

where the second inequality comes from Lemma 7.18 with $c_{1}>1$.

Next, we bound

$\displaystyle||\mathbf{X}_{k}-\gamma\mathbf{F}_{a}(\mathbf{X}_{k})-\mathbf{X}^{\star}+\gamma\mathbf{F}_{a}(\mathbf{X}^{\star})||_{\text{F}}^{2}$
(28)
$\displaystyle=||\mathbf{X}_{k}-\mathbf{X}^{\star}||_{\text{F}}^{2}+\gamma^{2}||\mathbf{F}_{a}(\mathbf{X}_{k})-\mathbf{F}_{a}(\mathbf{X}^{\star})||_{\text{F}}^{2}$
$\displaystyle-2\gamma\langle\mathbf{F}_{a}(\mathbf{X}_{k})-\mathbf{F}_{a}(\mathbf{X}^{\star}),\mathbf{X}_{k}-\mathbf{X}^{\star}\rangle$
$\displaystyle\leq(1+\gamma^{2}L_{F}^{2}-2\gamma\mu_{F})||\mathbf{X}_{k}-\mathbf{X}^{\star}||_{\text{F}}^{2},$

where the last inequality is based on Lemma 7.21 and Lemma 7.22.

From (28), we have
$\min\\{1+\gamma^{2}L_{F}^{2}-2\gamma\mu_{F}\\}=(1-\mu_{F}^{2}/L_{F}^{2})>0$.
Combining (27) and (28), we can have the following inequality by taking
$c_{1}=\frac{2L_{F}^{2}-\mu_{F}^{2}}{2L_{F}^{2}-2\mu_{F}^{2}}$.

$\displaystyle||\mathbf{X}_{k+1}-\mathbf{X}^{\star}||_{\text{F}}^{2}$
$\displaystyle\leq
c_{1}(1+\gamma^{2}L_{F}^{2}-2\gamma\mu_{F})||\mathbf{X}_{k}-\mathbf{X}^{\star}||_{\text{F}}^{2}$
(29)
$\displaystyle+\frac{c_{1}\gamma^{2}||I-W||_{\text{F}}^{2}}{c_{1}-1}||\mathbf{D}_{k}||_{\text{F}}^{2}.$

Then, from Lemma 3.2, we can obtain

$\displaystyle\mathbb{E}_{\xi}[||\mathbf{X}_{k+1}-\mathbf{X}^{\star}||_{\text{F}}^{2}\mid\mathcal{F}^{k}]$
(30) $\displaystyle\leq
c_{1}(1+\gamma^{2}L_{F}^{2}-2\gamma\mu_{F})\mathbb{E}_{\xi}[||\mathbf{X}_{k}-\mathbf{X}^{\star}||_{\text{F}}^{2}\mid\mathcal{F}^{k}]$
$\displaystyle+c_{2}\gamma^{2}\mathbb{E}_{\xi}[||\mathbf{X}_{k}-\mathbf{H}_{k}||_{\text{F}}^{2}\mid\mathcal{F}^{k}]+c_{2}\gamma^{2}||\mathbf{E}_{k}||_{\text{F}}^{2},$

where $c_{2}=\frac{2c_{1}||I-W||_{\text{F}}^{2}C}{c_{1}-1}$.

Compression error of the decision variable:

Denote
$\mathcal{C}_{r}^{k}(\mathbf{X}_{k})=\mathcal{C}^{k}(\mathbf{X}_{k})/r$,
according to (10d), for $0<\alpha\leq\frac{1}{r}$, we have

$\begin{split}&||\mathbf{X}_{k+1}-\mathbf{H}_{k+1}||^{2}\\\
=&||\mathbf{X}_{k+1}-\mathbf{X}_{k}+\mathbf{X}_{k}-\mathbf{H}_{k}-\alpha
r\frac{\mathbf{Q}_{k}}{r}||^{2}\\\ =&||\mathbf{X}_{k+1}-\mathbf{X}_{k}+\alpha
r(\mathbf{X}_{k}-\mathbf{H}_{k}-\mathcal{C}_{r}^{k}(\mathbf{X}_{k}-\mathbf{H}_{k}))\\\
&+(1-\alpha r)(\mathbf{X}_{k}-\mathbf{H}_{k})||^{2}\\\ \leq&\tau_{2}||\alpha
r(\mathbf{X}_{k}-\mathbf{H}_{k}-\mathcal{C}_{r}^{k}(\mathbf{X}_{k}-\mathbf{H}_{k}))\\\
&+(1-\alpha
r)(\mathbf{X}_{k}-\mathbf{H}_{k})||^{2}+\frac{\tau_{2}}{\tau_{2}-1}||\mathbf{X}_{k+1}-\mathbf{X}_{k}||^{2}\\\
\leq&\tau_{2}\Big{[}\alpha
r||\mathbf{X}_{k}-\mathbf{H}_{k}-\mathcal{C}_{r}^{k}(\mathbf{X}_{k}-\mathbf{H}_{k})||^{2}\\\
&+(1-\alpha
r)||\mathbf{X}_{k}-\mathbf{H}_{k}||^{2}\Big{]}+\frac{\tau_{2}}{\tau_{2}-1}||\mathbf{X}_{k+1}-\mathbf{X}_{k}||^{2},\\\
\end{split}$ (31)

where in the first inequality we use the result of Lemma 7.18 with
$\tau_{2}=\frac{2-\alpha r\delta}{2-2\alpha r\delta}>1$.

Taking conditional expectation on both sides of (31), we obtain

$\begin{split}&\mathbb{E}_{\xi}[||\mathbf{X}_{k+1}-\mathbf{H}_{k+1}||^{2}\mid\mathcal{F}^{k}]\\\
&\leq\tau_{2}[\alpha r(1-\delta)+(1-\alpha
r)]\mathbb{E}_{\xi}[||\mathbf{X}_{k}-\mathbf{H}_{k}||^{2}\mid\mathcal{F}^{k}]\\\
&+\frac{\tau_{2}}{\tau_{2}-1}\mathbb{E}_{\xi}[||\mathbf{X}_{k+1}-\mathbf{X}_{k}||^{2}\mid\mathcal{F}^{k}],\\\
\end{split}$ (32)

where the inequality holds based on Assumption 2.

Moreover, based on Lemma 3.2, we have

$\begin{split}&\mathbb{E}_{\xi}[||\mathbf{X}_{k+1}-\mathbf{X}_{k}||^{2}\mid\mathcal{F}^{k}]\\\
&=\mathbb{E}_{\xi}[||\gamma(I-W)(\mathbf{X}_{k}-\mathbf{\hat{X}}_{k})-\gamma\mathbf{F}_{a}(\mathbf{X}^{k})+\gamma\mathbf{F}_{a}(\mathbf{X}^{\star})\mid\mathcal{F}^{k}]\\\
&\leq
2\gamma^{2}C||(I-W)||^{2}(2\mathbb{E}_{\xi}[||\mathbf{X}_{k}-\mathbf{H}_{k}||^{2}\mid\mathcal{F}^{k}]+2||\mathbf{E}_{k}||_{\text{F}}^{2})\\\
&+2\gamma^{2}L_{F}^{2}\mathbb{E}_{\xi}[||\mathbf{X}_{k}-\mathbf{X}^{\star}||^{2}\mid\mathcal{F}^{k}]\\\
\end{split}$ (33)

Bringing (33) into (32) and denoting
$c_{3}=\frac{2\tau_{2}}{\tau_{2}-1}=\frac{4-2\alpha r\delta}{\alpha
r\delta},c_{x}=\tau_{2}[\alpha r(1-\delta)+(1-\alpha r)]=\tau_{2}(1-\alpha
r\delta)=\frac{2-\alpha r\delta}{2}<1$, we have

$\begin{split}&\mathbb{E}_{\xi}[||\mathbf{X}_{k+1}-\mathbf{H}_{k+1}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]\\\
&\leq
c_{3}\gamma^{2}L_{F}^{2}\mathbb{E}_{\xi}[||\mathbf{X}_{k}-\mathbf{X}^{\star}||_{\text{F}}^{2}\mid\mathcal{F}^{k}]\\\
&+(c_{x}+c_{4}\gamma^{2})\mathbb{E}_{\xi}[||\mathbf{X}_{k}-\mathbf{H}_{k}||^{2}\mid\mathcal{F}^{k}]+c_{4}\gamma^{2}||\mathbf{E}_{k}||_{\text{F}}^{2},\\\
\end{split}$ (34)

where $c_{4}=2c_{3}C||(I-W)||^{2}_{\text{F}}$.

Combing the above equalities (30) and (34) yields the desired result.

###  7.3 Proof of Theorem 3.7

Since $\gamma=\mu_{F}/L_{F}^{2}$, we have
$[\mathbf{A}]_{11}=c_{1}(1+L_{F}^{2}\gamma^{2}-2\mu_{F}\gamma)=(1-\mu_{F}^{2}/2L_{F}^{2})<1$.

We then infer the range of stepsize satisfying $\rho_{A}<1$ to establish the
convergence of ETC-DNES. Based on Corollary 8.1.29 in [36], to ensure
$\rho_{A}<1$, we can derive the range of $\eta$ and a positive vector
$\mathbf{\epsilon}:=[\epsilon_{1},\epsilon_{2}]^{\top}\in\mathbb{R}_{++}^{2}$,
such that

$\mathbf{A\epsilon}\leq(1-\frac{\mu_{F}^{2}}{4L_{F}^{2}})\mathbf{\epsilon}$
(35)

holds. Then, we derive the conditions that inequality (35) holds.

1) First inequality in (35):
$\quad[\mathbf{A\epsilon}]_{1}\leq[(1-\frac{\mu_{F}^{2}}{4L_{F}^{2}})\mathbf{\epsilon}]_{1}$

$(1-\frac{\mu_{F}^{2}}{2L_{F}^{2}})\epsilon_{1}+\frac{\mu_{F}^{2}c_{2}}{L_{F}^{4}}\epsilon_{2}\leq(1-\frac{\mu_{F}^{2}}{4L_{F}^{2}})\epsilon_{1}.$
(36)

Inequality (36) holds if
$\frac{4c_{2}}{L_{F}^{2}}\epsilon_{2}\leq\epsilon_{1}$.

2) Second inequality in (35):
$\quad[\mathbf{A\epsilon}]_{2}\leq[(1-\frac{\mu_{F}^{2}}{4L_{F}^{2}})\mathbf{\epsilon}]_{2}$

$\frac{c_{3}\mu_{F}^{2}}{L_{F}^{2}}\epsilon_{1}+(c_{x}+c_{4}\frac{\mu_{F}^{2}}{L_{F}^{4}})\epsilon_{2}\leq(1-\frac{\mu_{F}^{2}}{4L_{F}^{2}})\epsilon_{2},$
(37)

which is equivalent to

$\frac{c_{3}\mu_{F}^{2}}{L_{F}^{2}}\epsilon_{1}+(\frac{\mu_{F}^{2}}{4L_{F}^{2}}+c_{4}\frac{\mu_{F}^{2}}{L_{F}^{4}})\epsilon_{2}\leq(1-c_{x})\epsilon_{2}.$
(38)

Note that $L_{F}^{2}>||I-W||_{\text{F}}^{2}$ and denote

$m_{1}=\frac{c_{3}\epsilon_{1}}{||I-W||_{\text{F}}^{2}}+\frac{\epsilon_{2}}{4||I-W||_{\text{F}}^{2}}+\frac{c_{4}\epsilon_{2}}{||I-W||_{\text{F}}^{4}}.$
(39)

Inequality (37) is verified with

$\mu_{F}\leq\sqrt{\frac{1-c_{x}}{m_{1}}}.$ (40)

Since $\mu_{F}=\min\\{b_{1},b_{2}\\}>0$, the equality (40) becomes

$\displaystyle b_{1}=\eta\mu_{r}/2n\leq\sqrt{\frac{1-c_{x}}{m_{1}}},$ (41)
$\displaystyle
b_{2}=(\beta^{2}\tilde{\lambda}_{\text{min}}(I-W)/(\beta^{2}+1))-\eta^{2}L_{m}>0.$

It suffices to have

$\eta\leq\min\Big{\\{}\frac{2n}{\mu_{r}}\sqrt{\frac{1-c_{x}}{m_{1}}},\frac{\tilde{\lambda}_{\text{min}}(I-W)m_{2}^{2}}{L_{m}(m_{2}^{2}+1)}\Big{\\}},$
(42)

where
$m_{2}=-1+\sqrt{1+\frac{\mu_{r}^{2}}{4n^{2}L_{m}}\sqrt{\frac{m_{1}}{1-c_{x}}}}$.

To wrap up, if the positive constants $\epsilon_{1},\epsilon_{2}$ and the
step-size $\eta$ satisfy the following conditions,

$\begin{split}&\epsilon_{1}\geq\frac{4c_{2}}{L_{F}^{2}}\epsilon_{2},\quad\epsilon_{2}>0,\\\
&\eta\leq\min\Big{\\{}\frac{2n}{\mu_{r}}\sqrt{\frac{1-c_{x}}{m_{1}}},\frac{\tilde{\lambda}_{\text{min}}(I-W)m_{2}^{2}}{L_{m}(m_{2}^{2}+1)}\Big{\\}},\end{split}$
(43)

the linear system of element-wise inequalities in (35) can be shown.

According to the above results, i.e., $\rho_{A}<1$, we continue to establish
the remaining proof of convergence of ETC-DNES. We recursively iterate (16) as
follows:

$\mathbf{V}_{k}\leq\mathbf{A}^{k}\mathbf{V}_{0}+\sum\limits_{r=0}^{k-1}\mathbf{A}^{k-r-1}\mathbf{B}||\mathbf{E}_{r}||^{2}_{\text{F}}.$
(44)

Since $\mathbf{A}^{2}$ is a positive matrix, $\mathbf{A}$ is primitive
(Theorem 8.5.2 in [36]). Then each element of $\mathbf{A}^{k}$ decreases at
the rate of $\rho(\mathbf{A})$ (Theorem 8.5.1 in [36]), i.e.,

$\mathbf{A}^{k}\leq C_{A}\rho^{k}_{A}\mathbf{1}\mathbf{1}^{\top},$ (45)

where $C_{A}$ is a positive constant.

Hence, we have

$\displaystyle\sum\limits_{r=0}^{k-1}\mathbf{A}^{k-r-1}\mathbf{B}||\mathbf{E}_{r}||^{2}_{\text{F}}\leq\sum\limits_{r=0}^{k-1}C_{A}\rho^{k-r-1}_{A}\mathbf{1}\mathbf{1}^{\top}\mathbf{B}||\mathbf{E}_{r}||^{2}_{\text{F}}$
(46)
$\displaystyle=(c_{2}+c_{4})\gamma^{2}C_{A}\sum\limits_{r=0}^{k-1}\rho^{k-r-1}_{A}||\mathbf{E}_{r}||^{2}_{\text{F}}\mathbf{1}.$

Substituting (45) and (46) in (44) gives

$\mathbf{V}_{k}\leq
C_{A}\big{(}\rho^{k}_{A}\mathbf{1}^{\top}\mathbf{V}_{0}+(c_{2}+c_{4})\gamma^{2}\sum\limits_{r=0}^{k-1}\rho^{k-r-1}_{A}||\mathbf{E}_{r}||^{2}_{\text{F}}\big{)}\mathbf{1}.$
(47)

With Lemma 1 and Lemma 7.19, we have

$\lim\limits_{k\rightarrow\infty}\sum\limits_{r=0}^{k-1}\rho^{k-r-1}_{A}||\mathbf{E}_{r}||^{2}_{\text{F}}=0.$
(48)

Thus, we have $\lim\limits_{k\rightarrow\infty}\mathbf{V}_{k}=0$, which
completes the proof.

###  7.4 Proof of Corollory 3.9

Since $\tau_{i,k}=C_{i}p_{i}^{k}$, we can obtain
$||\mathbf{E}_{k}||^{2}_{\text{F}}\leq\sum_{i}^{n}\tau_{i,k}^{2}\leq Ca^{2k}$,
where $C=\max_{i}C_{i}$, $\bar{p}=\max_{i}p_{i}$. Then equation (47) can be
written as

$\displaystyle\mathbf{V}_{k}$ $\displaystyle\leq
C_{A}\big{(}\rho^{k}_{A}\mathbf{1}^{\top}\mathbf{V}_{0}+(c_{2}+c_{4})\gamma^{2}C\sum\limits_{r=0}^{k-1}\rho^{k-r-1}_{A}\bar{p}^{2r}\big{)}\mathbf{1}$
(49) $\displaystyle\leq
C_{A}\big{(}\rho^{k}_{A}\mathbf{1}^{\top}\mathbf{V}_{0}+(c_{2}+c_{4})\gamma^{2}C\sum\limits_{r=0}^{k-1}\rho^{k-r-1}_{A}\bar{p}^{r}\big{)}\mathbf{1}$
$\displaystyle\leq
C_{A}\big{(}\mathbf{1}^{\top}\mathbf{V}_{0}m^{k}+(c_{2}+c_{4})\gamma^{2}Cm^{k-1}\big{)}\mathbf{1},$

where $0<\max\\{\rho_{A},\bar{p}\\}<m<1$ and the last inequality can be
obtained from Lemma 7.20.

Hence, the vector $\mathbf{V}_{k}$ decreases at the linear rate
$\mathcal{O}(m^{k})$, where $0<m<1$, which implies that the error vector
converges to $0$ linearly.

## References

  * [1] Z. Ma, D. S. Callaway, and I. A. Hiskens, “Decentralized charging control of large populations of plug-in electric vehicles,” _IEEE Transactions on Control Systems Technology_ , vol. 21, no. 1, pp. 67–78, 2011.
  * [2] 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.
  * [3] W. Saad, Z. Han, H. V. Poor, and T. Basar, “Game-theoretic methods for the smart grid: An overview of microgrid systems, demand-side management, and smart grid communications,” _IEEE Signal Processing Magazine_ , vol. 29, no. 5, pp. 86–105, 2012.
  * [4] C.-K. Yu, M. Van Der Schaar, and A. H. Sayed, “Distributed learning for stochastic generalized Nash equilibrium problems,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 15, pp. 3893–3908, 2017.
  * [5] G. Belgioioso and S. Grammatico, “Projected-gradient algorithms for generalized equilibrium seeking in aggregative games arepreconditioned forward-backward methods,” in _IEEE European Control Conference (ECC),_ , 2018, pp. 2188–2193.
  * [6] J. S. Shamma and G. Arslan, “Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria,” _IEEE Transactions on Automatic Control_ , vol. 50, no. 3, pp. 312–327, 2005.
  * [7] J. Ghaderi and R. Srikant, “Opinion dynamics in social networks with stubborn agents: Equilibrium and convergence rate,” _Automatica_ , vol. 50, no. 12, pp. 3209–3215, 2014.
  * [8] Y. Liao, Z. Li, K. Huang, and S. Pu, “A compressed gradient tracking method for decentralized optimization with linear convergence,” _IEEE Transactions on Automatic Control_ , vol. 67, no. 10, pp. 5622–5629, 2022.
  * [9] D. Kovalev, A. Koloskova, M. Jaggi, P. Richtarik, and S. Stich, “A linearly convergent algorithm for decentralized optimization: Sending less bits for free!” in _Proceeding of the 24th International Conference on Artificial Intelligence and Statistics_. PMLR, 2021, pp. 4087–4095.
  * [10] X. Liu and Y. Li, “Linear convergent decentralized optimization with compression,” in _Proceedings of the 9th nternational Conference on Learning Representations_ , 2021.
  * [11] A. Beznosikov, S. Horváth, P. Richtárik, and M. Safaryan, “On biased compression for distributed learning,” _arXiv preprint arXiv:2002.12410_ , 2020.
  * [12] J. Zhang, K. You, and L. Xie, “Innovation compression for communication-efficient distributed optimization with linear convergence,” _IEEE Transactions on Automatic Control_ , 2023.
  * [13] E. Nekouei, G. N. Nair, and T. Alpcan, “Performance analysis of gradient-based Nash seeking algorithms under quantization,” _IEEE Transactions on Automatic Control_ , vol. 61, no. 12, pp. 3771–3783, 2016.
  * [14] Z. Chen, J. Ma, S. Liang, and L. Li, “Distributed nash equilibrium seeking under quantization communication,” _Automatica_ , vol. 141, p. 110318, 2022\.
  * [15] X. Chen, Y. Wu, X. Yi, M. Huang, and L. Shi, “Linear convergent distributed Nash equilibrium seeking with compression,” _arXiv preprint arXiv:2211.07849_ , 2022.
  * [16] W. He, B. Xu, Q.-L. Han, and F. Qian, “Adaptive consensus control of linear multiagent systems with dynamic event-triggered strategies,” _IEEE Transactions on Cybernetics_ , vol. 50, no. 7, pp. 2996–3008, 2019.
  * [17] X. Ge, S. Xiao, Q.-L. Han, X.-M. Zhang, and D. Ding, “Dynamic event-triggered scheduling and platooning control co-design for automated vehicles over vehicular ad-hoc networks,” _IEEE/CAA Journal of Automatica Sinica_ , vol. 9, no. 1, pp. 31–46, 2021.
  * [18] C. Liu, H. Li, Y. Shi, and D. Xu, “Distributed event-triggered gradient method for constrained convex minimization,” _IEEE Transactions on Automatic Control_ , vol. 65, no. 2, pp. 778–785, 2019.
  * [19] X. Cao and T. Başar, “Decentralized online convex optimization with event-triggered communications,” _IEEE Transactions on Signal Processing_ , vol. 69, pp. 284–299, 2020.
  * [20] C.-X. Shi and G.-H. Yang, “Distributed Nash equilibrium computation in aggregative games: An event-triggered algorithm,” _Information Sciences_ , vol. 489, pp. 289–302, 2019.
  * [21] K. Zhang, X. Fang, D. Wang, Y. Lv, and X. Yu, “Distributed Nash equilibrium seeking under event-triggered mechanism,” _IEEE Transactions on Circuits and Systems II: Express Briefs_ , vol. 68, no. 11, pp. 3441–3445, 2021\.
  * [22] W. Xu, S. Yang, S. Grammatico, and W. He, “An event-triggered distributed generalized Nash equilibrium seeking algorithm,” in _Proceedings of the 60th IEEE Conference on Decision and Control (CDC)_ , 2021, pp. 4301–4306.
  * [23] D. Han, Y. Mo, J. Wu, S. Weerakkody, B. Sinopoli, and L. Shi, “Stochastic event-triggered sensor schedule for remote state estimation,” _IEEE Transactions on Automatic Control_ , vol. 60, no. 10, pp. 2661–2675, 2015.
  * [24] K. F. E. Tsang, M. Huang, L. Shi, and K. H. Johansson, “Stochastic event-triggered algorithm for distributed convex optimisation,” _IEEE Transactions on Control of Network Systems_ , vol. 10, no. 3, pp. 1374–1386, 2023\.
  * [25] W. Huo, K. F. E. Tsang, Y. Yan, K. H. Johansson, and L. Shi, “Distributed Nash equilibrium seeking with stochastic event-triggered mechanism,” _Automatica_ , 2023.
  * [26] N. Singh, D. Data, J. George, and S. Diggavi, “SPARQ-SGD: Event-triggered and compressed communication in decentralized optimization,” _IEEE Transactions on Automatic Control_ , vol. 68, no. 2, pp. 721–736, 2022.
  * [27] X. Yi, S. Zhang, T. Yang, T. Chai, and K. H. Johansson, “Communication compression for distributed nonconvex optimization,” _IEEE Transactions on Automatic Control_ , 2022.
  * [28] A. Koloskova, S. Stich, and M. Jaggi, “Decentralized stochastic optimization and gossip algorithms with compressed communication,” in _Proceedings of the 22th International Conference on Machine Learning_. PMLR, 2019, pp. 3478–3487.
  * [29] M. Ye and G. Hu, “Distributed Nash equilibrium seeking by a consensus based approach,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 9, pp. 4811–4818, 2017.
  * [30] T. Tatarenko and A. Nedić, “Geometric convergence of distributed gradient play in games with unconstrained action sets,” _IFAC-PapersOnLine_ , vol. 53, no. 2, pp. 3367–3372, 2020.
  * [31] T. Tatarenko, W. Shi, and A. Nedić, “Geometric convergence of gradient play algorithms for distributed Nash equilibrium seeking,” _IEEE Transactions on Automatic Control_ , vol. 66, no. 11, pp. 5342–5353, 2020.
  * [32] G. Belgioioso and S. Grammatico, “A distributed proximal-point algorithm for Nash equilibrium seeking in generalized potential games with linearly coupled cost functions,” in _Proceedings of the 18th IEEE European Control Conference (ECC)_ , 2019, pp. 1–6.
  * [33] M. Ye, “Distributed robust seeking of Nash equilibrium for networked games: An extended state observer-based approach,” _IEEE Transactions on Cybernetics_ , vol. 52, no. 3, pp. 1527–1538, 2020.
  * [34] S. Sundhar Ram, A. Nedić, and V. V. Veeravalli, “Distributed stochastic subgradient projection algorithms for convex optimization,” _Journal of Optimization Theory and Applications_ , vol. 147, no. 3, pp. 516–545, 2010.
  * [35] N. Hayashi, T. Sugiura, Y. Kajiyama, and S. Takai, “Event-triggered consensus-based optimization algorithm for smooth and strongly convex cost functions,” in _Proceedings of the 57th IEEE Conference on Decision and Control (CDC)_ , 2018, pp. 2120–2125.
  * [36] R. A. Horn and C. R. Johnson, _Matrix analysis_. Cambridge University Press, 2012.