# Coalition Formation Game for Cost-Efficient Multiparty Payment Channel in Payment Channel Networks
## 4 Multiparty Payment Channel
### Concurrent Payments in Independent SPCs  
The aforementioned sequential payments induce significant delays as the number of PSPs increases in the MPC. For example, users should wait for six SPC instances to pay again to a particular user in Figure 5. The delay of each SPC consists of the handshaking time for the SPC update and local chain propagation. Additionally, the verification time for the previous \(n\) blocks is required, but it is negligible compared to the communication delay. We denote the delay of each SPC as \(\Delta\) in this study. To reduce such a turnaround delay, we form a group of independent SPCs for concurrent payments free from double spending. In Figure 4, payments on the SPC \(v_{AB}\) and \(v_{CD}\) can be conducted simultaneously because each SPC does not interfere with the other concerning the MPC state. The parallel SPCs can reduce the turnaround time from \(6\Delta\) to \(3\Delta\). Figure 6 illustrates an example of concurrent payments on independent SPCs of the six-party MPC. The figure shows that the MPC has the first several rounds with a maximum independent set of \(N/2=3\) SPCs and \(k=2\) SPCs in the remaining rounds. There is an optimal SPC schedule only with the maximum independent set during five rounds for this example. However, finding the maximum independent sets is known as NP-hard. Therefore, we propose an iterative greedy approximation algorithm for a bounded degree graph (an approximation ratio of \((deg(v_{ij})+2)/3\), which finds a maximal independent set (MIS) iteratively by choosing a minimum degree SPC first at each step. Theorem 3.1: _The number of MISs, \(M_{V}\), is bounded as proven in [49], and the number of MISs of size \(k\), \(M_{k}\), is at most [50]_  
\[k\leq V/3:\] \[\alpha^{k-(V\,\text{mod}\,k)}(\alpha+1)^{V\,\text{mod}\,k}, \alpha=\lfloor V/k\rfloor \tag{1}\] \[V/3\leq k\leq V(V-2)/8:\] \[3^{V/3}, V\,\text{mod}\,3=0\] (2) \[4\cdot 3^{\lfloor V/3\rfloor-1}, V\,\text{mod}\,3=1\] (3) \[2\cdot 3^{\lfloor V/3\rfloor}, V\,\text{mod}\,3=2 \tag{4}\]  
Corollary 1: _The SPC cycle, \(r\), as a minimum round for all SPCs, can be derived from the average number of simultaneous SPCs, \(\sum_{k}^{N/2}k\,\mathbb{P}(k,V)\), per round, where the probability \(\mathbb{P}(k,V)=M_{k}/M_{V}\) of the \(k\) MISs is given by Equations (1)-(4)._  
\[\arg\min_{r}\,\sum_{k=0}^{r}\sum_{k=1}^{N/2}k\,\mathbb{P}(k,V)\geq V \tag{5}\]  
Figure 6: Independent SPC schedule for concurrent transactions in a 6-party MPC. Table 3 shows the theoretical upper bound of the average SPCs and rounds for different sizes of the MPC derived by Equation (5). The average number of SPCs converges into the maximum independent set \(N/2\) as the probability of finding larger \(k\) MISs increases according to the number of users. We implemented the SPC scheduling algorithm with the iterative MIS search described in Algorithm 3 and evaluated it with the same MPCs for comparison, as shown in Table 3; the algorithm can find the optimal schedule of \(N-1\) rounds for each MPC. The algorithm complexity can be reduced to \(O(V\text{log}V)\) using the heap data structure and it needs to be executed only once at the beginning of MPC creation. ```
1:Initialization:
2:Node set N, \(i,j\in N\)
3:key, \(ij=\text{deg}(v_{ij})\), value \(v(ij)=\text{SPC }v_{ij}\)
4:Make a minHeap (\(ij\), \(v(ij)\)) \(\to Q\)
5:\(r=0\)
6:Instruction:
7:while True do
8: Set \(V_{r}=\{\}\)
9: Set \(M_{r}=\{\}\)
10: Dequeue \(v_{ij}\leftarrow\text{root}(Q)\) and Heapify(\(Q\))
11:while\(Q\) is not empty do
12:if\(i,j\
ot M_{r}\)then
13: Enqueue \(i,j\to M_{r}\)
14: Enqueue \(v_{ij}\to V_{r}\)
15:else
16: Enqueue \(v_{ij}\to Q^{\prime}\)
17:endif
18: Dequeue \(v_{ij}\leftarrow\text{root}(Q)\) and Heapify(\(Q\))
19:endwhile
20:if\(Q^{\prime}\) is not empty then
21:\(r=r+1\)
22:\(Q=Q^{\prime}\) and \(Q^{\prime}\)
23: Make a minHeap (\(ij\), \(v(ij)\)), \(ij\in Q^{\prime}\to Q\)
24:else
25: break
26:endif
27:endwhile
28:return \(M_{r}\), \(r=[0,\text{N}-1]\)
```  
**Algorithm 3** Find independent sets of SPCs in an MPC clique.