Age of Information Games Between Power Constrained Schedulers and Adversaries

I. INTRODUCTION

We consider a wireless communication system consisting of 𝑁 users, one base station (BS), [TeX:] $$N_s$$ communication channels and an adversary. A communication channel can have different channel gains to different users, and thus, all the sub-carriers may not be available to all the users for transmission of an update packet [1]. We consider the static setting. Thus, the communication channels are divided into 𝑁 potentially overlapping sets, where each set corresponds to a user. We denote the set of communication channels available to user 𝑖 as [TeX:] $$\mathcal{N}_{s, i}.$$ A sub-carrier can be an element of multiple sets, and thus, the set [TeX:] $$\mathcal{N}_{s, i} \cap \mathcal{N}_{s, j}$$ is not necessarily empty. The cardinality of [TeX:] $$\mathcal{N}_{s, i} \text { is } N_{s, i}$$. The set of all available channels is [TeX:] $$\mathcal{N}_s=\bigcup_i \mathcal{N}_{s, i},$$ and has cardinality [TeX:] $$N_s.$$ There are 𝑛 discrete power levels available to the BS for transmission of an update packet to the users and 𝑚 discrete power levels available to the adversary to block the transmission of an update packet. We consider a slotted time model. At each time slot, the BS chooses a transmission power to transmit an update packet to a user via a communication channel and the adversary chooses a communication channel and a blocking power to block any update packet that is being sent on the chosen channel. Though there are multiple communication channels available, because of the transmission power constraint, we assume that at each time slot, the BS can transmit an update packet to only one user. However, after choosing a power level, how the BS should split that power and transmit update packets to multiple users can be an interesting extension of this work. The system model studied in this paper is a useful abstraction of scenarios, where there is a transmitter who wants to minimize the age and a jammer who wants to maximize the age at a receiver, in the case the power constrained transmitter has multiple channels to use for transmitting update packets.

A large amount of work has been done on the analysis of age of information for various applications and system models, such as, scheduling policies for wireless networks, gossip networks, caching systems, source coding problem, remote estimation, energy harvesting systems and many more, see e.g., [2]–[46]. These papers consider systems without an adversary. The age of information in the presence of an adversary in a wireless communication network has been studied in the recent literature [47]–[55]. In particular, [54], [55] consider an adversarial gossip network. In this paper, we do not consider a gossip network, rather we consider that a central node, i.e., the BS transmits the update packets to the users. [47], [48] consider an adversary which decreases the signal to noise ratio of a communication link through jamming, due to which the rate of the communication decreases which results in a higher age for the communication system. In this paper, we consider that when the adversary blocks a communication channel it completely eliminates the update packet with a positive probability. [49] considers an adversary which blocks the communication channel for a duration in time which increases the average age of the system by disabling communication in that interval. In this paper, we consider that the adversary blocks the communication channel in a time slotted manner. [50], [51] consider an adversary which completely eliminates the update packet, however, they do not consider any power constraint on the adversary. In this paper, we consider a power constrained adversary. [52], [53] consider a power constrained adversary which completely eliminates the update packet. They have considered that on the time horizon 𝑇, the adversary blocks [TeX:] $$\alpha T$$ time slots where 0 < 0 < 1. On the contrary, in this paper, we consider that at each time slot 𝑡, the adversary chooses one of the 𝑚 blocking power levels with a pmf d(𝑡) and the expected power to be less than or equal to a power constraint. Different than the adversary in [52], [53], the adversary in this paper completely eliminates the update packet with a positive probability (strictly less than 1), and this probability depends on the blocking power chosen by the adversary and the transmission power chosen by the BS.

References [50], [51] have considered the problem in an online learning setting and studied the competitive ratio. Different than these works, in the first part of this paper, we study the behavior of the average age in the presence of the worst adversarial actions, as formally defined in (4). First, we find a lower bound on the average age for this setting. Then, we propose algorithms and study how they perform under the worst adversarial actions for the described wireless communication network. Specifically, we show that the uniform user choosing policy together with the uniform communication channel choosing policy and any arbitrary feasible transmission power choosing policy is 4 optimal, and in a special case, it is 2 optimal. We also show that the maximum-age user choosing policy together with the uniform communication channel choosing policy and any arbitrary feasible transmission power choosing policy is 2 optimal. References [52], [53] have considered a power constrained adversary, however due to the difference in how we define the power constraint in this paper compared to [52], [53], as discussed above, the techniques we use in this paper to prove the lower bound on the average age are different.

In the second part of this paper, we relax the system model and consider that at each time slot the BS can choose any one of the [TeX:] $$N_s$$ sub-carriers for transmission of an update packet to any one of the 𝑁 users, i.e., [TeX:] $$\mathcal{N}_{s, i}=\mathcal{N}_s,$$ for all 𝑖. We also restrict the action space of the BS and the action space of the adversary only to the stationary policies. As the BS aims to minimize the average age and the adversary aims to maximize the average age of the communication network, we pursue a multi-objective solution concept in a game theoretic setting. Specifically, we study the Nash equilibrium of this problem, as opposed to the first part of the paper, where we evaluate the performance of different transmission policies under the worst-case adversarial actions. If a Nash equilibrium for this problem exists, then we know that this point is optimal for both the adversary and the BS if they act simultaneously, i.e., neither of them could improve their performance by changing their policy while the other’s policy remains unchanged.

If the power level choosing algorithms are not fixed for the BS and for the adversary and if those are included in the action space of the BS and the action space of the adversary, then we show that in the stationary policy regime a Nash equilibrium may not exist. We give a counter example to prove this. We also show a special case in which the Nash equilibrium exists. However, when the power level choosing algorithms for the BS and for the adversary are fixed, i.e., those are not included in the list of the actions of the BS and the list of the actions of the adversary, then the Nash equilibrium always exists.

II. SYSTEM MODEL AND PROBLEM FORMULATION

At each time slot, the BS schedules a user 𝑖 out of 𝑁 users, 𝑁 > 1, with a user choosing algorithm [TeX:] $$\pi_u$$ and chooses a communication channel out of [TeX:] $$N_{s, i}$$ communication channels, [TeX:] $$N_{s, i}\gt 1 \text {, }$$ with a communication channel choosing algorithm [TeX:] $$\pi_s$$ to transmit an update packet to the scheduled user 𝑖. In this paper, we use sub-carrier and communication channel interchangeably. We consider that 𝑛 discrete transmission powers, namely [TeX:] $$\left\{p_1, p_2, \cdots, p_n\right\}$$ are available to the BS, and at each time slot the BS chooses one of these 𝑛 transmission powers, following a power choosing algorithm [TeX:] $$\pi_p.$$ Thus, an action of the BS is a triplet [TeX:] $$\left(\pi_u, \pi_s, \pi_p\right)$$ and we call a valid triplet as a BS scheduling algorithm π. We call the set of all causal scheduling algorithms as Π. Let us consider that [TeX:] $$\pi_p$$ is such that at time slot 𝑡 the BS chooses the 𝑖th transmission power with probability [TeX:] $$e_i(t)$$. We consider the following power constraint for the BS,

