# Neighbor-Aware Non-Orthogonal Multiple Access Scheme for Energy Harvesting Internet of Things
## 4 Constrained Stochastic Game
### Optimization Formulation  
When \(\pi\) denotes a stationary policy of all players (i.e., IoT devices), a long-term average aggregated data rate \(\zeta_{R}\) can be defined as  
\[\zeta_{R}(\pi)=\lim_{T\rightarrow\infty}\frac{1}{T}\sum_{t=1}^{T}E_{\pi}\big{[} r\big{(}S^{t},A^{t}\big{)}\big{]} \tag{12}\]where \(S^{t}\) and \(A^{t}\) are the global state and the action at time \(t\), respectively. Meanwhile, IoT device \(i\) tries to maintain the long-term energy outage probability \(\zeta_{E}\) below a certain level, which can be described by  
\[\zeta_{E}(\pi)=\lim_{T\to\infty}\frac{1}{T}\sum_{t=1}^{T}E_{\pi}\big{[}c\big{(}S ^{t},A^{t}\big{)}\big{]}\leq\theta_{E} \tag{13}\]  
where \(\theta_{E}\) is the target energy outage probability. Let \(\pi_{i}^{*}\) and \(\pi_{i}^{*}\) denote the optimal policies (i.e., Nash equilibrium) (note that, if a stochastic game is formulated with a finite number of players, states, and actions, there is always Nash equilibrium of the game [27]) of IoT device \(i\) and all devices except IoT device \(i\), respectively. Then, the integrated optimal policy (i.e., constrained Nash equilibrium) can be described by \(\pi^{*}=\big{(}\pi_{i}^{*},\pi_{-i}^{*}\big{)}\). Note that, for any other stationary policy \(\pi_{i}\) of IoT device \(i\), \(\zeta_{R}\big{(}\big{(}\pi_{i}^{*},\pi_{-i}^{*}\big{)}\big{)}\geq\zeta_{R} \big{(}\big{(}\pi_{i}^{*},\pi_{-i}^{*}\big{)}\big{)}\) while satisfying the constraint. Meanwhile, when the policies of all IoT devices except IoT device \(i\) (i.e., \(\pi_{-i}\)) are given, the optimal policy \(\pi_{i}^{*}\) of IoT device \(i\) (i.e., best response policy) should satisfy the inequality \(\zeta_{R}\big{(}\big{(}\pi_{i}^{*},\pi_{-i}\big{)}\big{)}\geq\zeta_{R}\big{(} \big{(}\pi_{i}^{*},\pi_{-i}\big{)}\big{)}\). When \(\phi_{i,\pi_{-i}}(S_{i},A_{i})\) denotes the stationary probability that IoT device \(i\) chooses the action \(A_{i}\) in local state \(S_{i}\) with the given stationary policies of other IoT devices \(\pi_{-i}\), we can formulate the equivalent LP model and its solution \(\phi_{i,\pi_{-i}}^{*}(S_{i},A_{i})\) can be interpreted as the optimal policy of the formulated game [28]. The LP model can be formulated as  
\[\max_{\phi(S,A)}\sum_{S}\sum_{A}\phi_{i,\pi_{-i}}(S_{i},A_{i})r(S_{i},A_{i}) \tag{14}\]  
\[\text{s.t.}\quad\sum_{S}\sum_{A}\phi_{i,\pi_{-i}}(S_{i},A_{i})c(S_{i},A_{i}) \leq\theta_{B} \tag{15}\]  
\[\sum_{A}\phi_{i,\pi_{-i}}\big{(}S_{i}^{\prime},A_{i}\big{)}=\sum_{S}\sum_{A} \phi_{i,\pi_{-i}}(S_{i},A_{i})P[S_{i}^{\prime}|S_{i},A_{i}] \tag{16}\]  
\[\sum_{S}\sum_{A}\phi_{i,\pi_{-i}}\big{(}S_{i}^{\prime},A_{i}\big{)}=1 \tag{17}\]  
\[\phi_{i,\pi_{-i}}\big{(}S_{i}^{\prime},A_{i}\big{)}\geq 0 \tag{18}\]  
For maximizing the aggregated average data rate of IoT devices, we define the objective function in (14). The average energy outage probability can be maintained below the target energy outage probability \(\theta_{E}\) by the constraint in (15). The Chapman-Kolmogorov equation is represented in the constraint in (16). The basic probability properties can be satisfied with the constraints in (17) and (18). The optimal policy of IoT device \(i\) is given by  
\[\pi_{i}^{*}(S_{i},A_{i})=\frac{\phi_{i,\pi_{-i}}^{*}(S_{i},A_{i})}{\sum\limits \limits_{A_{i}^{\prime}\in A_{i}}\phi_{i,\pi_{-i}}^{*}(S_{i},A_{i}^{\prime})}. \tag{19}\]  
To achieve the optimal policies (i.e., best response policies) of IoT devices, we develop a best response dynamics-based algorithm as in Algorithm 1. First, the policy for all IoT devices is initialized (line 1 in Algorithm 1). After that, IoT devices share the channel gain with each other (line 2 in Algorithm 1). (We assume that the channel gain is stable until the algorithm is done. This assumption is reasonable because few iterations are needed to converge the optimal policies (see Section 5.1).) Meanwhile, each IoT device transmits the expected transmission power \(\overline{A_{i}}\) to other IoT devices to interact with each other (line 5 in Algorithm 1).