# Lightning Creation Games

Zeta Avarikioti  TU Wien
Vienna, Austria
<EMAIL_ADDRESS>Tomasz Lizurej  University of Warsaw $\&$
IDEAS NCBR
Warsaw, Poland
<EMAIL_ADDRESS>Tomasz Michalak  Michelle Yeo  University of
Warsaw $\&$ IDEAS NCBR
Warsaw, Poland
<EMAIL_ADDRESS>Institute of Science and Technology Austria
Klosterneuburg, Austria
<EMAIL_ADDRESS>
###### Abstract

Payment channel networks (PCNs) are a promising solution to the scalability
problem of cryptocurrencies. Any two users connected by a payment channel in
the network can theoretically send an unbounded number of instant, costless
transactions between them. Users who are not directly connected can also
transact with each other in a multi-hop fashion. In this work, we study the
incentive structure behind the creation of payment channel networks,
particularly from the point of view of a single user that wants to join the
network. We define a utility function for a new user in terms of expected
revenue, expected fees, and the cost of creating channels, and then provide
constant factor approximation algorithms that optimise the utility function
given a certain budget. Additionally, we take a step back from a single user
to the whole network and examine the parameter spaces under which simple graph
topologies form a Nash equilibrium.

###### Index Terms:

Payment channel networks, Nash Equilibrium, Blockchain, Network design, Layer
2, Bitcoin

##  I Introduction

One of the critical limitations of the major cryptocurrencies, such as Bitcoin
or Ethereum, is their low transaction throughput [1, 2, 3]. For instance,
given Bitcoin’s block size limit of 1MB and the average block creation time of
10 minutes, its throughput is limited to tens of transactions per second. This
is clearly not enough to facilitate the widespread everyday use of Bitcoin.
For comparison, credit card payment systems such as VISA handles approximately
7K transactions per second [4].

Payment Channel Networks (PCNs), such as Bitcoin’s Lightning Network [5] and
Ethereum’s Raiden Network [6], are second-layer solutions that are designed to
address the above scalability problem. The core idea is to process the
majority of transactions off-chain by enabling nodes to establish bilateral
payment channels; each channel acts as a joint account between the channel
participants. To preserve security, opening a channel requires depositing
funds to a shared address on-chain. These funds serve as secure collateral to
possibly many off-chain transactions between both parties. When the channel is
closed, the final balance is settled on-chain.

Importantly, each node can establish such payment channels with many other
nodes. This gives rise to a network that allows for funds transfers to non-
neighbors through a path of intermediaries. Because opening and maintaining a
channel requires locking up funds, serving as an intermediary results in
opportunity costs. To mitigate this cost, intermediary nodes earn transaction
fees for their services.

The protocols underlying PCNs have attracted a lot of attention in the
literature [7]. In addition to analyzing cryptographic underpinnings of the
PCN’s security proofs [8, 9], an effort has been made to understand game-
theoretic aspects of these networks either with respect to security e.g., [10,
11, 12, 13, 14], or economics, e.g., [15, 16].

A particularly interesting question is how the nodes should choose _where to
connect_ to a PCN and _what portion of a budget should be locked_ to distinct
channels. This is important as their choice not only affects the situation of
individual nodes but also influences the resulting network as a whole.
However, this issue has been weakly studied in the literature. In fact, most
PCN implementations (e.g., the Lightning Network) still propose a simple
heuristic for new nodes, suggesting connecting to a trusted peer or a hub.

In this work, we answer this question by first presenting several attachment
strategies for newly-joining nodes in a PCN. The first key challenge to this
task is to define the new node’s utility function that accurately reflects the
key objectives of new PCN users. A newcomer has to weigh the cost of creating
channels and locking up capital against the profits stemming from these
connections and the node’s position in the network. Furthermore, the utility
function should be efficiently computable, so that it can be used in practice
by new nodes, posing a second challenge.

Unfortunately, the models of the utility function considered so far in the
literature do not take all the above aspects into account. In particular,
Guasoni et al. [17] analyse the cost of channel creation, and establish
conditions under which two parties would create unidirectional or
bidirectional channels between themselves, as opposed to transacting on-chain.
However, the utility function in [17] only accounts for the cost of channel
creation but neglects profits from routing transactions and fees a user could
encounter. Avarikioti et. al [18, 19] and Ersoy et. al [20], on the other
hand, account for fees and profits from routing transactions through the PCN
but neglect the opportunity costs from the locked capital and consider only a
simplified transaction model where users transact with each other with uniform
probability.

We take up the first challenge to define a utility function that accurately
depicts the gains and costs of newly joining nodes. In particular, we account
for on-chain costs for opening channels, routing fees paid to and by the node
due to its position in the network, and opportunity costs for locked capital.
We further leverage a realistic transaction distribution where nodes transact
with other nodes with probability proportional to their degree, inspired by
the well-known Barabási-Albert preferential attachment model [21]. We believe
this transaction distribution approximates well real-life scenarios where
nodes transact more often with big vendors and service providers. We further
address the second challenge by providing a series of approximation algorithms
to efficiently compute the optimal connection strategy for newly-joining
nodes. The approximation ratio and runtime of each algorithm depend on how
much freedom the node has to distribute its budget on the channels,
highlighting an interesting trade-off.

Apart from the myopic analysis for a single joining node, we also examine the
effect our strategies may have on the topological structure of a PCN. In
particular, we examine simple graph structures, i.e., path, circle, and star
graphs, to determine under which conditions these constitute stable graphs,
where no node may increase its utility by changing its strategy (Nash
equilibrium). Naturally, which topologies are stable or not heavily depends on
the parameters of the transaction distribution. We thus identify the exact
parameter space in which each topology constitutes a Nash equilibrium.

In summary, our contributions are as follows:

  * •

We extend the utility function of [19] to incorporate a _realistic transaction
model and opportunity costs_. To that end, we consider transaction
distributions where users transact with other users in proportion to their
degree instead of uniformly at random as in [19, 20, 18].

  * •

We provide a series of _approximation algorithms_ that maximize our utility
function under different constraints. In particular, we identify a _trade-off
between the runtime of the algorithm and capital distribution constraints_ ,
i.e., how much capital is locked in each channel at its creation.

  * •

Finally, we examine simple graph topologies and determine under which
parameter space of the transaction distribution, they form _Nash equilibria_.

##  II The Model

In this section, we outline our model which is an extension of the model
introduced in [19]. We alleviate several unrealistic assumptions introduced in
[19], thus providing more meaningful insights on the connection strategies and
expected network structure of PCNs. We indicate these assumptions below.

###  II-A Payment channel networks and routing fees

Payment channels provide a way for users on the blockchain to transact
directly with each other off-chain, thereby avoiding the high fees and latency
involved in transacting on the blockchain. Any two users on the blockchain can
open a payment channel with each other by locking some of their funds to be
used only in this channel, much like opening a joint account in a bank. Once
the channel is created, both users can send each other coins by updating the
channel balances in favour of the other party (see Figure 1 for an example).
For each payment (channel balance update), the respective capital must be
respected, meaning that a party cannot send more coins than it currently owns
to the counterparty. To close their payment channel, the parties post on-chain
a transaction that depicts the latest mutually agreed distribution of their
funds. The closing transaction can be posted either in collaboration or
unilaterally by one channel party. Note that _posting a transaction on-chain
bears a cost_ : the fee to the miner that includes the transaction on the
blockchain.

A payment channel network comprises of several two-party channels among users
of the blockchain. Each user of the network is represented by a vertex while
each (bidirectional) channel among two parties is represented by $2$ directed
edges (one in each direction) connecting the two vertices corresponding to the
parties. We model each bidirectional channel as $2$ directed edges to take
into account the balance on both ends of the channel which can be different
and thus impose different limits on the payment amount that can be sent in
each direction. More concretely, let us represent the topology of a payment
channel network with a directed graph $G=(V,E)$ with $|V|=n$, and $|E|=m$. For
node $u\in V$, let $Ne(u)$ denote the set of in- and out-neighbors of $u$.

Figure 1: Example of payments going through a channel between $2$ users $u$
and $v$. $b_{u}$ and $b_{v}$ denote the balances of $u$ and $v$ in the channel
and are updated with every successful payment. The last payment of size $6$
going from $u$ to $v$ is unsuccessful as the size of the payment is larger
than $b_{u}=5$.

Users who are not directly connected with a channel can still transact with
each other if there exists a path of channels between them in the PCN graph.
For instance, if Alice and Carol do not share a channel, but Alice shares a
channel with Bob and Bob with Carol then Alice may send coins to Bob and then
Bob to Carol111There exist techniques, namely HTLCs, to ensure that the
transactions on a path will be executed atomically, either all or none, so the
intermediaries do not lose any funds [5].. However, each channel must hold
enough coins to ensure the feasibility of the transaction routing. In our
previous example, if Alice wants to send to Carol 5 coins through Bob, then
Alice must own at least 5 coins in her channel with Bob, and Bob at least 5
coins in his channel with Carol, at the time of the transaction execution. The
users along the transaction path who are not the sender or receiver (e.g.,
Bob) typically _charge a fee for forwarding the transaction_ that depends on
the transaction amount and is publicly announced. The precise form of the fee
function for forwarding transactions is determined by the user who owns the
coins. That is, given a payment channel $(u,v)$ and a fixed transaction amount
of $t$, the fees incurred from forwarding $t$ can even differ depending on
whether $t$ is forwarded from $u$ to $v$ or from $v$ to $u$.

In our model, we assume transactions ($tx$) are of size at most $T>0$ and all
intermediary nodes take the same – global – fee function
$F:[0,T]\longrightarrow\mathbb{R}^{+}$ which is an abstraction for an average
fee function. We denote by $f_{avg}$ the value of the average fee when using
the global fee function $F$. That is, $f_{avg}=\int_{0}^{T}p_{tx\
\text{size}=t}\cdot F(t)dt$, where $p_{\text{tx size}=t}$ is a global
probability of occurrence of a transaction with size $t$. We assume that
$f_{avg}$ is publicly known (recall that the fee functions are publicly
announced in PCNs).