We consider that an adversary is present in the system as well. At each time slot, the adversary chooses a sub-carrier out of [TeX:] $$N_s$$ sub-carriers following an algorithm [TeX:] $$\psi_s$$ to block any update packet that is being transmitted by the BS in that subcarrier. We consider that 𝑚 discrete blocking powers, namely [TeX:] $$\left\{p_1^{\prime}, p_2^{\prime}, \cdots, p_m^{\prime}\right\}$$ are available to the adversary and at each time slot the adversary chooses one of these powers, following a blocking power choosing algorithm [TeX:] $$\psi_p,$$ to block any update packet on the sub-carrier chosen by [TeX:] $$\psi_s.$$ Thus, an action of the adversary is a pair [TeX:] $$\left(\psi_s, \psi_p\right)$$ and we call a valid pair as an adversarial action [TeX:] $$\psi$$. We call the set of all valid adversarial actions as [TeX:] $$\Psi$$. Let us consider that [TeX:] $$\psi_p$$ is such that at time slot 𝑡, the adversary chooses the 𝑖th blocking power with probability [TeX:] $$d_i(t).$$ We consider the following power constraint for the adversary,

We create an [TeX:] $$n \times m$$ matrix F, whose (𝑖, 𝑗 )th element, [TeX:] $$f_{i, j},$$ represents the probability of successful transmission of an update packet corresponding to the BS transmission power [TeX:] $$p_i$$ and adversary blocking power [TeX:] $$p_j^{\prime}.$$ Thus, at time slot 𝑡 if the BS schedules the user 𝑘, and chooses the sub-carrier 𝑙 to transmit an update packet with power [TeX:] $$p_i$$ and if the adversary blocks the sub-carrier 𝑙 with power [TeX:] $$p_j^{\prime},$$ then with probability [TeX:] $$f_{i, j},$$ the age of the 𝑘th user at time slot (𝑡 + 1) becomes 1 and with probability [TeX:] $$1-f_{i, j}$$ the age of the 𝑘th user at time slot 𝑡 + 1 increases by one.

The age of user 𝑖 at time slot 𝑡 is defined as [TeX:] $$t-t_i(t),$$ where [TeX:] $$t_i(t),$$ is the last time slot when the 𝑖th user has successfully received an update packet. Note that the minimum value for the age of user 𝑖 is 1. We consider that at each time slot the BS has a fresh update packet to transmit for every users present in the system. Here by fresh update packet, we mean the update packet for the 𝑖th user at time slot 𝑡 is generated at time slot 𝑡. As we are interested in freshness, we assume that if the 𝑖th user does not receive the corresponding update packet at time slot 𝑡, then that update packet gets dropped at the BS without any cost. This is a valid assumption used in [50]–[53]. For a pictorial representation of the system model and the evolution of age, please see Fig. 1.

Fig. 1.

The top figure illustrates the system model with 4 sub-carriers, 2 adversarial power levels, and 2 transmission power levels. The top figure shows how the BS chooses a sub-carrier and a transmission power level for a specific user, say user 1 for this example, and how the adversary chooses a sub-carrier and a blocking power level over the time horizon 𝑇. In this figure, for user 1, if the BS chooses the lower transmission power then the sub-carrier which is chosen by the BS is shown with a light green box, and if it chooses the higher transmission power then the sub-carrier which is chosen is shown with a light blue box. It can happen that the BS does not schedule user 1 at a given time slot, for example, see time slot 4, where there are no green or blue boxes. Similarly, at a given time slot, if the adversary chooses the lower blocking power then the sub-carrier which is chosen by the adversary at that time slot is shown with an orange cross, and if it chooses the higher blocking power then the sub-carrier which chosen is shown with a red cross. The bottom figure illustrates the age evolution for user 1, corresponding to the BS and adversarial actions in the top figure. Note that whenever the BS and the adversary choose the same sub-carrier the age of user 1 drops down by a certain probability, which depends on the corresponding blocking and transmission power levels.

The adversary has the knowledge of [TeX:] $$\pi_u, \pi_s \text { and } \pi_p.$$ However, as the BS uses a randomized algorithm at time slot 𝑡, the adversary has no knowledge about which user will get scheduled, which sub-carrier will get chosen and which transmission power will get used at time slot [TeX:] $$t^{\prime} \text { when } t \leq t^{\prime} \leq T.$$ However, at time slot 𝑡 it has full knowledge about all these for time slot [TeX:] $$t^{\prime} \text { when } t \leq t^{\prime} \lt t,$$ and the adversary can optimize its future actions based on these available information. The adversary has full knowledge about the elements of each set [TeX:] $$\mathcal{N}_{s, i}.$$ The age of user 𝑖 at time slot 𝑡 corresponding to a BS scheduling algorithm π and adversarial action ψ is denoted as [TeX:] $$v_i^{(\boldsymbol{\pi}, \boldsymbol{\psi})}(t),$$ thus, [TeX:] $$v_i^{(\boldsymbol{\pi}, \boldsymbol{\psi})}(t)=t-t_i(t),$$ and the expected age of user 𝑖 at time slot 𝑡, is denoted as [TeX:] $$\Delta_i^{(\pi, \psi)}(t).$$ Note that, if the BS successfully transmits an update packet to user 𝑖 at time slot 𝑡, then [TeX:] $$v_i^{(\boldsymbol{\pi}, \boldsymbol{\psi})}(t+1)=1,$$ otherwise [TeX:] $$v_i^{(\boldsymbol{\pi}, \boldsymbol{\psi})}(t+1)=v_i^{(\boldsymbol{\pi}, \boldsymbol{\psi})}(t)+1.$$ The average age of the overall system corresponding to the BS scheduling algorithm π and adversarial action ψ is,

For the simplicity presentation, in the rest of the paper we ignore the superscript [TeX:] $$(\pi, \psi)$$, unless we specify otherwise. Now as the BS has no control over the adversary, we consider the following constrained optimization problem,

For the second part of the paper, we consider a relaxed system model. We consider that at each time slot, all the [TeX:] $$N_S$$, sub-carriers are available to the BS to transmit an update packet to any one of the 𝑁 users, i.e., [TeX:] $$\mathcal{N}_{s, i}=\mathcal{N}_s$$ for all 𝑖. The BS chooses a scheduling algorithm and the adversary chooses an adversarial action from the corresponding sets of stationary randomized policies. In other words, [TeX:] $$\pi_u$$ is such that at each time slot the BS chooses a user following a pmf [TeX:] $$\boldsymbol{u}=\left[u_1, u_2, \cdots, u_N\right], \pi_s$$ is such that at each time slot the BS chooses a sub-carrier following a pmf [TeX:] $$s=\left[s_1, s_2, \cdots, s_{N_s}\right]$$ and [TeX:] $$\pi_p$$ is such that at each time slot the the BS chooses a power following a pmf [TeX:] $$e=\left[e_1, e_2, \cdots, e_n\right].$$ Similarly, [TeX:] $$\psi_S$$ is such that at each time slot the adversary blocks a subcarrier following a pmf [TeX:] $$a=\left[a_1, a_2, \cdots, a_{N_s}\right] \text { and } \psi_p$$ is such that at each time slot the adversary chooses a blocking power following a pmf [TeX:] $$d=\left[d_1, d_2, \cdots, d_m\right].$$ Thus, the power constraints for the adversary and the BS become [TeX:] $$\sum_{i=1}^m d_i p^{\prime}(i) \leq \tilde{p}$$ and [TeX:] $$\sum_{i=1}^n e_i p(i) \leq \bar{p},$$ respectively. When we restrict ourselves only to the stationary randomized policies, instead of writing [TeX:] $$\Delta^{\pi, \psi}$$ as in (3), we write the average age of the overall system corresponding to pmfs u, s, e (these three pmfs are chosen by the BS) and the pmfs a, d (these two pmfs are chosen by the adversary) as [TeX:] $$\Delta^{u, s, e, a, d}$$. We denote the expected age of user 𝑖 at time slot 𝑡 as [TeX:] $$\Delta_i^{u, s, e, a, d}(t) .$$ Thus, the average age for the 𝑖th user becomes

