## 4 The Coalition Formulation Game Model
### Coalition Formation Basic Concepts  
**Definition 1**. : _A distributed coalition game \(\mathcal{G}_{\mathcal{D}}\) with non-transferable utility (NTU) is defined by an ordered pair \((\mathcal{S},\,\mathcal{V})\), where \(\mathcal{S}\) represents the finite set of players (i.e., UAVs), and \(\mathcal{V}\) is a partition function, \(\mathcal{V}:\prod{(\mathcal{S})}\rightarrow\mathbb{R}^{\mathcal{S}}\) that maps, for every partition \(\prod{(\mathcal{S})}\) and coalition \(Q_{K}\in\prod{(\mathcal{S})}\), \(Q_{K}\
eq\varnothing\), to a closed convex subset of \(\mathbb{R}^{|Q_{K}|}\) that contains the payoff vectors that players in a coalition \(Q_{K}\) can achieve._Here, we note that the empty set in \(\mathcal{S}\) is \(0\), namely, \(v(\emptyset)=0\). A coalition denoted by \(S_{K}\) is defined as a nonempty subset of players over \(\mathcal{S}=\{1,2,\ldots,N\}\), where \(S_{K}\subseteq\mathcal{S}\). Each player \(i\in\mathcal{S}\) can freely join only one coalition. In the proposed game \(\mathcal{G}_{\mathcal{D}}=(\mathcal{S},\ \mathcal{V})\), all the \(N\) UAVs can autonomously organize according to the environment and choose their potential members with which to cooperate and to form coalitions. Subsequently, all the members in a coalition share their initial fixed time slot resources, that is, the UAVs in a coalition \(S_{K}\) can achieve \(|S_{K}|\) transmitting time slots. **Definition 2**. : _In the disjoint coalition game \(\mathcal{G}_{\mathcal{D}}=(\mathcal{S},\ \mathcal{V})\), a coalition structure denoted by \(\pi\) is defined as a set of \(\pi=\{S_{1},S_{2},\ldots,S_{M}\}\), where \(M\) is the number of coalitions, \(1\leq M\leq N,\bigcup_{i=1}^{M}S_{i}=\mathcal{S}\). Here, \(\exists S_{i},S_{j}\in\pi,i\
eq j\) such that \(S_{i}\cap S_{j}=\emptyset\)._  
The grand coalition is defined as a coalition containing all UAVs. In the network, \(2^{N}-1\) distinct nonempty coalitions and \(D_{N}\) different coalitional structures for \(N\) players can be formed:  
\[D_{N}=\left\{ \begin{aligned} \sum_{j=0}^{N-1}C_{N-1}^{j}D_{j},& \quad N\geq 1\\ 1,&\quad N=0\end{aligned} \right. \tag{16}\]  
**Definition 3**. : _For a given partition \(\pi\), we define the utility function of the coalitional structure \(\pi\) as \(v(\pi)=\sum_{j=1}^{M}v(S_{j},\pi)\), where \(v(S_{j},\pi)\) denotes the utility function of the coalition \(S_{j}\in\pi\). In such a case, the utility of coalition \(S_{j}\) can be defined as \(v(S_{j},\pi)=\sum_{i\in S_{j}}u_{i}(S_{j},\pi)\), where \(u_{i}(S_{j},\pi)\) is the individual payoff of UAV-\(i\) in coalition \(S_{j}\in\pi\)._  
\[u_{i}\big{(}S_{j},\pi\big{)}=\sum_{t\in T_{S_{j}}}R_{i}(t) \tag{17}\]  
\(R_{i}(t)\) _is the throughput at time slot \(t\) of UAV-\(i\), which is illustrated in (8), and \(T_{S_{j}}\) is the available time slots of the coalition \(S_{j}\in\pi\). Since each UAV-\(i\) has a fixed transmitting time slot \(i\), \(T_{S_{j}}=S_{j}=\left\{j_{1},j_{2},\ldots,j_{|S_{j}|}\right\}\). In this sense, the disjoint coalition can also be seen as the coalition of time slots._  
Note that \(v(\pi)\) can also be described as the system payoff, which is calculated as the sum of the payoff of each coalition in \(\pi\). This coalition game has a non-transferable utility (NTU), which means that the payoff of each UAV in a coalition \(S_{j}\) cannot be arbitrarily allotted. It is not hard to understand that the utility function satisfies the hyper-additive \(\forall S_{i},S_{j}\in\pi\); if \(S_{i}\cap S_{j}=\emptyset\), then \(v\big{(}S_{i}\cup S_{j}\big{)}\geq v(S_{i})+v\big{(}S_{j}\big{)}\). As an example, in Figure 1, we assume that the 16 UAVs in the multi-UAV network form a given partition: \(\pi=\{\{1\},\{2\},\{3,16\},\ \{4,8,13\},\ \{5,6,7\},\ \{9,10,11\},\{12,14,15\}\}\). The payoff of UAV-1 is \(u_{1}(\{1\},\pi)=R_{0}\), since there is only one player in the coalition and one slot to transmit. Then, the utility of the coalition \(\{1\}\) is \(v(\{1\},\pi)=R_{0}\). In the coalition \(\{3,16\}\), the two elements are so far away that they have no collision with each other.