###  II-B PCN transactions

In the following, we alleviate the assumption of [19] that transactions are
uniformly distributed among the PCN users, and introduce a more realistic
transaction model.

Transactions: Let $N_{u}$ denote the average number of transactions sent from
user $u$ over a unit of time. We denote with $N$ the sum of the number of all
transactions sent by users in a unit of time $N=\sum_{v\in V}N_{v}$. We assume
a user $u$ joining the network knows the distribution of transactions in the
network. These assumptions equally allow each user to estimate the mean rate
(denoted by $\lambda_{uv}$) of transactions going along any directed edge
$(u,v)$ which, we assume, follows a Poisson process with rate $\lambda_{uv}$.
We also stress that this estimation can be done efficiently in time
$\mathcal{O}(n^{2})$, by calculating shortest paths using e.g., Dijkstra’s
algorithm [22] for each pair of nodes in the network.

Reduced subgraph with updated capacities:: The topology of the PCN can change
with the size of transactions due to balance constraints: some directed edges
do not have enough capacity to forward transactions when the transaction size
is too large. However, given that we assume users know the distribution of
transactions in the network, and that the capacity and time of channel
creation are publicly posted on the blockchain, users can estimate the
expected balance on each end of all channels in the network. Thus, for the
rest of the paper, we consider that all our proposed algorithms for a given
transaction of size $x$ are computed on a subgraph $G^{\prime}$ of the
original PCN $G$ that only takes into account directed edges that have enough
capacity to forward $x$.

Transaction distribution: In the topological studies included in this work, we
assume that the probability that any two users transact with each other is
proportionate to their degree. Specifically, we use the Zipf distribution [23]
to model the occurrence of any two users transacting with each other. That is,
assume for a user $u$ a ranking of all other users in the network according to
their degree, breaking ties arbitrarily. That is, the highest degree vertex is
given rank 1, the second highest is given rank 2, etc. Then for some user-
specific parameter $s_{u}>0$, the probability $p^{trans}_{u,v}$ that $u$
transacts with another user $v\in V\setminus\\{u\\}$ with rank $k$ is:

$p^{trans}_{u,v}=\frac{1/k^{s_{u}}}{\sum_{i=1}^{n}1/i^{s_{u}}}.$ (1)

We note that the Zipf distribution is widely used in the natural and social
sciences for modelling data with a power law distribution [24, 25]. It is also
frequently used in the context of social networks [26] and thus seems a
natural model for approximating the probability of any 2 users transacting in
a payment channel network.

Let the edge betweenness centrality be defined as:

$EBC(e):=\sum_{s,r\in V;s\neq r;m(s,r)>0}\frac{m_{e}(s,r)}{m(s,r)},$

where $m_{e}(s,r)$ is the number of shortest paths that traverse through the
edge $e$ and $m(s,r)$ is the total number of shortest paths from $s$ to $r$.
The transaction rate $\lambda_{e}$ for all directed edges $e$ in $E$ can be
estimated by the edge betweenness centrality of the edge $e$ weighted by the
probability of any two vertices $s$ and $r$ transacting with each other. That
is, for a directed edge $e$, we first define the probability $p_{e}$ that the
edge $e$ is chosen in a single transaction:

$p_{e}=\sum_{s,r\in V;s\neq
r;m(s,r)>0}\frac{m_{e}(s,r)}{m(s,r)}p^{trans}_{s,r}.$ (2)

Let $N$ denote the average number of transactions that happen in a unit of
time sent out by a user in the network. We assume these transactions are
independent. The average number of times a directed edge $e=(u,v)$ is chosen
in $N$ transactions is the transaction rate $\lambda_{e}$ and is simply
$N\cdot p_{e}$.

In this work, we slightly modify the original Zipf distribution to ensure that
the probability of any user transacting with two other distinct users having
the same degree is equal. We do this by simply averaging the Zipf probability
of transacting with every user with the same degree. Below we propose a
detailed method of calculating the probability that a given node $u$ transacts
with any other node $v$ in the network.

Given a network $G=(V,E)$, we first consider the subgraph
$G^{\prime}=(V^{\prime}=V\setminus\\{u\\},E^{\prime})$ which is created by
removing the node $u$ all of its incident edges from $G$. Then, we sort all
nodes in $V^{\prime}$ by their _in-degree_ and then assign a _rank-factor_ –
$rf(v)$ to each node $v$ in $V^{\prime}$. Since we want to ensure that every
node with the same in-degree has the same rank-factor, we simply average the
ranks of nodes with the same in-degree. In more detail, let $r_{0}(v)$ denote
the smallest rank of a node $v^{\prime}\in V^{\prime}$ such that the in-degree
of $v^{\prime}$ is equal to the in-degree of $v$. Let $n(v)$ be the number of
nodes in $V^{\prime}$ with the same in-degree as $v$. The rank factor of $v$
can be computed as follows:

$rf(v)=\frac{\frac{1}{r_{0}^{s}(v)}+\ldots+\frac{1}{(r_{0}(v)+n(v))^{s}}}{n(v)}$

The probability that $u$ transacts with $v\in V^{\prime}$ is then:

$p^{trans}_{u,v}=\frac{rf(v)}{\sum_{v^{\prime}\in V^{\prime}}rf(v^{\prime})}$

Finally, observe that the modified Zipf distribution satisfies the following
property: $r_{1}(v_{1})<r_{2}(v_{2})\implies rf(v_{1})>rf(v_{2})$. This holds
because $rf(v_{1})\geq\frac{1}{(r_{0}(v_{1})+n(v_{1}))^{s}}$ and
$rf(v_{2})\leq\frac{1}{(r_{0}(v_{2}))^{s}}$.

###  II-C Utility function of a new user

When a new user joins a PCN, they must decide _which channels to create and
how much capital to lock in each channel_ , while respecting their own budget.
In their decision, the user must factor the following: (a) the on-chain costs
of the channels they choose to open, (b) the opportunity cost from locking
their capital for the lifetime of each channel, (c) the potential gains from
routing transactions of others (routing fees), (d) the routing fees they must
pay to route their own transactions through the PCN, (e) their budget.
Intuitively, the more channels a user opens and the higher the amount of the
total capital locked, the more fees they will obtain from routing and the less
cost they will bear for routing their own transactions. In other words,
increasing the initial costs also increases the potential gains. Our goal is
to analyze these trade-offs and find the sweet spot that maximizes the
benefits for a newly-joining user with a specific budget. We account for all
these factors in a realistic manner when we design the utility function of the
user, in contrast to previous work [19, 18] where the opportunity cost was
omitted, and the routing fees were calculated naively (i.e., constant fees and
uniform transaction distribution).

Figure 2: $E$ joins a PCN with existing users $A$, $B$, $C$, $D$. $E$ plans to
transact with $B$ once a month, and $A$ usually makes $9$ transactions with
$D$ each month. We assume the transactions are of equal size, and transaction
fees and costs are of equal size. $E$ has enough budget only for $2$ channels,
with the spare amount of funds to lock equaling $19$ coins. $E$ should create
channels with $A$ and $D$ of sizes $10$ and $9$ to maximize the intermediary
revenue and minimize $E$’s own transaction costs.

User strategy and constraints: Consider a fixed PCN $G=(V,E)$ and a new user
$u$ that wants to join $G$. Furthermore, let us denote the set of possible
actions by $\Omega:=\\{(v_{i},l_{i})\\}_{i}$, where each element
$(v_{i},l_{i})\in\Omega$ represents a node $v_{i}$ that $u$ wants to connect
to by locking in an amount of $l_{i}>0$ on the corresponding channel. The
strategy of $u$ is to select a set of users (a strategy) $S\subset\Omega$ that
$u$ wants to connect to and how much funds to deposit in these channels. Note
that both $\Omega$ and $S$ may contain more than one channel with the same
endpoints, but different amounts of locked funds on each end. We also assume
$u$ has some budget $B_{u}>0$ to create and fund channels and $u$’s budget
constraint imposes the requirement that for the strategy $S\subseteq\Omega$
chosen by $u$, $\sum_{j=1}^{|S|}[C+l_{j}]\leq B_{u}$. Finally, we remark that
$\Omega:=\\{(v_{i},l_{i})\\}_{i}$ may contain $v_{i}$ with continuously many
values of $0\leq l_{i}\leq B_{u}$. We will call it a continuous action set. In
this case, we will operate on the set of vertices $\Omega^{V}\subseteq V$ for
which the user $u$ will choose a strategy $S$ consisting of pairs
$(x_{j},l_{j}):x\in\Omega^{V},0\leq l_{j}\leq B_{u}$. Figure 2 highlights a
simple example of the decision-making process of a new user that wants to join
an existing PCN.

Now we define the _utility function_ for a new user $u$ that wants to join a
PCN $G$ and has a fixed budget $B_{u}$. The goal of $u$ is to _choose any
strategy $S=\\{(v_{i},l_{i})\\}_{i}\subseteq\Omega$ to maximize their expected
profit within a given budget $B_{u}$._ The expected profit (utility) of $u$ is
essentially the expected revenue from forwarding transactions through its
channels and collecting the routing fees, minus the costs of creating the
channels (on-chain fees and opportunity cost) and the expected fees
encountered by $u$ when sending transactions to other users in the network.

Channel costs: Typically, two on-chain transactions are needed to open and
close a channel 222We omit the case when one of the parties may commit fraud,
and a third transaction is necessary to award the cheated party all the
channel funds. This case is outside the scope of the paper as the costs for
publishing such a transaction may be covered by the total funds of the
channel. Recall that each blockchain transaction costs a fee to the miners,
denoted $C$.

