# Large Population Games on Constrained Unreliable Networks

Shubham Aggarwal, Muhammad Aneeq uz Zaman, Melih Bastopcu, Member, IEEE, and
Tamer Başar,
Life Fellow, IEEE Research of the authors was supported in part by the ARO
MURI Grant AG285 and in part by the AFOSR Grant FA9550-19-1-0353.The authors
are affiliated with the Coordinated Science Lab, University of Illinois at
Urbana-Champaign, Urbana, IL, USA 61801. Emails:
<EMAIL_ADDRESS>
###### Abstract

This paper studies an $N$–agent cost-coupled game where the agents are
connected via an _unreliable capacity constrained_ network. Each agent
receives state information over that network which loses packets with
probability $p$. A Base station (BS) actively schedules agent communications
over the network by minimizing a weighted Age of Information (WAoI) based cost
function under a capacity limit $\mathcal{C}<N$ on the number of transmission
attempts at each instant. Under a standard information structure, we show that
the problem can be decoupled into a _scheduling problem_ for the BS and a
_game problem_ for the $N$ agents. Since the scheduling problem is an NP hard
combinatorics problem, we propose an approximately optimal solution which
approaches the optimal solution as $N\rightarrow\infty$. In the process, we
also provide some insights on the case without channel erasure. Next, to solve
the large population game problem, we use the mean-field game framework to
compute an approximate decentralized Nash equilibrium. Finally, we validate
the theoretical results using a numerical example.

##  I Introduction

With the phenomenal expansion in data-traffic galvanized by the growing number
of connected devices, Internet-of-Things (IoT) finds applications in diverse
areas such as smart grids, autonomous vehicles, and monitoring systems [1, 2,
3], to name a few. A commonality among all of the above is the presence of
distributed sensing and actuating devices communicating via a wireless
network. While distributed systems can efficiently handle the growing network
size compared to their centralized counterparts, they come with added
challenges, such as limited channel capacities, network unreliability, and
scalability concerns. These constraints might cause end-to-end latency or in a
worse case, missing information at the end-user, which can lead to compromised
reliability in safety-critical applications. Thus, there is an urgent need for
the development of dependable and timeliness-aware communication technologies
with the potential to mitigate the above posed concerns. In this work, we aim
to propose strategies to mitigate the deleterious effects of unreliable
capacity-constrained communication in networks involving a large number of
decision-making agents.

Specifically, we consider a large population setting where $N$ rational agents
aim to form consensus while communicating intermittently over a network. This
intermittency is caused by i) a capacity-constrained downlink connecting the
BS to the decoders, and ii) the possibility of _erasure_ amidst transmission,
after information is relayed by the BS. This results in an unreliable
capacity-constrained network. As a result, the agents must maintain an
estimate of their state to consequently compute control actions that can
achieve consensus. Meanwhile, the BS, which is tasked with the scheduling of
information, must carefully design policies to account for the heterogeneity
in agent dynamics whilst also dealing with the possibility of erasure of the
scheduled information. We formulate the BS’s problem by proposing a Weighted
Age of Information (WAoI) based cost function which is monotonically
increasing in the average estimation error of the agents, thereby extending
the setting of our earlier work [4] to erasure channels. Further, we improve
upon the convergence guarantees in [4] for the case where the network is
erasure free by proposing a novel scheduling policy. Finally, we employ this
policy to construct an approximate Nash solution for the finite-agent
consensus problem.

In literature, the early works [5, 6] have dealt with an optimal control
problem with unreliable communication, albeit, for a single agent system and
an unconstrained network under the TCP and the UDP communication protocols.
The work [7] extends the setting to multi-agent games; however, the considered
network is unconstrained. In order to measure timeliness in communication
networks, age of information (AoI) has been introduced as a potential metric.
In the context of networked feedback systems, the AoI-based policies have been
proposed for solving resource allocation and end-user uncertainty reduction
problems as in [8]. Recently, age of incorrect information (AoII) is proposed
for solving multi-agent remote state estimation problems [9]. Age-optimal
scheduling policies have been considered with Markovian error-prone channel
state in [10, 11], with unknown erasure probabilities in [12], and over
erroneous broadcast channels in [13]. A more detailed literature review on
age-optimal scheduling policies can be found in [14].

To appropriately handle the concerns of increasing network interactions, one
of the most relevant framework is that of mean-field games (MFGs) [15, 16]. It
leads one to circumvent the issues posed by scalability, by allowing for a
representative agent to play against the population, although, at the cost of
entailing an approximate equilibrium solution to the finite-agent consensus
problem. It has been well-studied in the regime of linear-quadratic systems
[17, 18, 19] and holds great potential to solve problems involving ultradense
networks or massive machine-type communication [20, 21]. For additional
literature on large multi-agent systems with networked communication, we refer
the reader to [4].

We list below the main contributions of this paper. We extend the setting of
our previous works [22, 4] to the case of unreliable downlink communication.
Since the scheduling problem belongs to the class of restless multi-armed
bandits, for which an optimal policy is hard to compute, we propose a novel
suboptimal maximum age-based tie-breaking protocol (MATB-P) to solve the
capacity-constrained scheduling problem of the BS (which is also different
from the uniform sampling-based policy considered in [4]). We prove that this
policy approaches optimality (exponentially fast) as $N$ grows large, in
contrast to the $\mathcal{O}(N^{-0.5})$ rate proposed in [4]. Further, we also
provide high-probability guarantees on the tail of the AoI, which, in turn,
provides guarantees on the freshness of information under high traffic.
Additionally, in the special case with no channel erasure, we relax the
assumption on the $A$ matrix in the work [4] by proving a uniform upper bound
on the AoI of all agents under MATB-P. Finally, using the policy constructed
above, we solve the $N$–agent consensus problem by leveraging the MFG paradigm
and getting $\epsilon$–Nash policies for the agents where
$\epsilon\xrightarrow{N\rightarrow\infty}0$.

The rest of the paper is organized as follows. We formulate the $(N+1)$–player
game problem in Sec. II. In Sec.III, we solve the BS-level scheduling problem,
and provide its analysis in Sec. IV. Then, we solve the agent-level game
problem in Sec. V, and provide a numerical example in Sec. VI. The paper is
concluded in Sec. VII with some major highlights, followed by four appendices,
providing detailed derivations and proofs.

Notations: We let $[N]:=\\{1,2,\cdots,N\\}$ and $tr(\cdot)$ denote the trace
of its argument matrix. The Euclidean 2-norm and the Frobenius norm are
denoted by $\|\cdot\|$ and $\|\cdot\|_{F}$, respecively. All the empty
summations are set to 0. For a vector $x$ and a positive semi-definite matrix
$Q$, $\|x\|^{2}_{Q}:=x^{\top}Qx$. We define the limit superior of a real
sequence as $\overline{\lim}:=\limsup$. Finally, $\mathbf{1}_{A}$ denotes the
indicator function of the argument.

Figure 1: A prototypical networked control system constituting a BS and $N$
game playing agents. The BS, decoders, and controllers are active decision
makers. Dashed lines denote an erasure-free wireless transfer, dotted-dashed
lines denote erasure-prone one, and bold lines denote wired information
transfer.

##  II Problem Formulation

In this section, we set up the two sub-problems in the $(N+1)$–player game,
namely, a) the agent-level game problem, and b) the BS-level scheduling
problem.

Consider a multi-agent system consisting of $N$ cost-coupled agents receiving
information over an unreliable network. Each agent $i$ constitutes a plant, a
decoder and a controller, labeled as a tuple $(P_{i},D_{i},C_{i})$ as shown in
Fig. 1. Dynamics of $P_{i}$ evolve in discrete-time as

$\displaystyle
X^{i}_{k+1}=A(\phi_{i})X^{i}_{k}+B(\phi_{i})U^{i}_{k}+W^{i}_{k},~{}k\geq 0,$
(1)

where $X^{i}_{k}\in\mathbb{R}^{n}$ is the state and
$U^{i}_{k}\in\mathbb{R}^{m}$ is the control input, both for agent $i$. The
exogeneous noise $W^{i}_{k}\in\mathbb{R}^{n}$ is zero mean with covariance
$C_{W}(\theta_{i})>0$. The initial state $X^{i}_{0}$ of agent $i$ is assumed
to have symmetric density with mean $x_{\phi_{i},0}$ and covariance
$\Sigma_{x}>0$. Further, it is assumed to be independent of the noise process
for all timesteps $k$. The system matrices $A(\phi_{i}),$ $B(\phi_{i})$ are
time-invariant with suitable dimensions. Further, they are chosen according to
an empirical function $\mathbb{P}^{N}(\phi=\phi_{i}),$ where $\phi\in\Phi$
denotes the type of an agent chosen from a finite set
$\Phi:=\\{\phi_{1},\cdots,\phi_{p}\\}$. We assume that
$|\mathbb{P}^{N}(\phi)-\mathbb{P}(\phi)|=\mathcal{O}(1/N),$ $\forall\phi$,
where $\mathbb{P}(\phi)$ denotes the limiting distribution.

The state of plant $P_{i}$ is relayed to the decoder $D_{i}$ via an ideal
uplink to the BS, which then regulates agent communications over the downlink.
The downlink is constrained by a capacity limit of $\mathcal{C}<N$ units on
the number of transmissions and serves as a bottleneck from the plant to the
decoder. Further, it is unreliable in the sense that a packet communicated
over it may be lost according to a Bernoulli distributed signal
$\beta_{k}\sim\text{Ber}(p)$, with $p$ being the erasure probability. The
decoder receives the information signal:

$\displaystyle
z^{i}_{k}:=X^{i}_{k}\mathbf{1}_{E_{k}^{i}}+\emptyset\mathbf{1}_{(E_{k}^{i})^{c}},$
(2)

where the event $E^{i}_{k}$ denotes that state information is successfully
transmitted. Further, the event $\left(E^{i}_{k}\right)^{c}$ denotes no
transmission (or $\emptyset$), which can be either due to no transmission by
the BS or a packet drop over the channel. Let us denote the instants of
information reception by the decoder as $\wp^{i}_{k}:=\zeta^{i}_{k}\beta_{k}$.
Then, the information history of the decoder is defined as
$I^{D_{i}}_{k}:=\\{z^{i}_{0:k},\wp^{i}_{0:k},U^{i}_{0:k-1}\\}$, based on which
it computes the minimum mean-squared (MMS) estimate ($\mathbb{E}[X^{i}_{k}\mid
I^{D_{i}}_{k}]$) of the state $X^{i}_{k}$. We adopt the convention that
$z^{i}_{-1}=Z^{i}_{-1}=U^{i}_{-1}=0$, and $W^{i}_{-1}=X^{i}_{0}-Z^{i}_{0}$,
for all $i$.

Next, each controller $C_{i}$ receives the estimate from $D_{i}$ and aims to
minimize the average cost function

$\displaystyle
J_{i}(\pi_{c})\\!:=\\!\overline{\lim\limits_{T\rightarrow\infty}}\frac{1}{T}\mathbb{E}\left[\sum_{k=0}^{T-1}\\!\\!\|X^{i}_{k}\\!-\\!\mu^{N}_{k}\|_{Q(\phi_{i})}\\!+\\!\|U^{i}_{k}\|_{R(\phi_{i})}\right]\\!\\!,\\!$
(3)

