Paper: arXiv 2302.11250

Authors: Henri Froese, Martin Hoefer, Lisa Wilhelmi

Abstract

A debt swap is an elementary edge swap in a directed, weighted graph, where two edges with the same weight swap their targets. Debt swaps are a natural and appealing operation in financial networks, in which nodes are banks and edges represent debt contracts. They can improve the clearing payments and the stability of these networks. However, their algorithmic properties are not well-understood. We analyze the computational complexity of debt swapping. Our main interest lies in semi-positive swaps, in which no creditor strictly suffers and at least one strictly profits. These swaps lead to a Pareto-improvement in the entire network. We consider network optimization via sequences of v-improving debt swaps from which a given bank v strictly profits. For ranking-based clearing, we show that every sequence of semi-positive v-improving swaps has polynomial length. In contrast, for arbitrary v-improving swaps, the problem of reaching a network configuration that allows no further swaps is PLS-complete. In global optimization, the goal is to maximize the utility of a given bank $v$ by performing a sequence of debt swaps in the network. This problem is NP-hard to approximate for multiple types of swaps. Moreover, we study reachability problems – deciding if a sequence of swaps exists between given initial and final networks. We design a polynomial-time algorithm to decide this question for arbitrary swaps and derive hardness results for several other types of swaps. Many of our results can be extended to networks with arbitrary monotone clearing.

Complexity vs Empirical Score

  • Math Complexity: 8.0/10
  • Empirical Rigor: 1.5/10
  • Quadrant: Lab Rats — theoretically deep, empirically untested

Why this score: The paper presents a rigorous theoretical and graph-theoretic analysis of computational complexity (NP-hardness, PLS-completeness) in financial network clearing models. While mathematically sophisticated and novel, it is purely theoretical and completely lacks empirical backtesting or real-world data validation.

Research Flowchart

  flowchart TD
    A["Research Goal: Analyze computational complexity<br>of debt swapping in financial networks"] --> B["Inputs: Directed, weighted graphs<br>(banks & debt contracts) + Clearing Rules"]
    B --> C["Methodology: Algorithmic analysis of debt swaps<br>(Semi-positive, v-improving, Arbitrary)"]
    
    C --> D{"Problem Scope"}
    
    D -->|"Network Dynamics"| E["Analyze swap sequences & convergence<br>(Polynomial bounds vs. PLS-hardness)"]
    D -->|"Optimization & Reachability"| F["Evaluate bank utility maximization<br>& network state reachability algorithms"]
    
    E --> G["Outcomes: <br>1. Semi-positive v-swaps terminate in poly-length<br>2. Arbitrary v-swaps are PLS-complete<br>3. Utility optimization is NP-hard to approximate<br>4. Poly-time algorithm for arbitrary swap reachability"]
    F --> G