The cost of the _opening_ transaction can be shared by two parties, and we
assume that parties only agree to open channels if they share this cost
equally ($C/2$ each). The cost of the closing transaction, on the other hand,
is paid by both parties when the channel closes in collaboration, or by the
party that closes the channel when the channel is closed unilaterally. To
model the costs of a channel between $u$ and $v$, we assume that it is equally
probable that the channel closes in one of the three ways: unilaterally by
$v$, unilaterally by $u$, in collaboration of $u$ and $v$. Thus, the cost of
the closing transaction is on expectation $C/2$ for each party. Hence, in
total, the channel cost for each party is $C$.

We also account for the opportunity cost of locking funds (as opposed to using
or storing them elsewhere) in a channel for the lifetime of the channel.
Suppose two users $u$ and $v$ wish to open a channel locking $c_{u}$ and
$c_{v}$ amount of coins respectively. Let $l_{i},i\in V$ the opportunity cost
defined by user $i$; that is, typically a function of the amount of coins
$c_{i}$, e.g., $l_{i}=r\cdot c_{i}$, $r$ constant (a standard economic
assumption due to the non-specialized nature of the underlying coins [27]). We
denote the total cost for opening a channel for user $u$ by
$L_{u}(v,l)=C+l_{u}$. The cost of user $v$ is symmetric.

We direct the reader to the work by Guasoni et al. [17] for a more detailed
model of channel costs. We note that our computational results still hold in
this extended model of channel cost. We further note that while the utility
function in [17] only accounts for the cost of channel creation, in our work
we also consider the potential profit from routing transactions and fees a
user could encounter.

Revenue from routing fees: Each user of the PCN may route transactions of
others through their channels in exchange for a routing fee. Each time a user
$u$ provides such service, $u$ gains revenue equal to $f_{avg}$ as described
in section II-B. Specifically, the expected revenue gained by a user $u$ over
a unit time interval from routing transactions in the PCN is the sum of the
fees weighted by the average transaction rate from all of $u$’s incident
channels:

$\mathbb{E}^{rev}_{u}=\sum_{v_{i}\in Ne(u)}\lambda_{uv_{i}}\cdot f_{avg}.$ (3)

We write $\mathbb{E}^{rev}_{u_{S}}$ when we want to explicitly say that the
user $u$ already added edges from $S$ to the network.

Fees encountered by the user: Whenever a user in the network $u$ makes a
payment to another user $v$, $u$ has to pay some amount of fees to all the
intermediary nodes in the payment path from $u$ to $v$. Let $d(u,v)$ be the
length of the shortest path from $u$ to $v$ in the network and let us assume
that $u$ pays $f_{avg}^{T}$ to every intermediary node in the path. The
expected fees encountered by $u$ with a stream of $N_{u}$ output transactions
is the sum of costs which increases proportionally with the distance between
any two users:

$\mathbb{E}^{fees}_{u}=N_{u}\cdot\sum_{v\in V;v\neq u}d(u,v)\cdot
f_{avg}^{T}\cdot p^{trans}_{u,v}$

We write $\mathbb{E}^{fees}_{u_{S}}$ when we want to explicitly say that the
user $u$ already added edges from $S$ to the network. We note that when two
users $u$ and $v$ are not connected, then $d(u,v)=+\infty$.

Objective of the user: Here, we combine all the costs calculated above and
compute the utility function of a newly joining node. The expected utility of
a user $u$ under a given strategy $S\subseteq\Omega$ is the profit gained from
collecting the fees, minus the fees paid for sending out transactions, and
minus the costs of the channels. Formally,

$\mathcal{U}_{u_{S}}=\mathbb{E}^{rev}_{u}-\mathbb{E}^{fees}_{u}-\sum_{(v,l)\in
S}L_{u}(v,l)$

We assume the utility of a disconnected node (i.e. a node that is not
connected to any other node in the network) is $-\infty$.

The objective of $u$ is to select a subset of users to connect to as well as
the amount of funds to lock into these channels that maximises their expected
utility subject to the budget constraints. Formally:

$\max_{S\in\Omega}\mathcal{U}_{u_{S}}\text{ s.t. }\sum_{(v,l_{u})\in
S}[C+l_{u}]\leq B_{u}$

##  III Optimisation algorithms

Having defined the utility and objective for a new user $u$ in Section II-C,
we now propose several algorithms to optimise the objective in this section.
We begin by establishing some properties of our objective function. We first
show that our utility function is submodular but not necessarily monotone and
not necessarily non-negative. Thus, we cannot apply standard algorithms to
optimise it efficiently with guarantees on the approximation ratio. We thus
propose a series of constraints on the actions of the new user $u$ and define
a solution for the objective in each constrained setting. We then provide a
corresponding optimisation algorithm for each setting that comes with
guarantees on the approximation ratio. In the following, let $[k]$ denote
$\\{1,\dots,k\\}$.

###  III-A Properties of the objective function

Whenever we add a new edge, its estimated average transaction rate will depend
on the current topology of the network and the capacities of the channels in
the network. We first show that the objective function is submodular. Let
$S\subset\Omega$ be a strategy. Note that we allow the algorithm to add more
than one channel with the same endpoint $v$ but different amounts of funds
$l_{i}$ to the strategy set $S$.

######  Theorem 1.

The expected utility function $\mathcal{U}_{u_{S}}$ is submodular.

###### Proof.

We split $\mathcal{U}_{u_{S}}$ into three components that sum to
$\mathcal{U}_{u_{S}}$ and show that each component is submodular. Since the
sum of submodular functions is submodular, the claim follows.

We first rewrite $\mathcal{U}_{u_{S}}$ as

$\mathcal{U}_{u_{S}}=\mathbb{E}^{rev}_{u}+\left(-\mathbb{E}^{fees}_{u}\right)+\left(-\sum_{(v,l)\in
S}L_{u}(v,l)\right).$ (4)

Consider the configurations with two strategies $u_{S_{1}},u_{S_{2}}$ with
$S_{1}\subseteq S_{2}$, and consider a pair $X=(x,l_{ux})\notin S_{2}$. Recall
that a function $g$ is submodular if $g(u_{S_{2}\cup\\{X\\}})-g(u_{S_{2}})\leq
g(u_{S_{1}\cup\\{X\\}})-g(u_{S_{1}})$.

Now first observe that

$\displaystyle\mathbb{E}^{rev}_{u_{S1\cup\\{x\\}}}-\mathbb{E}^{rev}_{u_{S1}}$
$\displaystyle=\mathbb{E}^{rev}_{u_{\\{X\\}}}=\lambda_{xu}\cdot
f_{avg}=\mathbb{E}^{rev}_{u_{S2\cup\\{X\\}}}-\mathbb{E}^{rev}_{u_{S2}}$

Hence the expected revenue function $\mathbb{E}^{rev}_{u_{S}}$ is submodular.
Note that in the calculations we assume that $\lambda_{xy}$ is a fixed value.

Now we show that the second component of 4 is submodular. That is,
$-\mathbb{E}^{fees}_{u_{S}}=-\lambda_{u}\sum_{v\in V;v\neq u}d(u,v)\cdot
f_{avg}^{T}\cdot p^{trans}_{u,v}$ is submodular. Let us denote the marginal
contribution in terms of the expected fees of adding $X$ to strategy $S$ as
$MC_{S}(X):=\mathbb{E}^{fees}_{u_{S}}-\mathbb{E}^{fees}_{u_{S\cup\\{X\\}}}$.
We note that $MC_{S}(X)$ only changes when one adds a pair $X=(x,l_{ux})$ to
$S$, such that a shortest path from $u$ to some $v$ goes through the vertex
$x$ in the new configuration $S\cup\\{X\\}$, i.e.:

$MC_{S}(X)=\lambda_{u}f_{avg}^{T}\sum_{\begin{subarray}{c}v\in V;v\neq u;\\\
x\in
sp_{S\cup\\{X\\}}(u,v)\end{subarray}}p^{trans}_{u,v}\Big{[}d_{S}(u,v)-d_{S\cup\\{X\\}}(u,v)\Big{]}$

Recall that $d(u,v)$ as defined for two disconnected nodes $u,v$ is $+\infty$.
Thus, $d_{S_{1}\cup\\{X\\}}(u,v)-d_{S_{1}}(u,v)\leq 0$ as $X\notin
S_{1},S_{2}$. Moreover, as $v\in S_{1},S_{2}$ are direct neighbours of $u$ in
all configurations, then
$|d_{S_{1}}(u,v)-d_{S_{1}\cup\\{X\\}}(u,v)|>|d_{S_{2}}(u,v)-d_{S_{2}\cup\\{X\\}}(u,v)|$.
Hence, we conclude that $MC_{S_{1}}(X)>MC_{S_{2}}(X)$. Note that in the
calculations we assume that $p^{trans}_{u,v}$ is a fixed value.

Finally, we show that the last component $-\sum_{(v,l)\in S}L_{u}(v,l)$ in 4
is submodular. The marginal contribution of $X=(x,l_{ux})$ to the channel
costs given $u_{S_{1}}$ is simply the cost of a single bidirectional channel
between $u$ and $x$, i.e. $L_{u}(v,x)$. This is exactly equal to the marginal
contribution given $u_{S_{2}}$. ∎

Now, we show that although the objective function is submodular, it is
unfortunately non-monotone. That is, for any two strategy sets $S_{1},S_{2}$
with $S_{1}\subset S_{2}$, it is not necessarily the case that
$\mathcal{U}_{u_{s_{1}}}\leq\mathcal{U}_{u_{s_{2}}}$.

######  Theorem 2.

The expected utility function $\mathcal{U}_{u_{S}}$ is not necessarily
monotone, but the modified utility function
$\mathcal{U}_{u_{S}}^{\prime}=\mathbb{E}^{rev}_{u}-\mathbb{E}^{fees}_{u}$ is
monotonically increasing.

###### Proof.

We analyse each component of $\mathcal{U}_{u_{S}}$ separately. First, we note
that a direct application of [20] shows that $\mathbb{E}^{rev}_{u}$ is
monotone increasing. Next, we look at expected fees:

$-\mathbb{E}[\text{fees encountered by }u_{S}]=-\lambda_{u}\sum_{v\in V;v\neq
u}d(u,v)\cdot f_{avg}^{T}\cdot p^{trans}_{u,v}.$

The monotonicity of this function directly follows from the fact that for any
$S_{1}\subseteq S_{2}$, $d_{S_{1}}(u,v)\geq d_{S_{2}}(u,v)$. Thus, the
function is monotonically increasing. Note that in the calculations we assume
that $p^{trans}_{u,v}$ is a fixed value.

Finally, $-\sum_{(v,l)\in S}L_{u}(v,l)$ is clearly a monotonically decreasing
function. Since two components of $\mathcal{U}_{u_{S}}$ are monotonically
increasing and one component is monotonically decreasing,
$\mathcal{U}_{u_{S}}$ is non-monotone. ∎

The final property we show about our objective function is that it is not
necessarily non-negative.

######  Theorem 3.

The expected utility function $\mathcal{U}_{u_{S}}$ is not necessarily non-
negative.

###### Proof.

This follows from the observation that the sum of the cost of creating
channels and the expected fees $\sum_{(v,l)\in
S}L_{u}(v,l)+\mathbb{E}^{fees}_{u}$ might easily get bigger than the expected
revenue $\mathbb{E}^{rev}_{u}$ when choosing some strategy $S\subseteq\Omega$.
∎

###  III-B Fixed amounts of funds per channel

We first show that if we restrict the amount of funds (say $l_{1}$) that the
new user $u$ can lock in each created channel, we can achieve an approximation
ratio of $1-\frac{1}{e}$. This setting is useful for users who want to
minimize their computational cost. The algorithm (described in Algorithm 1)
that achieves this ratio in this setting is simple – we greedily pick the $k$
best channels to connect with that maximize the expected revenue minus the
expected fees. Formally, let us define a simplified utility function
$\mathcal{U}_{u_{S}}^{\prime}$ which is the sum of the expected revenue and
the expected fees:
$\mathcal{U}_{u_{S}}^{\prime}=\mathbb{E}^{rev}_{u}+(-\mathbb{E}^{fees}_{u})$.

We note that the simplified utility function $\mathcal{U}_{u_{S}}^{\prime}$ is
submodular and monotone, as shown in III-A. Let us denote the maximum number
of channels that can be created given $u$’s budget $B_{u}$ by
$\textsc{M}:=\lfloor\frac{B_{u}}{C+l_{1}}\rfloor$. We can now maximize
$\mathcal{U}_{u_{S}}^{\prime}$ and find the optimal set of vertices to connect
to for each possible subset of vertices of size $k$. We do this for
$k\in\\{1,2,\ldots,\textsc{M}\\}$, and then compare the results for all $k$.
Since the channel creation cost is now fixed for any choice of $k$ new
channels, the $(1-\frac{1}{e})$-approximation we achieve when we greedily
maximize $\mathcal{U}_{u_{S}}^{\prime}$ simply follows from the result in [28]
since $\mathcal{U}_{u_{S}}^{\prime}$ is submodular and monotone.

The next theorem shows that Algorithm 1 returns a
$(1-\frac{1}{e})$-approximation and runs in time linear in M.

######  Theorem 4.

Algorithm 1 with inputs $\Omega=\\{(v,l_{1})\in V:v\neq u\\}$ and M returns a
$(1-\frac{1}{e})$-approximation of the optimum of
$\mathcal{U}_{u_{S}}^{\prime}$. The result is computed in at most
$\mathcal{O}(\textsc{M}\cdot n)$ number of estimations of the $\lambda_{uv}$
parameter.

###### Proof.

To see that Algorithm 1 returns a $(1-\frac{1}{e})$-approximation of the
optimum of $\mathcal{U}_{u_{S}}^{\prime}$, we need to see that in the
algorithm for each possible $k$ we compute a $(1-\frac{1}{e})$-approximation
of $\mathcal{U^{\prime}}$ (in $\mathcal{O}(n)$ time), because the function
$\mathcal{U^{\prime}}$ is submodular and monotonically increasing, then the
overall solution that compares partial results gives a
$(1-\frac{1}{e})$-approximation ratio for a fixed $k$. This in turn gives a
$(1-\frac{1}{e})$-approximation ratio for each
$k\in\\{1,2,\ldots,\textsc{M}\\}$. ∎

Input: $\Omega,\textsc{M}$

$P_{S}\leftarrow\text{array indexed }1,\ldots,\textsc{M}\text{ initialized
with }P[i]=\emptyset$

$P_{U}\leftarrow\text{array indexed }1,\ldots,\textsc{M}\text{ initialized
with }P[i]=-\infty$

$S\leftarrow\emptyset$

$A\leftarrow\Omega$

while  _$|S|\leq\textsc{M}$_ do

$X\leftarrow argmax_{X\in
A}[\mathcal{U^{\prime}}_{u_{S\cup\\{X\\}}}-\mathcal{U^{\prime}}_{u_{S}}]$

$S\leftarrow S\cup\\{X\\}$

$P_{S}[|S|]\leftarrow S$

$P_{U}[|S|]\leftarrow\mathcal{U^{\prime}}_{u_{S}}$

$A\leftarrow A\setminus\\{X\\}$

end while

$i\leftarrow argmax_{i\in\\{1,\ldots,M\\}}[P_{U}[i]]$

return $P_{S}[i]$

Algorithm 1 Greedy algorithm

###  III-C Varying amount of funds per channel, discrete version

Next, we give the new user a choice of locking varying amounts of capital in
each channel. Enabling varying capital on channels depicts more accurately the
realistic model of transaction distribution we leverage. However, in order to
achieve the same approximation ratio of $1-\frac{1}{e}$ as in the previous
setting, we have to discretize the capital that can be locked into a channel
to some minimal amount $m>0$. That is, opening a channel would require
injecting funds of the form $km$ for some $k\in\mathbb{N}$. We impose this
discretization constraint in order to perform an exhaustive search over all
possible assignments of the budget $B_{u}$ to the capital in each channel.

We again operate on the modified utility function
$\mathcal{U}_{u_{S}}^{\prime}$ and present an algorithm (described in
Algorithm 2) that achieves the same approximation ratio of $1-\frac{1}{e}$. In
more detail, given a parameter $m$, Algorithm 2 firstly divides the budget
$B_{u}$ to $\frac{B_{u}}{m}$ units that can be spent. Then, the algorithm
divides these units into $k+1$ parts (where $k=\lfloor\frac{B_{u}}{C}\rfloor$
is a bound on the number of channels that $u$ can possibly create). Finally,
for each possible division, it runs Algorithm 1 (again by temporarily skipping
the channel costs) in each step locking the capital assigned to this channel
in the division. Let us denote
$T:=\binom{\frac{B_{u}}{m}}{\frac{B_{u}}{C}+1}$.

Input: $V,B_{u},m$

$k=\lfloor\frac{B_{u}}{C}\rfloor$

$D=\text{array of all divisions of }[\lfloor\frac{B_{u}}{m}\rfloor]\text{ to
}k+1\text{ parts}$

$D_{S}\leftarrow\text{array indexed }1,\ldots,|D|\text{ initialized with
}D_{S}[i]=\emptyset$

for  _$i\in[|D|]$_ do

$(l_{1},\ldots,l_{k+1})\leftarrow D[i]$

$D_{S}[i]\leftarrow$ the output of Algorithm 1 run on $M=k$ with a restriction
that in every step $j$ of _while_ loop in the algorithm a channel of capacity
$l_{j}$ is selected

end for

$i\leftarrow
argmax_{i\in\\{1,\ldots,|D|\\}}\mathcal{U^{\prime}}_{u_{D_{S}[i]}}$

return $D_{S}[i]$

Algorithm 2 Exhaustive search over channel funds

######  Theorem 5.

Algorithm 2 with inputs $V$, budget $B_{u}$, and parameter $m$ returns a
$(1-\frac{1}{e})$-approximation of the optimum of
$\mathcal{U}_{u_{S}}^{\prime}$. The result is computed in at most
$\mathcal{O}(T\cdot\frac{B_{u}}{C}\cdot n)$ steps.

###### Proof.

The budget $\frac{B_{u}}{m}$ can be split to at most
$k=\lfloor\frac{B_{u}}{C}\rfloor$ parts in at most
$\binom{\frac{B_{u}}{m}}{k+1}$ cases. Algorithm 1 is run as a subroutine of
Algorithm 2. The main routine iterates through all possible combinations of
amounts locked to channels, each of them giving the
$(1-\frac{1}{e})$-approximation for the selected assignments of funds. ∎

We note that there is a trade-off between the choice of $m$ and the run time
of Algorithm 2: a larger $m$ would reduce the search space and hence the
runtime of the algorithm. However, it would reduce the control over the
capital the user could lock into any particular channel.

###  III-D Varying amount of funds per channel, continuous version

In this section, we remove the previous discrete constraint on the capital the
new user $u$ can inject into the channel, that is, $u$ can now inject funds of
the form $m\in\mathbb{R}+$ into any channel. We sketch a polynomial-time
$\frac{1}{5}$-approximation algorithm for the optimisation problem: let us
first denote the total expected on-chain transaction cost for a user $u$ with
an average output stream of $N_{u}$ transactions as $C_{u}:=\frac{N_{u}\cdot
C}{2}$. That is, $C_{u}$ represents the total expected cost for user $u$ when
$u$ transacts entirely on the blockchain. One can now consider what we term
the benefit function, which is simply the sum of $C_{u}$ and the utility of
$u$ when $u$ joins the network with strategy $S$. Formally, we denote this
function by $\mathcal{U}_{u_{S}}^{b}:=C_{u}+\mathcal{U}_{u_{S}}$. Intuitively,
the benefit function captures the potential benefit $u$ would gain from
transacting with other users over the PCN rather than on the blockchain.