where $Q(\phi_{i})\geq 0$, $R(\phi_{i})>0$, and
$\mu^{N}_{k}:=\frac{1}{N}\sum_{j=1}^{N}X^{j}_{k}$ represents the coupling
between agents. Due to this coupling, the cost $J_{i}$ depends on the strategy
$\pi_{c}:=\\{\pi^{1}_{c},\cdots,\pi^{N}_{c}\\}$ of the entire population. In
the sequel, we will denote the policy of the population excluding that of
agent $i$ as $\pi^{-i}_{c}$. Further,
$\pi^{i}_{c}\in\Pi_{i}:=\\{\pi^{i}_{c}\mid\pi^{i}_{c}\text{ is adapted to
}\sigma(I^{C_{i}}_{s},s=0,\cdots,k)\\}$, $\forall i$, where
$I^{C_{i}}_{k}:=\\{U^{j}_{0:k-1},Z^{j}_{0:k}\\}_{j\in[N]}$ denotes the
information history of $C_{i}$, and $\sigma(\cdot)$ denotes the sigma-algebra
generated by its argument. We assume that the pair $(A(\phi_{i}),B(\phi_{i}))$
is controllable and the pair $(A(\phi_{i}),\sqrt{Q(\phi_{i})})$ is observable
[23]. Due to the difficulty in computing Nash equilibrium for the game
(1)-(3), we will resort to the MFG framework (later in Section V) to compute
decentralized $\epsilon$-Nash policies where only local information will be
required for decision-making and $\epsilon\rightarrow 0$ as
$N\rightarrow\infty$. Next, we describe the BS-level problem, where the
objective is to compute an optimal scheduling policy of the BS.

The aim of the BS is to efficiently transmit information over the downlink. To
this end, consider the most recent timestep when information was received by
the $i^{th}$ controller, which is defined as $\ell^{i}_{k}:=\sup_{\ell\leq
k}\\{\ell\geq 0\mid z^{i}_{\ell}\neq\emptyset\\}$. Then, the AoI at the
controller, which is the time elapsed since the generation of the most recent
packet at the plant, is defined as $\tau^{i}_{k}:=k-\ell^{i}_{k}$. Further,
its evolution is given as
$\tau^{i}_{k+1}=(\tau^{i}_{k}+1)\mathbf{1}_{\\{\wp^{i}_{k}=0\\}}$, i.e., the
AoI drops to zero only when a transmission is attempted by the BS and the
packet is not dropped by the network. With the above AoI evolution, we
formally define the capacity-constrained scheduling problem at the BS as
follows:

######  Problem 1.

$\displaystyle\inf_{\gamma\in\Gamma}$ $\displaystyle
J^{BS}(\gamma):=\overline{\lim}_{T\rightarrow\infty}\frac{1}{T}\mathbb{E}\left[\frac{1}{N}\sum_{k=0}^{T-1}\sum_{i=1}^{N}w^{i}_{k}\tau^{i}_{k}\right]$
s.t. $\displaystyle~{}\sum_{i=1}^{N}{\zeta^{i}_{k}}\leq\mathcal{C},~{}\forall
k,$

where $\gamma:=\\{\gamma^{1},\cdots,\gamma^{N}\\}$ and
$\Gamma:=\\{\gamma\mid\gamma\text{ is adapted to}$
$\sigma(I^{BS}_{s}),s=0,\cdots,k\\}$ is the space of admissible scheduling
policies with
$I^{BS}_{k}:=\\{\tau^{i}_{0:k},\zeta^{i}_{0:k-1},\wp^{i}_{0:k-1}\\}_{i\in[N]}$
being the information history of the BS. Moreover,
$w^{i}_{k}:=\mathbb{E}[\|e^{i}_{k}\|^{2}]$ denote the importance weights
associated to each agent and are functions of the estimation error
$e^{i}_{k}:=X^{i}_{k}-Z^{i}_{k}$ at the controller. Finally, the expectation
is taken over the probabilistic scheduling due to the erasure-prone downlink
and (possible) randomization in the scheduling policy.

We note here that the information history of the BS includes the information
reception instants of the agent decoders. This can be easily facilitated by a
TCP-like protocol [5], where the decoder sends a one-bit ACK/NACK information
to acknowledge whether or not the transmitted information was received by it.
Further, Problem 1 involves a hard-limit on the number of transmissions, which
makes it a combinatorics problem. It belongs to the class of restless multi-
armed bandit problems, computing an optimal policy for which is quite
difficult. Thus, in the sequel, we first reformulate the problem using the
AoIs of each agent and then solve a relaxed problem involving a time-averaged
constraint. The solution to the latter problem will then lead to a sub-optimal
policy for Problem 1, which we will finally show to approach the optimal
policy as $N$ increases.

To this end, we start by defining the shorthands $A_{i}:=A(\phi_{i})$,
$B_{i}:=B(\phi_{i})$ and $C_{W^{i}}:=C_{W}(\phi_{i})$. Then, we construct the
decoder’s MMS estimate as

$\displaystyle
Z^{i}_{k}=X^{i}_{k}\mathbf{1}_{[\wp^{i}_{k}=1]}+\mathbb{E}[X^{i}_{k}\mid
I^{D_{i}}_{k}]\mathbf{1}_{[\wp^{i}_{k}=0]},$ (4)

which upon using (1), yields

$\displaystyle
Z^{i}_{k}=X^{i}_{k}\mathbf{1}_{[\wp^{i}_{k}=1]}\\!+\\!(A_{i}Z^{i}_{k-1}\\!+\\!B_{i}U^{i}_{k-1}\\!+\\!\mathbb{E}_{c}[W^{i}_{k-1}])\mathbf{1}_{[\wp^{i}_{k}=0]},$

where $\mathbb{E}_{c}[\cdot]:=\mathbb{E}[\cdot\mid\zeta^{i}_{k}=0]$. Then,
using similar arguments as in [4], we can show that the term
$\mathbb{E}_{c}[W^{i}_{k-1}]=0$ under the assumption of symmetric densities of
$X^{i}_{0}$ and $W^{i}_{0}$. Hence, the estimate at the decoder can be easily
computed as:

$\displaystyle
Z^{i}_{k}=X^{i}_{k}\mathbf{1}_{[\wp^{i}_{k}=1]}+(A_{i}Z^{i}_{k-1}+B_{i}U^{i}_{k-1})\mathbf{1}_{[\wp^{i}_{k}=0]}.$
(5)

With the above estimate, we can re-express the term $w^{i}_{k}$ in Problem 1
using Lemma 1 from [4] as:

$\displaystyle
w^{i}_{k}:=w^{i}_{k}(\tau^{i}_{k},A_{i},C_{W^{i}})=\sum_{\ell=1}^{\tau^{i}_{k}}tr\left({A^{\ell-1}_{i}}^{\top}A^{\ell-1}_{i}C_{W^{i}}\right).$
(6)

Now, let us define the running cost
$c(\tau^{i}_{k},A_{i},C_{W^{i}}):=w^{i}_{k}\tau^{i}_{k}$. Then, since the
capacity constraint in Problem 1 makes the optimal policy difficult to
compute, we relax the problem to one with an average constraint:

######  Problem 2.

$\displaystyle\inf_{\gamma\in\Gamma}$ $\displaystyle
J^{BS}(\gamma):=\overline{\lim}_{T\rightarrow\infty}\frac{1}{T}\mathbb{E}\left[\frac{1}{N}\sum_{k=0}^{T-1}\sum_{i=1}^{N}c(\tau^{i}_{k},A_{i},C_{W^{i}})\right]$
s.t.
$\displaystyle~{}\overline{\lim}_{T\rightarrow\infty}\frac{1}{T}\mathbb{E}\left[\sum_{k=0}^{T-1}\sum_{i=1}^{N}{\zeta^{i}_{k}}\right]\leq\mathcal{C}.$

We note that the constraint in the the above problem entails that more than
$\mathcal{C}$ agents can be connected over the downlink at any given timestep
as long as the capacity constraint is satisfied in the long run. This is
clearly a weaker constraint than the one in Problem 1 since the latter
requires the capacity constraint to be satisfied at all timesteps $k$. Hence,
it is indeed a relaxation of Problem 1. The objective now is to compute an
optimal solution to Problem 2 and then utilize the solution to come up with an
asymptotically optimal solution to Problem 1. To this end, we start by
constructing the Lagrangian of Problem 2 (with $\lambda\geq 0$ the Lagrange
multiplier):

$\displaystyle\mathscr{L}(\gamma,\lambda)\\!=\\!\overline{\lim\limits_{T\rightarrow\infty}}\frac{1}{T}\mathbb{E}\\!\\!\left[\frac{1}{N}\\!\\!\sum_{k=0}^{T-1}\sum_{i=1}^{N}c(\tau^{i}_{k},A_{i},C_{W^{i}})\\!\\!+\\!\lambda\\!\\!\left(\zeta^{i}_{k}\\!\\!-\\!\\!\frac{\mathcal{C}}{N}\right)\\!\\!\right]\\!\\!,$

where $\lambda$ can be thought of as a price on the downlink utilization.
Thus, given a fixed $\lambda$, we decouple the $N$–agent scheduling problem
into $N$ decoupled single-agent problems:

######  Problem 3.

For all $i\in[N]$,

$\displaystyle\inf_{\gamma^{i}\in\Gamma^{i}}V^{i}(\gamma):=\overline{\lim}_{T\rightarrow\infty}\frac{1}{T}\mathbb{E}\left[\sum_{k=0}^{T-1}c(\tau^{i}_{k},A_{i},C_{W^{i}})+\lambda\zeta^{i}_{k}\right].$

In the next section, we will first solve Problem 3, for which we will cast the
evolution of the AoI in an MDP framework and then construct a suboptimal
policy for Problem 1. Additionally, we will also suppress the superscript $i$.

##  III Solution to the BS-level Problem

We compute an optimal policy for Problem 3 by first defining it as a discrete-
time MDP
$\operatorname{M}:=(\operatorname{S},\operatorname{A},\operatorname{P},\operatorname{C})$.
The state space $\operatorname{S}$ is the space of non-negative integers. The
action set $\operatorname{A}=\\{0,1\\}$. An action $a=0$ denotes that a
transmission is not attempted while $a=1$ denotes that it is. The probability
transition function $\operatorname{P}$ describes the evolution of the AoI,
i.e., $\operatorname{P}(\tau_{k+1}=0\mid\tau_{k})=a_{k}(1-p)$ and
$\operatorname{P}(\tau_{k+1}=\tau_{k}+1\mid\tau_{k})=1-a_{k}+a_{k}p$. Finally,
with the per stage cost defined to be $C(\tau,a):=c(\cdot)+\lambda a$, the MDP
objective is to infimize the function
$V(\gamma):=\overline{\lim}_{T\rightarrow\infty}\frac{1}{T}\mathbb{E}\big{[}\sum_{k=0}^{T-1}\operatorname{C}(\tau_{k},a_{k})\big{]}$
for which we compute an optimal policy next.

###  III-A Solution to Problem 2

We start by stating the following theorem, which characterizes an optimal
policy solving Problem 3.

######  Theorem 1.

Given $\lambda\geq 0$, there exists a stationary policy $\gamma_{s}$ solving
the above MDP with an optimal cost of $\sigma^{*}$, which is independent of
$\tau$. Moreover, the optimal policy is given as
$a:=\mathbf{1}_{[\tau\geq\kappa]}$, for integer
$\kappa:=\kappa(A,C_{W},\lambda)$.

