## 5 Algorithm Design
### Offloading Decision  
When \(f_{i,\text{S}}^{*}\) and \(f_{i,\text{B}}^{*}\) are given, \(\mathcal{P}\) can be reformulated to the problem \(\mathcal{P}\)2. \[\min_{\{x_{i,0},x_{i},s_{i},x_{i,\rm B}\}}\;\sum_{i\in\mathcal{N}}\left[x_{i,0} \frac{c_{i}a_{i}}{f_{i,0}}+x_{i,\rm S}\bigg{(}\frac{a_{i}}{r_{i,\rm S}}+\frac{2d _{i,\rm S}}{c}+\frac{c_{i}a_{i}}{f_{i,\rm S}}\bigg{)}+x_{i,\rm B}\bigg{(}\frac{a _{i}}{r_{i,\rm S}}+\frac{2d_{i,\rm S}}{c}+\frac{a_{i}}{r_{\rm S,\rm G}}+\frac{2d _{\rm S,\rm G}}{c}+\frac{c_{i}a_{i}}{f_{i,\rm B}}\bigg{)}\right] \tag{23}\]  
s.t. (7f) and (7g). This is an integer programming (IP) problem, which is difficult to solve by traditional optimization methods, e.g., the convex optimization [30]. Because computing resources of the LEO satellite's MEC server and the BS's MEC server are limited, there is a fierce competition for them among UEs. Therefore, this paper considers \(\mathcal{P}2\) as a multi-UEs task offloading game and uses the game theory approach to solve it, so as to obtain an approximate optimal solution within acceptable time. \(\mathcal{P}2\) can be constructed as a game \(\mathcal{G}=\{\mathcal{N},\mathcal{Y}_{i},V_{i}\}\), where \(\mathcal{N}\) is the set of participants, i.e., UEs. \(\mathcal{Y}_{i}=\{0,1,2\}\) is the strategy space, i.e., the set of all optional task offloading strategies of UE \(i\), and \(y_{i}\) represents the task offloading decision of UE \(i\). \(y_{i}=0\) denotes \(\{x_{i,0}=1,x_{i,\rm S}=0,x_{i,\rm B}=0\}\), \(y_{i}=1\) denotes \(\{x_{i,0}=0,x_{i,\rm S}=1,x_{i,\rm B}=0\}\), \(y_{i}=2\) denotes \(\{x_{i,0}=0,x_{i,\rm S}=0,x_{i,\rm B}=1\}\). \(V_{i}\) is the payoff function of UE \(i\), because the payoff needs to be maximized, and \(U_{i}\) should be minimized, so \(V_{i}=-U_{i}\). \(V_{i}(y_{i},y_{-i})\) represents the payoff that UE \(i\) selects \(y_{i}\) when \(y_{-i}\) is given, where \(y_{-i}\) indicates the task offloading decisions of UEs except UE \(i\). In the game process, each UE is purely rational or selfish, hoping to make the task offloading decision that can obtain the most payoff. The decision of each UE affects the payoffs of other UEs, so it is necessary to obtain an optimal decision set recognized by all UEs [31]. This is the solution of the game process, i.e., NE, which is defined as follows:  
**Definition 1**. : _Nash equilibrium. If and only if no UE \(i\) can unilaterally change its task offloading decision to increase its own payoff when the task offloading decisions of other UEs remain unchanged, the task offloading decision set \(y^{*}=\big{(}y^{*}_{1},y^{*}_{2},y^{*}_{3},\ldots,y^{*}_{N}\big{)}\) is an NE of \(\mathcal{G}\) and can be expressed as \(V_{i}(y^{*}_{i},y^{*}_{-i})\geq V_{i}(y_{i},y^{*}_{-i}),\forall i\in\mathcal{ N},\forall y^{*}_{i},y_{i}\in\mathcal{Y}_{i},y^{*}_{i}\
eq y_{i}\)._  
In this case, the game reaches an equilibrium state, and the task offloading decision set can be accepted by all UEs. The EPG is defined as follows:  
**Definition 2**. : _Exact potential game. If and only if there exists a potential function \(\Gamma\), which satisfies \(V_{i}(y_{i},y_{-i})-V_{i}(y^{\prime}_{i},y_{-i})=\Gamma(y_{i},y_{-i})-\Gamma(y ^{\prime}_{i},y_{-i}),\forall i\in\mathcal{N},\forall y_{i},y^{\prime}_{i}\in \mathcal{Y}_{i},y_{i}\
eq y^{\prime}_{i}\). The game is an EPG [32]._  
No matter which UE changes its task offloading decision, its payoff function and potential function will show the same variation tendency. **Corollary 1**. : \(\mathcal{G}\) _is an EPG with at least one pure strategy NE and finite improvement property (FIP)._  
Proof of Corollary 1.: The potential function is set to be \(\Gamma(y_{i},y_{-i})=-\sum_{i\in\mathcal{N}}U_{i}(y_{i},y_{-i})\). When UE \(i\) changes \(y_{i}\) to \(y^{\prime}_{i}\). The variation of its payoff function is \(V_{i}(y_{i},y_{-i})-V_{i}(y^{\prime}_{i},y_{-i})=-U_{i}(y_{i},y_{-i})+U_{i}(y^{ \prime}_{i},y_{-i})\).