# Resource- and Neighbor-Aware Observation Transmission Scheme in Satellite Networks
## 4 Constrained Stochastic Game
### Optimization Formulation  
If a stationary multipolicy of all observation satellites \(\pi\) is given, a long-term average delay \(\zeta_{D}\) to deliver the observation to the destination can be defined as  
\[\zeta_{D}(\pi)=\lim_{T\to\infty}\frac{1}{T}\sum_{t=1}^{T}E_{\pi}\big{[}r\big{(}S ^{t},A^{t}\big{)}\big{]} \tag{15}\]  
where \(S^{t}\) and \(A^{t}\) are the global state and the action at time \(t\), respectively. Meanwhile, observation satellite \(i\) tries to keep the average utilization of its computational and storage resources below certain levels. The constraints for the average utilization of computational and storage resources, \(\zeta_{C}\) and \(\zeta_{S}\), can be represented as  
\[\zeta_{C}(\pi)=\lim_{T\to\infty}\frac{1}{T}\sum_{t=1}^{T}E_{\pi}\big{[}c_{C} \big{(}S^{t},A^{t}\big{)}\big{]}\leq\theta_{C} \tag{16}\]  
and  
\[\zeta_{S}(\pi)=\lim_{T\to\infty}\frac{1}{T}\sum_{t=1}^{T}E_{\pi}\big{[}c_{S} \big{(}S^{t},A^{t}\big{)}\big{]}\leq\theta_{S} \tag{17}\]  
where \(\theta_{C}\) and \(\theta_{S}\) denote the target utilization of the computational and storage resources, respectively. Let \(\pi_{i}^{*}\) and \(\pi_{-i}^{*}\) denote the optimal policies (i.e., Nash equilibrium) of observation satellite \(i\) and all observation satellites except observation satellite \(i\), respectively. Consequently, the optimal multipolicy (i.e., constrained Nash equilibrium) can be described by \(\pi^{*}=\big{(}\pi_{i}^{*},\pi_{-i}^{*}\big{)}\). (When a stochastic game is constructed with a finite number of players, states, and actions, there is always Nash equilibrium (i.e., optimal solution) in the game [19].) Note that, for any other stationary policy \(\pi_{i}\) of observation satellite \(i\), \(\zeta_{D}\big{(}(\pi_{i}^{*},\pi_{-i}^{*})\big{)}\geq\zeta_{D}\big{(}(\pi_{i},\pi_{-i}^{*})\big{)}\) while satisfying all constraints. Meanwhile, when the policies of all observation satellites except observation satellite \(i\) (i.e., \(\pi_{-i}\)) are given, the optimal policy \(\pi_{i}^{*}\) of observation satellite \(i\) (i.e., best-response policy) should satisfy the inequality \(\zeta_{D}\big{(}(\pi_{i}^{*},\pi_{-i})\big{)}\leq\zeta_{D}\big{(}(\pi_{i},\pi_ {-i})\big{)}\). Let \(\phi_{i,\pi_{-i}}(S_{i},A_{i})\) represent the stationary probability that observation satellite \(i\) chooses the action \(A_{i}\) in local state \(S_{i}\) when the stationary policies of other observation satellites \(\pi_{-i}\) are given. Then, we can formulate the equivalent linear programming (LP) model and its solution \(\phi_{i,\pi_{-i}}^{*}(S_{i},A_{i})\) can be interpreted as the optimal policy of the formulated game [22; 23; 24]. The LP model can be formulated by  
\[\min_{\phi(S,A)}\sum_{S}\sum_{A}\phi_{i,\pi_{-i}}(S_{i},A_{i})r(S_{i},A_{i}) \tag{18}\]  
\[\text{s.t.}\ \ \sum_{S}\sum_{A}\phi_{i,\pi_{-i}}(S_{i},A_{i})c_{C}(S_{i},A_{i}) \leq\theta_{C} \tag{19}\]  
\[\sum_{S}\sum_{A}\phi_{i,\pi_{-i}}(S_{i},A_{i})c_{S}(S_{i},A_{i})\leq\theta_{S} \tag{20}\]  
\[\sum_{A}\phi_{i,\pi_{-i}}  
\[\phi_{i;\pi_{-i}}(S_{i}^{\prime},A_{i})\geq 0 \tag{23}\]  
In order to minimize the delay to deliver the observation to the destination from observation satellite \(i\), the objective function in (18) is designed. Meanwhile, the average utilization of the computational and storage resources can be maintained below the desired levels \(\theta_{C}\) and \(\theta_{S}\) by the constraints in (19) and (20), respectively. The constraint in (21) is for the Chapman-Kolmogorov equation derived by the chain rule for the probability and Markov property. The basic probability properties can be constrained by (22) and (23). If any feasible solution of the LP problem exists, the stationary best-response policy of observation satellite \(i\) can be obtained as [25].