# Coalition Formation Game for Cost-Efficient Multiparty Payment Channel in Payment Channel Networks
## 1 Introduction  
With the many successes of cryptocurrency, the blockchain has been confirmed as a tamper-proof ledger operating in autonomous peer-to-peer (P2P) networks. However, the blockchain suffers from inherent scalability problems as the number of nodes and transactions grows rapidly. The consensus algorithms, such as proof of work for Bitcoin [1] and Ethereum [2], require excessive time to order transactions chronologically and synchronize them globally. Although many consensus algorithms, termed PoX (e.g., Proof of Stake [3], Delegated Proof of Stake [4], Proof of Validation [5], Proof of Elapsed time [6]), have been proposed to improve the performance in terms of transactions per second, it is still critical to maintain a unique chain agreed by globally distributed nodes. Instead, multiple leading chains can be used to deal with transactions in parallel, for which separate committees of these chains decide the final status of their chain independently, called blockchain sharding (e.g., RScoin [7], omniLedger [8], or rapidChain [9]). Similarly, parasite chains (called side chains) plugged into the main chain can be used to improve scalability, e.g., Plasma [10]. However, such multiple-chain approaches require periodic mutual verification for integrity checks. In contrast to the legacy blockchain, a directed acyclic graph (DAG)-based blockchain (e.g., IOTA [11], Nxt, ByteBall, and coDAG [12; 13; 14]) allows forking, which enables asynchronous updates within multiple side chains, converging in a specific direction. It is vulnerable to double spending by split attacks or long parasite chaining and still relies on a global consensus. In this paper, we focus on the L2 protocol for the blockchain network, called an \"off-chain\" protocol [15], by which two users can create a local ledger (\"payment channel (PC)\") for transactions between them and pay each other directly by updating the balanceinformation in the PC [16]. Therefore, the off-chain technique completes transactions faster than the blockchain without a consensus and fee. The PC is expanded to payment networks for indirect payment, called payment channel networks (PCN), because all users cannot have direct PCs to each other. A user can pay someone indirectly through multiple PCs of unknown intermediary users and payment service providers (PSP), such as multihop routing in ad hoc networks. Such multihop payment is a path-based transaction (PBT) in the PCN. This PCN is a promising technology to improve the scalability and efficiency of the main blockchain. Several off-chain payment networks have been proposed and developed for cryptocurrencies, such as the Lightning network [17] for Bitcoin, Raiden network [18] for Ethereum, and Paymo [19] for Monero. There have been many studies about the PCN. First, the PBT routing algorithm was explored, which is critical to protect privacy and maximize the PCN throughput. Flare [20], as the first routing protocol, finds a feasible transaction path in the PCN by mimicking a multihop ad hoc network protocol for the Lightning network. SilentWhispers [21] and SpeedMurmurs [22] introduced efficient decentralized routing algorithms for fast and private payment settlement in the PBT. VOUTE [23] followed, enhancing the efficiency of the landmark routing of SilentWhispers. Meanwhile, [PERSON] and [PERSON] [24] provided privacy and concurrency mechanisms in the PBT. Several studies proposed ideas to improve the PCN performance, limited by the channel deposit amount and PBT length. [PERSON] [25; 26] and Flash [27] introduced atomic multipath payments, which increased the PCN throughput by splitting a large PBT flow into many small flows. A redundant and secure balance was planned [28; 29] and transaction forwarding was scheduled [30] by the mathematical optimization model, assuming that the payment demands are known. Some studies investigated the economic aspects of the PCN [31; 32]. Cheapay [33] and payGo [34] found an economic payment path in terms of low fees of PSPs.