# A Coalition Formation Game Approach for Efficient Cooperative Multi-UAV Deployment
## 3 A Coalition Formation Game Approach for Coverage Utility Maximization
### Analysis of the Stable Coalition Partition  
(1) Utility Function: In Step 2, under fixed deployment, UAV \(n\)'s individual energy consumption can be expressed as follows:  
\[T1(c_{n})=\sum_{k\in\text{CO}_{\Pi}(n)}(E(d_{k,c_{l_{n}}})\cdot U_{k})+E(d_{0,c_ {l_{n}}})\cdot U_{CO_{\Pi}(n)}, \tag{17}\]  
where \(g_{cn}^{cl}\) represents the three-dimensional position of coalition \(c_{n}\)'s cluster head UAV. \(T1(c_{n})\) represents the coalition \(c_{n}\)'s data traffic energy consumption from the terrestrial to the central controller. Then, for each UAV \(n\in\mathcal{N}\), it makes coalition selection through its individual coverage utility, which can be derived as follows:  
\[u_{n}(c_{n},c_{-n})=u_{n}^{*}(g_{n},g_{-n})-\rho\cdot E_{0}(c_{n}). \tag{18}\]  
In Definition 1, the preference relation is introduced, which decides whether a player prefers to join or leave the coalition. Notably, the preference relation can affect the convergence and the stable state of the final structure of CFG [30]. Next, an ordinary preference order called Pareto order is adopted to analyze the property of the proposed game model. **Definition 4** (Pareto order). : _In CFG, its preference relation \(\succ_{n}\) satisfies Pareto order if for each player \(n\in\mathcal{N}\) and all coalition partition \(CO^{\prime},CO\in\Pi\), there exists the following formula:_  
\[ \begin{split} CO\succ_{n}CO^{\prime}\Longleftrightarrow& u_{n}(CO)>u_{n}(CO^{\prime})\wedge u_{i}(CO)>u_{i}(CO\setminus n),\ \forall i\in CO\setminus\{n\},\\ & u_{i}(CO^{\prime})<u_{i}(CO^{\prime}\setminus n),\ \forall i\in CO^{\prime}\setminus\{n\}.\end{split}  \tag{19}\]  
In Pareto order, each player \(n\) obeys the principle that they won't make strategy damage the utility of other players \(i\) in the original or new coalition. Hence, the profit of all coalition partition will not decrease. Due to the limited profit players can get, Pareto order can be a very strong proof of stable coalition partition. The UAVs' coalition selection satisfies the definition of preference profiles, which also indicates that \(\mathcal{G}_{2}\) is a typical CFG according to Definition 1. Typically, in a CFG, the most important part is the formation criteria, which determines the structure of coalitions. Here, we consider the Pareto order [31], which rests with the preference on the individual payoffs of the players rather than the coalition value [22]. Afterwards, the coalition formation rule is required when the preference order is determined. Authors in [32] introduced a merge and split rule, which is used for forming or breaking coalition. Both rules focus on the profits of all the players in the coalition. For example, any pair of coalition \(CO\) and \(CO^{\prime}\) can be merged into one coalition when all the players have an increased profit. On thecontrary, a coalition can be split into coalition \(CO\) and \(CO^{\prime}\) since each players in their new coalition can achieve a better profit. It is noted that, according to Equation (18), for each UAV \(n\), the first item of its individual coverage utility function is fixed due to the stability of \(\mathcal{G}_{1}\). (2) Analysis of CFG: In this part, we analyze the stability of the proposed CFG through the given preferences and rules, and then solve the problem. **Definition 5** (Stable coalition partition [19]). : _A partition \(\Pi\) is said to be stable if no player can improve its utility by arbitrarily change its strategy, i.e., if_  
\[u_{n}(c_{n},c_{-n})\geq u_{n}(c_{n},c^{\prime}_{-n}),\ \forall n\in\mathcal{N}, \forall c_{n},c^{\prime}_{n}\in C_{n},c_{n}\
eq c^{\prime}_{n}, \tag{20}\]  
_then \(\Pi\) is thought to have a stable coalition partition._  
**Theorem 1**. : _With the preference relation of Pareto order, the CFG \(\mathcal{G}_{2}\) can be converged to the stable coalition partition._  
Proof.