Let us assume that the set of all valid user choosing pmfs, the set of all valid sub-carrier choosing pmfs and the set of all valid transmission power choosing pmfs are [TeX:] $$\mathcal{F}_u, \mathcal{F}_s \text { and } \mathcal{F}_e,$$ respectively. Similarly, the set of all valid sub-carrier blocking pmfs and the set for all valid blocking power choosing pmfs are [TeX:] $$\mathcal{F}_a \text { and } \mathcal{F}_d,$$ respectively. For a given adversarial action, namely a sub-carrier blocking pmf a, and a blocking power level choosing pmf d, the BS aims to minimize the average age of the overall system by selecting a scheduling algorithm, namely a user choosing pmf u, a sub-carrier choosing pmf s and a transmission power choosing pmf e from the set 𝐵(a, d), where 𝐵(a, d) is defined as follows,

Similarly, for a given scheduling algorithm, i.e., a triplet of pmfs (u, s, e), the adversary aims to maximize the average age by choosing a pair of pmfs, namely (a, d) from the set 𝐵(u, s, e), where 𝐵(u, s, e) is defined as

We call a 5-tuple of pmfs, namely (u, s, e, a, d) as a Nash equilibrium point if and only if [TeX:] $$(u, s, e) \in B(a, d) \text{ and } (a, d) \in B(u, s, e)$$

In the previous Nash equilibrium setting we consider that the transmission power choosing pmf e and blocking power choosing pmf d are components of the action space of the BS and the action space of the adversary, respectively. However, if e and d are fixed and not included in the action space of the BS and the action space of the adversary, respectively, then we define,

Similarly, we write,

We call a triplet of pmfs, namely (u, s, a) as a Nash equilibrium point if and only if [TeX:] $$(u, s) \in B(a,) \text { and } a \in B(u, s) \text {. }$$

III. ALGORITHM AND ANALYSIS OF AGE

We find a fundamental lower bound for the optimization problem in (4). Let us define [TeX:] $$x=\arg \max _{i \in\{1, \cdots, m\}} p_i^{\prime} \leq \tilde{p} .$$ Consider the following adversarial action: at each time slot the adversary blocks any one of the [TeX:] $$N_S$$ sub-carriers with a uniform pmf and chooses the power level [TeX:] $$p_x$$. We denote this adversarial action as [TeX:] $$\bar{\psi}=\left(\bar{\psi}_s, \bar{\psi}_p\right)$$. At each time slot, if the BS schedules the user which has the maximum age and breaks the tie with scheduling the lower indexed user, we call that user choosing policy as the max-age policy.

Lemma 1. For the adversarial action [TeX:] $$\bar{\psi}$$, an optimal user choosing policy is the max-age policy; and if the 𝑖th user gets chosen by the max-age policy, then an optimal sub-carrier choosing policy is to choose a sub-carrier in [TeX:] $$\mathcal{N}_{s, i}$$ uniformly.

Proof: Let us assume that the user choosing algorithm employed by the BS is [TeX:] $$\bar{\pi}_u,$$ and the action of the BS corresponding to the 𝑖th user at time slot 𝑡 is [TeX:] $$\bar{\pi}_{u, i}(t).$$ Here, [TeX:] $$\bar{\pi}_{u, i}(t) \in\{0,1\},$$ and [TeX:] $$\bar{\pi}_{u, i}(t)=0$$ implies that the BS does not schedule user 𝑖 at time slot 𝑡, [TeX:] $$\bar{\pi}_{u, i}(t)=1$$ implies that the BS schedules user 𝑖 at time slot 𝑡. Similarly, assume that the BS employs [TeX:] $$\bar{\pi}_S$$ as the sub-carrier choosing algorithm. At time slot 𝑡, the action of the BS corresponding to the sub-carrier 𝑗 , [TeX:] $$j \in \mathcal{N}_i,$$ is [TeX:] $$\bar{\pi}_{s, i}(t),$$ where [TeX:] $$\bar{\pi}_{s, i}(t) \in\{0,1\} .$$ Here, [TeX:] $$\bar{\pi}_{s, i}(t)=0$$ implies that the BS does not choose sub-carrier 𝑗 at time slot 𝑡, and [TeX:] $$\bar{\pi}_{s, i}(t)=1$$ implies that the BS chooses sub-carrier 𝑗 at time slot 𝑡. Assume that the BS chooses the transmission power [TeX:] $$p_y,$$ where [TeX:] $$y=\arg \max _{i \in\{1, \cdots, n\}} p_i \leq \bar{p} .$$ Now, we can write the expected age of user 𝑖 at time slot 𝑡 + 1, conditioned on the age of user 𝑖 at time slot 𝑡 as,

The first term of (10), corresponds to the fact that, if the BS does not schedule the 𝑖th user at time slot 𝑡, the age of the 𝑖th user increases irrespective of the sub-carrier choosing algorithm [TeX:] $$\bar{\pi}_S$$ and sub-carrier blocking algorithm [TeX:] $$\bar{\psi}_S .$$ Now, if the BS schedules user 𝑖 at time slot 𝑡, then the age of user 𝑖 at time slot 𝑡 + 1, depends on [TeX:] $$\bar{\pi}_s, \bar{\psi}_s$$ and the probability of successful transmission corresponding to the transmission power [TeX:] $$p_y$$ and the blocking power [TeX:] $$p_x,$$ i.e., [TeX:] $$f_{y, x}$$. These facts are reflected in the last three terms of (10).

Noting the fact that [TeX:] $$\sum_{j=1}^{N_{s, i}} \bar{\pi}_{s, j}(t)=1$$ for all 𝑡, taking the expectation of [TeX:] $$v_i(t)$$ in (10) and after simplifying, we obtain

Note that (10) is independent of [TeX:] $$\bar{\pi}_s,$$ thus we can choose any sub-carrier blocking policy and for simplicity of later theorems we choose it to be a uniform pmf over the sub-carriers of the set [TeX:] $$\mathcal{N}_{s, i},$$ if the BS chooses user 𝑖. We define the overall age of the communication system till time slot 𝑡 + 𝑘, starting from time slot 𝑡, corresponding to a scheduling policy π, and an adversarial action ψ, as

