# Coalition Formation Game for Cost-Efficient Multiparty Payment Channel in Payment Channel Networks
## 5 Coalition Formation Game for MPC Creation
### Coalition Cost Function  
If each PC needs deposit amount \(C_{ij}\) to afford the given PBT demand, \(\sum_{u}x_{ij}^{u}\leq C_{ij}\), the total required deposit of the MPC coalition \(S_{k}\) can be as below:  
\[v_{c}^{1}(S_{k})=\sum_{ij\in S_{k}}\alpha_{ij}C_{ij},\ S_{k}\subseteq S_{k}, \tag{7}\]  
where \(\alpha_{ij}\in\{0,1\}\) according to the existence of a PC \(ij\), and \(S_{k}\) is a subset of PCs with the maximum deposit for each PSP \(i\), \(S_{k}=\cup_{i}^{N}S_{k}^{i}\), \(S_{k}^{i}=\{ij|C_{ij}\geq C_{ik},ij,ih\in S_{k}\}\). For each PSP, the maximum PBT rate deposit amount can cover all SPC transactions in its SPCs. The payment delay of the legacy PC, \(D_{ij}^{\text{PC}}\), consists of transaction processing, propagation, and queuing. The transaction process delay is negligible compared to the two other factors, e.g., several micro-seconds. The message propagation delay, \(D_{m,ij}^{u}\), depends on the distance and congestion in the underlying network, defined as a random variable of the exponential distribution in this study, \(\mathbb{P}(D_{m,ij}^{u}<t)=1-e^{-\Delta_{ij}^{-1}t}\), with average \(\mathbb{E}(D_{m})=\Delta_{ij}\), as Ethernet based on carrier-sense multiple access with collision detection (CSMA/CD) has an access delay according to the binary back-off window [54] (i.e., the network delay can be modeled also by normal or Pareto distributions). Meanwhile, the queuing delay is critical according to bidirectional PBT flows modeled by M/M/1. \[D_{q_{i},ij}^{u}(x_{ij}^{u})=\frac{\sum_{u\in U}x_{ij}^{u}}{\sum_{u\in U}x_{ji} ^{u}(\sum_{u\in U}x_{ji}^{u}-\sum_{u\in U}x_{ij}^{u})} \tag{8}\]  
Although the queuing delay is theoretically infinite for \(\sum_{u}x_{ij}^{u}<\sum_{u}x_{ij}^{u}\), the maximum delay is the lock time in the off-chain system as all transactions over \(T_{exp}\) are canceled automatically. Furthermore, PSPs can cancel in-flight lock transactions using a rollback procedure in advance. For \(\sum_{u}x_{ji}^{u}=\sum_{u}x_{ij}^{u}\), in which the same amount moves back and forth for bidirectional PBTs, the queuing delay of a PBT is limited by the PBT interval, \(x_{ji}^{-1}\). Moreover, the MPC delay \(D_{ij}^{\text{MPC}}\) is mainly caused by the queuing and SPC turnaround. The queuing delay of the MPC, \(D_{q,ij}^{u}\), is determined by the balance of the aggregated flow rate. The egress aggregated PBT flow rate from a PSP \(i\) to any PSP \(j\), \(\lambda_{ij}\) can be written as below:  
\[\lambda_{ij}=\sum_{u\in U}\sum_{j\in N\backslash i}x_{ij}^{u}(1+\Sigma_{D}), \tag{9}\]  
where the maximum delay for SPC turnaround, \(\Sigma_{D}=\max_{\Delta}\sum_{r=0}^{N-1}\Delta_{ij}^{r}\), depends on the transaction process and propagation delay of each SPC. **Property 1**: _The MPC is balanced regardless of the individual PBT flow rate if the ingress and egress flow rate is equivalent at the outlink PCs of the MPC._  
Suppose that each PSP has multiple PCs outside of the MPC, \(ik\in\mathcal{L}\setminus\mathcal{V}\), and asymmetric and bidirectional PBT flows \(x_{ik}^{u}\) and \(x_{ki}^{u}\) are passed through the MPC; the aggregated PBT flow from the PSP \(i\) to others \(j\) in the MPC, \(\lambda_{ij}\) in Equation (9), is equivalent to \(\sum_{k\in\mathcal{L}\setminus\mathcal{V}}\sum_{u}x_{ki}^{u}\) and \(\mu_{ij}\) is the same as \(\sum_{k\in\mathcal{L}\setminus\mathcal{V}}\sum_{u}x_{ik}^{u}\), the sum of all PBT flows toward the PSP \(i\). Consequently, \(\lambda_{ij}=\mu_{ij}\) for a PSP \(i\) as \(\sum_{k\in\mathcal{L}\setminus\mathcal{V}}\sum_{u}x_{ki}^{u}=\sum_{k\in \mathcal{L}\setminus\mathcal{V}}\sum_{u}x_{ki}^{u}\) is satisfied. **Property 2**: _The MPC queuing delay is limited by the SPC turnaround time if the MPC is balanced, \(\lambda_{ij}=\mu_{ij}\)._  
Once the deposit of a particular PSP is unbalanced due to a pair of asymmetric flows, \(x_{ik}^{u}\) and \(x_{ik}^{u}\), it will be rebalanced by another pair of flows, \(x_{ik}^{u}\) and \(x_{ik}^{u}\), within the \(\Sigma_{D}\) because \(\lambda_{ij}=\mu_{ij}\) is guaranteed.