The proof follows in a similar manner as the proof of [4, Theorem 1]. The
theorem says that the optimal policy for Problem 3 is a threshold policy.
Next, we compute the threshold parameter $\kappa$ by invoking the following
condition, which links the erasure probability $p$ and the instability in the
agent’s dynamics.

######  Assumption 1.

We have that $\|A\|_{F}^{2}p<1$.

Notice that the above assumption is standard in the literature on unreliable
communication [5, 6, 7] and formalizes the fact that a higher erasure
probability restricts our ability to stabilize highly unstable agents. In the
extreme case when no communication is possible (i.e., $p=1$) it requires that
all agents must be stable. The detailed derivation for computing $\kappa$ is
provided in Appendix A. Now, with the deterministic single-agent policy as
provided above, we proceed toward constructing an optimal policy for Problem 2
which, as we will see, will be a randomized policy since the optimal policy
for such a constrained optimization problem may not, in general, lie in the
class of stationary deterministic policies [24]. Henceforth, we resume the use
of superscript $i$ to denote the $i^{th}$ agent.

We start by computing an optimal value of $\lambda$. To this end, consider the
threshold parameter $\kappa^{i}(\lambda):=\kappa^{i}(A_{i},C_{W^{i}},\lambda)$
as in Theorem 1. Then, the expected return time of agent $i$ starting from
$\tau^{i}_{k}=0$ can be found by
$\operatorname{R}^{i}_{0}=[\sum_{r=0}^{\infty}(\kappa^{i}+r+1)(1-p)^{r+1}p^{r}]^{-1}$
and is equal to:

$\displaystyle\operatorname{R}^{i}_{0}\\!=\\!\frac{((1-p)p-1)^{2}}{(1-p)((p-1)p(\kappa^{i}+1)\\!+\\!(1-p)p\\!+\\!\kappa^{i}\\!+\\!1)}.\\!$
(7)

Then, under the average constraint in Problem 2, we have
$R(\lambda):=\sum_{i=1}^{N}\operatorname{R}^{i}_{0}\leq\mathcal{C}$.
Consequently, we can use the iterative Bisection search algorithm, as given in
[4, 9], starting with the initial parameters $\underline{\lambda}^{(0)}=0$,
and $\overline{\lambda}^{(0)}=1$. The algorithm terminates when
$|\overline{\lambda}^{(m)}-\underline{\lambda}^{(m)}|\leq\epsilon$, for an
iterating index $m$ and a suitably chosen $\epsilon>0.$ Next, let us define
$\underline{\lambda}^{*}=\underline{\lambda}^{(m)}$ and
$\overline{\lambda}^{*}=\overline{\lambda}^{(m)}$ as obtained above, and the
corresponding deterministic policies as $\gamma^{i}_{s_{1}}$ and
$\gamma^{i}_{s_{2}}$, which are obtained from Theorem 1. More precisely, we
have that
$\underline{\lambda}^{*}\\!\\!\mapsto\\!\underline{\kappa}(\underline{\lambda}^{*})\\!\\!:=\\!\\!\\{\underline{\kappa}^{1}(\underline{\lambda}^{*}),\cdots,\underline{\kappa}^{N}(\underline{\lambda}^{*})\\}^{\top}\\!\\!$
and $\overline{\lambda}^{*}\\!\\!\mapsto\\!$
$\overline{\kappa}(\overline{\lambda}^{*}):=\\!\\{\overline{\kappa}^{1}(\overline{\lambda}^{*}),\cdots,\overline{\kappa}^{N}(\overline{\lambda}^{*})\\}^{\top}$.
Also, let $\overline{\mathcal{C}}$ and $\underline{\mathcal{C}}$ be the total
capacities used corresponding to the multipliers $\overline{\lambda}^{*}$ and
$\underline{\lambda}^{*}$, respectively. Then, we define the deterministic
policies:

$\displaystyle\gamma^{i}_{s_{1}}(\tau^{i}):=\mathbf{1}_{[\tau^{i}\geq\underline{\kappa}^{i}(\cdot,\cdot,\underline{\lambda}^{*})]},\hskip
4.26773pt\gamma^{i}_{s_{2}}(\tau^{i}):=\mathbf{1}_{[\tau^{i}\geq\overline{\kappa}^{i}(\cdot,\cdot,\overline{\lambda}^{*})]},$
(8)

for all $i$ using which we can construct a randomized policy
$\gamma_{R}:=[\gamma^{1}_{R},\cdots,\gamma^{N}_{R}]^{\top}$ for the relaxed
Problem 2 as:

$\displaystyle\gamma^{i}_{R}=q\gamma^{i}_{s_{1}}+(1-q)\gamma^{i}_{s_{2}},~{}\forall
i,$ (9)

where
$q:=(\mathcal{C}-\overline{\mathcal{C}})/(\underline{\mathcal{C}}-\overline{\mathcal{C}})$
is the probability of randomization. Next, in the following proposition, we
state that the randomized policy obtained is indeed optimal for Problem 2.

######  Proposition 1.

[4] Under Assumption 1, the policy (8)-(9) is optimal for the relaxed
minimization Problem 2.

With the solution to Problem 2, in the next subsection, we propose a novel
asymptotically optimal policy for Problem 1.

###  III-B Solution to Problem 1

In this subsection, we provide a sub-optimal solution to Problem 1, using the
solution to Problem 2, which is shown to be asymptotically optimal as
$N\rightarrow\infty$. We refer to this policy as the maximum-age-first tie-
breaking protocol (or MATB-P for short). Consider the solution
$\gamma^{i}_{R}$ to Problem 2 as computed in the previous subsection and let
$a^{i}_{k}=\gamma^{i}_{R}(I^{BS}_{k})$ be the scheduling action at timestep
$k$. Define $\Lambda_{k}:=\\{j\in[N]\mid a^{j}_{k}=1\\}$ as the set of agents
scheduled to be transmitted at instant $k$ and its cardinality to be
$n^{\lambda}_{k}$. Then, the scheduling decision $\zeta^{i}_{k}$ under MATB-P
($\gamma^{i}$) is given as:

  * •

If $n^{\lambda}_{k}\leq\mathcal{C}$, then $\zeta^{i}_{k}=a^{i}_{k}$

  * •

If $n^{\lambda}_{k}>\mathcal{C}$, then ${\zeta}^{i}_{k}=1$ for a subset
$\Lambda^{max}_{k}\subset\Lambda_{k}$ of the agents, where the cardinality of
$\Lambda^{max}_{k}$ is $\mathcal{C}$ for all $k$, and it constitutes the
agents with the maximum values of $\tau_{k}$. The agents in the set
$\Lambda_{k}\setminus\Lambda^{max}_{k}$ remain unselected.

In the next section, we provide a tail-bound analysis of the constructed MATB
policy, first, for the special case with no channel erasure, and then, for the
general case.

##  IV Tail-bound Analysis & $\varepsilon$-Optimality

In this section, we show that the costs under $\gamma_{R}$ and ${\gamma}$
approach each other as $N\rightarrow\infty$. To this end, we first prove
Proposition 2 for the case of an ideal downlink with $p=0$, where we show that
the maximum AoI is uniformly bounded independent of $N$, and then Theorem 3
for the general non-ideal downlink case, where we provide a high confidence
bound on the maximum AoI, again, independent of $N$. Then, we finally show
(using Theorems 2 and 4) that $\gamma$ approaches the optimal policy as
$N\rightarrow\infty$ in both cases.

To this end, consider the Markov chain induced by the relaxed policy
$\gamma^{i}_{R}$ for the $i^{th}$ agent as