We observe that $\mathcal{U}_{u_{S}}^{b}$ will stay submodular and positive
whenever the user chooses channels $(u,v)$, such that

$\mathbb{E}^{fees}_{u}+\frac{B_{u}}{C}\cdot L_{u}(v,l)<C_{u}.$

As such, we can apply the algorithm and result of Lee et al. [29] for
optimising submodular and non-negative functions to $\mathcal{U}_{u_{S}}^{b}$
to achieve a $\frac{1}{5}$-approximation of $\mathcal{U}_{u_{S}}^{b}$.

##  IV Structural properties of simple graph topologies

In this section, we complement our study of optimisation algorithms for users
in the payment channel network (Section III) with a study of structural
properties of simple graph topologies given the transaction model between
users as defined in Section II-B. We are particularly interested in properties
of stable networks, that is, networks that are in a Nash Equilibrium where no
user can increase their utility by any unilateral change in strategy.
Stability is an important notion in the context of PCNs as this has
implications not only on the choice of which nodes to connect to for a new
user [19] but also on payment routing and finding off-chain rebalancing cycles
for existing users to replenish depleted channels [30]. We are also interested
in the parameter space of our model under which specific graph topologies form
a Nash Equilibrium.

We use the following assumptions and notations in our analysis in this
section:

  1. 1.

Recall from Equations 2 and 3 in Section II that the expected revenue of a
user $u$ can be written as: $\mathbb{E}^{rev}_{u}=\sum_{v_{i}\in
Ne(u)}\lambda_{uv_{i}}\cdot f_{avg}=\sum_{\begin{subarray}{c}v_{1}\neq
v_{2}\\\ v_{1},v_{2}\in
V\setminus\\{u\\}\end{subarray}}\frac{m_{u}(v_{1},v_{2})}{m(v_{1},v_{2})}\cdot
N_{v_{1}}\cdot p^{trans}_{v_{1},v_{2}}\cdot f_{avg}$

We denote $b:=N_{v_{1}}\cdot f_{avg}$ and assume it is constant for $v_{1}\in
V\setminus\\{u\\}$.

  2. 2.

We denote $a:=N_{u}\cdot f_{avg}^{T}$.

  3. 3.

For any $s>0$ and $n\in\mathbb{N^{*}}$, we denote
$H_{n}^{s}:=\sum_{k=1}^{n}\frac{1}{k^{s}}$.

  4. 4.

All the players create channels of equal cost $l$.

###  IV-A Upper bound on the longest shortest path containing a hub

An interesting question is how large is the diameter of stable networks with
highly connected nodes. In the context of PCNs, this has implications on
efficient payment routing algorithms[31, 32, 33, 34]. As a first step to
answering this question, we derive an upper bound on the longest shortest path
in a stable network that contains a hub node, i.e., an extremely well-
connected node that transacts a lot with other nodes in the network. Let us
select a hub node $h$ and consider the longest shortest path that $h$ lies on
(if there are multiple we simply select one of them arbitrarily). We denote
the length of the path by $d$. The following theorem derives an upper bound on
$d$ for a stable network.

######  Theorem 6.

$d$ is upper bounded by $2(\frac{\frac{C+\epsilon}{2}-\lambda_{e}\cdot
f}{p_{\min}\cdot N\cdot f})+1$.

###### Proof.

Let $P=(v_{0},v_{1},\dots,v_{d})$ be the path. Consider the addition of an
edge $e$ between $v_{\lfloor\frac{d}{2}\rfloor-1}$ and
$v_{\lfloor\frac{d}{2}\rfloor+1}$. Denote by $\lambda_{e}$ the minimum rate of
transactions going through the edge $e$ in both directions, i.e.
$\lambda_{e}:=\min\\{\lambda_{(v_{\lfloor\frac{d}{2}\rfloor-1},v_{\lfloor\frac{d}{2}\rfloor+1})},\lambda_{(v_{\lfloor\frac{d}{2}\rfloor+1},v_{\lfloor\frac{d}{2}\rfloor-1})}\\}$.

Now consider the set of directed shortest paths $S$ such that each path
$s_{i}\in S$ is a sub sequence of $P$ and one end point of $s_{i}$ lies in
$\\{v_{0},\dots,v_{\lfloor\frac{d}{2}\rfloor-1}\\}$ and the other end point of
$s_{i}$ lies in $\\{v_{\lfloor\frac{d}{2}\rfloor+1},\dots,v_{d}\\}$. Let
$p_{i}$ be the probability that $s_{i}$ is selected, with probabilities of
directed paths being selected as defined by the probability of the source of
the path transacting with the sink (refer to 1 for more details). Let
$p_{\min}:=\min_{i}p_{i}$.

We know the cost (split equally) of creating the edge $e$ is at least
$\frac{C+\epsilon}{2}$. Since the network is stable, this implies that the
cost of creating $e$ is larger than any benefits gained by the $2$ users
$v_{\lfloor\frac{d}{2}\rfloor-1}$ and $v_{\lfloor\frac{d}{2}\rfloor+1}$ by
creating $e$. That is,

$\frac{C+\epsilon}{2}\geq\lambda_{e}\cdot f+N\cdot p_{\min}\cdot
f\cdot\lfloor\frac{d}{2}\rfloor,$ (5)

where the first term on the RHS of the inequality is the minimum (among the
two parties $v_{\lfloor\frac{d}{2}\rfloor-1}$ and
$v_{\lfloor\frac{d}{2}\rfloor+1}$) of the average revenue gained by adding the
edge $e$. The second term on the RHS of the inequality is a lower bound on the
average amount of fees saved by $v_{\lfloor\frac{d}{2}\rfloor-1}$ and
$v_{\lfloor\frac{d}{2}\rfloor+1}$. Rearranging, this implies that $d\leq
2(\dfrac{\dfrac{C+\epsilon}{2}-\lambda_{e}\cdot f}{p_{\min}\cdot N\cdot
f})+1.$ ∎

Note that since a hub node is on the path, as long as it is not directly in
the middle of the path (i.e. vertex $v_{\lfloor\frac{d}{2}\rfloor}$),
$p_{\min}$ should be fairly large as hubs are typically high degree vertices.
Moreover, if a hub node is on a diametral path, we extract a meaningful bound
on the diameter of a stable network.

###  IV-B Stability of simple graph topologies

In this section, we study some simple graph topologies, and the parameter
spaces of the underlying transaction distribution under which they form a Nash
Equilibrium. We restrict our analysis to these simple topologies because
computing Nash Equilibria for a general graph using best response dynamics is
NP-hard (see Theorem $2$ in [19]). As mentioned in Section II-B, we assume the
underlying transaction distribution that gives the probability of any two
nodes transacting with each other is the Zipf distribution.

We firstly show that when the scale parameter $s$ of the Zipf distribution is
large (i.e. the distribution is heavily biased towards transacting with only
high-degree nodes), the star graph is a Nash Equilibrium.

######  Theorem 7.

The star graph with the number of leaves $\geq 4$ is a Nash Equilibrium when
nodes transact with each other according to the Zipf distribution with
parameter $s$ such that $\frac{1}{2^{s}}$ is negligible, i.e.
$\frac{1}{2^{s}}\approx 0$.

###### Proof.

First note that, because $\frac{1}{2^{s}}$ is negligible, then all leaf nodes
have negligible expected revenue. Now consider a leaf node $u$. The costs of
the leaf node $u$ are triggered by transacting with the central node. If $u$
removes the edge between $u$ and the central node, and replaces this
connection with a set of edges to other leaf nodes, $\mathbb{E}^{fees}_{u}$
can only rise, as the central node still remains the one with the highest
degree.

The central node may want to delete all of its edges, but this will result
only in lowering its $\mathbb{E}^{rev}_{u}$. The $\mathbb{E}^{fees}_{u}$ may
not go down, because the central node already communicates directly with all
leaf nodes. ∎

Secondly, we establish the necessary conditions that make the star graph a
Nash Equilibrium in general.

######  Theorem 8.

The star graph with the number of leaves $n\geq 2$ is a Nash Equilibrium when
nodes transact with each other according to the Zipf distribution with
parameter $s\geq 0$ whenever the following conditions hold:

  1. 1.

$a/H_{n}^{s}\leq 2^{s}\cdot l\cdot 1$,

  2. 2.

$b\cdot\frac{i}{2}\cdot\frac{H_{i+1}^{s}-1-1/2^{s}}{H_{n}^{s}}+a\cdot\frac{H_{i+1}^{s}-1}{H_{n}^{s}}\leq
l\cdot(i)$ (for $2\leq i\leq n-1$),

  3. 3.

$b\cdot\frac{i}{2}\cdot\frac{H_{n}^{s}-1-1/2^{s}}{H_{n}^{s}}+a\frac{H_{i+1}^{s}-2}{H_{n}}\leq
l\cdot(i-1)$ (for $2\leq i\leq n-1$).

###### Proof.

Firstly, we prove that the _central node_ is in Nash Equilibrium in the star
graph. Since the central node is connected to all other nodes, adding an
additional channel to any node just increases the channel creation cost and
thus decreases the utility for the central node. Removing a single edge
disconnects the central node from a user and thus leads to infinite cost. Thus
the central node has no incentive to switch to a different strategy.

Secondly, we prove when any _leaf node_ is also in Nash Equilibrium in the
star graph. For every strategy defined below, we calculate expected revenue
$\mathbb{E}^{rev}_{u}$, expected costs $\mathbb{E}^{fees}_{u}$, and channels
cost $L$ of the node $u$ after changes.

– By default a leaf node $u$ will not add/remove any edges.

  * •

$\mathbb{E}^{rev}_{u}=0$

  * •

