信用违约金融网络的计算复杂性

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《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下载：
--> The_Computational_Complexity_of_Financial_Networks_with_Credit_Default_Swaps.pdf (712.78 KB)

2022-6-1 11:35:22 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：复杂性 违约金 金融网 Quantitative Applications

具有信用违约掉期的金融网络的计算复杂性*苏黎世斯特芬·舒尔登祖克大学苏黎世SeukenUniversity of ZurichStefano BattistonUniversity of ZurichFirst version：2017年10月5日此版本：2019年5月20日冲击后清算金融网络的抽象问题。之前的工作表明，当银行只能彼此签订简单的债务合同，然后再签订信用违约掉期（CDS），即依赖于另一家银行违约的金融衍生品合同时，甚至可能不存在解决方案。允许使用CDS。如果我们将问题放宽到ε-近似ε，则在保证存在解的情况下，近似搜索问题是常数ε的PPADcomplete。然后，我们试图分离出复杂性的“起源”。结果表明，已经很难确定哪些银行违约。此外，我们还表明，复杂性并非由交易对手之间的相互依赖所驱动，而是取决于所谓的裸CDS的存在。如果没有裸CDSSA，我们将得到一个简单的多项式时间算法。

我们的结果对监管机构的压力测试和监管政策具有实际意义。1引言相对而言，小型金融市场可以在金融系统中传播和扩大，从而人们普遍认为这不仅仅是金融机构个人*{schuldenzucker，seuken}@i fi。乌兹。chstefano。battiston@uzh.chin一页的摘要，发表在EC\'16会议记录（Schuldenzucker，ITCS\'17）（Schuldenzucker，Seuken和Battiston，2017）上。“复杂、自适应网络的压力”，其中“金融创新[已经]增加了美联储主席的建议，描述了危机后的监管变化，即我们金融系统的互联性。”衍生工具（即，支付义务取决于其他事件或市场变量的金融合同）如今允许使用衍生工具交易和重新分配单个组成部分，以支付国内和国外对外币贬值的担忧之间的差异。另一位交易员将接手（“银行”简称），边缘是金融合约。我们称之为金融网络。网络可能以多种方式出现，大多数人都有一种直觉，即监管机构需要解决的具体问题的财务复杂性。更详细地说，我们研究了清算问题。我们拥有一个由银行和银行间合同组成的金融网络。每份合同都规定了在特定条件下支付一定金额款项的义务。我们假设存在某种默认情况）。违约可能引发下游其他银行违约。对于每家银行来说，形成金融网络的其他两种方式。

证券化产生的产品（最主要的债务抵押债券（CDO））有时被称为“衍生品”，但与我们在本文中讨论的衍生品类型相比，它们是使用优先权结构和dodiscussion定义的，因此我们认为这些产品是一种债务形式。在标准破产法规中，这意味着一种让人想起流动身份的约束：违约银行必须将其所有资产支付给债权人，而且必须这样做，因为合同关系可能在网络中形成循环。初始冲击后。一旦找到清算问题的解决方案，初始冲击的影响可以通过违约次数等指标来判断，以研究网络结构对系统性风险的影响，如金融冲击规模和网络结构（Acemoglu、Ozdaglar和Tahbaz Salehi，2015），Glasserman和Young，2015），以及其他许多指标。在压力测试的背景下，清算问题具有实际的相关性，其中，官方压力测试仍在微观审慎（个别银行）层面上运行，目前正在向宏观审慎的角度过渡，其中金融系统欧元压力测试关键取决于能否获得清算问题的高效算法。信用违约掉期市场，将在下文讨论。如上所述，“清算”一词是指Eisenberg和Noe（2001）提出的模型及其扩展。Martin（2017年，图表12.1）。另一个，但它也可以作为一个模型，例如，当债务导致违约成本时，衍生工具。这些清算模型在研究和压力测试中得到了广泛采用，例如在上述印花欧元框架中。我们的付款义务可能不固定。投机性押注此事件。

