# Coalition Formation Game for Cost-Efficient Multiparty Payment Channel in Payment Channel Networks
## 5 Coalition Formation Game for MPC Creation
### MPC Formation Algorithm  
In this CFG, the PSPs constitute multiple independent and disjoint coalitions considering deposit gains from cooperation and additional costs from the MPC size. This partition problem for the coalition structure \(\Pi\) is known as NP-hard, as the number of the coalitions is the Bell number. Moreover, the PCN is a fully distributed system in which a PSP joins or leaves freely through the main blockchain. This study introduces a distributed algorithm using the switch operation based on preference order. The preference order, \(\succeq_{i}\), provides each PSP with a strict rule of preference between two coalitions during dynamic coalition formation. For instance, the relation \(S_{1}\succeq_{i}S_{2}\) indicates that a player \(i\) prefers to join the \(S_{1}\) coalition rather than the other, \(u_{i}(S_{1})\geq u_{i}(S_{2})\), \(S_{1},S_{2}\in\Pi\). Although revenue and cost are given to each directional PC, \(ij\in\mathcal{L}\), the bidirectional PCs, \(ij\) and \(ji\), need to derive a common strategy for switching operations regardless of individual payoff. Otherwise, the individual payoff will be practically zero as the PC is not established. Therefore, the switch operation splits and merges two PCs \(ij\) and \(ji\) together between MPCs at each step. For simplicity of notation, we use \(i\) of \(\succeq_{i}\) for an SPC \(i\)\(in\mathcal{V}\) hereafter. For the preference order of an SPC \(i\), \(u_{i}(S_{k})\) is the sum of individual SPC payoff without coalition and the expected coalition gain that is calculated by dividing fairly the marginal utility of the coalition \(S_{k}\). Here, the fair division encourages a PSP with fewer PBT flows to join an MPC with many PBT flows. \[u_{i}(S_{k})= \begin{cases}0,&\text{if }S_{k}\in\mathbb{H}_{i}(k)\\ -\infty,&\text{if }v_{c}(S_{k})=-\infty\\ v(\{i,\tilde{i}\})+\frac{2\left(v(S_{k})-\sum\limits_{j\in S_{k}}v(\{j\}) \right)}{|S_{k}|},&\text{otherwise},\end{cases}  \tag{11}\]where the \(i\) and \(\vec{i}\) are an SPC \(ij\), \(ji\), respectively, and \(\mathbb{H}_{i}(k)\) is a history set that contains all previous coalitions that the SPC \(i\) joined across all past partitions, \(\Pi_{0},\Pi_{1},...\Pi_{k}\). In this study, we introduce two preference rules, Pareto and selfish order, for forming MPC coalitions. Utilitarian order, which considers social welfare altruistically, is inappropriate for PSPs to pursue their profits, i.e., payment fees and incentives for their deposits. Definition 3: (Pareto order): Pareto order is one of the traditional preference relations for the CFG, which has strong restrictions, preventing damage for original and new coalitions, as in the following equation. \[S_{1}\succeq_{i}S_{2}\Leftrightarrow \tag{12}\] \[u_{i}(S_{1})>u_{i}(S_{2})\ \wedge u_{j}(S_{1})>u_{j}(S_{1} \setminus\{i\})\] \[\wedge u_{k}(S_{2})<u_{k}(S_{2}\setminus\{i\}),\forall j\in S_{1 }\setminus\{i\},\forall k\in S_{2}\setminus\{i\}\]  
Definition 4: (Selfish order): In contrast to the Pareto order, a player switches coalitions only based on its expected utility in a new coalition if existing members accept. The existing members of the new MPC can reject the join request from the player if their payoff decreases with his participation. \[S_{1}\succeq_{i}S_{2}\Leftrightarrow \tag{13}\] \[u_{i}(S_{1})\geq u_{i}(S_{2})\ \wedge u_{j}(S_{1})\geq u_{j}(S_{1 }\setminus\{i\}),\forall j\in S_{1}\setminus\{i\}\]  
Definition 5: (Switch operation): A PSP \(\{i\}\) as a player leaves a coalition \(S_{k}\) and joins another coalition \(S_{1}\) according to the preference order, denoted as \(\varphi_{k,l}(i):S_{k}\setminus\{i\},S_{1}\cup\{i\}\), which changes MPC coalition formation in a PCN from initial partition \(\Pi_{0},\Pi_{1},...,\Pi_{n}\) sequentially. The switching gain, \(g(\varphi_{k,l}(i))\), is an individual payoff increment that can vary according to the preference order. Theorem 2: (Nash-stable coalition): A coalition \(\Pi\) is Nash-stable if and only if no player individually improves its utility via the switch operation.