$\displaystyle\tau^{i}_{k+1}\\!=\\!\left\\{\begin{array}[]{ll}\tau^{i}_{k}+1,\qquad\text{w.p.}~{}1,&\tau^{i}_{k}<\underline{\kappa}^{i}(\underline{\lambda}^{*}),\\\
\\!\\!\left\\{\begin{array}[]{ll}\tau^{i}_{k}+1,&\text{w.p.}~{}(1-q)p,\\\
{0},&\text{w.p.}~{}1-(1-q)p,\end{array}\right.\\!\\!&\\!\\!\tau^{i}_{k}\\!=\\!\underline{\kappa}^{i}(\underline{\lambda}^{*}),\\\
\\!\\!\left\\{\begin{array}[]{ll}\tau^{i}_{k}+1,&\text{w.p.}~{}p,\\\
{0},&\text{w.p.}~{}1-p,\end{array}\right.&\tau^{i}_{k}\geq\overline{\kappa}^{i}(\overline{\lambda}^{*}).\end{array}\right.$

Then, since each state in the set $\operatorname{S}$ is reachable from every
other state, the above Markov chain is irreducible, and hence admits a unique
stationary distribution $\pi^{i}$. Now, we provide the following proposition
which shows that the AoI under MATB-P for a deterministic channel (with $p=0$)
is uniformly bounded, independent of $N$.

######  Proposition 2.

Under a fixed $\alpha\\!=\\!\mathcal{C}/N$ and $p=0$, the AoI $\tau^{i}_{k}$
of any agent $i\in[N]$ under MATB-P is bounded by $\mathcal{O}(\alpha^{-1})$.

The proof can be found in Appendix B. As a result of the above proposition, we
next prove that MATB-P and the relaxed policy approach each other as
$N\rightarrow\infty$, which would then (as a result of (11)) imply that MATB-P
is asymptotically optimal for Problem 1. To this end, we define an auxiliary
policy $\hat{\gamma}$, under which the AoI sample paths are the same as those
under the relaxed policy $\gamma_{R}$, but for each additional agent that is
not supposed to be transmitted by MATB-P, it adds a penalty to the cost as:

$\displaystyle\omega(y,A,C_{W})=$ $\displaystyle
c(\bar{\Delta},A,C_{W})\times\mathbf{1}_{\\{(1-\frac{\mathcal{C}}{n^{\lambda}_{k}})>0\\}}\mathbf{1}_{\\{\tau\geq
y\\}}.$ (10)

Further, we let $\\{\tilde{\tau}^{i}_{k}\\}_{k=1}^{\infty}$ and
$\\{\tau^{i}_{k}\\}_{k=1}^{\infty}$ to be the sequences of AoIs of the
$i^{th}$ agent under MATB-P and $\gamma^{i}_{R}$ (or equivalently
$\hat{\gamma}^{i}$), respectively. Then, it is easy to see that
$\omega(\tilde{\tau}^{i}(t),A_{i},C_{W^{i}})$ dominates
$c(\tilde{\tau}^{i}(t),A_{i},C_{W^{i}})$, $\forall i,k$. As a consequence, it
follows that

$\displaystyle J^{BS}({\gamma_{R}})\leq J^{BS}({\gamma^{*}})\leq
J^{BS}({\gamma})\leq J^{BS}({\hat{\gamma}}),$ (11)

where $\gamma^{*}$ is any optimal policy that solves Problem 1. Then, we have
the following result.

######  Theorem 2.

Let $\alpha$ be fixed and suppose that Assumption 1 holds. Then, the
difference in the scheduling cost under MATB-P and $\gamma_{R}$ converges to 0
exponentially fast as a function of $N$. Consequently, as
$N\rightarrow\infty$, MATB-P becomes asymptotically optimal for Problem 1.

The proof of Theorem 2 is provided in Appendix C. Next, we provide a remark on
Proposition 2 and Theorem 2.

######  Remark 1.

As a consequence of Proposition 2, in the case of deterministic channel, no
assumptions are needed on the system parameters to prove the asymptotic
optimality of the MATB protocol. This is thus a significant relaxation of the
result given in [4], where an upper bound on $\|A(\theta)\|_{F}$ was required.
Second, we note that Theorem 2 proposes an exponential order of convergence of
MATB-P toward optimality as $N\rightarrow\infty$, which is sharper than the
$\mathcal{O}(1/\sqrt{N})$ convergence bound obtained in [4].

Next, we proceed to the general case with $p>0$. The following theorem shows
that under MATB-P, the AoI takes large values with arbitrarily small
probability.

######  Theorem 3.

Let $\alpha$ be fixed and $p>0$. Then, given $\delta\in(0,1)$, the upper
confidence bound on AoI $\tau^{i}_{k}=\mathcal{O}(\log(1/\delta)),$ $\forall
i$, $\forall k$ with probability at least $1-\delta$.

The proof of the theorem can be found in Appendix D. Further, it shows that
the AoI has a vanishing tail under MATB-P, which can be used to give high-
probability guarantees on the freshness of information under high traffic.
Next, to prove asymptotic optimality of MATB-P under the case with erasure-
prone channel, we again consider an auxiliary policy $\check{\gamma}$, which
transmits agents according to $\gamma_{R}$, except that, for each agent which
is not supposed to be transmitted by MATB-P, it adds an additional penalty to
the cost, which (by a slight abuse of notation) is defined as:

$\displaystyle\omega(y,A,C_{W})=$
$\displaystyle\sum_{\ell=1}^{\infty}p^{\ell}c(\tau+\ell,A,C_{W})\times\mathbf{1}_{\\{(1-\frac{\mathcal{C}}{n^{\lambda}_{k}})>0\\}}\mathbf{1}_{\\{\tau\geq
y\\}},$

such that $\omega(\tilde{\tau}^{i}_{k},A_{i},C_{W^{i}})$ dominates the
expected WAoI $c(\tilde{\tau}^{i}_{k},A_{i},C_{W^{i}})$, for all $i$, $k$.
Further, $\omega(y,A,C_{W})<\infty$ as a consequence of Assumption 1. Thus,
using similar arguments as for Theorem 2, we can prove the following main
result.

######  Theorem 4.

Let $\alpha$ be fixed and $0<p<1$. Then, MATB-P approaches the optimal policy
$\gamma^{*}$ for Problem 1 exponentially fast as the number of agents grows.

######  Remark 2.

We note here that in most literature such as [25, 8, 26], the authors rely on
truncating the AoI state space to a sufficiently large value and consequently
working with a finite space to derive the corresponding scheduling policies.
Here, however, we do not require any such truncation on the state space. This
is more natural since in communication systems with non-zero erasure
probability, the AoI can always exceed the truncation value, even if the
probability of the same tends to 0.

The solution to the original capacity-constrained problem is thus completely
characterized, and we next proceed to solving the finite-agent game problem.

##  V Solution to Agent-Level Game Problem

In this section, we solve the agent-level game problem by using the BS’s
scheduling policy as constructed in the previous section. Typically, networked
problems involve a large number of users, and thus, belong to the class of
large population games. Characterizing Nash equilibria based on a centralized
information structure introduced in Section II in such a setting is therefore
unrealistic. Thus, the objective here is to characterize decentralized Nash
policies for each agent. For that purpose, we first consider a limiting game
(or the MFG) with a countably infinite number of players. Then, we
characterize the equilibrium of the MFG (called the MFE) by utilizing the Nash
certainty equivalence principle [15]. As a result of the latter, each agent’s
effect on the aggregate behavior becomes negligible, which gives rise to the
notion of a representative agent solving a decentralized stochastic optimal
control problem using only local information, by playing against the aggregate
distribution. Consequently, we also show that the MFG solution provides an
approximate Nash solution for the finite-agent game.

###  V-A Decentralized Stochastic Optimal Tracking Problem

Consider a generic agent of type $\phi$ from the infinite population, whose
plant dynamics evolve as

$\displaystyle X_{k+1}=A(\phi_{i})X_{k}+B(\phi_{i})U_{k}+W_{k},~{}k\geq 0,$
(12)

where $X_{k}\in\mathbb{R}^{n}$ and $U_{k}\in\mathbb{R}^{m}$ denote the state
and control input of the generic agent, respectively. $W_{k}\in\mathbb{R}^{n}$
is an i.i.d zero mean Gaussian noise with positive definite covariance
$C_{W}(\phi)$. The initial state $X_{0}$ has symmetric density with mean
$x_{\phi,0}$ and covariance $\Sigma_{x}>0$. The decoder and the controller
information structures are same as in subsection II, except with the
superscript $i$ removed. The objective of the controller is to minimize the
function

$\displaystyle\\!\\!J(\xi,\mu)\\!:=\\!\overline{\lim\limits_{T\rightarrow\infty}}\frac{1}{T}\mathbb{E}\left[\sum_{k=0}^{T-1}\|X_{k}-\mu_{k}\|^{2}_{Q(\phi)}\\!+\\!\|U_{k}\|^{2}_{R(\phi)}\right]\\!\\!,\\!\\!$
(13)

where the policy $\xi\in\Xi$ is adapted to the decentralized information
structure
$I^{d,con}_{0}:=Z_{0},~{}I^{d,con}_{k}:=\\{U_{0:k-1},Z_{0:k}\\},\forall k\geq
1$ being the decentralized information structure of the generic agent. Note
that this is different from the centralized information structure, which
involves the information of all the other agents as well. Further,
$\mu=(\mu_{k})_{k\geq
0}\in\mathcal{M}:=\\{\mu_{k}\in\mathbb{R}^{n}\mid\|\mu\|_{\infty}:=\sup_{k\geq
0}\|\mu_{k}\|\leq\infty\\}$, also called the MF trajectory, denotes the
infinite agent approximation to the consensus term $(\mu^{N}_{k})_{k\geq 0}$
in (3). This term leads to decoupling between the otherwise cost-coupled
agents in the finite-agent game, and the resulting problem becomes a linear-
quadratic tracking (LQT) problem, for which the optimal policy is well known
(and is provided in Proposition 3).

Next, we introduce the operator $\Psi:\mathcal{M}\rightarrow\Xi$ which defines
the mapping $\mu\mapsto\xi$ and the operator
$\Theta:\Xi\rightarrow\mathcal{M}$, which defines the mapping $\xi\mapsto\mu$.
While the former generates an optimal policy given a MF trajectory $\mu$, the
latter computes a trajectory from a given control policy.

The MFE can then be defined as the pair $(\xi^{*},\mu^{*})$ such that
$\mu^{*}$ is the fixed point of the composite operator $\Theta\circ\Psi$,
i.e., $\mu^{*}=\Theta\circ\Psi(\mu^{*})$. Now, we state the following
proposition which characterizes the optimal control policy for the LQT problem
of the generic agent.

######  Proposition 3.

Suppose that the Assumption 1 holds and consider the dynamics (12) with cost
(13). Then, the following are true:

  1. 1.

The optimal control action of the generic agent is:

$\displaystyle U^{*}_{k}=-K_{1}(\phi)Z_{k}-K_{2}(\phi)g_{k+1}$ (14)

where
$K_{2}(\phi)=(R(\phi)+B(\phi)^{\top}K_{1}(\phi)B(\phi))^{-1}B(\phi)^{\top}$,
$K_{1}(\phi)=K_{2}(\phi)K(\phi)A(\phi)$, and $K(\phi)>0$ is the unique
solution to

$\displaystyle
K(\phi)\\!=\\!A(\phi)^{\top}\\![K(\phi)A(\phi)\\!-\\!K(\phi)^{\top}\\!B(\phi)K_{1}(\phi)]\\!+\\!Q(\phi).$

Further, the trajectory $g_{k}$ satisfies the backward dynamics
$g_{k}=A_{cl}(\phi)^{\top}g_{k+1}Q(\phi)\mu_{k}$, with the initial condition
$g_{0}=-\sum_{j=0}^{\infty}{(A_{cl}(\phi)^{j}})^{\top}$ $Q(\phi)\mu_{j}$ and
$A_{cl}(\phi)=A(\phi)-B(\phi)K_{1}(\phi)$ being Hurwitz. In addition, the
dynamics for $g_{k}$ has a unique solution in $\mathcal{M}$, which can be
given as
$g_{k}=-\sum_{j=k}^{\infty}{(A_{cl}(\phi)^{j-k})}^{\top}Q(\phi)\mu_{j}$.

  2. 2.

The optimal cost is bounded above as:

$\displaystyle
J(\xi,\mu^{*})\\!\leq\\!tr(K(\phi)C_{W}(\phi))\\!+\\!\overline{\lim\limits_{T\rightarrow\infty}}\frac{1}{T}\\!\sum_{k=0}^{T-1}\\!\\!\xi_{k}^{\top}\\!Q(\phi)\xi_{k}$
$\displaystyle-
g_{k+1}^{\top}B(\phi)K_{2}(\phi)g_{k+1}\\!+\\!\|A(\phi)^{\top}\\!\\!K(\phi)^{\top}\\!\\!B(\phi)K_{1}(\phi)\|$
$\displaystyle\times\left(\\!\sum_{m=1}^{\hat{\kappa}}\sum_{r=1}^{m}tr(A(\phi)^{{r-1}^{\top}}\\!\\!A(\phi)^{r-1}C_{W}(\phi))\\!\right.$
$\displaystyle\left.+\\!\frac{\|C_{W}(\phi)\|_{F}}{\|A(\phi)\|_{F}^{2}\\!-\\!1}\\!\times\\!\left[\frac{\|A(\phi)\|^{2\hat{\kappa}+2}_{F}p}{1-\|A(\phi)\|^{2}_{F}p}-\frac{p}{1-p}\right]\right).$
(15)

###### Proof.

The proof of 1) follows from [4]. For the proof of 2), we substitute (14) in
(13), to arrive at

$\displaystyle
J(\xi,\mu^{*})\\!\leq\\!tr(K(\phi)C_{W}(\phi))\\!+\\!\overline{\lim\limits_{T\rightarrow\infty}}\frac{1}{T}\\!\sum_{k=0}^{T-1}\\!\\!\xi_{k}^{\top}\\!Q(\phi)\xi_{k}$
$\displaystyle-g_{k+1}^{\top}B(\phi)K_{2}(\phi)g_{k+1}$
$\displaystyle+\overline{\lim\limits_{T\rightarrow\infty}}\frac{1}{T}\sum_{k=0}^{T-1}\\!\|A(\phi)^{\top}\\!\\!K(\phi)^{\top}\\!\\!B(\phi)K_{1}(\phi)\|\mathbb{E}\left[\|e_{k}\|^{2}\right].$
(16)

Consider the following:

$\displaystyle\mathbb{E}\left[\|e_{k}\|^{2}\right]\\!\\!=\\!\\!\sum_{m=1}^{\infty}\sum_{r=1}^{m}tr(A(\phi)^{{r-1}^{\top}}\\!\\!A(\phi)^{r-1}C_{W}(\phi))\mathbb{P}(\tau_{k}=m)$
$\displaystyle\leq\sum_{m=1}^{\hat{\kappa}}\\!\sum_{r=1}^{m}tr(A(\phi)^{{r-1}^{\top}}\\!\\!A(\phi)^{r-1}C_{W}(\phi))$
$\displaystyle+\\!\\!\sum_{m=\hat{\kappa}+1}^{\infty}\sum_{r=1}^{m}\\!tr(A(\phi)^{{r-1}^{\top}}\\!\\!A(\phi)^{r-1}C_{W}(\phi))p^{m-\tau_{u}}$
$\displaystyle\\!\\!\leq\\!\sum_{m=1}^{\hat{\kappa}}\sum_{r=1}^{m}tr(A(\phi)^{{r-1}^{\top}}\\!\\!A(\phi)^{r-1}C_{W}(\phi))\\!$
$\displaystyle+\\!\frac{\|C_{W}(\phi)\|_{F}}{\|A(\phi)\|_{F}^{2}\\!-\\!1}\\!\times\\!\left[\frac{\|A(\phi)\|^{2\hat{\kappa}+2}_{F}p}{1-\|A(\phi)\|^{2}_{F}p}-\frac{p}{1-p}\right],$
(17)

where $\hat{\kappa}:=\overline{\kappa}^{\phi}(\overline{\lambda}^{*})$ and the
last inequality follows using the scheduling policy of Section III-B,
Assumption 1, and the fact that $\|AB\|_{F}\leq\|A\|_{F}\|B\|_{F}$. Then,
combining (V-A) and (V-A), we arrive at (2). This completes the proof.∎

######  Remark 3.

We remark here that the boundedness of the cost in the special case of
deterministic channels is similarly implied by the uniform bound on the AoI
from Proposition 2. This reiterates the advantage of the MATB-P over the
uniformly randomized policy in [4], where an assumption on $\|A\|_{F}$ was
required to entail the boundedness of the cost.

###  V-B $\epsilon$–Nash Equilibrium

Now, that we have computed the optimal policy of the generic agent of type
$\phi$, we will henceforth prove the existence of a unique MFE. To this end,
we use the policy $\gamma$ from Section III-B to arrive at the closed-loop
system (CLS) in (5) under the policy (14) as

$\displaystyle Z_{k+1}$
$\displaystyle=(A_{cl}(\phi)Z_{k}-B(\phi)K_{2}(\phi)g_{k+1}+W_{k+1})\mathbf{1}_{[\wp_{k+1}=1]}$
$\displaystyle+(A_{cl}(\phi)Z_{k}-B(\phi)K_{2}(\phi)g_{k+1})\mathbf{1}_{[\wp_{k+1}=0]},$
(18)

which on taking expectation and using Proposition 3 yields

$\displaystyle\mu^{\phi}_{k}:=$
$\displaystyle\mathbb{E}[X_{k}]:=A_{cl}(\phi)^{k}x_{\phi,0}+\sum_{j=0}^{k-1}A_{cl}(\phi)^{k-j-1}B(\phi)K_{2}(\phi)$
$\displaystyle\hskip
28.45274pt\times\sum_{r=j+1}^{\infty}(A_{cl}(\phi)^{r-j-1})^{\top}Q(\phi)\mu_{r}.$
(19)

Define the MF operator as

$\displaystyle\\{\operatorname{M}_{\operatorname{F}}(\mu)\\}_{k}:=\sum_{\phi\in\Phi}\mu^{\phi}_{k}\mathbb{P}(\phi),k\geq
0.$ (20)

Also, we invoke the following assumption on model parameters.

######  Assumption 2.

$\|A_{cl}(\phi)\|+\sum_{\phi\in\Phi}\|Q(\phi)\|\|B(\phi)K_{2}(\phi)\|(1\\!-\\!\|A_{cl}(\phi)\|)^{-2}\mathbb{P}(\phi)<1$,
$\forall\phi\in\Phi$.

We next prove the following lemma and state the main theorem showing the
$\epsilon$–Nash property of the MFG solution.

######  Lemma 1.

Suppose that Assumptions 1-2 hold. Then, the following are true:

  1. 1.

(MFE Uniqueness): There exists a unique $\mu^{*}$ such that
$\mu^{*}=\operatorname{M}_{\operatorname{F}}(\mu^{*})$ with the property that
$\exists K_{3}^{*}\in\mathbb{K}:=\\{K_{3}\in\mathbb{R}^{n\times
n}\mid\|K_{3}\|<1,\mu^{*}_{k+1}=K_{3}\mu^{*}_{k}\\}$, and
$\mu^{*}_{0}=\sum_{\phi\in\Phi}x_{\phi,0}\mathbb{P}(\phi)$.

  2. 2.

(CLS stability): The CLS (1) under (14) is mean-squared stable, i.e.,
$\sup_{N\geq 1}\max_{1\leq j\leq N}$ $\overline{\lim}_{T\rightarrow\infty}$
$\frac{1}{T}\sum_{k=0}^{T-1}\mathbb{E}[\|\mu^{*}_{k}\|^{2}]<$ $\infty$.

  3. 3.

(MFE Approximation): We have that
$\mu^{N,*}_{k}\xrightarrow[\text{$N\rightarrow\infty$}]{\text{m.s.}}\mu^{*}_{k}$
at a rate of $\mathcal{O}(1/\min_{\phi}N_{\phi})$, where $N_{\phi}$ denotes
the cardinality of agents of type $\phi$, and $\mu^{N,*}_{k}$ is the empirical
state average under (14).

###### Proof.

The proof of parts 1) and 3) follow in a similar manner as Theorem 3 and
Proposition 6 in [4]. For part 2), consider the following, with the
superscript $*$ dropped for ease of notation. Substituting (14) in (12), we
arrive at the closed-loop system as