Note that, [TeX:] $$v^{\boldsymbol{\pi}, \boldsymbol{\psi}}(t, t+k)$$ is the sum of all the instantaneous ages of all the users till time slot 𝑡 + 𝑘 from the time slot 𝑡. Now, consider the evolution of the overall age from time slot 𝑡 to time slot 𝑡 + 𝑘. Together with the uniform sub-carrier choosing policy over the set of sub-carriers corresponding to the max-age user and the transmission power level [TeX:] $$p_y,$$ we call the max-age user choosing policy as [TeX:] $$\tilde{\pi} .$$ Then, [TeX:] $$v^{\tilde{\pi}, \bar{\psi}}(t, t+1)$$ can take two values, one corresponding to the case when there is no successful transmission and the other corresponding to the case when there is a successful transmission. We call the possible values of [TeX:] $$v^{\tilde{\boldsymbol{\pi}}, \overline{\boldsymbol{\psi}}}(t, t+k)$$ as the states of [TeX:] $$v^{\tilde{\boldsymbol{\pi}}, \overline{\boldsymbol{\psi}}}(t, t+k).$$ Note that, [TeX:] $$v^{\tilde{\pi}, \bar{\psi}}\left(t, t+k_1\right), 0 \leq k_1 \leq k,$$ can take any one of the possible [TeX:] $$2^{k_1}$$ states. Now, consider a particular instance where the BS successfully transmits update packets for all 𝑘 time slots. There is only one possible state of [TeX:] $$v^{\tilde{\boldsymbol{\pi}}, \overline{\boldsymbol{\psi}}}(t, t+k)$$ which corresponds to this particular instance of BS transmission, and the evolution of [TeX:] $$v^{\tilde{\boldsymbol{\pi}}, \overline{\boldsymbol{\psi}}}(t, t+k_1)$$ corresponding to this particular instance is deterministic. The probability of occurrence of this particular BS transmission instance is [TeX:] $$\left(\frac{N_s-1}{N_s}+\frac{f_{y, x}}{N_s}\right)^k.$$ Note that there are no other instances of BS transmission for which the state of [TeX:] $$v^{\tilde{\boldsymbol{\pi}}, \overline{\boldsymbol{\psi}}}(t, t+k)$$ can be the same as the state of [TeX:] $$v^{\tilde{\boldsymbol{\pi}}, \overline{\boldsymbol{\psi}}}(t, t+k)$$ which corresponds to all successful BS transmission instance. Thus, with the probability [TeX:] $$\left(\frac{N_s-1}{N_s}+\frac{f_{y, x}}{N_s}\right)^k, v^{\tilde{\boldsymbol{\pi}}, \overline{\boldsymbol{\psi}}}(t, t+k)$$ will be in that particular state. Together with the uniform sub-carrier choosing policy and transmission power level [TeX:] $$p_y,$$ we call an arbitrary user choosing policy as [TeX:] $$\hat{\pi} .$$ Note that [TeX:] $$v^{\hat{\pi}, \bar{\psi}}(t, t+1)$$ can have maximum 𝑁 +1 states. Similarly, [TeX:] $$v^{\tilde{\boldsymbol{\pi}}, \overline{\boldsymbol{\psi}}}(t, t+k_1)$$ can have maximum [TeX:] $$(N+1)^{k_1}$$ states. Now, consider the BS transmission instance for which the BS successfully transmits the update packets in all the 𝑘 time slots, again the probability of this instance is [TeX:] $$\left(\frac{N_s-1}{N_s}+\frac{f_{y, x}}{N_s}\right)^k.$$ For this BS transmission instance, [TeX:] $$v^{\hat{\boldsymbol{\pi}}, \overline{\boldsymbol{\psi}}}(t, t+k)$$ can have maximum [TeX:] $$N^k$$ states. Using similar arguments to those we used for the max-age user choosing policy, we claim that the total probability of occurrence of all these states is [TeX:] $$\left(\frac{N_s-1}{N_s}+\frac{f_{y, x}}{N_s}\right)^k.$$ Note that the values of [TeX:] $$v^{\hat{\boldsymbol{\pi}}, \overline{\boldsymbol{\psi}}}(t, t+k)$$ corresponding to all these [TeX:] $$N^k$$ states are greater than or equal to the value of [TeX:] $$v^{\tilde{\boldsymbol{\pi}}, \overline{\boldsymbol{\psi}}}(t, t+k)$$ corresponding to the one state which occurs at the instance of all successful BS transmission. Thus,

where 𝐼 is the instance that the BS transmits the update packets successfully for all the 𝑘 time slots. We can use the same arguments for any instances of BS transmission. Thus,

completing the proof.

Theorem 1. The average age of the communication network defined in (3) is lower bounded by [TeX:] $$\frac{(N+1) N_s}{2\left(N_s-1+f_{\bar{y}, x}\right)} \text {. }$$

Proof: From Lemma 1, we know that when the adversarial action is [TeX:] $$\bar{\psi},$$ at each time slot, the optimal sub-carrier choosing strategy for the BS is to choose any one of the sub-carriers uniformly from the set of sub-carriers corresponding to the max-age user and the optimal user choosing algorithm is the max-age algorithm. We consider that the BS chooses power [TeX:] $$p_{\bar{y}}$$ for the transmission of an update packet, this violates the power constraint of the BS, however, with this transmission power we get a lower bound on the average age. Together with the uniform sub-carrier choosing policy and the transmission power [TeX:] $$p_{\bar{y}}$$, we call the max-age user choosing policy as [TeX:] $$\check{\pi}$$. For a user 𝑖, the whole time horizon 𝑇 can be divided into multiple blocks, where each block consists of consecutive time slots where user 𝑖 does not receive any update packet and each block ends when the user 𝑖 successfully receives an update packet. Thus, if a block starts at time slot 𝑡, 𝑡 > 1, then it implies that at time slot 𝑡 − 1 user 𝑖 has successfully received an update packet. Consider such a block Γ. Now, Γ can be divided into several sub blocks, [TeX:] $$\Gamma_1, \Gamma_2, \cdots, \Gamma_N,$$ where [TeX:] $$\Gamma_j$$ is the length of the consecutive time slots for which user 𝑗 is scheduled by the BS but does not receive any update packet. We define the total age of user 𝑖 in Γ as [TeX:] $$\Gamma_{\text {age }}$$. Thus,

The evolution of age corresponding to [TeX:] $$\check{\pi} \text { and } \bar{\psi}$$ is a renewal process and Γ is a renewal interval. Note that [TeX:] $$\Gamma_j, j \in\{1, \cdots, N\}$$ is a geometric distributed random variable with probability of successful transmission [TeX:] $$q=\frac{N_s-1}{N_s}+\frac{f_{\bar{y}, x}}{N_s},$$

and

Thus, using the renewal reward theorem [56],

proving the theorem.

Now, we consider that at each time slot the BS schedules a user 𝑖 with probability [TeX:] $$\frac{1}{N}$$ and chooses one of the [TeX:] $$N_{s, i}$$ subcarriers with probability [TeX:] $$\frac{1}{N_{s, i}},$$ to transmit an update packet to the scheduled user with transmission power [TeX:] $$p_y$$ with probability β and with transmission power [TeX:] $$p_{\bar{y}}$$ with provavility (1-β), where β satisfies the following identity:

Let us denote this BS scheduling policy as [TeX:] $$\hat{\tilde{\pi}}.$$ Let us define [TeX:] $$\bar{x}=\arg \min _{i \in\{1, \cdots, m\}} p_i^{\prime} \geq \tilde{p}.$$

