金融网络的敏感性和计算复杂性

另一方面，我们考虑资产价格最严重的下跌（即，在最佳情况均衡中导致最多失败的资产价格下跌）。因此，“最大”失败次数是指资产价值的最大有界下降，以及在每次资产价值下降时可能发生的最小失败次数（即，在这些新的、较低的价值下，所有均衡的最小值）。我们在第6.3节中更详细地讨论了多重平衡问题。在现实世界的金融网络中，监管机构以及机构本身都会例行进行“压力测试”，以评估网络对金融风险的鲁棒性。我们的结果表明，存在没有（计算上可行的）压力测试的金融网络，它甚至可以近似计算出系统受到小冲击时可能发生的最大故障数。然而，请注意，我们的结果不是概率性的，因为我们没有对资产价格具体下跌的可能性进行建模，而只是对资产价值总下跌的幅度施加了一个界限。如果不为资产价格分配概率分布，我们无法评估这种级联可能发生的可能性，只能评估其可行性。因此，我们的问题是，资产价格是否存在可能导致巨大失败的小幅下跌——这种下跌是否可能超出了我们模型的范围。

因此，如果压力测试能够准确地模拟资产价格的概率分布，它可能能够评估由系统冲击引起的少量故障，但任何计算上可行的压力测试都无法确定对系统的小冲击（但可能不太可能）是否会导致更大的故障级联。6.3多重均衡当系统中引入不连续故障惩罚（~b（~v））时，系统中的机构可能存在多重均衡值，即市场价值可能不是唯一确定的[EGJ14，第2.6节和Ap pendix A.7]。如[EGJ14]所述，一个网络有两种不同的方式可以实现多重平衡。第一类属于银行挤兑的标准理论[DD83]，即使在非循环网络中，这种多样性也可能发生。例如，假设有一个由单个机构组成的网络，该机构持有一项价值为p的资产。让vdenote表示该机构的价值，vdenote表示其失败阈值，β表示其失败惩罚。Ifp>v>p- β、 然后对v=p和v=p进行估值- β与方程3一致。第二类多重贫困是由网络中的周期引起的。关于具有多个平衡点的简单（循环）网络，请参见图4。在一个具有多重均衡的网络中，我们可以讨论“最佳情况”均衡（故障最少的那个）和“最坏情况”均衡（故障最多的那个）。正如[EGJ14]中所述，我们关注的是最佳情况均衡，因此当我们提到“故障数量”时，我们指的是最佳情况均衡中的故障数量。6.4平衡完全二部子图（BCBS）问题我们的硬度结果基于在二部图中找到最大平衡团的难度。

这就是所谓的平衡完全二部图（BCBS）问题。定义1（BCBS）。给定一个|V |=|V |=n的二部图G=（V，V，E），平衡完全二部子图（BCBS）问题是找到最大整数K，这样就存在1BB1/2/2图4：银行为蓝色，外部股东为绿色，资产为红色。在这个例子中D~p=1 00 1, C=. 如果vi=2，bi=1，则两个平衡为：~v=, 和~v=集C 范德C 具有| C |=|C |=K的性质，以及诱导图onC∪ Cis是G的完全二部子图。已知BCBS问题是NP难[GJ79，87]。这提供了强有力的证据，证明没有可伸缩的算法可以确定无分图中最大平衡团的大小。事实上，有大量证据表明，即使是接近最大平衡液的大小也很难。Feige证明，对于某些δ>0的情况，很难用nδ的因子来逼近BCBSto[Fei02，定理3]。Feige和Kogan证明，如果BCB可以近似为每δ>0的因子2（对数n）δ内，那么对于每>0，3-SAT可以在时间2n3/4+内求解[FK04，定理1.3]。Feige和Kogan继续推测，对于某些δ>0的情况，没有多项式时间算法将BCB近似为nδ的因子[FK04，猜想1.1]。我们的初步结果表明，在某些网络中，计算小冲击可能导致的最大银行故障数相当于解决BCBSP问题。

因此，在金融网络中，即使粗略估计资产价格任意下跌可能导致的银行倒闭数量，在计算上也是一个棘手的问题。6.5计算最大故障数的复杂性在本节中，我们给出了我们的主要结果，即在标的资产价值小幅下降的情况下，估计可能发生的最大故障数的计算复杂性。尤其是，当机构交叉持股固定且完全已知，但标的资产价格存在一些小的不确定性时，这一结果适用于确定均衡时发生的失败次数。在交叉持股和资产固定的情况下，可以直接计算机构在均衡状态下的市场价值[EGJ14，第3.2.3节]。请注意，我们构建的网络是非循环的。定理3。对于2n个节点上的y二部图G，每>0，就有一个财务网络Ohm（n） 并且d>0，因此计算资产价格d震荡后可能倒闭的最大机构数与解决G.证明中的BCB问题一样困难。允许l > 0可以是任意整数。我们的起点是BCBS项目的以下硬度结果。给定一个n×非平衡二部图G，很难确定某个间隙函数G的最大平衡二部团大小G是至少K×K还是最多K/G×K/G∈ DT IM En3/4+对于一些人来说，>0。给定一个n×n平衡二部图G，我们将构造一个具有（2+l)n如果G有一个大小为K的平衡二部子图，那么资产价格的下降K至少会导致（2+l)K.失败。