信用违约掉期在雷曼兄弟交易对手和参考实体的违约中发挥了重要作用（惠誉评级，2007年）。因此，传统观点认为，他们是大额CDS债务的交易对手，只有在参考实体可以是其他金融机构的情况下，他们才是CDS债务的交易对手。我们考虑扩展Rogers和Veraart（2013）clearingSeuken和Battiston，2019）的模型，我们研究了该模型中解的存在性。即使已知存在解决方案，也可以扩展到CDS。这立即引发了关于CDS清算问题计算方面的两个问题：1。给定一个金融网络，我们能否有效地确定是否存在清算问题的解决方案？2、考虑到已知存在解决方案的金融网络，我们能否高效地进行国际结算（2018年，单名工具部分，金融公司小节）以及此处链接的图表。计算它？在本文中，我们以否定的方式回答这两个问题。对于第一个问题，对于没有ε-近似解的问题，对于自然近似解概念和足够小的常数ε。特别是，确定精确解或ε-近似解的存在性是NP困难的（第3节）。精确解可能是无理的，我们需要考虑一个近似问题。如果ε是一个非常小的常数，那么在没有违约成本的金融系统中找到ε-近似解的总搜索问题是完全的。（第4节）。在这一点上，我们已经表明，带有CDS的金融网络确实“问题更大”在我们寻求计算复杂性的“起源”的过程中，我们分两步进行。在第一步中，我们询问清算问题解决方案的哪些方面是硬的，这完全是因为需要计算回收率的精确数值。

相反，要确定某一给定银行是否会在某些ε-解决方案中违约（适当的区分变量为NP-完全），已经是NP难了，如果没有违约成本，则已经完成了PPAD，以找到一组将在某些ε-解决方案中违约的银行（第5节）。从…起从我们的减少可以看出，在一个模型中，问题仍然很难解决，我们可以说，复杂性源于基本风险（即CDS交易对手对参考实体的依赖性）。最后，我们得到了复性的上界。我们表明，硬度取决于裸CDS的存在，即持有的CDS不同时持有相应的债务合同。如果裸CDS被称为CDS，则CDS在实践中是一种常见现象。虽然我们不知道有任何实证研究量化了裸CDS的份额，但似乎有一个广泛的共识，即它们构成了CDS头寸的大多数。Kiff等人（2009）指出，CDSS多项式时间近似方案的（总体）概念（FPTA；第6节）。这些见解将允许它们对监管政策产生各种影响（第7节）。当然，之前已经有人试图捕捉金融网络的“复杂性”。由于i）互联结构和ii）合同本身的性质，我们区分了非正式复杂性。复杂性dueconcentration（Arinaminpathy，Kapadia和May，2012），网络熵（Battistonet al.，2016），或光谱度量（Bardocia et al.，2017）。由于这些指标需要普通图作为输入，其中边不能包含比权重更多的信息，因此需要提取合同的详细信息，例如金融衍生品对其基础市场变量的依赖性。

敏感性结果（Hemenway和Khanna，2016；Liu和Staum，2010；Feinstein et al.，2017）是另一种获取“互联复杂性”的方法，也与计算银行监管相关，2014）。开始受到理论计算机科学的关注。Arora等人（2011）指出，复合期权在计算上很难正确定价。相比之下，一张CD是一份非常简单的合同。因此，我们在本文中表明，“继续远远超过大多数合同所依据的公司债券和贷款的存量。”Crotty（2009）引用当时纽约州保险总监Eric Dinallo的话说，与中央清算和组合压缩（见第7节）一样，可能降低了NAKEDCDS的份额，但他们无法将其消除到显著水平以下。场外交易，即直接与其他银行进行交易，而不是通过交易所进行交易。在本文中，我们只考虑场外衍生品。期权是授予持有人购买（看涨期权）或出售（看跌期权）权利的衍生工具。AKoption是一种期权，其中a本身就是一种期权。如果参考实体和交易对手知道回收率的分布，则CDS的估值很简单。见杜菲（1999年）。构建一个高度（计算）复杂的财务系统。很难确定给定的总体负面冲击对银行的分布，这对清算问题来说是一个计算困难的结果。使用的技术由于清除问题是指一个明确的网络，因此我们很自然会使用电路问题的约简来证明我们的硬度结果/门的输入和实现NAND操作的输入。我们通过一个特殊的重置小工具，将低值映射到0±ε，将高值映射到1±ε，防止错误累积。