Theorem 2. The average age of the communication system when the BS employs the scheduling algorithm [TeX:] $$\hat{\tilde{\pi}}.$$ is upper bounded by 2𝑁; when [TeX:] $$N_{s, i}=N_s$$ for all 𝑖, then the average age is upper bounded by [TeX:] $$\frac{N N_s}{N_s-1+\beta f_{y, \bar{x}}+(1-\beta) f_{\bar{y}, \bar{x}}} .$$

Proof: Let us assume that the blocking power for the adversary is [TeX:] $$p_{\bar{x}}^{\prime},$$ this violates the power constraint of the adversary, however, it gives an upper bound for the scheduling policy [TeX:] $$\hat{\tilde{\pi}}.$$ First, consider the case when [TeX:] $$N_{s, i}=N_s,$$ for all 𝑖. Note that the adversary always blocks one sub-carrier in every time slot. Thus, for scheduling policy [TeX:] $$\hat{\tilde{\pi}}.$$ and any adversarial sub-carrier choosing policy, the probability of successful transmission of the update packet to the 𝑖th user is given as,

Note that [TeX:] $$q_i$$ does not depend on the adversarial sub-carrier blocking algorithm, thus, we choose the uniform sub-carrier blocking pmf. Together with the blocking power [TeX:] $$p_{\bar{x}}^{\prime},$$ we call the uniform sub-carrier blocking pmf as adversarial action [TeX:] $$\tilde{\psi}.$$ Note that the age of user 𝑖 is a renewal process. Thus,

where (24) follows from the renewal reward theory [56].

Next, we consider the case when at least one of the 𝑁 sets of the communication channels has less than [TeX:] $$N_S$$ sub-carriers. If we consider that at each time slot the adversary blocks a sub-carrier from each and every set [TeX:] $$\mathcal{N}_{s, i}$$, then, we get a lower bound on [TeX:] $$q_i$$. Thus,

Therefore,

completing the proof.

Now, we consider that at each time slot the BS schedules the max-age user, 𝑖, and chooses one of the [TeX:] $$N_{s, i}$$ sub-carriers with probability [TeX:] $$\frac{1}{N_{s, i}}.$$ We also consider that the BS chooses power [TeX:] $$p_y$$ with probability β and power [TeX:] $$p_{\bar{y}}$$ with probability 1-β, where β satisfies (22). Denote this BS scheduling policy as [TeX:] $$\tilde{\tilde{\pi}} \text {. }$$

Theorem 3. The average age of the communication system when the BS employs the scheduling algorithm [TeX:] $$\tilde{\tilde{\pi}}$$ is upper bounded by [TeX:] $$\frac{(N+1) \bar{N}_s}{2\left(\bar{N}_s-1+\beta f_{y, \bar{x}}+(1-\beta) f_{\bar{y}, \bar{x}}\right)},$$ where [TeX:] $$\bar{N}_s=\min \left\{N_{s, 1}, N_{s, 2}, \cdots, N_{s, N}\right\} .$$

Proof: At each time slot, the optimal action for the adversary is to block any one sub-carrier from the set of sub-carriers corresponding to the maximum age user. We call this subcarrier choosing policy, together with the blocking power [TeX:] $$p_{\bar{x}}$$ as the adversarial action [TeX:] $$\breve{\psi}.$$ Thus, the probability of successful transmission for any user 𝑖, [TeX:] $$q_i,$$ is lower bounded as,

From (20), the average age of use 𝑖 can be upper bounded as,

completing the proof.

Next, we make some concluding remarks about the findings of this section. From Theorem 1 and Theorem 2, we see that in the general setting, [TeX:] $$\hat{\tilde{\pi}} \text { is } \frac{4 N\left(N_s-1+f_{\bar{y}, x}\right)}{(N+1) N_s}$$ optimal, where

For the special case, when [TeX:] $$\mathcal{N}_{s, i}=\mathcal{N}_s$$, for all 𝑖, [TeX:] $$\hat{\tilde{\pi}}$$ is [TeX:] $$\frac{2(N+1)\left(N_s-1+f_{\bar{y}, x}\right)}{N\left(N_s-1+f_{y, \bar{x}}\right)}$$ optimal, where

If [TeX:] $$N_s$$ is large, then the right side of (34) can be approximated as 2. Thus, for the aforementioned special case and for large [TeX:] $$N_s$$, [TeX:] $$\hat{\tilde{\pi}}$$ is 2 optimal.

From Theorem 1 and Theorem 3, we see that the scheduling policy [TeX:] $$\tilde{\tilde{\pi}}$$ is [TeX:] $$\frac{\bar{N}_s}{\bar{N}_s-1}$$ optimal and as [TeX:] $$N_{s, i}\gt 1,$$ for all 𝑖, [TeX:] $$\tilde{\tilde{\pi}}$$ is 2 optimal. Note that when [TeX:] $$\bar{p}$$ exactly matches with one of the powers from the sets [TeX:] $$\left\{p_1, p_2, \cdots, p_n\right\}$$ and [TeX:] $$\mathcal{N}_{s, i}=\mathcal{N}_s$$, for all 𝑖, then [TeX:] $$\tilde{\tilde{\pi}}$$ is the optimal scheduling policy.

IV. EQUILIBRIUM POINTS OF THE AVERAGE AGE FOR RANDOMIZED STATIONARY ACTION SPACE

Let us assume that at each time slot the BS chooses a user following a pmf u, chooses a sub-carrier following a pmf s, chooses a transmission power with a pmf e and the adversary chooses a sub-carrier with a pmf a and chooses a blocking power following a pmf d. Recall that for this section we use a relaxed system model, where we consider that [TeX:] $$\mathcal{N}_{s, i}=\mathcal{N}_s,$$ for all 𝑖. At some ime slot 𝑡, user 𝑖 successfully receives an update packet transmitted by the BS and then after waiting for [TeX:] $$\Gamma_i,$$ time slots it again receives another update packet from the BS. Note that [TeX:] $$\Gamma_i$$ is a random variable. The evolution of the age for the 𝑖th user is a renewal process and [TeX:] $$\Gamma_i$$ is a renewal interval. Thus, from the renewal reward theorem,

Let the probability of successful transmission of the update packet to user 𝑖 be [TeX:] $$q_i$$. Then, [TeX:] $$\Gamma_i$$ is geometrically distributed with success probability [TeX:] $$q_i$$. Thus, (36) simplifies as,

Theorem 4. The optimal sub-carrier choosing pmf s, for a given adversarial action, namely, a pair of pmfs (a, d), depends only on a and is independent of user choosing pmf u, transmission power choosing pmf e and d. Moreover, if the adversary blocks any 𝑙 sub-carriers with lowest probability then the optimal choice for the BS is to choose any subset of these 𝑙 sub-carriers with probability 1. Similarly, the optimal user scheduling pmf u does not depend on a, s, d, e. The optimal user scheduling pmf is the uniform pmf.

Proof: The probability of successful transmission of an update packet to the 𝑖th user [TeX:] $$q_i$$ is as follows,

Therefore, the total average age becomes,

Thus, for a given (a, d), the optimization problem

becomes

Thus, for a given adversarial action (a, d), [TeX:] $$\Delta^{u, s, e, a, d}$$ can be optimized with respect to u independent of s and e. Similarly, [TeX:] $$\Delta^{u, s, e, a, d}$$ can be optimized with respect to s independent of u and e. First, we find the optimal solution for the following problem,

The Lagrangian for (43) is