另一方面，如果G的最大平衡二部子图是sizeKg，那么K的资产价格下跌最多可能导致K+Kg(l + 1） 失败。这表明，估计固定资产价格下降导致的最大失败次数至少与估计最大平衡的两方集团的规模一样困难。在不丧失一般性的情况下，我们假设G中的每个顶点至少有d度K。设d表示G中任何顶点的最大度。设0<<1是一个任意参数，设0<r<1表示我们正在构建的网络中机构的最小自持有量。（对于0<，r<1的任何选项，该降幅都有效。）对于图G中的每个节点，我们将关联一个金融机构。让我们一起来，n对应于G的左侧节点，以及n+1，2n对应于G的右手节点。我们还将生成n个标的资产，标记为a′i，如果i=1，…，我将完成自己的资产，n、 机构n+1，2n将不拥有任何相关资产。所有资产最初的估值为1。重击=......定义N=D1-r（回忆D是G的最大程度，r是一个任意参数，它将决定最终财务网络的整合）。我们将使用Γ（j）来表示G中顶点j的第八位。请注意，我们对N的定义确保了1- r=DN≥|Γ（j）|对于所有j=1，2n。这意味着，如果机构j将自己的一个同等品牌出售给所有邻居，它将至少拥有r部分的自主权。为了实现这一点，我们必须=如果i>j且（i，j）G0的边为1=1，n设vi=1-|Γ（i）|N-因此，如果机构i的资产价值下降，那么机构i将失败。让失败惩罚βi=1-|Γ（i）|N- 对于i=1。

因此，如果资产i的价格下降了，机构i就会失败，其价值立即下降到0。对于i=n+1，2n让“vi=|Γ（i）|-dN。请注意，如果所有资产最初的估值为1，那么=1.-|Γ（i）|Nif 1≤ 我≤ n |Γ（i）|如果n<i≤ 2该金融网络具有以下特性：1。如果j银行的邻居的j>n和d破产，即资产ai（i）的d∈ Γ（j））如果价值下降，那么j银行就会倒闭。2.如果j>n，并且j银行的邻居的总价值下降小于dn，则j银行不会倒闭。现在，我们来研究这个系统的性质，当资产被允许以总金额d的价格下跌时。d的下降总是会导致网络左侧的d机构倒闭，只需将其每项资产的价值降低即可。如果降价不是集中在不稳定的资产上，那该怎么办？让t表示价值至少下降的资产数量。如果t<d，则至少使用d的“冲击预算”中的tf来降低这些t资产的价格，从而使预算为（d）- t） 剩余。现在，考虑这一下降对一个右手机构j的影响有多大。即使这一下降完全集中在j的左手邻居们中间，j感觉到的下降在m ostN（t+（d））处- t） ）<N（t+（d）- t） ）=Dn因此机构j不能倒闭，因为右翼机构的倒闭要求其价值至少下降Tdn。这意味着，在这种情况下，正是t<d机构失败了。由于我们对d资产价值下降可能导致的最大失败次数感兴趣，在不丧失普遍性的情况下，我们可以假设d资产价值下降了，导致左侧机构中的d次失败。现在，假设G中有一个大小为K的iclike。

如果d=K，那么在这个双离合器的左手边m个成员之间导致d故障将在右手边d个成员之间导致d=K故障。另一方面，假设最大的biclique是sizeKg。如果d个左侧机构的故障导致P个右侧机构的故障，则右侧的P个故障机构必须连接到左侧的d个故障机构。因此，在（d，P）=P中必须有大小为m的小集团。因此，在“是”的情况下（G有大小为K的小集团），我们可以导致至少K个右手故障，故障预算为K。在“否”情况下（G中最大的BICLUE为sizeK/G），右侧机构的最大故障数以kg为界。现在，为了扩大这种差异，我们添加了一系列l 与每个右翼机构相连的机构。因此，对于每一个右翼机构bi，它都会有一系列机构b（1）i，b(l)我这里b（j）看起来像个1- b（j）的r分数-1） iand没有其他股份。因此，如果发生故障，则b（1）通过b(l)ifail（参见图5）。这个新的网络(l + 2） n家银行，并拥有以下公共财产。假设K的失败预算，如果G中最大的平衡团是K×K，K的值下降最多会导致（2+l)K、 但如果最大的biclique是sizeKg，那么资产价值最多下降K可能会导致mostK+的资产价值下降(l + 1） Kg=（g+l + 1） 失败。注意，当间隙g=nδ时，选择l = poly（n），我们得到了((l + 2） n）对于某些δ′<δ。应用[FK04]的结果，我们得到以下推论。推论2。

如果3-6∈ DT-IMEn3/4+对于某些>0，则存在δ>0，因此没有多项式时间算法可以计算出因资产价格下跌d至2（对数n）δ′以内而导致的金融网络最大故障数。对于某些δ′>0.7的结论，这项工作突出了金融网络中两个不同的不稳定来源，交叉持股波动产生的稳定性和资产价格波动产生的不稳定性。更具体地说，我们表明，在一些网络中，交叉持有或资产价格中的小波动可能会产生显著的后果，这些后果会产生许多影响。我们的第一个结果（推论1，定理1，2）表明，交叉持股的微小变化的影响与网络的整合密切相关。在高度集成的网络中，交叉持股的小规模变动可能会对市场估值产生潜在的无限影响，而在集成度较低的网络中，交叉持股的变动会对A′abb（1）·b产生更紧密的影响(l)1.- r 1- r1- ra′abb（1）·b(l)1.- r 1- r1- ra′abb（1）·b(l)1.- r 1- r1- R阿恩-2an-20亿-2b（1）n-2··b(l)N-21- r 1- r1- 拉恩-1an-10亿-1b（1）n-1··b(l)N-11- r 1- r1- ra′nanbnb（1）nb(l)n··1- r 1- r 1- 图5：有n个资产，{a′i}，以红色显示。每一项资产都由研究所完全管理。制度{ai}，{bi}相当于一个平衡的两党集团的硬性例子。研究所NB（j）致力于放大第一级出现的故障。网络中机构的市场价值。这些结果可以用多种方式解释。从监管角度来看，在高度整合的网络中，任何监管机构都必须非常准确地了解整个交叉持股网络，以便有效地理解机构的市场价值。

从一个机构的角度来看，个别机构投资的微小变化可以通过网络大大增强其影响。从预测性的角度来看，如果一个人希望预测未来的市场价值，任何s mall预测交叉持股的确定性都会对机构的（预测）市场价值产生巨大影响。从隐私角度来看，在不损害外部人士（如其他机构、外部投资者或监管机构）计算机构市值的能力的情况下，机构无法在其投资组合中维护任何隐私。这些问题只有在高度集成的网络中才会出现（定理1），通过对集成设置上限，它们都可以得到缓解。如果要求机构在网络的eof之外保持一定比例的所有权，则可以大幅降低对交叉持股变化的敏感性。我们的第二个结果表明，资产价格的微小变化可能会对系统故障的数量产生不可预测的影响。具体地说，我们表明，在某些网络中，即使有关于交叉持股的完美信息，也很难计算出资产价格小幅下跌后可能发生的失败次数。这一结果也可以从不同的角度进行解释。这一结果表明，如果监管者（拥有关于网络交叉持股的完美信息）认为资产价格可能存在某种有限的波动，那么就不能期望将这些波动导致少量故障的网络与同样规模的波动可能导致大量故障的网络区分开来。机构也面临同样的计算挑战。

一个机构可能想知道，它的投资组合是否能保护它免受设定价格的有限冲击，我们的结果表明，即使有关于系统中所有其他代理的投资的完整信息，也可能无法确定特定投资组合是否安全。以前的工作对资产价格中的波动施加了特定的概率模型，对于给定的概率模型，通常可以估计故障的数量。但是，如果模型不正确（例如，资产价格不会独立波动），该怎么办？我们的研究结果表明，在某些情况下，故障分布的变化（而不是其总体大小）会对故障数量产生巨大且不可预测的影响。接下来，一个重要的研究问题是了解网络上的哪些约束将允许机构和监管者进行这些稳定性分析。参考文献[ABBG10]桑耶夫·阿罗拉、波阿斯·巴拉克、马库斯·布伦内梅尔和荣格。金融产品中的计算复杂性和信息不对称。在ICS中，第49-65页。清华大学出版社，2010年。Sanjeev Arora、Boaz Barak、Markus Brunnermeier和荣格。金融产品中的计算复杂性和信息不对称。公社。ACM，54（5）：101–107，2011年5月。[AG98]富兰克林·艾伦和道格拉斯·盖尔。最佳财务状况上升。《金融杂志》，53（4）：1245-12841998年8月。[AG00]富兰克林·艾伦和道格拉斯·盖尔。金融传染。政治经济学杂志，108（1）：1+，2000年2月。[AOTS13]达伦·阿塞莫格鲁、阿苏曼·奥兹达格拉尔和阿利雷扎·塔巴兹·萨利希。金融网络中的系统性风险和稳定性。技术报告，国家经济研究局，2013年。[BBC89]弗朗西斯科·布里奥斯基、路易吉·布扎基和马西莫·G·科伦坡。风险资本融资以及企业集团所有权和控制权的分离。