最后，我们添加了一个没有解决方案的金融子网，因为电路“输出组”的回收率很低。ε-ε解可能不是多项式长度。例如，Schoenebeck和VadhanGoldreich（2005）进行了进一步的讨论。我们通过广义不平衡的约化显示了搜索问题的PPAD硬度（Daskalakis、Goldberg和Papadimitriou，2009；Chen、Deng和Teng，2009；Rubinstein，2018），广义电路在比较门的研究中得到了应用，并且可以有循环。与之相关的搜索问题有四个方面：传统上，广义电路也支持布尔门，这些布尔门在与上面类似的近似布尔值上运行。Schuldenzucker和Seuken（2019）最近指出，布尔门实际上是多余的，因此可以省略。对恢复率执行相应的操作。然后，除非P=PPAD，否则PPAD硬度遵循PTA的εε存在。如果ε随输入量的增加而多项式收缩，则为P.medium或low。这些状态对应于闸门定义中的“决策点”或“截断点”。例如，当且仅当加法门的输入和大于1时，加法门处于高状态，因此其输出被截断为1。状态也允许ε误差。找到与电路的某些ε-解一致的状态集合是PPAD完成的，因为状态固定后，门的约束是线性的，可以通过线性规划重构ε-解。Wethen指出，在上述从金融网络到广义电路的简化过程中，违约银行的集合已经决定了闸门的状态。我们希望这是未来的问题。基本符号εε与以下内容相关。

阈值可能取决于任意但固定的参数，但它永远不会取决于任何计算问题的输入，因此应视为常数。我们有时写ε β表示阈值是β项的单调（不一定是线性）函数。我们写εcεc>[x]min（1，max（0，x））x，xy±ε| x-y |≤ εxykx- yk公司∞≤ ε±ε[x±ε]形式上对应于区间算术。2个信用违约掉期金融网络（2019年）。现在，我们将介绍该模型的详细信息，并对CDS的影响进行高层次的讨论。然后，我们提出了一个新的放松我们的解决方案的概念，这是必要的，能够得到有限的，多项式长度的（近似）解决方案。2.1模型金融系统。镍∈ n一定数量的外部资产，以EI表示≥0、任何两家银行之间i、 j≥ijk公司∈ Ncki，j≥ijkcki，jk∈ N∪ {}cki，j>一些k∈ N∪ {}, 我们称j为i的债权人，j为i.c的债务人i、 icji，icji，jcii，ji，j∈ 作为CDS中参考实体的Nbank还必须是某些债务合同（即ifPk、l∈Ncik，l>0，然后是PJ∈北卡罗来纳州i、 j>0，对于所有i∈ N） 。我们按照Rogers和Veraart（2013）的模型对违约成本进行建模：有两种违约α，β∈,αβαβαβ- α- β违约成本。金融系统是一个元组（N、e、c、α、β），其中有一组银行，即一个向量cαβαβ问题到任意但固定的α和β值。因此，可以将这些参数视为常数。请注意，在签订合同时，我们既没有指定冲击分布，也没有指定初始付款。

我们假设这些值隐含地反映在第2.1、2.2小节的外部扩展版本中，并且本节允许CDS的部分影响之前已经出现在我们之前的工作中（Schuldenzucker、Seuken和Battiston，2019年，第2节）。具有CDS的金融网络的替代模型。在考虑解决方案时，忽略合同和。资产资产和负债。国际扶轮社∈,IJI TOJ的责任。这是我应该付给J的金额。债务合同产生的无条件责任等于其名义上的责任，但一些银行的债务偿还率与1成正比- rk。因此，从i到j在r的总负债为：li，j（r）：=ci、 j+Xk∈N（1- rk）·cki，J总负债是指I对所有其他银行的总负债，用I（r）表示：=Xj∈Nli，j（r）。pi、jrijrli、jrithe各自的责任；pi，j（r）：=ri·li，j（r）。银行的总资产包括其外部资产和收入；ai（r）：=ei+Xj∈Npj，i（r）。Iair根据因子α和β。这是将支付给债权人的金额；ai（r）：=αei+βXj∈Npj，i（r）。备注1。为了确保CDS确实可以作为违约保险，leti，j，k∈ Nandjkknotional：cki，j=ck、 j=：δ>0。那么，j的资产包含术语δ+ri（1-rk）·δ。只要ri=1，该项等于δ，与rk无关。清除恢复率向量。r∈,破产法：1。拥有充足资产以全额偿还债务的银行必须这样做。资产不足以全额偿还债务的银行违约，必须在扣除违约成本后向债权人支付全部资产。这导致了以下正式定义：图1财务系统示例。设α=β=0.5AB CDe定义1（清除恢复率向量）。LetX=（N，e，c，α，β）是一个金融系统。