The optimal solution [TeX:] $$\boldsymbol{u}^*$$ satisfies [TeX:] $$\left.\nabla \mathcal{L}(\boldsymbol{u}, \lambda)\right|_{\boldsymbol{u}^*}=0$$. Solving this gives, [TeX:] $$u_i=\frac{1}{\sqrt{\lambda}}, i=1, \cdots, N \text {, }$$ which using [TeX:] $$\sum_{i=1}^N u_i=1,$$ yields [TeX:] $$u_i=\frac{1}{N} \text {, }$$ for all 𝑖.

Now, for a given adversarial action (a, d), we find the optimal solution for the following problem,

Without loss of generality, consider that [TeX:] $$a_1 \geq a_2 \geq \cdots \geq a_{N_s-l}\gt a_{N_s-l+1}=a_{N_s-l+2}=\cdots=a_{N_s} \text {, }$$ i.e., the adversary blocks the last 𝑙 sub-carriers with the lowest probability. Then, the equivalent problem of (45) becomes

Theorem 5. The optimal sub-carrier blocking pmf, a, for a given BS scheduling policy depends only on s and is independent of u, e and d. Moreover, if the BS chooses any 𝑙 sub-carriers with the highest probability, then the optimal choice for the adversary is to block any subset of these 𝑙 subcarriers with probability 1.

Proof: Without loss of generality, let [TeX:] $$s=\left[s_1, s_2, \cdots, s_{N_s}\right]$$ and [TeX:] $$s_1=s_2=\cdots=s_l\gt s_{l+1} \geq \cdots \geq s_{N_s} .$$ From (42), we have to solve the following problem

which is maximized when [TeX:] $$\sum_{j=1}^l s_j=1.$$

Without loss of generality, let [TeX:] $$p_1 \leq p_2 \leq \cdots \leq p_n$$ and [TeX:] $$p_1^{\prime} \leq p_2^{\prime} \leq \cdots \leq p_m^{\prime}.$$ Thus, we have [TeX:] $$f_{1, j} \leq f_{2, j} \leq \cdots \leq f_{n, j}$$ and [TeX:] $$f_{i, 1} \geq f_{i, 2} \geq \cdots \geq f_{i, m}, i=1, \cdots, n, j=1, \cdots, m .$$ Algorithm 1 below provides an optimal transmission power choosing pmf e for a given blocking power choosing pmf d. The algorithm states that, if [TeX:] $$\bar{p}\lt p_1,$$ then there does not exist a feasible e; if [TeX:] $$p_n \lt \bar{p},$$ then the optimal e is to choose the power [TeX:] $$p_n$$ with probability 1; if [TeX:] $$\bar{p}$$ exactly matches one of the powers from the set [TeX:] $$\left\{p_1, p_2, \cdots, p_n\right\},$$ then the optimal e is to choose that particular power with probability 1. If these three cases do not occur, then we define [TeX:] $$x=\arg \max _{i \in\{1, \cdots, n\}, p_i \leq \bar{p}} i$$ and [TeX:] $$y=\arg \min _{i \in\{1, \cdots, n\}, p_i \geq \bar{p}} i .$$ Clearly, x < y. We define a constant, [TeX:] $$g_i=\sum_{j=1}^m d_j f_{i, j},$$ [TeX:] $$i=1, \cdots, n \text {. }$$ We call the constant [TeX:] $$\left(g_i+g_x \frac{p_y-p_i}{p_x-p_y}-g_y \frac{p_x-p_i}{p_x-p_y}\right)$$ as the coefficient for power [TeX:] $$p_i, i \in\{1, \cdots, n\} \backslash\{x, y\}.$$ Then, we traverse from power [TeX:] $$p_{y+1}$$ to power [TeX:] $$p_n,$$ we call this procedure as the first traversing procedure. During this traversing process, if we find that [TeX:] $$\left(g_j+g_x \frac{p_y-p_j}{p_x-p_y}-g_y \frac{p_x-p_j}{p_x-p_y}\right), j\gt y,$$ is a strictly positive number, then we change the coefficient of the power [TeX:] $$p_k$$ as [TeX:] $$\left(g_k+g_x \frac{p_j-p_k}{p_x-p_j}-g_j \frac{p_x-p_k}{p_x-p_j}\right), k \in\{1, \cdots, n\} \backslash\{x, j\} .$$ We keep on doing this procedure till we reach [TeX:] $$p_n.$$ Let us assume that during this traversing procedure [TeX:] $$p_i$$ is the last power for which we get a positive coefficient, then we define 𝑦 = 𝑖. Then, we start performing a second traversing procedure from the power [TeX:] $$p_{x-1}$$ to the power [TeX:] $$p_1.$$ During this traversing process, if we find that the coefficient of [TeX:] $$p_l, l\lt x,$$ is a strictly positive number, then we change the coefficient of the power [TeX:] $$p_k$$ as [TeX:] $$\left(g_k+g_l \frac{p_y-p_k}{p_l-p_y}-g_y \frac{p_l-p_k}{p_l-p_y}\right), k \in\{1, \cdots, n\} \backslash\{l, y\} .$$ We keep on doing this procedure till we reach [TeX:] $$p_1.$$ Let us assume that during this second traversing procedure [TeX:] $$p_r$$ is the last power for which we get a positive coefficient, then we define 𝑥 = 𝑟. Finally, the algorithm returns [TeX:] $$\left(\frac{\bar{p}-p_y}{p_x-p_y} z_x+\frac{p_x-\bar{p}}{p_x-p_y} z_y\right)$$ as an optimal e, where [TeX:] $$z_i$$ is the 𝑖th basis vector of [TeX:] $$\mathbb{R}^n \text {. }$$

We note that, Algorithm 1 finds an optimal solution in 𝑂(𝑛) time. Next, we prove the optimality of Algorithm 1.

Theorem 6. For a given blocking power pmf d, Algorithm 1 gives an optimal transmission power pmf e.

Proof: From (42), we have to solve the following problem,

For a given d finding an optimal e

The first two constraints ensure that [TeX:] $$e \in \mathcal{F}_e$$ and the last one is the constraint on the BS transmission power. Now, if [TeX:] $$\bar{p}\lt p_1,$$ then the optimization problem of (50) is infeasible. If [TeX:] $$p_n\lt \bar{p},$$ then the optimal solution for (50) is to choose [TeX:] $$p_n$$ with probability 1. If [TeX:] $$\bar{p}$$ is exactly equal to one of the feasible BS transmission powers, then the optimal solution for (50) is to choose that transmission power with probability 1. Now, we consider the case where [TeX:] $$p_x\lt \bar{p}\lt p_y.$$ First, we solve (50), ignoring the constraint [TeX:] $$0 \leq e_i \leq 1, i=1, \cdots, n.$$ Thus, the constraint set is given by

where 𝑠 is a slack variable. Now, we ignore the constraint [TeX:] $$s \geq 0$$ and pivoting on variables [TeX:] $$e_x \text { and } e_y \text {, }$$ we get the following constraints

Note that as [TeX:] $$p_x\lt \bar{p}\lt p_y,$$ the right hand sides in (52) for both the constraints are strictly positive. Now, replacing [TeX:] $$e_x \text { and } e_y$$ into the objective function of (50), we obtain

