Complexity of Payment Network

Abstract

A graph-theoretic framework is developed to study decentralized settlement in
a general payment network. This paper argues settlement efficiency through examining
how much settlement fund needs to be provided to settle all given obligations.
Observing that required amount of settlement fund depends on in which order those
obligations are settled, we focus on a pair of problems that derives its lower-bound
and upper-bound, each formalized as a numbering problem on flow network. Our
main finding is that twist nature of underlying directed graph (who obliged to whom)
is a key factor to form settlement efficiency. The twist nature is captured through
our original concepts; arrow-twisted, and vertex-twisted. Lower-bound of required
settlement fund tends to be larger when underlying directed graph is twisted in
arrow-twisted sense, while upper-bound tends to be smaller when it is twisted in
vertex-twisted sense.