She interacts with 1 central node with $rf=1$, and $n-1$ leaf nodes with
$rf=\frac{H_{n}^{s}-1}{n-1}$. $\sum_{v^{\prime}\in
V\setminus\\{u\\}=1+(n-1)\cdot\frac{H_{n}^{s}-1}{n-1}}=H_{n}^{s}$,
$\mathbb{E}^{fees}_{u}=-a(n-1)\frac{\frac{H_{n}^{s}-1}{n-1}}{H_{n}^{s}}=-a\cdot\frac{H_{n}^{s}-1}{H_{n}^{s}}$,
$L=-l\cdot 1$.

– A leaf node may also try to add connections to $n-1$ other leaf nodes.

  * •

the other leaf nodes $v^{\prime}$ interact directly, with $2$ nodes (the
central node, and the nodes that changes its strategy, both connected to $n-1$
other nodes) with $rf=\frac{1+1/2^{s}}{2}$, and indirectly with $n-2$ other
nodes with $rf=\frac{H_{n}^{s}-1-1/2^{s}}{n-2}$. $\sum_{v^{\prime\prime}\in
V\setminus\\{v^{\prime}\\}}rf(v^{\prime\prime})=H_{n}^{s}$
$\mathbb{E}^{rev}_{u}=b\cdot[2\cdot
1/2]\binom{n-1}{2}\frac{\frac{H_{n}^{s}-1-1/2^{s}}{n-2}}{H_{n}^{s}}=b\cdot\frac{n-1}{2}\cdot\frac{H_{n}^{s}-1-1/2^{s}}{H_{n}^{s}}$

  * •

$\mathbb{E}^{fees}_{u}=0$, $L=-l\cdot n$.

– The leaf node may also add connections to $n-1$ leaf nodes and remove the
connection with the central node.

  * •

the other leaf nodes $v^{\prime}$ interact directly, with $2$ nodes (the
central node, and the nodes that changes its strategy, both connected to $n-2$
other nodes) with $rf=\frac{1+1/2^{s}}{2}$, and indirectly with $n-2$ other
nodes with $rf=\frac{H_{n}-1-1/2^{s}}{n-2}$. $\sum_{v^{\prime\prime}\in
V\setminus\\{v^{\prime}\\}}rf(v^{\prime\prime})=H_{n}^{s}$
$\mathbb{E}^{rev}_{u}=b\cdot[2\cdot
1/2]\binom{n-1}{2}\frac{\frac{H_{n}-1-1/2^{s}}{n-2}}{H_{n}^{s}}=b\cdot\frac{n-1}{2}\cdot\frac{H_{n}^{s}-1-1/2^{s}}{H_{n}^{s}}$

  * •

$\mathbb{E}^{fees}_{u}=-a/H_{n}^{s}$, $L=-l\cdot(n-1)$.

– The leaf node can add connection to only one other $1$ leaf node.

  * •

$\mathbb{E}^{rev}_{u}=0$

  * •

$u$ connects to one central node $rf=1$, $1$ node with $rf=\frac{1}{2^{s}}$,
and $n-2$ other nodes - $rf=\frac{H_{n}^{s}-1-\frac{1}{2^{s}}}{n-2}$.
$\sum=H_{n}^{s}$

$\mathbb{E}^{fees}_{u}=-a(n-2)\cdot\frac{\frac{H_{n}^{s}-1-\frac{1}{2^{s}}}{n-2}}{H_{n}^{s}}=-a\cdot(H_{n}^{s}-1-\frac{1}{2^{s}})/H_{n}^{s}$,
$L=-l\cdot 2$.

– The leaf node can add connections to $2\leq i\leq n-2$ other leaf nodes.

  * •

the leaf nodes $v^{\prime}$ that $u$ connects to interact with $1$ central
node ($rf=1$), the $u$ node ($rf=1/2$), $i-1$ other nodes that $u$ connects to
$rf=\frac{H_{i+1}^{s}-1-1/2}{i-1}$, and $n-H_{i+1}^{s}$ other nodes.

$\sum_{v^{\prime\prime}\in
V\setminus\\{v^{\prime}\\}}rf(v^{\prime\prime})=H_{n}^{s}$
$\mathbb{E}^{rev}_{u}=b\cdot[2\cdot
1/2]\binom{i}{2}\frac{\frac{H_{i+1}^{s}-1-1/2}{i-1}}{H_{n}^{s}}=b\cdot\frac{i}{2}\cdot\frac{H_{i+1}^{s}-1-1/2^{s}}{H_{n}^{s}}$

  * •

From the perspective o f $u$, the central node has $rf=1$, the nodes that the
$u$ connects to have $rf=\frac{H_{i+1}^{s}-1}{i}$, the other nodes have
$rf=\frac{H_{n}^{s}-H_{i+1}^{s}}{n-i-1}$. $\sum=H_{n}^{s}$.

$\mathbb{E}^{fees}_{u}=-a(n-i-1)\frac{H_{n}^{s}-H_{i+1}^{s}}{n-i-1}/H_{n}^{s}=-a\cdot(H_{n}^{s}-H_{i+1}^{s})/H_{n}^{s}$,
$L=-l\cdot(i+1)$.

– The leaf node can add connections to $2\leq i\leq n-2$ leaf nodes and remove
the connection with the central node.

  * •

the other leaf nodes $v^{\prime}$ interact directly, with $2$ nodes, the
central node with $rf=1$, the $u$ node with $rf=1/2$ and indirectly with $i-1$
other nodes with $rf=\frac{H_{i+1}-1-1/2}{i-1}$. $\sum_{v^{\prime\prime}\in
V\setminus\\{v^{\prime}\\}}rf(v^{\prime\prime})=H_{n}$
$\mathbb{E}^{rev}_{u}=b\cdot[2\cdot
1/2]\binom{i}{2}\frac{\frac{H_{i+1}^{s}-1-1/2^{s}}{i-1}}{H_{i+1}^{s}}=b\cdot\frac{i}{2}\cdot\frac{H_{i+1}^{s}-1-1/2^{s}}{H_{n}}$

  * •

From the perspective o f $u$, the central node has $rf=1$, the nodes that the
$u$ connects to have $rf=\frac{H_{i+1}^{s}-1}{i}$, the other nodes have
$rf=\frac{H_{n}^{s}-H_{i+1}^{s}}{n-i-1}$. $\sum=H_{n}^{s}$.

$\mathbb{E}^{fees}_{u}=-a\cdot[(n-i-1)\frac{H_{n}^{s}-H_{i+1}^{s}}{n-i-1}/H_{n}^{s}+1/H_{n}^{s}]=-a\cdot(H_{n}^{s}-H_{i+1}^{s}+1)/H_{n}^{s}$,
$L=-l\cdot i$.

Now we compare the utility gained by switching to each strategy as opposed to
sticking to the default strategy:

#### (1) vs (2).

If (1) remains a NE then:

$\displaystyle-a\cdot\frac{H_{n}^{s}-1}{H_{n}^{s}}-l\cdot 1\geq
b\cdot\frac{n-1}{2}\cdot\frac{H_{n}^{s}-1-1/2^{s}}{H_{n}^{s}}-l\cdot(n)$
$\displaystyle\iff$ $\displaystyle
a\cdot\frac{H_{n}^{s}-1}{H_{n}^{s}}+b\cdot\frac{n-1}{2}\cdot\frac{H_{n}^{s}-1-1/2^{s}}{H_{n}^{s}}\leq
l\cdot(n-1)$

#### (1) vs (3).

If (1) remains a NE, then for any value of the parameter $s\geq 0$:

$\displaystyle-a\cdot\frac{H_{n}^{s}-1}{H_{n}^{s}}-l\cdot 1\geq
b\cdot\frac{n-1}{2}\cdot\frac{H_{n}^{s}-3/2}{H_{n}^{s}}-l\cdot(n-1)-$
$\displaystyle-a/H_{n}^{s}\iff$ $\displaystyle
a\cdot\frac{H_{n}^{s}-2}{H_{n}^{s}}+b\cdot\frac{n-1}{2}\cdot\frac{H_{n}^{s}-1-1/2^{s}}{H_{n}^{s}}\leq
l\cdot(n-2)$

#### (1) vs (4).

If (1) remains a NE:

$\displaystyle-a\cdot\frac{H_{n}^{s}-1}{H_{n}^{s}}-l\cdot
1\geq-a\cdot(H_{n}^{s}-1-1/2^{s})/H_{n}^{s}-\text{cost of 2}$
$\displaystyle\iff$ $\displaystyle a/H_{n}^{s}\leq 2^{s}\cdot l\cdot 1$

#### (1) vs (5).

If (1) remains a NE:

$\displaystyle-a\cdot\frac{H_{n}^{s}-1}{H_{n}^{s}}-l\cdot 1\geq
b\cdot\frac{i}{2}\cdot\frac{H_{i+1}^{s}-1-1/2^{s}}{H_{n}^{s}}-\frac{a\cdot(H_{n}^{s}-H_{i+1}^{s})}{H_{n}^{s}}-$
$\displaystyle-l\cdot(i+1)\iff$ $\displaystyle
b\cdot\frac{i}{2}\cdot\frac{H_{i+1}^{s}-1-1/2^{s}}{H_{n}^{s}}+a\cdot\frac{H_{i+1}^{s}-1}{H_{n}^{s}}\leq
l\cdot i$

#### (1) vs (6).

If (1) remains a NE:

$\displaystyle-a\cdot\frac{H_{n}^{s}-1}{H_{n}^{s}}-l\cdot 1\geq
b\cdot\frac{i}{2}\cdot\frac{H_{n}^{s}-1-1/2^{s}}{H_{n}^{s}}-a\cdot\frac{1+H_{n}^{s}-H_{i+1}^{s}}{H_{n}^{s}}-$
$\displaystyle-l\cdot i\iff$ $\displaystyle
b\cdot\frac{i}{2}\cdot\frac{H_{n}^{s}-1-1/2^{s}}{H_{n}^{s}}+a\frac{H_{i+1}^{s}-2}{H_{n}}\leq
l\cdot(i-1)$

∎

