# Coalition Formation Game for Cost-Efficient Multiparty Payment Channel in Payment Channel Networks
## 5 Coalition Formation Game for MPC Creation
### MPC Formation Algorithm
\(g(\varphi_{k,l}(i))\leq 0\) for all \(S_{k},S_{l}\in\Pi\). The selfish and Pareto orders enable MPC coalitions to converge into the Nash-stable coalition partitions. Proof: Suppose that a final partition \(\Pi_{f}\) from finite iterations is not Nash-stable; any PSP can perform further switch operations for higher utility, which means that the \(\Pi_{f}\) is not the final coalition. Accordingly, the final partition state will be stable. Moreover, the number of switching iterations is finite, less than several possible partitions, since a player switches only to a coalition that has not been visited before. Algorithm 4 shows an MPC formation function for a PSP. The PSP starts with a single-tone coalition and merges with another SPC based on preference until the Nash-stable coalition formation is established. The new MPC coalitions provide the maximum gain for each SPC in every iteration. Each SPC considers candidate MPC coalitions that have not been visited before and contain other SPCs of the same PSP to maximize their payoff. These partition updates continue until no SPC improves its payoff for further switching. We show a simple MPC CFG in Figure 7 with PBT flows demanded as in Table 4. Because all PCs are noncooperative initially, some PCs having asymmetric flows need to set a circular flow and increase the deposit amount to avoid excessive queuing delays; for instance, the imbalance of the PC \(V_{12}\) by AB and BA forces PSP 1 to find a circular flow toward PSP 2 and increase the deposit up to 100 tokens. Therefore, the final deposit is 100 tokens for each PC, and 300 tokens are necessary for each PSP. Alternatively, PSP B can reduce the flow BA rate to 50, which, however does not satisfy the user demand. Meanwhile, the MPC formation of PSPs 1-4 can support all flows with \(100+100\Sigma_{D}\) tokens. ```
1: Initialization:
2:User demand of PBTs, \(x^{u}\), \(u\in\mathcal{U}\) by routing
3:Set PCs, \(\alpha_{ij}=1\), \(ij\in\mathcal{L}\)
4:Set deposit, \(C_{ij}\) for max(\(\sum_{u}x^{u}_{ij}\), \(\sum_{u}x^{u}_{ji}\))
5:Set preference order, \(g(\varphi_{k,l}(ij))\)
6:Instruction:
7:Set \(S_{k}=\{ij,ji\},\forall ij\) for a PSP \(i\)
8:Calculate utility, \(u_{ij}(S_{k})\)
9:while\(ij\) and \(g(\varphi_{k,l}(ij))>0\), \(ij\in\mathcal{L}\)do
10: Find \(S_{k}\), \(ij\in S_{k}\)
11:maxGain = 0
12:for\(S_{l}\in\Pi\) and \(ik\in S_{l}\)do
13:if\(S_{k}\) not \(\in\mathbb{H}_{ij}(k)\) and \(g(\varphi_{k,l}(ij))>\)maxGain then
14: maxGain = \(g(\varphi_{k,l}(ij))\) based on Equation (11)-(13)
15:\(S^{*}_{l}=S_{l}\)
16:endif
17:endfor
18:Request coalition join to the MPC \(S^{*}_{l}\)
19:Switch coalition from \(S_{k}\) to \(S^{*}_{l}\)
20:Update \(\Pi\) with \(S_{k}\), \(S^{*}_{l}\)
21:endwhile
22:return \(\Pi\)
```  
**Algorithm 4** Distributed MPC coalition algorithm for a PSP. Based on Equations (6), (7), (10), and (11) with parameters such as \(e_{r}=0.2\), \(e_{c}=0.1\), and \(\mathbb{E}\Delta=0.01\) (\(\Sigma_{D}=N\mathbb{E}\Delta\)), in the above example, the payoff of single-tone sets, such as \(v(S_{k}=\{(1,2)\})\) and \(v(S_{k}=\{(2,1)\})\), can be \(v(S_{k}=\{(1,2)\})=0\) and \(v(S_{k}=\{(2,1)\})=\epsilon_{r}(100)-\epsilon_{c}(100+100\times 0)=10\) according to asymmetric user PBT flows. Thereby, the initial payoff of the SPC is \(v(S_{k}=\{(1,2),(2,1)\})=10\). A newly merged MPC, \(S_{k}=\{(1,2),(2,1),(1,4),(4,1)\}\), can gain additional coalition utility of \(4.75\) and accordingly \(4.75/4=1.19\) is given for each PC since the MPC utility is \(v(S_{k})=e_{r}(250)-\epsilon_{c}(250+250\times 0.01)=24.75\) and the sum of the original utility of each SPC \(\{(1,2),(2,1)\}\) and \(\{(1,4),(4,1)\}\) is approximately 20. Furthermore, the MPC clique of PSPs can increase the utility; for example, \(S_{k}=\{(1,2),(2,1),(1,4),(4,1),(2,4),(4,2)\}\) results in \(v(S_{k})=49.4\) and the marginal payoff for each PC is \(19/6=3.17\); the revenue increases through deposit reuse without changing the collateral cost. The maximum cliques 1-4 in the figure can provide a marginal payoff of 4.8 to each PC.