Paper: arXiv 2611.00855

Authors: Michal Čertík

Abstract

We study approximate clearing in financial networks with credit default swaps. For weak notions (W) and (I), we prove PPAD-hardness below a threshold approximately $0.2530$ and give a polynomial-time interval algorithm above a threshold approximately $0.2834$. On networks whose CDS writers are solvent ex ante, the corresponding bounds are $(13-\sqrt{153})/4$ and $3-2\sqrt{2}$, approximately $0.1577$ and $0.1716$. The thresholds are sharp for bounded-radius algorithms: for (I) on writer-solvent networks, and for (I) and (W) in general. On non-degenerate networks, (W) and (I) have identical hardness and tractability threshold endpoints. For exact-solvency notion (D), PPAD-hardness holds at every rational error $\varepsilon<1$ on non-degenerate networks. On a restricted unit-notional class, let $d$ be the maximum number of CDS contracts held by a core bank, counted with multiplicity. For rational $\varepsilon\in[1/2,1)$, writing $ρ=(1+\varepsilon)/(1-\varepsilon)$, the problem is polynomial-time solvable when $d<(\lceilρ\rceil+1)ρ$ and PPAD-complete otherwise. At $\varepsilon=1/3$ the boundary is $d=5$ versus $d=6$; below $\varepsilon=1/9$, degree $2$ is already PPAD-complete, while degree $1$ is exactly solvable. These degree results concern (D) and do not close the (W)/(I) approximation windows. We also establish a barrier to Pure-Circuit reductions certified by interval propagation under stated interface and auxiliary-bank restrictions. A finite-precision interval algorithm reduces writer-solvent (I) to point selection in near-stalled boxes; selection is polynomial-time when the residual matrix is symmetric or monotone on each strongly connected component. The general and writer-solvent approximation windows remain open.

Complexity vs Empirical Score

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

Why this score: This paper is exceptionally strong in its mathematical depth, exploring PPAD-hardness and polynomial-time solvability thresholds for complex financial network clearing problems. Its novelty lies in precisely defining these computational boundaries and introducing new algorithmic approaches. While theoretically robust, it lacks empirical validation or backtesting, focusing purely on the computational complexity of the models.

Research Flowchart

  flowchart TD
    A[Research Goal: Approximate Clearing in Financial Networks with CDS] --> B{Key Methodology: Theoretical Analysis & Algorithm Design};
    B --> C[Inputs: Financial Networks, CDS Contracts, Notions of Clearing (W, I, D)];
    C --> D{Computational Processes: Hardness Proofs (PPAD), Interval Algorithm Design & Analysis, Barrier Analysis, Finite-Precision Interval Algorithm};
    D --> E[Key Findings (Thresholds for PPAD-Hardness & Tractability)];
    E --> F[Findings: Hardness thresholds for W/I (~0.2530), Tractability thresholds for W/I (~0.2834)];
    E --> G[Findings: Writer-solvent W/I thresholds (~0.1577, ~0.1716), Exact-solvency (D) is PPAD-hard for ε<1];
    E --> H[Findings: (D) on Unit-Notional Networks: Tractability based on max CDS degree (d) and error (ε)];