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.