# Traffic Offloading in Unlicensed Spectrum for 5G Cellular Network: A Two-Layer Game Approach
## 4 Coalition Game
### Merge-and-Split Based Coalition Formation Algorithm
Similarly, according to the merge-and-split rule and game prize, the theoretical computational complexity of this algorithm is \(K_{s}(K-K_{s})\). In summary, the theoretical computational complexity of our proposed algorithm is \(K_{s}(K-K_{s})\). ### Stability Analysis

As illustrated in Algorithm 2, an AP could either choose to join a new coalition or remain in its current coalition. To obtain the stable coalitional structure, a dynamic coalition formation model based on a Discrete Time Markov Chain (DTMC) can be formulated [31]. The state of the DTMC can be expressed as the set of all the coalition structures in Definition 2 denoted by \(\mathrm{Y}=\{S_{1},S_{2},\ldots,S_{L}\}\), where \(L\) is the total number of coalitions formed and \(S_{i}\cap S_{j}=\phi\). The state space of the Markov chain is

\[\Theta=\{(\mathrm{Y}_{1}),\ldots,(\mathrm{Y}_{x}),\ldots,(\mathrm{Y}_{M})\}, \tag{13}\]

where \(\mathrm{Y}_{x}\) represents a coalition structure and \(M\) is the Bell number obtained from

\[M(i)=\sum_{j=0}^{i-1}\binom{i-1}{j}M(j),\quad\forall i>1\quad and\quad M(0)=1.\]

The transition probability from one partition to another depends on the decisions of the players to leave and join the coalitions, which is denoted by a transfer matrix \(P\) and the elements of which are transition probabilities \(\rho_{\mathrm{Y},\mathrm{Y}^{\prime}}\),

\[\rho_{\mathrm{Y},\mathrm{Y}^{\prime}}=\left\{ \begin{array}{ll}\prod_{r\in \mathbb{R}}P_{x}(x\in S_{L}\in\mathrm{Y}\to x\in S_{L}^{\prime}\in\mathrm{Y}^{ \prime})\varphi_{i}(\mathrm{Y}^{\prime}|\mathrm{Y}),&\mathrm{Y}\
eq\mathrm{Y} ^{\prime}\\ 1-\Sigma_{i\in\Theta,i\
eq\mathrm{Y}}\ \rho_{\mathrm{Y},i},&\mathrm{Y}= \mathrm{Y}^{\prime}\end{array} \right., \tag{14}\]

where \(P_{x}(x\in S_{L}\in\mathrm{Y}\to x\in S_{L}^{\prime}\in\mathrm{Y}^{\prime})\) is the transition probability the \(AP_{x}\) changes from coalition \(S_{L}\in\mathrm{Y}\) to coalition \(S_{L}^{\prime}\in\mathrm{Y}^{\prime}\). The detailed derivation is given in Appendix A. In addition, \(\varphi_{x}(\mathrm{Y}^{\prime}|\mathrm{Y})\) is the probability that the player \(AP_{x}\) decides to move from its current coalition \(S_{L}\) to a new coalition \(S_{L}^{\prime}\), which makes the coalitional structure to change from \(\mathrm{Y}\) to \(\mathrm{Y}^{\prime}\), which can be expressed as:

\[\varphi_{x}(\mathrm{Y}^{\prime}|\mathrm{Y})=\left\{ \begin{array}{ll}\vartheta,&\quad\
u(S_{L}^{\prime})\geq\
u(S_{L})\\ 0,&\quad\text{otherwise}\end{array} \right., \tag{15}\]

where \(0<\vartheta\leq 1\), \(S_{L}\in\mathrm{Y}\) and \(S_{L}^{\prime}\in\mathrm{Y}^{\prime}\). The solution of the coalition formation game is the coalitional structure that can exhibit internal and external stability notions [32]. Internal stability implies that, given a coalition, no player in this coalition has an incentive to leave this coalition and obtain a higher payoff. External stability indicates that, given a partition, no player can improve its payoff by switching its current coalition and joining another one. In addition, the solution for the DTMC can be obtained in a centralized manner by using the inter-RAT centralized controller and the stable coalitional structure can be selected randomly by using the Algorithm 2 to find the solution based on the individual decision of each player. A stable coalitional structure can be identified from the stationary probability of the Markov chain defined with the state space in Equation (13) and transition probability in Equation (14). The stationary probability of the Markov chain can be obtained by solving

\[\vec{\pi}^{T}P=\vec{\pi}^{T}, \tag{16}\]

where \(\vec{\pi}^{T}=[\pi_{Y_{1}},\dots,\pi_{Y_{M}}]^{T}\), \(\vec{\pi}^{T}\vec{1}=\vec{\pi}^{T}\) is a vector of stationary probabilities and \(\vec{1}\) is a vector of ones. \(\pi_{Y}\) is the probability that a coalition structure is formed.