# Traffic Offloading in Unlicensed Spectrum for 5G Cellular Network: A Two-Layer Game Approach
## 4 Coalition Game
### Merge-and-Split Based Coalition Formation Algorithm  
In this section, a distributed coalition formation algorithm is shown in Algorithm 2. We construct this algorithm based on rules denoted as \"merge-and-split\" which permits to modify a partition of \(T\)```
1: Define \(K\) coalitions as \(S=\{S_{1},S_{2},...,S_{K}\}\) in the network and every coalition has an AP at the start of the coalition game. 2:Initialization:\(v_{d}^{*}=0\), \(S_{d}^{*}=\phi\)
3:for\(i,j\in S\)do
4:if\(\
u(S_{i})\cup\
u(S_{j})>\
u(S_{i})\)then
5:\(\
u(S_{i})=\
u(S_{i})\cup\
u(S_{j})\), \(S_{j}=\phi\)
6:else
7:if\(\
u(S_{i})\cup\
u(S_{j})<\
u(S_{i})\)then
8:\(\
u(S_{i})=\
u(S_{i})\setminus\
u(S_{j})\)
9:endif
10:endif
11:if\(\
u(S)>\
u^{*}\)then
12:\(v_{d}^{*}=\
u(S)\)
13:\(S_{d}^{*}=S\)
14:endif
15:endfor
```

**Algorithm 2** Distributed Coalition Formation Algorithm. We define the merging rule as: For \(\
u(i)\geq 0\), if \(\
u(S\cup i)>\
u(S)\), the player \(i\) would join in this coalition. In addition, we define the splitting rule as: For \(\
u(i)\geq 0\), if \(\
u(S\setminus i)>\
u(S)\), the player \(i\) would get away from this coalition. Three states in the coalition based on merge-and-split rule are shown when a new period begins or any player joins or leaves the coalition spontaneously. 1. Initial State. Each AP node is a single coalition and \(K\) coalitions are formed totally. 2. Merged State. The coalition would be formed among overloaded APs and light-loaded APs. The formed coalition could help each AP achieve the nearly optimal station number within its coverage area. AP coalitions could work either in the centralized schedule way or in the free competition way. After occupying the channel, data transmission could be allowed for APs in this coalition. 3. Split State. Splitting any coalition if the utility of the player after the split is larger than the utility before the split or if there are better association choices for the player, which means the coalition cannot exist steadily. A split form would happen in this condition before any new coalition is composed. **Definition 3**. : _(The principle of a player joining a new coalition) Player \(i\in S_{1}\) tends to leave its original coalition and to join \(S_{2}\) if and only if \(\
u(S_{2}\cup\{i\})\succ\
u(S_{1})\)._

The algorithm starts at a partition where each AP itself is a coalition. Then, in each iteration, the AP will join in another coalition which can maximize the game value. Finally, until all APs form stable coalitions, the algorithm outputs the final partition. According to the repeated cyclical merging and splitting, every AP can find the optimal combination structure. ### Computational Complexity Analysis

In general, the computational complexity is considered as the times that merge-and-split rule and transfer rule of coalition structure are used. The proposed scheme can effectively reduce the computational complexity because APs would form coalitions based on their station numbers and their own \(\alpha_{s}\) and \(\alpha_{a}\). We assume that there are \(K_{s}\) light-loaded APs, so the number of heavy-loaded AP is \(K-K_{s}\). In the beginning of the coalition game, each AP is a single coalition and \(K\) coalitions are formed totally. * \(K_{s}>K-K_{s}\). In this case, there are more light-loaded APs than heavy-loaded APs and we consider there is only one heavy-loaded AP in a coalition after the game. The light-loaded AP will join in the heavy-loaded AP coalition to help reduce its burden based on the merger rule. If there are better heavy-loaded coalition choices for this light-loaded AP, it will split from current coalition based on the spitting rule and join in the new coalition. For each light-loaded AP, it has \(K-K_{s}\) choices, so the theoretical computational complexity of this algorithm is \((K-K_{s})K_{s}\). * \(K_{s}\geq K-K_{s}\). In this case, there are more heavy-loaded APs. The heavy-loaded AP only could cooperate with APs which can help reduce its burden.