Payment channels allow transactions between participants of the blockchain to be executed securely off-chain, and thus provide a promising solution for the scalability problem of popular blockchains. We study the online network design problem for payment channels, assuming a central coordinator. We focus on a single channel, where the coordinator desires to maximize the number of accepted transactions under given capital constraints. Despite the simplicity of the problem, we present a flurry of impossibility results, both for deterministic and randomized algorithms against adaptive as well as oblivious adversaries.
Additionally, the design of payment networks with fees from the viewpoint of a payment service provider who wants to maximise the profit is discussed in @cite_15 . In the contrary to this work where we assume constant fee for every transaction, in @cite_15 , each channel requires a different fee, much like the tolls on a road network. Despite the different assumptions, both works share the same objective, to maximize the profit for the network operator (and designer).
@cite_15
2890103577 2152629569 1974835443 2048523876
Payment channels are the most prominent solution to the blockchain scalability problem. We introduce the problem of network design with fees for payment channels from the perspective of a Payment Service Provider (PSP). Given a set of transactions, we examine the optimal graph structure and fee assignment to maximize the PSP’s profit. A customer prefers to route transactions through the PSP’s network if the cheapest path from sender to receiver is financially interesting, i.e., if the path costs less than the blockchain fee. When the graph structure is a tree, and the PSP facilitates all transactions, the problem can be formulated as a linear program. For a path graph, we present a polynomial time algorithm to assign optimal fees. We also show that the star network, where the center is an additional node acting as an intermediary, is a near-optimal solution to the network design problem. We study revenue-maximizing pricing by a service provider in a communication network and compare revenues from simple pricing rules to the maximum revenues that are feasible. In particular, we focus on flat entry fees as the simplest pricing rule. We provide a lower bound for the ratio between the revenue from this pricing rule and maximum revenue, which we refer to as the price of simplicity. We characterize what types of environments lead to a low price of simplicity and show that in a range of environments, the loss of revenue from using simple entry fees is small. We then study the price of simplicity for a simple non-linear pricing (price discrimination) scheme based on the Paris Metro Pricing. The service provider creates different service classes and charges differential entry fees for these classes. We show that the gain from this type of price discrimination is small, particularly in environments in which the simple entry fee pricing leads to a low price of simplicity. This paper derives a simple fast algorithm for computing minimal-revenue tolls in a single-origin network. It assumes that trips have the same value of time, that they make user-optimizing path choices, and they have multiple destinations--but come from the same origin. The algorithm finds tolls that induce a traffic pattern minimizing average time per trip at a minimal average toll per trip. Formally, let X be the set of all feasible traffic assignments and assume all trips have the same value of time [alpha]>0; then the algorithm inputs a network with the system-optimizing flow xo vector and associated arc times t(xo). It outputs an optimal arc toll vector c*[greater-or-equal, slanted]0 such that for x[set membership, variant]X:([alpha]t(xo)+c*)T(x-xo)[greater-or-equal, slanted]0 Â forÂ x[set membership, variant]X (user Â optimal) That is, xo[set membership, variant]X becomes user-optimal, too. Compared to marginal-cost tolls, which would also produce this same effect, the min-revenue tolls c* possess important practical advantages. Perforce, they provide the same system-optimal network usage, but at a much cheaper price to the traveler--remarkably, they assure at least one toll-free path to every destination. In addition, min-revenue tolls have admirable stability: even large increases in travel demand can leave the solution c* virtually unchanged--an important feature since traffic volume can change continuously but tolls cannot. Finally, they provide guidance regarding potential network improvements. The algorithm presented is very efficient, easily able to solve networks with tens of thousands of nodes. A greedy potentials calculator, its expected running time for an n-node road network is a speedy O(n), while its worst case time for any network is O(m), where m is the number of arcs. The second of a two-part series, this paper derives an efficient solution to the minimal-revenue tolls problem. As introduced in Part I, this problem can be defined as follows: Assuming each trip uses only a path whose generalized cost is smallest, find a set of arc tolls that simultaneously minimizes both average travel time and out-of-pocket cost. As a point of departure, this paper first re-solves the single-origin problem of Part I, modeling it as a linear program. Then with a change of variable, it transforms the LP's dual into a simple longest-path problem on an acyclic network. The multiple-origin problem - where one toll for each arc applies to all origins - solves analogously. In this case, however, the dual becomes an elementary linear multi-commodity max-cost flow problem with an easy bundling constraint and infinite arc capacities. After a minor reformulation that simplifies the model's input to better accommodate output from common traffic assignment software, a solution algorithm is exemplified with a numerical example.