Paper: arXiv 2409.18717

Authors: Simon Dohn, Kristoffer Arnsfelt Hansen, Asger Klinkby

Abstract

We study computational problems in financial networks of banks connected by debt contracts and credit default swaps (CDSs). A main problem is to determine \emph{clearing} payments, for instance right after some banks have been exposed to a financial shock. Previous works have shown the $\varepsilon$-approximate version of the problem to be $\mathrm{PPAD}$-complete and the exact problem $\mathrm{FIXP}$-complete. We show that $\mathrm{PPAD}$-hardness hold when $\varepsilon \approx 0.101$, improving the previously best bound significantly. Due to the fact that the clearing problem typically does not have a unique solution, or that it may not have a solution at all in the presence of default costs, several natural decision problems are also of great interest. We show two such problems to be $\exists\mathbb{R}$-complete, complementing previous $\mathrm{NP}$-hardness results for the approximate setting.

Complexity vs Empirical Score

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

Why this score: The paper provides strong theoretical contributions to financial network theory, significantly tightening the computational hardness bounds (PPAD-hardness up to epsilon around 0.101) and proving ETR-completeness for clearing decision problems using advanced complexity-theoretic reductions. However, it is a purely theoretical computer science/mathematical paper with no empirical backtests or empirical financial data analysis.

Research Flowchart

  flowchart TD
    A[Research Goal: Strengthen computational hardness for CDS financial network clearing] --> B[Inputs: Financial networks with debt contracts & Credit Default Swaps]
    B --> C[Methodology: Reductions from fixed-point and real algebraic problems]
    C --> D[Analysis 1: Approximate clearing with error tolerance epsilon]
    C --> E[Analysis 2: Decision problems on clearing solution existence and uniqueness]
    D --> F[Outcome 1: Improved PPAD-hardness bound to epsilon approx 0.101]
    E --> G[Outcome 2: Proved Existential Theory of the Reals completeness]

Cited References (19)

  1. On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence (1994) — link
  2. On the Complexity of Nash Equilibria and Other Fixed Points (2010) — link
  3. Pure-Circuit: Strong Inapproximability for PPAD (2022) — link
  4. Some Algebraic and Geometric Computations in PSPACE (1988) — link
  5. Settling the complexity of computing two-player Nash equilibria (2009) — link
  6. Complexity of Some Geometric and Topological Problems (2009) — link
  7. Realizability of Graphs and Linkages (2013) — link
  8. Exotic Quantifiers, Complexity Classes, and Complete Problems (2009) — link
and 11 more
  1. Fixed Points, Nash Equilibria, and the Existential Theory of the Reals (2017) — link
  2. The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games (2019) — link
  3. FIXP -Membership via Convex Optimization: Games, Cakes, and Markets (to appear) — link
  4. Systemic Risk in Financial Systems (2001) — link
  5. Failure and Rescue in an Interbank Network (2013) — link
  6. Default Ambiguity: Credit Default Swaps Create New Systemic Risks in Financial Networks (2020) — link
  7. Finding Clearing Payments in Financial Networks with Credit Default Swaps is PPAD-complete (2017) — link
  8. The Computational Complexity of Financial Networks with Credit Default Swaps (2019) — link
  9. Strong Approximations and Irrationality in Financial Networks with Derivatives (2022) — link
  10. Financial networks with singleton liability priorities (2023) — link
  11. Clearing Financial Networks with Derivatives: From Intractability to Algorithms (2023) — link

0 of 19 cited works are in the corpus; resolved via arXiv source bundles, Semantic Scholar and OpenAlex. Corpus-wide: 2518 linked papers.