$\displaystyle X^{i}_{k+1}=$ $\displaystyle
A_{cl}(\phi_{i})X^{i}_{k}+B(\phi_{i})K_{1}(\phi_{i})e^{i}_{k}$
$\displaystyle-B(\phi_{i})K_{2}(\phi_{i})g^{i}_{k+1}+W^{i}_{k}.$ (21)

Then, from (V-B) we have that

$\displaystyle\mathbb{E}\left[\|X^{i}_{k}\|^{2}\right]\leq
4\mathbb{E}\left[\left\lVert
A_{cl}(\phi_{i})^{k}X^{i}_{0}\right\rVert^{2}\right]$
$\displaystyle+4\mathbb{E}\left[\left\lVert\sum_{r=0}^{k-1}A_{cl}(\phi_{i})^{k-r-1}B(\phi_{i})K_{1}(\phi_{i})e^{i}_{r}\right\rVert^{2}\right]$
$\displaystyle+4\mathbb{E}\left[\left\lVert\sum_{r=0}^{k-1}A_{cl}(\phi_{i})^{k-r-1}B(\phi_{i})K_{2}(\phi_{i})g^{i}_{r+1}\right\rVert^{2}\right]$
$\displaystyle+4\mathbb{E}\left[\left\lVert\sum_{r=0}^{k-1}A_{cl}(\phi_{i})^{k-r-1}W^{i}_{r}\right\rVert^{2}\right],$
(22)

where we used the fact that $\|\sum_{i=1}^{k}x_{i}\|^{2}\leq
k\sum_{i=1}^{k}\|x_{i}\|^{2}$. We note that since $A_{cl}(\phi)$ are Hurwitz
(as a result of proposition 3), using [27, Theorem 3.9], we can bound the
first term in (V-B) by
$\iota(\phi_{i})tr(\Sigma_{x}+x_{\phi_{i},0}x_{\phi_{i},0}^{\top})/(1-\varsigma(\phi_{i}))$,
and the fourth term in (V-B) by $\iota(\phi_{i})\sup_{1\leq j\leq
p}C_{W}(\phi_{i})/(1-\varsigma(\phi_{i}))$ for constants $\iota(\phi_{i})\geq
1$ and $0<\varsigma(\phi_{i})<1$. Similarly, using the fact that
$\|g^{i}\|_{\infty}<\infty$ (from Proposition 3), the third term in (V-B) can
be bounded by
$\frac{2\iota(\phi_{i})\|B(\phi_{i})K_{2}(\phi_{i})\|^{2}\|g^{i}\|_{\infty}^{2}}{(1-\sqrt{\varsigma(\phi_{i})})(1-\varsigma(\phi_{i}))}$.
Finally, using similar arguments as for the third term, we can show that the
second term (call it $T_{2}$) can be bounded as

$\displaystyle
T_{2}\leq\sum_{r=0}^{k-1}\iota(\phi_{i})\varsigma(\phi_{i})^{k-r-1}\|B(\phi_{i})K_{1}(\phi_{i})\|^{2}\mathbb{E}\left[\|e_{r}\|^{2}\right]$
$\displaystyle+\\!\\!\\!\sum_{\begin{subarray}{c}r,s=0,\\\ r\neq
s\end{subarray}}^{k-1}\\!\\!\\!\iota(\phi_{i})\varsigma(\phi_{i})^{k\\!-\frac{r}{2}\\!-\\!1\\!-\frac{s}{2}}\|B(\phi_{i})K_{1}(\phi_{i})\|^{2}\\!\\!\sqrt{\\!\mathbb{E}\left[\|e_{r}\|^{2}\right]\\!\mathbb{E}\left[\|e_{s}\|^{2}\right]}$
$\displaystyle\leq\beta(\phi_{i})\iota(\phi_{i})\|B(\phi_{i})K_{1}(\phi_{i})\|^{2}\\!\left[\\!\frac{1}{1-\varsigma(\phi_{i})}\\!+\\!\frac{1}{(1\\!-\\!\sqrt{\varsigma(\phi_{i})})^{2}}\right]\\!\\!,$

where
$\beta(\phi_{i})\\!=\\!\\!\sum_{m=1}^{\bar{\kappa}}\\!\sum_{r=1}^{m}tr(A(\phi_{i})^{{r-1}^{\top}}\\!\\!A(\phi_{i})^{r-1}C_{W}(\phi_{i}))\\!+\\!\frac{\|C_{W}(\phi_{i})\|_{F}}{\|A(\phi_{i})\|_{F}^{2}\\!-\\!1}\\!\times\\![\frac{\|A(\phi_{i})\|^{2\bar{\kappa}^{\phi_{i}}+2}_{F}p}{1-\|A(\phi_{i})\|^{2}_{F}p}\\!-\\!\frac{p}{1-p}]$.
Finally, summing up all the bounds and noting that $\Phi$ is a finite set, we
have the desired result. The proof is thus complete. ∎

We next state the following definition below.

######  Definition 1 (Approximate Nash equilibrium).

Given $\epsilon>0$, the set of control policies $\\{\xi^{j}\\}_{j\in[N]}$
constitutes an $\epsilon$–Nash equilibrium for the cost functions
$\\{J_{j}\\}_{i\in[N]}$, if

$\displaystyle
J_{i}(\xi^{*,i},\xi^{*,-i})\leq\inf_{\pi_{c}^{i}\in\Pi_{i}}J_{i}(\pi_{c}^{i},\mu^{*,-i})+\epsilon,~{}~{}\forall
i\in[N].$ (23)

Then, we present the main result of this section stating that the MFE control
laws constitute an $\epsilon$-Nash equilibrium for the finite-population case.

######  Theorem 5.

Suppose that Assumptions 1-2 hold. Then the sequence of decentralized control
policies $\\{\xi^{j}\\}_{j\in[N]}$, constitutes an $\epsilon$–Nash equilibrium
for the $N$–agent capacity-constrained LQ-mean field game. In particular, we
have that

$\displaystyle\\!\\!J_{i}(\xi^{*,i}\\!,\\!\xi^{*,-i})\\!\leq\\!\inf_{\pi_{c}^{i}\in\Pi_{i}}\\!\\!J_{i}(\pi_{c}^{i},\mu^{*,-i})\\!+\\!\mathcal{O}\\!\\!\left(\\!\frac{1}{\sqrt{\min_{\phi\in\Phi}\\!N_{\phi}\\!}}\\!\right)\\!.\\!\\!$
(24)

