# A Coalition Formation Game Approach for Efficient Cooperative Multi-UAV Deployment
## 3 A Coalition Formation Game Approach for Coverage Utility Maximization
### Analysis of the Mission Reward Maximization  
(1) Utility Function: As discussed before, each UAV prefers a higher coverage performance and less energy consumption of transmission. Accordingly, we consider the UAV \(n\)'s marginal coverage contribution and measure the coverage utility of mission area \(I\) of UAV \(n\) as follows:  
\[u_{n}^{*}(g_{n},g_{-n})=\int\limits_{I}h\Big{(}\min\limits_{k\in\mathcal{N}}( \|g_{k}-g_{i}^{*}\|\Big{)}\sigma(i)di-\int\limits_{I}h\Big{(}\min\limits_{k\in \mathcal{N}\setminus n}(\|g_{k}-g_{i}^{*}\|\Big{)}\sigma(i)di-\rho\cdot E_{0}( CO_{n}). \tag{9}\]  
In Step 1, given the method that coverage optimization deployment should be done before coalition selection each loop, we have the following equation:  
\[\mathcal{P}_{1}:\max u_{n}^{*}(g_{n},g_{-n}). \tag{10}\]  
(2) Analysis of \(\mathcal{G}_{1}\): Considering that the cooperative behaviours among UAVs should be well depicted, a potential game is adopted, which applies to a distributed multi-agent system and can associate with the local utility and global utility of each participant [26]. Hence, combining with the distributed self-organizing characteristics of UAVs, the whole system can make decisions to achieve more efficient performance. Here, the definition of Nash equilibrium (NE) is shown in the following, indicating the steady state of a noncooperative game. **Definition 2** (**Nash equilibrium (NE) [27]**). : _A position selection profile \(g^{*}=(g_{n}^{*},\ldots,g_{-n}^{*})\) is a pure strategy NE of game \(\mathcal{G}_{1}=(\mathcal{N},\{S_{n}\}_{n\in\mathcal{N}},\{u_{n}^{*}\}_{n\in \mathcal{N}})\) if and only if no player \(n\) can improve its utility by changing its states, i.e.,_  
\[u_{n}^{*}(g_{n}^{*},g_{-n}^{*})\geq u_{n}^{*}(g_{n},g_{-n}^{*}),\ \forall n\in \mathcal{N},\forall g_{n}\in G_{n},g_{n}\
eq g_{n}^{*}. \tag{11}\]  
**Definition 3** (**Exact potential game (EPG) [28]**). : _For utility function \(u_{n}^{*}(g_{n},g_{-n})\) in a game \(\mathcal{G}_{1}=(\mathcal{N},\{S_{n}\}_{n\in\mathcal{N}},\{u_{n}^{*}\}_{n\in \mathcal{N}})\), if there exists a potential function \(\phi:G_{n}\rightarrow\mathbb{R}\), for arbitrary position strategy selection changes from \(g_{n}\) to \(g_{n}^{\prime}\), the following equation is true:_  
\[u_{n}^{*}(g_{n},g_{-n})-u_{n}^{*}(g_{n}^{\prime},g_{-n})=\phi(g_{n},g_{-n})- \phi(g_{n}^{\prime},g_{-n}),\quad\forall n\in\mathcal{N},\forall G_{n},g_{n}^ {\prime}\in G_{n}. \tag{12}\]_Then, this game is called exact potential game and has at least one NE point._  
**Lemma 1**. : _Given that the current coalition partition \(\Pi\), \(\mathcal{G}_{1}\) is an EPG and has at least one NE point._  
Proof. : Here, we construct the potential function as follows:  
\[\phi(g_{n},g_{-n})=\int\limits_{I}h\big{(}\min\limits_{k\in\mathcal{N}}\|g_{k} -g_{i}^{*}\|\big{)}\sigma(i)di-\rho\cdot E_{0}(CO), \tag{13}\]  
which also represents the global coverage utility of UAV network. Assume that an arbitrary UAV \(n\) changes its position profile from \(g_{n}\) to \(g_{n}^{\prime}\); then, we have the following formulation:  
\[ \begin{split} u_{n}^{*}(g_{n},g_{-n})-u_{n}^{*}(g_{n}^{\prime},g_ {-n})&=\int\limits_{I}h\Big{(}\min\limits_{k\in\mathcal{N}}(\|g_ {k}-g_{i}^{*}\|\big{)}\sigma(i)di-\int\limits_{I}h\Big{(}\min\limits_{k\in \mathcal{N},g_{n}=g_{n}^{\prime}}(\|g_{k}-g_{i}^{*}\|\Big{)}\sigma(i)di\\ -\int\limits_{I}h\Big{(}\min\limits_{k\in\mathcal{N}\setminus n }(\|g_{k}-g_{i}^{*}\|\Big{)}\sigma(i)di+\int\limits_{I}h\Big{(}\min\limits_{ k\in\mathcal{N}\setminus n,g_{n}=g_{n}^{\prime}}(\|g_{k}-g_{i}^{*}\|\Big{)} \sigma(i)di+\rho\cdot(E_{0}(CO_{n}^{\prime})-E_{0}(CO_{n})).\end{split}  \tag{14}\]  
Intuitively, for each UAV \(k\in\mathcal{N}\setminus n\), its individual coverage performance is completely unaffected by the above action changes, in addition to the energy consumption of UAV set \(CO_{k},k\in\mathcal{N}\setminus c_{n}\). Thus, the results of the last four items from Equation (14) are identical: zero.