英文标题：
《The Computational Complexity of Financial Networks with Credit Default
  Swaps》
---
作者：
Steffen Schuldenzucker, Sven Seuken, Stefano Battiston
---
最新提交年份：
2019
---
英文摘要：
  The 2008 financial crisis has been attributed to \"excessive complexity\" of the financial system due to financial innovation. We employ computational complexity theory to make this notion precise. Specifically, we consider the problem of clearing a financial network after a shock. Prior work has shown that when banks can only enter into simple debt contracts with each other, then this problem can be solved in polynomial time. In contrast, if they can also enter into credit default swaps (CDSs), i.e., financial derivative contracts that depend on the default of another bank, a solution may not even exist.   In this work, we show that deciding if a solution exists is NP-complete if CDSs are allowed. This remains true if we relax the problem to $\\varepsilon$-approximate solutions, for a constant $\\varepsilon$. We further show that, under sufficient conditions where a solution is guaranteed to exist, the approximate search problem is PPAD-complete for constant $\\varepsilon$. We then try to isolate the \"origin\" of the complexity. It turns out that already determining which banks default is hard. Further, we show that the complexity is not driven by the dependence of counterparties on each other, but rather hinges on the presence of so-called naked CDSs. If naked CDSs are not present, we receive a simple polynomial-time algorithm. Our results are of practical importance for regulators\' stress tests and regulatory policy.
---
中文摘要：
2008年的金融危机被归因于金融创新导致的金融体系“过于复杂”。我们运用计算复杂性理论使这个概念更加精确。具体来说，我们考虑的是在冲击后清算金融网络的问题。先前的研究表明，当银行之间只能签订简单的债务合同时，这个问题可以在多项式时间内得到解决。相反，如果他们还可以签订信用违约掉期（CDS），即依赖于另一家银行违约的金融衍生品合同，那么解决方案甚至可能不存在。在这项工作中，我们证明了如果允许CDS，则判定解是否存在是NP完全的。如果我们将问题放宽到$\\varepsilon$近似解，对于常数$\\varepsilon$，这仍然是正确的。我们进一步证明，在保证解存在的充分条件下，对于常数$\\ varepsilon$，近似搜索问题是PPAD完全的。然后，我们试图分离出复杂性的“起源”。事实证明，已经很难确定哪些银行违约。此外，我们还表明，复杂性并非由交易对手之间的相互依赖所驱动，而是取决于所谓的裸CDS的存在。如果没有裸CDS，我们将得到一个简单的多项式时间算法。我们的结果对监管机构的压力测试和监管政策具有实际意义。
---
分类信息：

一级分类：Quantitative Finance        数量金融学
二级分类：Risk Management        风险管理
分类描述：Measurement and management of financial risks in trading, banking, insurance, corporate and other applications
衡量和管理贸易、银行、保险、企业和其他应用中的金融风险
--
一级分类：Computer Science        计算机科学
二级分类：Computational Complexity        计算复杂度
分类描述：Covers models of computation, complexity classes, structural complexity, complexity tradeoffs, upper and lower bounds. Roughly includes material in ACM Subject Classes F.1 (computation by abstract devices), F.2.3 (tradeoffs among complexity measures), and F.4.3 (formal languages), although some material in formal languages may be more appropriate for Logic in Computer Science. Some material in F.2.1 and F.2.2, may also be appropriate here, but is more likely to have Data Structures and Algorithms as the primary subject area.
涵盖计算模型，复杂度类别，结构复杂度，复杂度折衷，上限和下限。大致包括ACM学科类F.1（抽象设备的计算）、F.2.3（复杂性度量之间的权衡）和F.4.3（形式语言）中的材料，尽管形式语言中的一些材料可能更适合于计算机科学中的逻辑。在F.2.1和F.2.2中的一些材料可能也适用于这里，但更有可能以数据结构和算法作为主要主题领域。
--
一级分类：Computer Science        计算机科学
二级分类：Computer Science and Game Theory        计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Quantitative Finance        数量金融学
二级分类：General Finance        一般财务
分类描述：Development of general quantitative methodologies with applications in finance
通用定量方法的发展及其在金融中的应用
--

---
PDF下载：
-->