###### Proof.

The proof follows from Lemma 1 using techniques similar to those in [18, 7],
and hence is omitted. ∎

##  VI An Illustrative Example

In this section, we validate the theoretical results using a numerical
example. We first demonstrate the asymptotic optimality of MATB-P. For this
purpose, we consider values for $N$ from 5 till 100, a time horizon of 5000
seconds, a low capacity $\mathcal{C}=0.25N$, and an erasure probability
$p=0.2$. We plot the average weighted AoI of the system as a function of $N$
in Fig. 2, for both the relaxed policy and MATB-P. We can see that the
difference in the average cost under the above decays to 0, which shows the
asymptotic optimality of the MATB policy.

Figure 2: Plot shows the performance of the relaxed policy ($\gamma_{R}$) and
the MATB policy, converging to each other.

Next, we simulate the behavior of a $900$–agent system, with 3 types of
(scalar) agents, namely, with $A=0.5,1.0,1.15$, under the MATB scheduling
protocol and the MFE policy $\xi^{*}$. We take $B=0.1269,C_{W}=5$, $Q=R=2$,
and a horizon of 500 seconds. In Fig. 3, in the left plot, we show the
variation of the average cost per agent as a function of the available
capacity for a fixed erasure probability $p=0.2$. Next, in the right, we show
the variation of the average cost per agent as a function of the channel
erasure for a fixed capacity ratio $\alpha=0.45$. The figures show a box plot
depicting the median (red line) and spread (box) of the average cost per agent
over 100 runs for each value of $\alpha$, and $p$, respectively. We can easily
see that the average cost varies inversely with the available downlink
capacity and in direct proportion to the erasure probability, aligned with
intuition.

Figure 3: Plots show the variation of aggregate cost per agent with (a)
capacity ratio $\alpha$, and (b) erasure probability $p$.

##  VII Conclusion

In this paper, we have formulated a large population game problem involving
information transmission over unreliable networks, thereby extending the
setting of [4] and improving the guarantees in the special case of [4]. The
network is regulated by a BS, for which we have constructed an asymptotically
optimal scheduling policy. We have provided a tail analysis of the AoI under
the same, first, for the case when the channel is free of any erasure and then
for the case with erasure. Next, by using this policy, we have solved the
consensus problem between the non-cooperative agents using the MFG framework
by proving the existence of a unique equilibrium and consequently showing its
$\epsilon$–Nash property to the finite-agent game problem. Finally, we have
simulated a numerical example, which corroborates the theoretical
developments.

## References

  * [1] A. Nanda, D. Puthal, J. J. Rodrigues, and S. A. Kozlov, “Internet of autonomous vehicles communications security: overview, issues, and directions,” _IEEE Wireless Comm._ , vol. 26, no. 4, pp. 60–65, 2019.
  * [2] M. Rana, L. Li, and S. W. Su, “Distributed state estimation over unreliable communication networks with an application to smart grids,” _IEEE Transactions on Green Communications and Networking_ , vol. 1, no. 1, pp. 89–96, 2017.
  * [3] A. Osseiran, J. F. Monserrat, and P. Marsch, _5G mobile and wireless communications technology_. Cambridge University Press, 2016.
  * [4] S. Aggarwal, M. A. uz Zaman, M. Bastopcu, and T. Başar, “Weighted age of information based scheduling for large population games on networks,” _Submitted to IEEE Jrnl. on Selec. Areas in Info. Theory. Available on arXiv:2209.12888._ , September 2022.
  * [5] O. C. Imer, S. Yüksel, and T. Başar, “Optimal control of LTI systems over unreliable communication links,” _Automatica_ , vol. 42, no. 9, pp. 1429–1439, 2006.
  * [6] L. Schenato, B. Sinopoli, M. Franceschetti, K. Poolla, and S. S. Sastry, “Foundations of control and estimation over lossy networks,” _Proceedings of the IEEE_ , vol. 95, no. 1, pp. 163–187, 2007.
  * [7] J. Moon and T. Başar, “Discrete-time LQG mean field games with unreliable communication,” in _IEEE CDC_ , Dec. 2014, pp. 2697–2702.
  * [8] O. Ayan, M. Vilgelm, and W. Kellerer, “Optimal scheduling for discounted age penalty minimization in multi-loop networked control,” in _IEEE CCNC_ , January 2020, pp. 1–7.
  * [9] A. Maatouk, S. Kriouile, M. Assaad, and A. Ephremides, “The age of incorrect information: A new performance metric for status updates,” _IEEE/ACM Trans. on Networking_ , vol. 28, no. 5, pp. 2215–2228, 2020.
  * [10] Y. Chen, H. Tang, J. Wang, and J. Song, “Optimizing age penalty in time-varying networks with Markovian and error-prone channel state,” _Entropy_ , vol. 23, no. 1, p. 91, January 2021.
  * [11] B. Sombabu, B. Dedhia, and S. Moharir, “Whittle index based age-of-information aware scheduling for Markovian channels,” _Computer Networks and Comm._ , vol. 1, no. 1, pp. 59–84, December 2022.
  * [12] S. Wu, X. Ren, Q.-S. Jia, K. H. Johansson, and L. Shi, “Towards efficient dynamic uplink scheduling over multiple unknown channels,” _arXiv:2212.06633_ , December 2022.
  * [13] I. Kadota, A. Sinha, E. Uysal-Biyikoglu, R. Singh, and E. Modiano, “Scheduling policies for minimizing age of information in broadcast wireless networks,” _IEEE/ACM Transactions on Networking_ , vol. 26, no. 6, pp. 2637–2650, December 2018.
  * [14] R. D. Yates, Y. Sun, D. R. Brown, S. K. Kaul, E. Modiano, and S. Ulukus, “Age of information: An introduction and survey,” _IEEE Jrnl. on Selec. Areas in Comm._ , vol. 39, no. 5, pp. 1183–1210, 2021.
  * [15] M. Huang, P. E. Caines, and R. P. Malhamé, “Large-population cost-coupled LQG problems with nonuniform agents: individual-mass behavior and decentralized $\varepsilon$-Nash equilibria,” _IEEE Transactions on Automatic Control_ , vol. 52, no. 9, pp. 1560–1571, 2007.
  * [16] J.-M. Lasry and P.-L. Lions, “Mean field games,” _Japanese Journal of Mathematics_ , vol. 2, no. 1, pp. 229–260, 2007.
  * [17] M. A. u. Zaman, E. Miehling, and T. Başar, “Reinforcement learning for non-stationary discrete-time linear–quadratic mean-field games in multiple populations,” _Dynamic Games and Apps._ , vol. 13, pp. 118–164, 2023.
  * [18] S. Aggarwal, M. A. uz Zaman, and T. Başar, “Linear quadratic mean-field games with communication constraints,” in _IEEE ACC_ , June 2022, pp. 1323–1329.
  * [19] A. Bensoussan, K. Sung, S. C. P. Yam, and S.-P. Yung, “Linear-quadratic mean field games,” _Journal of Optimization Theory and Applications_ , vol. 169, no. 2, pp. 496–529, 2016.
  * [20] H. Zhang, Y. Kang, L. Song, Z. Han, and H. V. Poor, “Age of information minimization for grant-free non-orthogonal massive access using mean-field games,” _IEEE Transactions on Communications_ , vol. 69, no. 11, pp. 7806–7820, 2021.
  * [21] M. Bennis, M. Debbah, and H. V. Poor, “Ultrareliable and low-latency wireless communication: Tail, risk, and scale,” _Proceedings of the IEEE_ , vol. 106, no. 10, pp. 1834–1853, 2018.
  * [22] S. Aggarwal, M. A. uz Zaman, M. Bastopcu, and T. Başar, “Large population games with timely scheduling over constrained networks,” in _IEEE ACC (to appear)_ , May-June 2023.
  * [23] F. L. Lewis, D. Vrabie, and V. L. Syrmos, _Optimal Control_. John Wiley & Sons, 2012.
  * [24] E. Altman, _Constrained Markov Decision Processes: Stochastic Modeling_. Routledge, 1999.
  * [25] O. Ayan, M. Vilgelm, M. Klügel, S. Hirche, and W. Kellerer, “Age-of-information vs. value-of-information scheduling for cellular networked control systems,” in _ACM/IEEE ICCPS_ , April 2019, pp. 109–117.
  * [26] M. Hatami, M. Leinonen, Z. Chen, N. Pappas, and M. Codreanu, “On-demand AoI minimization in resource-constrained cache-enabled IoT networks with energy harvesting sensors,” _arXiv:2201.12277_ , 2022.
  * [27] O. L. V. Costa, M. D. Fragoso, and R. P. Marques, _Discrete-time Markov Jump Linear Systems_. Springer Sci. & Business Media, 2006.
  * [28] I. Shevtsova, “On the absolute constants in the berry-esseen type inequalities for identically distributed summands,” _arXiv:1111.6554_ , November 2011\.

##  Appendix A Computation of $\kappa$

Consider the finite state-space
$\operatorname{S}^{\prime}=\\{0,1,\cdots,\kappa\\}$. Then, the Bellman
equation for Problem 3 can be written as

$\displaystyle V(\tau)+\sigma^{*}$
$\displaystyle=\min\\{\operatorname{C}(\tau,0)+V(\tau+1),\operatorname{C}(\tau,1)$
$\displaystyle+pV(\tau+1)+(1-p)V(0)\\}.$ (25)

Then, by using (A), for $\tau\geq\kappa$, we have that

$\displaystyle V(\tau)=c(\tau)+\lambda+pV(\tau+1)+(1-p)V(0)-\sigma^{*}$
$\displaystyle\\!=\\!\sum_{r=0}^{n-1}(c(\tau+r)\\!+\\!\lambda+(1-p)V(0)\\!-\\!\sigma^{*})p^{r}\\!+\\!p^{n}V(\tau+n).$

Taking the limit as $n\rightarrow\infty$, we get

$\displaystyle\\!V(\tau)\\!=\\!\frac{\lambda\\!+\\!(1\\!-\\!p)V(0)\\!-\\!\sigma^{*}}{1\\!-\\!p}\\!+\\!\underbrace{\lim_{n\rightarrow\infty}\sum_{r=0}^{n-1}c(\tau+r)p^{r}}_{f(\tau)},$
(26)

where we define $c(x):=c(x,A,C_{W})=\sum_{r=1}^{x}tr((A^{r-1})^{\top}$
$A^{r-1}C_{W})x=\\!\sum_{r=1}^{x}tr\\!\left(\\!\left(A^{r-1}\\!xC_{W}^{0.5}\right)^{\top}\\!\\!\\!A^{r-1}\\!C_{W}^{0.5}\right)\\!x\\!=\\!\sum_{r=1}^{x}\|A^{r-1}C_{W}^{0.5}\|_{F}^{2}x$.

Next, in order to give a closed-form equation to compute $\kappa$, we consider
a scalar system (with $n=1$ in (1)) for the computation of the function
$f(\cdot)$, which can be given as

$\displaystyle
f(x)\\!\\!=\\!\\!\begin{cases}\\!\frac{C_{W}}{1-A^{2}}\\!\left[x(\frac{1}{1-p}\\!-\\!\frac{A^{2x}}{1-A^{2}p})\\!+\\!\frac{p}{(1-p^{2})}\\!-\\!\frac{A^{2x+2}p}{(1-A^{2}p)^{2}}\right]\\!\\!,&\\!\\!\\!\\!\\!A\neq
1,\\\
\\!\frac{C_{W}x^{2}}{1-p}+\frac{2C_{W}xp}{(1-p)^{2}}+\frac{C_{W}p(1+p)}{(1-p)^{3}},&\\!\\!\\!\\!\\!A=1.\end{cases}$
(27)