where [TeX:] $$h_i(x, y)=\left(g_i+g_x \frac{p_y-p_i}{p_x-p_y}-g_y \frac{p_x-p_i}{p_x-p_y}\right) .$$ Note that the coefficient of 𝑠 in (53) is always a negative number as [TeX:] $$g_x \leq g_y.$$ Now, assume that [TeX:] $$h_i(x, y)\lt 0, i \in\{1, \cdots, n\} \backslash\{x, y\}.$$ Then, [TeX:] $$e_i=0, i \in\{1,2, \cdots, n\} \backslash\{x, y\}$$ and and 𝑠 = 0 optimize (53). Thus, we get an optimal e as [TeX:] $$\left(\frac{\bar{p}-p_y}{p_x-p_y} z_x+\frac{p_x-\bar{p}}{p_x-p_y} z_y\right).$$

Now, let us assume that during the first traversing procedure, we observe that [TeX:] $$h_{y_1}(x, y)\gt 0,$$ where [TeX:] $$y_1=\min \left\{\bar{y} \mid y\lt \bar{y} \leq n, h_{\bar{y}}(x, y)\gt 0\right\} .$$ Now, if we pivot [TeX:] $$e_x \text { and } e_{y_1} \text {, }$$ we claim that [TeX:] $$h_{\bar{y}}\left(x, y_1\right) \leq 0, \bar{y} \in\left\{y, \cdots, y_1-1\right\} .$$ From the definition of [TeX:] $$y_1, h_{y_1}(x, y)=\left(g_{y_1}+g_x \frac{p_y-p_{y_1}}{p_x-p_y}-g_y \frac{p_x-p_{y_1}}{p_x-p_y}\right)\gt 0.$$ Thus,

As [TeX:] $$\frac{p_{y_1}-p_x}{p_x-p_y}\lt 0, h_y\left(x, y_1\right)\lt 0.$$ Now, consider [TeX:] $$h_{\bar{y}}\left(x, y_1\right) \text {, }$$ where [TeX:] $$y\lt \bar{y}\lt y_1.$$ From the previous discussion, we know that the following relations are true,

From (56), we get the following lower bound on [TeX:] $$g_y,$$

Now, substituting this lower bound to (57) and after simplification we get

that is, [TeX:] $$h_{y_1}(x, \bar{y})\gt 0$$ and from the above discussion we know that, this implies [TeX:] $$h_{\bar{y}}\left(x, y_1\right)\lt 0.$$ Now, similar arguments can be made for the whole first traversing procedure and the second traversing procedure as well. At the end of both traversing procedures if the pivot variables are [TeX:] $$e_{x_2} \text { and } e_{y_2}$$ then [TeX:] $$h_{\bar{y}}\left(x_2, y_2\right)\lt 0, \bar{y} \in\{1, \cdots, n\} \backslash\left\{x_2, y_2\right\}\lt 0$$ and from the previous discussion we know that we get an optimal e as [TeX:] $$\left(\frac{\bar{p}-p_{y_2}}{p_{x_2}-p_{y_2}} z_x+\frac{p_{x_2}-\bar{p}}{p_{x_2}-p_{y_2}} z_y\right) .$$

Algorithm 2 provides an optimal blocking power choosing pmf d for a given e. In Algorithm 2, we perform a similar traversing procedure as Algorithm 1. The only difference is while traversing in Algorithm 1, we change the coefficient of a power level if the corresponding coefficient is strictly positive, in Algorithm 2, we change the coefficient if it is strictly negative. Next, we state the optimality of Algorithm 2.

Theorem 7. For a given transmission power choosing pmf e, Algorithm 2 gives an optimal blocking power pmf d.

Theorem 7 can be proved by similar lines of arguments as in the proof for Theorem 6.

For a given e finding an optimal d

Next, we present a counter example which suggests that when the transmission power choosing pmf and the blocking power choosing pmf are not fixed and are part of the action space of the BS and the action space of the adversary, respectively, then a Nash equilibrium may not exist. Consider a system where the BS has three power levels and the adversary has also three power levels, i.e., 𝑛 = 𝑚 = 3. Both the power constraint for the BS and the adversary is 3.5 watts. The feasible powers for the BS and for the adversary are the same, which is [1, 3, 5]. The matrix F is chosen as

We can show that for this example, for a given d, e cannot be of the form [TeX:] $$\left[e_1, e_2, e_3\right],$$ where [TeX:] $$e_i\gt 0, i \in\{1,2,3\}$$ and satisfy [TeX:] $$\sum_{i=1}^3 e_i p_i \leq \bar{p}.$$ This can be shown by following the same line of arguments made in the proof for Theorem 6. Now, from Algorithm 1, we know that if the adversary chooses powers 3 and 5, then the optimal choice for the BS is to choose powers 3 and 5, similarly, if the adversary chooses powers 1 and 5, then the optimal choice for the BS is to choose powers 1 and 5. From Algorithm 2, we know that if the BS chooses powers 1 and 5, then the optimal choice for the adversary is to choose powers 3 and 5, similarly, if the BS chooses powers 3 and 5, then the optimal choice for the adversary is to choose powers 1 and 5. Thus, a Nash equilibrium does not exist for this example.

In the next theorem, we consider the Nash equilibrium when the transmission power choosing pmf and the blocking power choosing pmf are not included in the action space of the BS and in the action space of the adversary, respectively.

Theorem 8. The triplet of actions [TeX:] $$(\hat{\boldsymbol{u}}, \hat{\boldsymbol{s}}, \hat{\boldsymbol{a}})$$ is the Nash equilibrium point, where [TeX:] $$\hat{\boldsymbol{a}} \text { and } \hat{\boldsymbol{s}}$$ are the uniform pmfs over [TeX:] $$N_s$$ sub-carriers and [TeX:] $$\hat{\boldsymbol{u}}$$ is the uniform pmf over 𝑁 users.

Proof: First, we prove that [TeX:] $$(\hat{\boldsymbol{u}}, \hat{\boldsymbol{s}}, \hat{\boldsymbol{a}})$$ is a Nash equilibrium point, then we prove that this is the only possible Nash equilibrium point. From Theorem 4 and Theorem 5, it is clear that [TeX:] $$(\hat{\boldsymbol{u}}, \hat{\boldsymbol{s}}) \in B(\hat{\boldsymbol{a}}) \text { and } \hat{\boldsymbol{a}} \in B(\hat{\boldsymbol{u}}, \hat{\boldsymbol{s}}) \text {. }$$ Thus, [TeX:] $$(\hat{\boldsymbol{u}}, \hat{\boldsymbol{s}}, \hat{\boldsymbol{a}})$$ is a Nash equilibrium point. Now, assume that [TeX:] $$(\hat{\boldsymbol{u}}, \hat{\boldsymbol{s}}, \hat{\boldsymbol{a}})$$ is another Nash equilibrium point. From Theorem 4, it is clear that [TeX:] $$\Delta^{\hat{\boldsymbol{u}}, \check{\boldsymbol{s}}, \check{\boldsymbol{a}}} \leq \Delta^{\check{\boldsymbol{u}}, \check{\boldsymbol{s}}, \check{\boldsymbol{a}}}$$, the equality holds only when [TeX:] $$\check{\boldsymbol{u}}=\hat{\boldsymbol{u}}=\left[\frac{1}{N}, \frac{1}{N}, \cdots, \frac{1}{N}\right].$$ Without loss of generality, consider that [TeX:] $$\check{\boldsymbol{a}}=\left[\check{a}_1, \check{a}_2, \cdots, \check{a}_{N_s}\right] \text {, }$$ where [TeX:] $$\check{a}_1 \geq \check{a}_2 \geq \cdots \geq \check{a}_{N_s-l}\gt \check{a}_{N_s-l+1}=\check{a}_{N_s-l+2}=\cdots=\check{a}_{N_s} \text {. }$$ From the assumption and from Theorem 4, we can say that [TeX:] $$\sum_{i=N_s-l+1}^{N_s} \check{s}_i=1 .$$ However, from Theorem 5, we can say that [TeX:] $$\check{\boldsymbol{a}} \notin B(\check{\boldsymbol{u}}, \check{\boldsymbol{s}}).$$ Thus, the triplet [TeX:] $$(\check{\boldsymbol{u}}, \check{\boldsymbol{s}}, \check{\boldsymbol{a}})$$ cannot be a Nash equilibrium point. Hence, the Nash equilibrium unique.