Given the result above, we show that if the scale parameter of the
distribution is _only_ moderately large ($s\geq 2$) and not too many messages
are sent out in the network (i.e. $a/H_{n}^{s},b/H_{n}^{s}\leq l$), then the
star graph is still a Nash Equilibrium. The values
$a/H_{n}^{s},b/H_{n}^{s}\leq l\cdot 1$ give a bound on the transactions sent
to the highest ranked node of a user.

######  Theorem 9.

The star graph with a number of leaves $n\geq 2$ is a Nash Equilibrium when
nodes follow the Zipf distribution with parameter $s\geq 2$ whenever the cost
of all edges is equal, and $a/H_{n}^{s},b/H_{n}^{s}\leq l\cdot 1$.

###### Proof.

Taking the conditions from Theorem 8:

  1. 1.

$b\cdot\frac{i}{2}\cdot\frac{H_{i+1}^{s}-1-1/2^{s}}{H_{n}^{s}}+a\cdot\frac{H_{i+1}^{s}-1}{H_{n}^{s}}\leq
l\cdot(i)$ (for $2\leq i\leq n-1$),

  2. 2.

$b\cdot\frac{i}{2}\cdot\frac{H_{n}^{s}-1-1/2^{s}}{H_{n}^{s}}+a\frac{H_{i+1}^{s}-2}{H_{n}^{s}}\leq
l\cdot(i-1)$ (for $2\leq i\leq n-1$),

  3. 3.

$a/H_{n}^{s}\leq 2^{s}\cdot l\cdot 1$.

We can see that with our assumptions, condition $3$ holds trivially as
$a/H_{n}^{s}\leq l\cdot 1$. Moreover, whenever the cost of all edges is equal,
conditions $1,2$ are more restrictive, whenever $i$ increases, so the most
restrictive case is when $i=n-1$. Now, because $a/H_{n}^{s}\leq l\cdot 1$,
condition $2$ is more restrictive than $1$. Finally, condition $2$ holds,
because $a/H_{n}^{s},b/H_{n}^{s}\leq l\cdot 1$, and for $s\geq 2$,
$H_{n}^{s}=\sum_{i=1}^{n}\dfrac{1}{i^{s}}\leq\sum_{j=1}^{+\infty}j\cdot\dfrac{1}{j^{s}}\leq
2.$ ∎

We also show that the path graph essentially will never become a Nash
Equilibrium.

######  Theorem 10.

A path graph is never a Nash Equilibrium when nodes transact with each other
according to the Zipf distribution with parameter $s\geq 0$.

###### Proof.

Since the cost of any edge is split equally between both parties, the
endpoints of the path would always prefer joining to a node that is not an
endpoint of the path. In this case, even when $s=0$, their expected revenue
factor still remains $0$, but the cost of the expected fees naturally gets
lower. ∎

We finally show that circle graph cannot be a NE when it is sufficiently
large.

######  Theorem 11.

The Circle graph does not form a Nash Equilibrium for all $n\geq n_{0}$, for
some $n_{0}$, when nodes transact with each other according to the Zipf
distribution with $s\geq 0$.

###### Proof.

Assume that we have a circle graph with $n+1$ nodes. – Default strategy for a
node $u$ is not to add or remove any edges.

  * •

In this case $u$ is an intermediary node to all of the pairs of nodes for
which the shortest path goes through this node. They rank each other equally,
so each node ranks other nodes with equal $rf=H_{n}^{s}/n$, thus $\sum
rf=H_{n}^{s}$, finally
$\mathbb{E}^{rev}_{u}=b\cdot\frac{H_{n}^{s}/n}{H_{n}^{s}}2\cdot(\binom{n}{2}-\binom{n/2}{2}-n/2\cdot
n/2)\approx\frac{b}{n}\cdot n^{2}/4$

  * •

The node $u$ interacts with $n$ nodes with $rf=H_{n}^{s}/n$. $2$ of them are
in distance $0$, $2$ are in distance $1$, and so on. Finally at most $2$ of
them are in distance $\lfloor n/2\rfloor$.
$\mathbb{E}^{fees}_{u}=-a\cdot\frac{H_{n}^{s}/n}{H^{s}_{n}}\cdot
2\cdot(1+2+\ldots+n/2)\approx\frac{-a}{n}\cdot n^{2}/4$.

  * •

$L=-l\cdot 1$.

– A strictly better strategy for the node $u$ is to connect to its opposite
node.

  * •

In this case $u$ is an intermediary node to all of the pairs of nodes for
which the shortest path goes through this node. The opposite node $u$ ranks
$u$ with $rf=1$ and all of the other nodes with $rf=\frac{H_{n}^{s}-1}{n-1}$
the other nodes rank 2 nodes with $rf=\frac{1+1/2^{s}}{2}$, and all of the
other nodes with $rf=\frac{H_{n}^{s}-1-1/2^{s}}{n-2}$, thus $\sum
rf=H_{n}^{s}$. We will thus asymptotically count only the weakest
$rf=\frac{H_{n}^{s}-1-1/2^{s}}{n-2}$ factor. Finally
$\mathbb{E}^{rev}_{u}=b\cdot\frac{H_{n}^{s}-1-1/2^{s}}{n-2}\cdot
2\cdot(\frac{n}{4}\cdot\frac{n}{2}+\frac{1}{2}\cdot\frac{n}{4}\
\cdot\frac{n}{4})\approx\frac{b}{n}\cdot n^{2}(5/16)$

  * •

The node $u$ interacts with $n-1$ nodes with $rf=(H_{n}^{s}-1)/(n-1)$, and
directly with one node with $rf=1$. We calculate the closeness as:

$\displaystyle\mathbb{E}^{fees}_{u}\leq-a\cdot\frac{(H_{n}^{s}-1)/(n-1)}{H^{s}_{n}}\cdot\frac{3\frac{n}{4}(\frac{n}{4}-1)}{2}$
$\displaystyle+\frac{n/2+n/4}{2}\cdot\frac{n}{4})=\frac{-a(H_{n}^{s}-1)/(n-1)}{H^{s}_{n}}\leq\frac{3}{16}n^{2}.$

  * •

$L=-l\cdot 1.$

∎

##  V Related work

Strategic aspects of cryptocurrencies, and more generally the blockchain
technologies, have attracted a lot of attention in the literature [35, 36, 37]
as by their very nature, they are created to facilitate interactions between
self-interested parties in a decentralised manner.

Apart from the works discussed in the introduction ([19, 18, 20, 17]), perhaps
the closest research line to which our paper contributes is the one on
creation games. In a well-known work by Fabrikant et al. [38], players choose
a subset of other players to connect to in order to minimise their total
distance to all others in the network. The result of Fabrikant et al. was
later strengthened by Albers et al. [39], and also extended to the weighted
network creation game setting. Ehsani et al. [40] considers the network
creation game with a fixed budget for each player, thus constraining the
number of connections each player can make. Another well-known body of
research of this kind are network formation games [41, 42]. All of these
works, however, consider the problem of network creation in general networks
which do not take into account fees and channel collateral which are specific
to PCNs.

Our work is also closely related to the study of stable network topologies for
real-world networks (e.g. social and communication networks) that are formed
by the interaction of rational agents [43, 26]. Demaine et al. [43] show that
all equilibrium networks satisfy the small world property, that is, these
networks have small diameters. Bilo et al. [26] establish properties on the
diameter, clustering and degree distribution for equilibrium networks. In [18,
19], Avarikioti et al. consider stable graph topologies in the context of
PCNs. Our work extends the analysis of Avarikioti et al. [19] and considers
stable graph topologies in PCNs under a non-uniform distribution of
transactions between users.

##  VI Conclusion and Future Work

In this paper, we modeled and analysed the incentive structure behind the
creation of PCNs. We first focused on the perspective of a new user who wants
to join the network in an optimal way. To this end, we defined a new user’s
utility function in terms of expected revenue, expected fees, on-chain cost of
creating channels, and opportunity costs, while accounting for realistic
transaction distributions.

We also introduced a series of approximation algorithms under specific
constraints on the capital distribution during the channel creation: (a) We
first presented a linear time $1-\frac{1}{e}$ approximation algorithm when a
user locks a fixed amount to all channels; thus, providing an efficient
approach for users who wish to lower computational costs. (b) We further
provided a pseudo-polynomial time $1-\frac{1}{e}$ approximation algorithm when
users may lock varying, but discretized by $m$, amounts to different channels.
This setting applies to most real-life scenarios but comes with a
computational overhead that depends on $m$. (c) Finally, we proposed a $1/5$
approximation solution when a user can pick the amounts from a continuous set.
We used a modified utility function, the benefit function, which may be
leveraged by a user to test whether assuming continuous funds yields
unexpected profits. Altogether, our results in this section show that
depending on the number of assumptions a new user joining a PCN wants to make,
the user has a range of solutions to deploy to optimize the way they connect
to the network.

Lastly, we analysed the parameter spaces in our underlying model and
conditions under which the star, path, and circle graph topologies form a Nash
Equilibrium. Our analysis indicates that under a realistic transaction model,
the star graph is the predominant topology, enhancing the results of [19].

We highlight three interesting directions for future work. First, it would be
beneficial to develop more advanced algorithms for maximizing the general
utility function that also come with guarantees on the approximation ratio.
Second, we believe there are still avenues in which our model can be made more
realistic, for instance, by considering a more realistic cost model that takes
into account interest rates as in [17]. Lastly, as the accuracy of our model
depends on estimations of the underlying PCN parameters, for instance, the
average total number of transactions and the average number of transactions
sent out by each user, developing more accurate methods for estimating these
parameters may be helpful.

## Acknowledgments

The work was partially supported by the Austrian Science Fund (FWF) through
the project CoRaF (grant 2020388). It was also partially supported by NCN
Grant 2019/35/B/ST6/04138 and ERC Grant 885666.