We note that the calculation of $f(\cdot)$ involves an infinite sum which is
finite under Assumption 1. Further, we observe that
$V(\kappa)\leq\lambda/(1-p)+V(0)\leq V(\kappa+1)$. Hence, there exists
$\eta\in[0,1]$ such that $V(\kappa+\eta)=\lambda/(1-p)+V(0)$. Combining this
with (26), we get that $\sigma^{*}=(1-p)f(\kappa+\eta)$. Next, for
$\tau<\kappa$, we have from (A) that $V(\tau)+\sigma^{*}=V(\tau+1)+c(\tau)$.
Combining this with (26), evaluated at $\tau=\kappa$, we arrive at

$\displaystyle(1+\kappa(1-p))f(\kappa+\eta)=\frac{\lambda}{(1-p)}\\!+\\!f(\kappa)\\!+\\!\sum_{i=1}^{\kappa-1}c(i).$
(28)

The above is an implicit equation in $\kappa$ and $\eta$, for a given tuple
$(A,C_{W},p,\lambda)$, and can be solved in conjunction with (28) to compute
$\kappa$.

##  Appendix B Proof of Proposition 2

Let us start by defining the sets $\bar{S}_{k}$ and $S^{\gamma}_{k}$ for
$k\geq 0$:

$\displaystyle\bar{S}_{k}$
$\displaystyle:=\\{i\in[N]|\tau^{i}_{k}>\bar{\kappa}:=\max(\max_{\phi\in\Phi}\overline{\kappa}^{\phi}(\bar{\lambda}^{*}),\lceil\alpha^{-1}\rceil)\\},$
$\displaystyle S^{\gamma}_{k}$
$\displaystyle:=\\{i\in[N]|\zeta^{i}_{k}=1,t_{0}\leq k\leq
t_{0}+\lceil\alpha^{-1}\rceil,t_{0}\geq 0\\}.$

The set $\bar{S}_{k}$ is the set of agents whose AoIs exceed $\bar{\kappa}$,
and hence the subset of agents which are supposed to be scheduled for
transmission. The set $S^{\gamma}_{k}$ is the subset of agents which are
scheduled at time $k$ using MATB-P. Let us also define the quantity
$\tau_{\max,k}$ as:

