# A Coalition Formation Game Approach for Efficient Cooperative Multi-UAV Deployment
## 3 A Coalition Formation Game Approach for Coverage Utility Maximization
### Algorithm Design of CFG Model  
Based on the existence of the stable state in the above section, next we are going to solve the stable stable of \(\mathcal{G}\) by designing an algorithm. However, due to the diversity of UAV set and strategy sets (position and coalition), the kind of optimal selection approach often falls into a trap loop, that is, local optimum.  
In that case, learning algorithms need to be applied to explore the stable state of game. Motivated by the exploring mechanism of a distributed learning algorithm called spatial adaptive play (SAP) in [27], we designed a coalition selection and position deployment algorithm based on Pareto order (CSPDA-PO) to converge the proposed model to the stable coalition state. In each iteration of the algorithm, the chosen UAV updates its coalition selection and makes a comparative update under Pareto order, while all the other UAVs maintain their current selection strategy. Learning from Theorem 1, the stable solution of \(\mathcal{P}_{1}\) can be solved out. In the following table, Algorithm 2 demonstrates procedures of CSPDA-PO. In Equation (16), \(q^{\mathcal{S}}_{n}(t)\) represents the coalition selection probability function of UAV \(n\). \(\beta\) is the learning parameter (\(\beta>0\)).  
Combining the existence of NE in \(\mathcal{G}_{1}\) with the existence of stable coalition partition in \(\mathcal{G}_{2}\), our proposed method can converge the problem \(\mathcal{P}_{1}\) to a stable state solution.  
**Initialization:** Set \(j=1\) and the position of central UAV \(g^{ccn}\), initialize UAVs' state \(s_{n}=\{g_{n},c_{n},n\in\mathcal{N}\}\) and mission area \(I\)'s state \(\sigma(i),i\in I\). Specially, each UAV \(n\in\mathcal{N}\) chooses different coalition from \(C_{n}\).  
**Loop:**  
**Step 1:** All UAVs in the network exchange information (coverage deployment and coalition selection) with each other.  
**Step 2:** Randomly select one UAV at each iteration, says \(n\). Input UAVs' current position profiles \(\{s_{n}\}_{n\in\mathcal{N}}\) to Algorithm 1 and obtain optimal coverage deployment \(\{s_{n}^{opt}\}_{n\in\mathcal{N}}\) under given coalition selections of UAVs. \(\{s_{n}\}_{n\in\mathcal{N}}\longleftarrow\{s_{n}^{opt}\}_{n\in\mathcal{N}}\).  
**Step 3:** All the other UAVs repeat the previous coalition selection, i.e., \(c_{k}(j+1)=c_{k}(j),k\in\mathcal{N}\backslash n\). For the choosing UAV \(n\), it changes its coalition selection to \(c_{n}^{\prime}\in C_{n}\backslash c_{n}\). Update \(s_{n}^{\prime}=\{g_{n}^{opt},c_{n}^{\prime}\}\) and input \(\{s_{n}^{\prime}\}_{n\in\mathcal{N}}\) to Algorithm 1, obtain optimal coverage deployment \(s_{n}^{opt}\) under a given coalition selection for UAV \(n\). \(\{s_{n}^{\prime}\}_{n\in\mathcal{N}}\longleftarrow\{s_{n}^{opt}\}_{n\in \mathcal{N}}\).  
**Step 4:** Set \(CO=CO_{c_{n}},CO^{\prime}=CO_{c_{n}^{\prime}}\); then, UAV \(n\) calculates its coverage utility \(u_{n}(j)\) on the original and expected coalition and updates its strategy according to Definition 4 (Pareto order), where the relationships of utility are explored using probability formula according to Equation (21):  
\[q_{n}^{c}(j)=\frac{exp\{\beta u_{n}(c_{n},c_{-n})(j)\}}{exp\{\beta u_{n}(c_{n},c _{-n})(j)\}+exp\{\beta u_{n}(c_{n}^{\prime},c_{-n})(j)\}}, \tag{21}\]  
where \(\beta\) is the learning parameter (\(\beta>0\)) and can be used to adjust convergence performance and speed.  
**Step 5:**\(j=j+1\). If the stop criterion* is satisfied, output UAVs' state \(\{s_{n}\}_{n\in\mathcal{N}}\); otherwise, go to Step 1.  
* Stop criterion can be described as the following rules: \(q_{n}^{c}(j)\) is more than a certain value like 0.98 or \(j\) reaches a predefined maximum number of iteration steps.