arXiv preprint ·
Approximate clearing in financial networks with credit default swaps: hardness thresholds, a box algorithm, barriers, and exact solvency at bounded degree
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
The Laplace transform of the time of ruin in the Cramér--Lundberg model with Erlang $E_2(μ)$ claims: spectrum, exact moments and matrix reduction
Quantifying Repair Risk in Crypto Option Surfaces
Interpretable Allocation and Model-Predictive Rebalancing of Equity Portfolios, Tested on Real and Synthetic Markets
Robust distortion riskmetrics under symmetry, unimodality, and Wasserstein constraints
Robust distortion riskmetrics over Bregman--Wasserstein balls and their intersections
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.