2017/10/04 by Steffen Schuldenzucker, Schuldenzucker, Steffen, Sven Seuken +3 · 1 citation
Economics, Econometrics and Finance · #Banking stability, regulation, efficiency #Complex Systems and Time Series Analysis #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #Economic theories and models #FOS: Computer and information sciences #FOS: Economics and business #General Finance (q-fin.GN) #Risk Management (q-fin.RM)
paper · pdf · doi:10.48550/arxiv.1710.01578
openalex publication_date 2017/10/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The 2008 financial crisis has been attributed to "excessive complexity" of\nthe financial system due to financial innovation. We employ computational\ncomplexity theory to make this notion precise. Specifically, we consider the\nproblem of clearing a financial network after a shock. Prior work has shown\nthat when banks can only enter into simple debt contracts with each other, then\nthis problem can be solved in polynomial time. In contrast, if they can also\nenter into credit default swaps (CDSs), i.e., financial derivative contracts\nthat depend on the default of another bank, a solution may not even exist.\n In this work, we show that deciding if a solution exists is NP-complete if\nCDSs are allowed. This remains true if we relax the problem to\n\ε-approximate solutions, for a constant \ε. We further\nshow that, under sufficient conditions where a solution is guaranteed to exist,\nthe approximate search problem is PPAD-complete for constant \ε. We\nthen try to isolate the "origin" of the complexity. It turns out that already\ndetermining which banks default is hard. Further, we show that the complexity\nis not driven by the dependence of counterparties on each other, but rather\nhinges on the presence of so-called naked CDSs. If naked CDSs are not present,\nwe receive a simple polynomial-time algorithm. Our results are of practical\nimportance for regulators' stress tests and regulatory policy.\n