## References

  * [1] A. Chauhan, O. P. Malviya, M. Verma, and T. S. Mor, “Blockchain and scalability,” in _2018 IEEE International Conference on Software Quality, Reliability and Security Companion (QRS-C)_. IEEE, 2018, pp. 122–128.
  * [2] K. Croman, C. Decker, I. Eyal, A. E. Gencer, A. Juels, A. E. Kosba, A. Miller, P. Saxena, E. Shi, E. G. Sirer, D. Song, and R. Wattenhofer, “On scaling decentralized blockchains - (A position paper),” in _Financial Cryptography and Data Security FC_ , ser. Lecture Notes in Computer Science.
  * [3] A. Jain, S. Siddiqui, and S. Gujar, “We might walk together, but i run faster: Network fairness and scalability in blockchains,” in _International Conference on Autonomous Agents and MultiAgent Systems_ , 2021.
  * [4] Visa Inc., “Operational performance data for 4q21 https://s1.q4cdn.com $>$ doc$\\_$financials $>$ 2021 $>$ q4,” 12 2021.
  * [5] T. D. Joseph Poon, “The bitcoin lightning network: Scalable off-chain instant payments,” 2016. [Online]. Available: https://lightning.network/lightning-network-paper.pdf
  * [6] S. K. T. Utomo, T. H. Koshizuka, and N. Koshizuka, “Blockchain-based incentive system for public trash bin,” in _2020 IEEE 9th Global Conference on Consumer Electronics (GCCE)_. IEEE, 2020, pp. 168–172.
  * [7] L. Gudgeon, P. Moreno-Sanchez, S. Roos, P. McCorry, and A. Gervais, “Sok: Layer-two blockchain protocols,” in _International Conference on Financial Cryptography and Data Security_. Springer, 2020, pp. 201–226.
  * [8] A. Kiayias and O. S. T. Litos, “A composable security treatment of the lightning network,” _Cryptology ePrint Archive_ , 2019.
  * [9] G. Malavolta, P. Moreno-Sanchez, A. Kate, M. Maffei, and S. Ravi, “Concurrency and privacy with payment-channel networks,” in _ACM SIGSAC Conference on Computer and Communications Security_ , 2017.
  * [10] S. Rain, Z. Avarikioti, L. Kovács, and M. Maffei, “Towards a game-theoretic security analysis of off-chain protocols,” _arXiv preprint arXiv:2109.07429_ , 2021.
  * [11] Z. Avarikioti, E. Kokoris-Kogias, R. Wattenhofer, and D. Zindros, “Brick: Asynchronous incentive-compatible payment channels,” in _Financial Cryptography and Data Security FC_ , 2021.
  * [12] Z. Avarikioti and O. S. T. Litos, “Suborn channels: Incentives against timelock bribes,” in _Financial Cryptography and Data Security FC_ , 2022\.
  * [13] P. McCorry, S. Bakshi, I. Bentov, S. Meiklejohn, and A. Miller, “Pisa: Arbitration outsourcing for state channels,” in _Proceedings of the 1st ACM Conference on Advances in Financial Technologies, AFT_ , 2019.
  * [14] Z. Avarikioti, O. S. T. Litos, and R. Wattenhofer, “Cerberus channels: Incentivizing watchtowers for bitcoin,” in _Financial Cryptography and Data Security FC_ , 2020.
  * [15] X. Wang, H. Gu, Z. Li, F. Zhou, R. Yu, and D. Yang, “Why riding the lightning? equilibrium analysis for payment hub pricing.”
  * [16] Y. van Engelshoven and S. Roos, “The merchant: Avoiding payment channel depletion through incentives,” in _IEEE International Conference on Decentralized Applications and Infrastructures, DAPPS_ , 2021.
  * [17] P. Guasoni, G. Huberman, and C. Shikhelman, “Lightning network economics: Channels,” 2021. [Online]. Available: http://dx.doi.org/10.2139/ssrn.3840374
  * [18] G. Avarikioti, R. Scheuner, and R. Wattenhofer, “Payment networks as creation games,” in _Data Privacy Management, Cryptocurrencies and Blockchain Technology CBT_ , vol. 11737, 2019, pp. 195–210.
  * [19] Z. Avarikioti, L. Heimbach, Y. Wang, and R. Wattenhofer, “Ride the lightning: The game theory of payment channels,” in _Financial Cryptography and Data Security - 24th International Conference, FC_ , ser. Lecture Notes in Computer Science, vol. 12059, 2020, pp. 264–283.
  * [20] O. Ersoy, S. Roos, and Z. Erkin, “How to profit from payments channels,” in _Financial Cryptography and Data Security FC_ , 2020, p. 284–303. [Online]. Available: https://doi.org/10.1007/978-3-030-51280-4_16
  * [21] A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” _science_ , vol. 286, no. 5439, pp. 509–512, 1999.
  * [22] E. W. Dijkstra, “A note on two problems in connexion with graphs,” _Numerische Mathematik_ , vol. 1, pp. 269–271, 1959. [Online]. Available: https://doi.org/10.1007/BF01386390
  * [23] G. K. Zipf, _Human behavior and the principle of least effort_. Addison-Wesley Press, 1949.
  * [24] C. Salge, N. Ay, D. Polani, and M. Prokopenko, “Zipf’s law: Balancing signal usage cost and communication efficiency,” in _PLoS ONE_ , N. R. Smalheiser, Ed., 2015.
  * [25] L. Aitchison, N. Corradi, and P. E. Latham, “Zipf’s law arises naturally when there are underlying, unobserved variables,” in _PLoS computational biology_ , O. Sporns, Ed., 2016.
  * [26] D. Bilò, T. Friedrich, P. Lenzner, S. Lowski, and A. Melnichenko, “Selfish creation of social networks,” in _Thirty-Fifth AAAI Conference on Artificial Intelligence, Virtual Event_. AAAI Press, 2021, pp. 5185–5193.
  * [27] R. Hall and M. Lieberman, _Macroeconomics: Principles and Applications_ , ser. Accounting Principles S. South-Western College Pub., 1998. [Online]. Available: https://books.google.at/books?id=pyazAAAAIAAJ
  * [28] D. P. Williamson, “Bridging continuous and discrete optimization,” https://people.orie.cornell.edu/dpw/orie6334/lecture23.pdf, 2019.
  * [29] J. Lee, V. S. Mirrokni, V. Nagarajan, and M. Sviridenko, “Non-monotone submodular maximization under matroid and knapsack constraints,” in _ACM Symposium on Theory of Computing, STOC_ , M. Mitzenmacher, Ed., 2009\.
  * [30] Z. Avarikioti, K. Pietrzak, I. Salem, S. Schmid, S. Tiwari, and M. Yeo, “Hide & seek: Privacy-preserving rebalancing on payment channel networks,” in _Financial Cryptography and Data Security FC_ , 2022.
  * [31] S. Roos, P. Moreno-Sanchez, A. Kate, and I. Goldberg, “Settling payments fast and private: Efficient decentralized routing for path-based transactions,” in _25th Annual Network and Distributed System Security Symposium, NDSS_ , 2018.
  * [32] V. Sivaraman, S. B. Venkatakrishnan, K. Ruan, P. Negi, L. Yang, R. Mittal, G. Fanti, and M. Alizadeh, “High throughput cryptocurrency routing in payment channel networks,” in _17th USENIX Symposium on Networked Systems Design and Implementation, NSDI_ , 2020.
  * [33] K. Pietrzak, I. Salem, S. Schmid, and M. Yeo, “Lightpir: Privacy-preserving route discovery for payment channel networks,” in _IFIP Networking Conference, IFIP Networking 2021_ , 2021.
  * [34] M. Gerla, X. Hong, and G. Pei, “Landmark routing for large ad hoc wireless networks,” in _Globecom ’00 - IEEE. Global Telecommunications Conference. Conference Record (Cat. No.00CH37137)_ , vol. 3, 2000, pp. 1702–1706 vol.3.
  * [35] L. Chen, L. Xu, Z. Gao, A. Sunny, K. Kasichainula, and W. Shi, “A game theoretical analysis of non-linear blockchain system,” in _International Conference on Autonomous Agents and MultiAgent Systems_ , 2021\.
  * [36] Y. Amoussou-Guenou, B. Biais, M. Potop-Butucaru, and S. Tucci-Piergiovanni, “Rational vs byzantine players in consensus-based blockchains,” in _International Conference on Autonomous Agents and MultiAgent Systems_ , 2020, pp. 43–51.
  * [37] Y. Lewenberg, Y. Bachrach, Y. Sompolinsky, A. Zohar, and J. S. Rosenschein, “Bitcoin mining pools: A cooperative game theoretic analysis,” in _International conference on autonomous agents and multiagent systems_ , 2015, pp. 919–927.
  * [38] A. Fabrikant, A. Luthra, E. N. Maneva, C. H. Papadimitriou, and S. Shenker, “On a network creation game,” in _ACM Symposium on Principles of Distributed Computing, PODC_ , 2003, pp. 347–351.
  * [39] S. Albers, S. Eilts, E. Even-Dar, Y. Mansour, and L. Roditty, “On nash equilibria for a network creation game,” _ACM Trans. Economics and Comput._ , vol. 2, no. 1, pp. 2:1–2:27, 2014.
  * [40] S. Ehsani, M. Fazli, A. Mehrabian, S. S. Sadeghabad, M. Safari, M. Saghafian, and S. ShokatFadaee, “On a bounded budget network creation game,” _CoRR_ , vol. abs/1111.0554, 2011.
  * [41] V. Bala and S. Goyal, “A noncooperative model of network formation,” _Econometrica_ , vol. 68, no. 5, pp. 1181–1229, 2000.
  * [42] M. O. Jackson, “A survey of network formation models: stability and efficiency,” _Group formation in economics: Networks, clubs, and coalitions_ , vol. 664, pp. 11–49, 2005.
  * [43] E. D. Demaine, M. Hajiaghayi, H. Mahini, and M. Zadimoghaddam, “The price of anarchy in network creation games,” in _ACM Symposium on Principles of Distributed Computing, PODC_ , 2007, pp. 292–298.