Next, we present a special case in which the Nash equilibrium exists even when the transmission power choosing pmf and the blocking power choosing pmf are part of the action space of the BS and the action space of the adversary, respectively. Consider that the matrix F has the following property,

where [TeX:] $$l_i$$ are non-negative constants. Consider a fixed blocking power choosing pmf d. Then, [TeX:] $$g_i$$ in Algorithm 1 is

Thus,

Thus, the sign of [TeX:] $$g_i+g_x \frac{p_y-p_i}{p_x-p_y}-g_y \frac{p_x-p_i}{p_x-p_y}$$ does not depend on 𝒅, which implies that the optimal transmission power choosing pmf is the same for all d. Similarly, the sign of [TeX:] $$g_i+g_x \frac{p_y^{\prime}-p_i^{\prime}}{p_x^{\prime}-p_y^{\prime}}-g_y \frac{p_x^{\prime}-p_i^{\prime}}{p_x^{\prime}-p_y^{\prime}}$$ in Algorithm 2 does not depend on e, in other words the optimal blocking power choosing pmf is independent of e. Now, run Algorithm 1 for any arbitrary d and denote the output as [TeX:] $$\hat{e},$$ similarly run Algorithm 2 for any arbitrary e and denote the output as [TeX:] $$\hat{d} .$$ Then, using Theorem 8, we have that the 5 tuple [TeX:] $$(\hat{b}, \hat{c}, \hat{e}, \hat{a}, \hat{d})$$ is the unique Nash equilibrium.

V. NUMERICAL RESULT

We consider a system with two sub-carriers, four blocking power levels and four transmission power levels, i.e., [TeX:] $$N_s=2$$ 𝑚 = 𝑛 = 4. We assume that all sub-carriers are available to all users, i.e., [TeX:] $$N_{s, i}=N_s, i \in 1,2, \cdots, N \text {. }$$ We compare the performance of the policy [TeX:] $$\tilde{\tilde{\pi}}$$ and the policy [TeX:] $$\hat{\tilde{\pi}}$$ for varying numbers of users. The blocking power levels are 1, 2, 3 and 4, similarly, the transmission power levels are 1, 2, 3 and 4, the transmission power constraint [TeX:] $$\bar{p}=3.5$$ and the blocking power level constraint is [TeX:] $$\tilde{p}=3.$$ We assume that the matrix of probability of successful transmission F is,

For the simulations, we use the adversarial action [TeX:] $$\bar{\psi}$$, i.e., at each time slot the adversary chooses one of the two subcarriers uniformly and chooses the blocking power level 3. From Lemma 1, we know that the max-age user choosing policy and the uniform sub-carrier choosing policy are the optimal user choosing and the optimal sub-carrier choosing policy for the adversarial action [TeX:] $$\bar{\psi}$$, respectively. That is the reason we see in Fig. 2 that the lower bound of the average age and the average age for the policy [TeX:] $$\tilde{\tilde{\pi}}$$ are very close. Note that, the power choosing policies for both [TeX:] $$\tilde{\tilde{\pi}}$$ and [TeX:] $$\hat{\tilde{\pi}}$$ are the same, i.e., choose the power levels 3 and 4 with probability 0.5 each, however as the user choosing policy of [TeX:] $$\tilde{\tilde{\pi}}$$ is optimal for the adversarial action [TeX:] $$\bar{\psi}$$, we see that the policy [TeX:] $$\tilde{\tilde{\pi}}$$ outperforms [TeX:] $$\hat{\tilde{\pi}}$$ in terms of the average age. We also note in Fig. 2 that the performance gap between the policy [TeX:] $$\tilde{\tilde{\pi}}$$ and the policy [TeX:] $$\hat{\tilde{\pi}}$$ increases as we increase the number of users 𝑁. This can be intuitively explained as follows: Note that for the policy [TeX:] $$\hat{\tilde{\pi}}$$, the user choosing policy is the uniform user choosing policy and as 𝑁 increases the probability with which the BS chooses the maximum aged user decreases and as choosing the maximum aged user is the optimal user choosing policy for the adversarial action [TeX:] $$\bar{\psi}$$, the gap between the policies [TeX:] $$\tilde{\tilde{\pi}}$$ and [TeX:] $$\hat{\tilde{\pi}}$$ increases with 𝑁.

Fig. 2.

Comparison of the performances the the proposed algorithms.

VI. CONCLUSIONS

We considered a communication network with 𝑁 users, one BS, [TeX:] $$N_S$$ sub-carriers and one adversary. The BS transmits an update packet to the 𝑖th user via a communication channel from a subset of these [TeX:] $$N_S$$ communication channels, called [TeX:] $$\mathcal{N}_{s, i}$$. At each time slot, the BS transmits an update packet to a user via a communication channel to decrease the age of the system and the adversary aims to block this update packet to increase the age of the system. The BS has 𝑛 transmission powers and the adversary has 𝑚 blocking powers available. Both the BS and the adversary are subject to average power constraints. First, we determined a universal lower bound for the average age for this communication system. We showed that the uniform user choosing policy, the uniform sub-carrier choosing policy and any arbitrary power choosing policy is 4 optimal; and if [TeX:] $$\mathcal{N}_s = \mathcal{N}_{s, i}$$ and [TeX:] $$N_s$$ is large, then it is 2 optimal. We then showed that the max-age user choosing policy, the uniform sub-carrier choosing policy and any arbitrary power choosing policy is 2 optimal; and if [TeX:] $$\mathcal{N}_s = \mathcal{N}_{s, i}$$ and th BS power constraint exactly matches with one of the powers from the feasible BS powers, then it is the optimal scheduling policy. Second, we considered the scenario where [TeX:] $$\mathcal{N}_s = \mathcal{N}_{s, i}$$ and the BS chooses its scheduling policy, the adversary chooses its blocking policy from the set of stationary randomized policies. We found that if the power choosing policies are part of the action space of the BS and the action space of the adversary, then a Nash equilibrium may or may not exist. However, when those are not part of the action space of the BS and the adversary, then the uniform user choosing policy, the uniform sub-carrier choosing policy and the uniform subcarrier blocking policy form the Nash equilibrium point. Finding a Nash equilibrium point in the most general setting is an interesting research direction.