$\displaystyle\tau_{\max,k}:=\left\\{\begin{array}[]{cc}\max\\{\tau^{i}_{k}|i\in\bar{S}_{k}\\},&\text{if
}|\bar{S}_{k}|>0,\\\ \bar{\kappa},&\text{if
}|\bar{S}_{k}|=0.\end{array}\right.$

This quantity is the upper bound on $\tau^{i}_{k}$ by definition. Now, we
first investigate some properties of the sets $\bar{S}_{k}$ and
$S^{\gamma}_{k}$. By definition, it holds that $|\bar{S}_{0}|=0$. Define
$t_{0}$ as the first timestep when the cardinality of $\bar{S}_{k}$ exceeds
$\mathcal{C}$, i.e.,

$\displaystyle t_{0}:=\min_{k\geq
0}\\{k\mid\lvert\bar{S}_{k}\rvert>\mathcal{C}\\}$

If $t_{0}=\infty$, then $\tau^{i}_{k}$ can be trivially bounded by
$\bar{\kappa}$. Hence, we assume $t_{0}<\infty$. Let $m\geq 0$ be the
timesteps it takes for the cardinality of $\bar{S}_{k}$ to drop below
$\mathcal{C}+1$. More formally, we have that

$\displaystyle|\bar{S}_{k}|>\mathcal{C},t_{0}\leq k\leq t_{0}+m\text{ and
}|\bar{S}_{t_{0}+m+1}|\leq\mathcal{C}.$

First, we notice that for any $k$ such that $t_{0}\leq k\leq t_{0}+m$,

$\displaystyle S^{\gamma}_{k}\subset\bar{S}_{k}.$ (29)

This is due to the fact that for $k\in[t_{0},t_{0}+m]$, we have that
$|\bar{S}_{k}|>\mathcal{C}$, and thus, the number of agents to be scheduled is
larger than $\mathcal{C}$. As a result, the scheduling policy breaks the tie
using MATB-P and since the agents with the highest AoIs reside in
$\bar{S}_{k}$ for $t_{0}\leq k\leq t_{0}+m$, they will be scheduled. This also
means that

$\displaystyle|S^{\gamma^{d}}_{k}|=\mathcal{C},\text{ and }t_{0}\leq k\leq
t_{0}+m.$ (30)

Next, we notice that if an agent with index $i\in\bar{S}_{k}\cap
S^{\gamma}_{k}$ for $t_{0}\leq k\leq t_{0}+m$, then

$\displaystyle i$ $\displaystyle\notin\bar{S}_{k^{\prime}},k<k^{\prime}\leq
t_{0}+\min(m,\lceil\alpha^{-1}\rceil).$ (31)

This is due to the fact that if $i\in S^{\gamma}_{k}$ for any $i\in[N]$ and
$k\geq 0$, then $\tau^{i}(k^{\prime})\leq\lceil\alpha^{-1}\rceil$ for
$k<k^{\prime}\leq k+\lceil\alpha^{-1}\rceil$, and thus,
$i\notin\bar{S}_{k^{\prime}}$, for $k<k^{\prime}\leq
k+\lceil\alpha^{-1}\rceil$. Further, (31) follows since
$t_{0}+\min(m,\lceil\alpha^{-1}\rceil)\leq k+\lceil\alpha^{-1}\rceil$.
Combining (29) and (31), we can deduce that if $i\in S^{\gamma}_{k},t_{0}\leq
k\leq t_{0}+\min(m,\lceil\alpha^{-1}\rceil)$, then $i\notin
S^{\gamma}(k^{\prime}),k<k^{\prime}\leq
t_{0}+\min(m,\lceil\alpha^{-1}\rceil)$. This means that if an agent is
scheduled in the interval $[t_{0},t_{0}+\min(m,\lceil\alpha^{-1}\rceil)]$,
then it will not be scheduled again in this interval. Hence,

$\displaystyle\\!\\!\\!S^{\gamma}_{k}\cap
S^{\gamma}_{k^{\prime}}\\!=\\!\varnothing,k,k^{\prime}\\!\in\\![t_{0},t_{0}+\min(m,\lceil\alpha^{-1}\rceil)],k\neq
k^{\prime}.\\!\\!\\!$ (32)

Using this result, we will prove that the cardinality of the set $\bar{S}_{k}$
cannot be higher than $\mathcal{C}$ for more than $\lceil\alpha^{-1}\rceil$
timesteps. Let us assume by contradiction that $m>\lceil\alpha^{-1}\rceil$.
Using (30) and (32) for $T\in[0,\lceil\alpha^{-1}\rceil]$, we get:

$\displaystyle\Bigg{\lvert}\bigcup_{k=t_{0}}^{t_{0}+T}S^{\gamma}_{k}\Bigg{\rvert}=\sum_{k=t_{0}}^{t_{0}+T}\lvert
S^{\gamma}_{k}\rvert=(T+1)\mathcal{C},$

Fixing $T=\lceil\alpha^{-1}\rceil$, we obtain

$\displaystyle\Bigg{\lvert}\bigcup_{k=t_{0}}^{t_{0}+\lceil
k\rceil}S^{\gamma}(t)\Bigg{\rvert}=(\lceil\alpha^{-1}\rceil+1)\mathcal{C}\geq
N+\mathcal{C}>N.$

Now, since the union takes care of duplications and the total number of agents
in the game is $N$ for $T^{\prime}\geq 0$,

$\displaystyle\Bigg{\lvert}\bigcup_{k=t_{0}}^{t_{0}+T^{\prime}}S^{\gamma}_{k}\Bigg{\rvert}\leq
N,$

which leads to a contradiction. Thus, our assumption of
$m>\lceil\alpha^{-1}\rceil$ was incorrect to begin with, and we have finally
proved that $m\leq\lceil\alpha^{-1}\rceil$.

Next, we prove that $\tau_{\max,k}=\mathcal{O}(\lceil\alpha^{-1}\rceil)$. For
$k\notin[t_{0},t_{0}+m]$, it is easy to see that
$\tau_{\max,k+1}\leq\bar{\kappa}$. Moreover, for $k\in[t_{0},t_{0}+m]$,
$\tau_{\max,k+1}\leq\tau_{\max,k}+1$. Now, since
$m\leq\lceil\alpha^{-1}\rceil\leq\bar{\kappa}$, $\tau_{\max,k}\leq
2\bar{\kappa}$ for any $k\geq 0$. Hence, the statement of the theorem follows,
which completes the proof.

##  Appendix C Proof of Theorem 2

Consider the following.

$\displaystyle
J^{BS}_{\hat{\gamma}}-J^{BS}_{\gamma_{R}}\\!=\\!\overline{\lim\limits_{T\rightarrow\infty}}\frac{1}{NT}\mathbb{E}\\!\\!\left[\sum_{k=0}^{T-1}\sum_{i=1}^{N}c(\bar{\Delta},A_{i},C_{W^{i}})\right.$
$\displaystyle\left.\times\mathbf{1}_{\left\\{1\geq{\mathcal{C}}/{n^{\lambda}_{k}}\right\\}}\mathbf{1}_{\left\\{\tilde{\tau}^{i}_{k}\geq\kappa^{i}\right\\}}\right]$
$\displaystyle\leq\overline{\lim\limits_{T\rightarrow\infty}}\frac{\operatorname{U}}{NT}\mathbb{E}\left[\sum_{k=0}^{T-1}\sum_{i=1}^{N}\mathbf{1}_{\left\\{{n^{\lambda}_{k}}>{\mathcal{C}}\right\\}}\mathbf{1}_{\left\\{\tilde{\tau}^{i}_{k}\geq\kappa^{i}\right\\}}\right]$
$\displaystyle\leq\overline{\lim\limits_{T\rightarrow\infty}}\frac{\operatorname{U}}{T}\sum_{k=0}^{T-1}\mathbb{E}\left[\mathbf{1}_{\left\\{{n^{\lambda}_{k}}>{\mathcal{C}}\right\\}}\right]$
$\displaystyle=\overline{\lim\limits_{T\rightarrow\infty}}\frac{\operatorname{U}}{T}\sum_{k=0}^{T-1}\mathbb{P}(n^{\lambda}_{k}>\mathcal{C})$
$\displaystyle\leq\overline{\lim\limits_{T\rightarrow\infty}}\frac{\operatorname{U}}{T}\sum_{k=0}^{T-1}\mathbb{P}(e^{\theta
n^{\lambda}_{k}}\geq e^{\theta\mathcal{C}}),~{}\theta>0$
$\displaystyle\leq\overline{\lim\limits_{T\rightarrow\infty}}\frac{\operatorname{U}}{T}\sum_{k=0}^{T-1}\inf_{\theta>0}\frac{\mathbb{E}[e^{\theta
n^{\lambda}_{k}}]}{e^{\theta\mathcal{C}}}$
$\displaystyle=\overline{\lim\limits_{T\rightarrow\infty}}\frac{\operatorname{U}}{T}\sum_{k=0}^{T-1}\inf_{\theta\geq
0}\frac{(\mathbb{E}[e^{\theta
a^{i}_{k}}])^{N}}{e^{\theta\mathcal{C}}}\leq\operatorname{U}\sum_{k=0}^{T-1}e^{-\operatorname{D}(\alpha||q)N},$
(33)

where $J^{BS}_{\hat{\gamma}}$ and $J^{BS}_{\gamma_{R}}$ are the costs under
policies $\hat{\gamma}$ and $\gamma_{R}$, respectively, and
$\operatorname{U}:=\max_{i\in[N]}c(\bar{\Delta},A_{i},C_{W^{i}})$. The first
equality follows since the sample paths of the AoI under $\hat{\gamma}$
coincide with those under the policy $\gamma_{R}$ by definition. The first
inequality follows as a result of Proposition 2. The third inequality follows
by the monotonic nature of the exponential function and second-to-last
inequality follows using Markov’s inequality. Finally, the last equality
follows because $a^{i}_{k}$’s are i.i.d. random variables (independent since
they were computed using a decoupling procedure, and identically distributed
since the probability of randomization $q$ is common for all agents for any
given $k$). Finally, in the last inequality
$\operatorname{D}(x||y):=x\ln{x/y}+(1-x)\ln{(1-x)/(1-y)}$ denotes the
Kullback-Liebler divergence between independent Bernoulli distributed random
variables distributed with parameters $x$ and $y$. Next, we observe that
$\operatorname{D}(x||y)=0$ if and only if $x=y$. For our case, this would then
imply that $\alpha=q$, which can happen if and only if $\bar{\mathcal{C}}=0$,
which is not possible as a result of the constraint on $R(\lambda)$. Hence,
$\operatorname{D}(x||y)>0$. Finally, by (11) and (C), it follows that
$J^{BS}_{\gamma}-J^{BS}_{\gamma_{R}}\leq
J^{BS}_{\hat{\gamma}}-J^{BS}_{\gamma_{R}}\rightarrow 0$, exponentially fast,
which completes the proof.

##  Appendix D Proof of Theorem 3

Let us start by defining two events $\tilde{\operatorname{E}}(\cdot)$ and
$\hat{\operatorname{E}}(\cdot)$. The event $\tilde{\operatorname{E}}(x)$ is
when any agent takes longer than $x$ time steps to re-enter the set
$S^{\gamma}$ (which is the set of agents that need to be transmitted). The
event $\hat{\operatorname{E}}(x)$ is when any agent takes longer than $x$
timesteps to be transmitted while in the set $S^{\gamma}$. Now, let us define
the event $\bar{\operatorname{E}}(x)$ when any agent’s AoI is larger than $x$
at any time instant. Then, we can deduce that

$\displaystyle\bar{\operatorname{E}}^{c}(x)$
$\displaystyle\supseteq\big{(}\tilde{\operatorname{E}}^{c}(x/2)\cap\hat{\operatorname{E}}^{c}(x/2)\big{)},\Leftrightarrow$
$\displaystyle\bar{\operatorname{E}}(x)$
$\displaystyle\subset\big{(}\tilde{\operatorname{E}}(x/2)\cup\hat{\operatorname{E}}(x/2)\big{)},$

using which we deduce

$\displaystyle\mathbb{P}(\bar{\operatorname{E}}(x))$
$\displaystyle\leq\mathbb{P}\big{(}\tilde{\operatorname{E}}(x/2)\cup\hat{\operatorname{E}}(x/2)\big{)}$
$\displaystyle\leq\mathbb{P}(\tilde{\operatorname{E}}(x/2))+\mathbb{P}(\hat{\operatorname{E}}(x/2)).$
(34)

First analyze the event $\tilde{\operatorname{E}}(x)$. The probability
$\mathbb{P}(\tilde{\operatorname{E}}(x))$ can be upper bounded as

$\displaystyle\mathbb{P}(\tilde{\operatorname{E}}(x))\leq\mathbb{P}\bigg{(}\sum_{k=0}^{x-1}|S_{suc,k}^{\gamma}|\leq
N-\mathcal{C}-1\bigg{)},$ (35)

where $S_{suc,k}^{\gamma}$ denotes the set of agents that are in
$S^{\gamma}_{k}$, and their updates are successfully transmitted at time $k$.
In the worst case scenario, when $k\in[x]$, the number of agents whose updates
are successfully transmitted is less than $N-\mathcal{C}-1$ so that in the
$x^{th}$ time, the $i^{th}$ agent is still not present in the set
$S^{\gamma}_{x}$. We note that $|S_{suc,k}^{\gamma}|$ is a Binomially
distributed random variable with number of trials $\mathcal{C}$, and success
probability $1-p$, i.e., $|S_{suc,k}^{\gamma}|\sim Bin(\mathcal{C},1-p)$, and
$\mathbb{P}(|S_{suc,k}^{\gamma}|=\ell)={\mathcal{C}\choose\ell}(1-p)^{\ell}p^{\mathcal{C}-\ell}$,
for $\ell\in[\mathcal{C}]$. Next, by using the fact that the sum of
independent binomial distributions with the same success probabilities is also
a Binomial distribution, we have that
$\sum_{k=0}^{x-1}|S_{suc,k}^{\gamma}|\sim Bin(x\mathcal{C},1-p)$. The
probability of $\mathbb{P}(\sum_{k=0}^{x-1}|S_{suc,k}^{\gamma}|\leq
N-\mathcal{C}-1)$ can then be rewritten as

$\displaystyle\\!\\!\mathbb{P}\left(\frac{\sum_{x=0}^{x-1}|S_{suc,k}^{\gamma}|-x\mathcal{C}(1-p)}{\sqrt{x\mathcal{C}p(1-p)}}\leq
c_{x,N}\right),\\!\\!$ (36)

where

$\displaystyle c_{x,N}=\frac{\sqrt{N}(1-(1+x(1-p))\alpha)}{\sqrt{x\alpha
p(1-p)}}-\frac{1}{\sqrt{x\alpha Np(1-p)}}.$

Next, given $x>\big{(}\frac{2}{\alpha(1-p)}\big{)}^{2}$, we can obtain an
upper bound on $c_{x,N}$ as:

$\displaystyle c_{x,N}$
$\displaystyle\leq\frac{\sqrt{N}((1-\alpha)-\alpha(1-p)x)}{\sqrt{x\alpha
p(1-p)}}$ $\displaystyle=\sqrt{\frac{N}{\alpha
p(1-p)}}\bigg{(}\frac{1-\alpha}{\sqrt{x}}-\alpha(1-p)\sqrt{x}\bigg{)}$
$\displaystyle\leq\sqrt{\frac{N}{\alpha
p(1-p)}}\bigg{(}\frac{(1-\alpha)\alpha(1-p)}{2}-2\bigg{)}$
$\displaystyle\leq-\sqrt{\frac{N}{\alpha p(1-p)}}=:\bar{c}_{N}.$ (37)

Then, by using the central limit theorem, the distribution of
$\frac{\sum_{k=0}^{x-1}|S_{suc,k}^{\gamma}|-x\mathcal{C}(1-p)}{\sqrt{x\mathcal{C}p(1-p)}}$
converges to the standard Gaussian distribution, as the number $x\mathcal{C}$
gets large. Thus, by using the Berry–Esseen theorem [28], we have that

$\displaystyle\left|\mathbb{P}\left(\frac{\sum_{k=0}^{x-1}|S_{suc,k}^{\gamma}|-x\mathcal{C}(1-p)}{\sqrt{x\mathcal{C}p(1-p)}}\leq
c_{x,N}\right)-\Upphi(c_{k,N})\right|\leq\epsilon_{1},$ (38)

where
$\Upphi(c_{x,N})=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{c_{x,N}}e^{-\frac{z^{2}}{2}}dz$
is the CDF of the standard Gaussian distribution and $\epsilon_{1}\leq
0.33554\frac{1-p+0.415}{\sqrt{x\mathcal{C}}}$ [28, Theorem 2]. Now, let us
define two random variables:

$\displaystyle Z_{N}(x)$
$\displaystyle=\frac{\sum_{k=0}^{x-1}|S_{suc,k}^{\gamma}|-x\mathcal{C}(1-p)}{\sqrt{x\mathcal{C}p(1-p)}},\text{
and }$ $\displaystyle Z_{\infty}(x)$
$\displaystyle=\lim_{N\rightarrow\infty}Z_{N}(x).$

Then, we know that the CDF of $Z_{\infty}(x)$ is given by $\Upphi(\cdot)$.
Using (35) and the definitions of $Z_{N}(x)$ and $Z_{\infty}(x)$, we get

$\displaystyle\mathbb{P}(\tilde{\operatorname{E}}(x))$
$\displaystyle\leq\mathbb{P}(Z_{N}(x)\leq c_{x,N})$
$\displaystyle\leq\big{\lvert}\mathbb{P}(Z_{N}(x)\leq
c_{x,N})-\mathbb{P}(Z_{\infty}(x)\leq c_{x,N})\big{\rvert}$
$\displaystyle\hskip 56.9055pt+\mathbb{P}(Z_{\infty}(x)\leq c_{x,N})$
$\displaystyle\leq 0.33554\frac{1-p+0.415}{\sqrt{x\alpha N}}+\Upphi(c_{x,N})$
$\displaystyle\leq 0.3354\frac{1-p+0.415}{\sqrt{\alpha
N}}+\Upphi(\bar{c}_{N}),$

where the third inequality follows from (38) and the fourth inequality follows
from the fact that if $x>\big{(}\frac{2}{\alpha(1-p)}\big{)}^{2}$ then
$c_{x,N}<\bar{c}_{N}$ using (37), which implies that
$\Upphi(c_{x,N})<\Upphi(\bar{c}_{N})$ due to the monotonically increasing
nature of $\Upphi(\cdot)$. Let us choose $N$ such that
$0.3354\frac{1-p+0.415}{\sqrt{\alpha N}}\leq\delta/4$ and
$\Phi(\bar{c}_{N})\leq\delta/4$. Then,

$\displaystyle\mathbb{P}(\tilde{\operatorname{E}}(x))\leq\delta/2.$ (39)

Notice that the conditions on $N$ suggest a lower bound on $x$ which is
independent of $N$ but dependent on $\delta$.

Next, we determine $\mathbb{P}(\hat{\operatorname{E}}^{i}(x))$, where
$\hat{\operatorname{E}}^{i}(x)$ is the event that agent $i$ takes longer than
$x$ timesteps to be transmitted while in the set $S^{\gamma}$. The former can
be computed as:

$\displaystyle\mathbb{P}(\hat{\operatorname{E}}^{i}(x))=(1-p)\sum_{s=x}^{\infty}p^{s}=(1-p)\bigg{(}\frac{p^{x}}{1-p}\bigg{)}=p^{x}.$

Hence, if we choose $x\geq\log(2/\delta)/\log(1/p)$, then

$\displaystyle\mathbb{P}(\hat{\operatorname{E}}^{i}(x))\leq\delta/2,$ (40)

Combining (D), (39) and (40) we get

$\displaystyle\mathbb{P}(\bar{\operatorname{E}}^{i}(x))\leq\delta$

for agent $i$, given that $N$ is chosen such that
$0.3354\frac{1-p+0.415}{\sqrt{\alpha N}}\leq\delta/4$ and
$\Upphi(\bar{c}_{N})\leq\delta/4$ and $x=\mathcal{O}(\log(1/\delta))$. This
then completes the proof of the theorem.