多企业投资网络中的最优抵押品

因此，如果全合作是唯一的纳什均衡，由于如命题1所述的单调性，存在严格控制策略迭代消除的边σ，…，σe，从而导致全合作策略的唯一均衡。3.2通过抵押品的唯一均衡。抵押品最小化问题的兴趣在于寻找最优抵押品以诱导完全投资的唯一均衡；这个相当强的解决方案概念作为一种机制设计，旨在确保玩家之间没有错误的协调问题，并确保游戏达到一个e-cient的结果。寻求一个独特的均衡是由经验文献很好地激励的，这些文献表明，在战略风险存在的情况下，参与者如何经常收敛到内-内均衡（参见例如，[7])。有趣的是，与非网络情形（每个企业都有自己的投资者群体）不同的是，在网络结构中，担保物不能诱导出独特的均衡。这些情况发生在循环投资网络中，是由于网络中循环结构的特定类型。我们的特征说明了如何识别这种情况和隔离这些有问题的结构。具体而言，在单企业网络和所有有向无环网络中，不存在有问题的结构，并且总是可以由抵押品诱导唯一均衡。下面的结果，命题3，给出了投资网络的构造性特征，在投资网络中，一个唯一的均衡可以通过抵押品来诱导。命题3（抵押品合同的可解性）：考虑以下迭代过程：如果图中存在一个企业k，使得来自该企业的非企业顶点（尖峰）的总投资至少是该企业的成本(Zk)，则移除该企业及其非企业投资者顶点和事件边，并将k拥有的所有投资机会替换为来自新顶点（尖峰）的相同机会。然后，在新的图形上重申。当且仅当上述过程以空图告终时，有可能通过侧支诱导出唯一的平衡。图1：命题3迭代过程中的一个步骤的示例。字母表示顶点名称，有向边附近的数字表示投资机会金额。例如，顶点a在顶点G的企业中有金额为2的投资机会。在这个例子中，没有指示数字的边可以有任何正值。左：迭代步骤之前的网络。顶点a是一个企业顶点，运营成本ZA=2。顶点a也是Tenetwork中的一个循环顶点，并且有三个非企业投资者（尖峰顶点），每个投资者的投资金额为1，合计超过成本Za，因此（全额）担保可以保证a不会违约。右：迭代步骤后的新网络，捕获了一个确保的偿付能力。顶点a与它的尖峰顶点(b，c，d)和入射边一起被移除。金额1和2的顶点a的投资机会被来自新的尖峰顶点的相同金额的投资所取代，这些新的尖峰顶点用虚线边界表示，并用AA和a表示。图1给出了一个例子，说明了迭代过程的一个步骤。该命题的证明和进一步的细节可在附录A.3.3零络和全络中找到。第2.2节我们将络分为两种类型：全络和部分络。侧支类型的划分区分了两种类型的部分侧支：零侧支和正侧支。下一个结果引理1刻画了零络的情形；它对企业k中的一组Akof投资者的条件进行了调整，使另一个玩家我更愿意与零抵押品合作。

直觉上，引理要求即使在i的最坏情况下，即所有其他参与者都不在Akdefect中，企业投资时的回报toi将弱于xki，因此我不需要抵押品来激励她更喜欢投资。引理1（零抵押品条件）：用K表示在企业K中有投资机会的参与者的集合。修复一组ak funkk和任何玩家i∈K\\ak。如果XKI+XJ∈AKXKJ≥Zk(1+1/αk)(4)那么，对于i不缺省的所有玩家的任何一个动作，玩家i有一个严格的最佳回复来配合W.R.T.另外，如果CKI=0的参与者i至少有效用xki，假设参与者aké{i}投资，而其他参与者在k缺陷中投资，则方程（4）必须成立。下一个引理给出了一个关于企业k中投资者的集合AKF的条件，使得集合外的一个参与者不是缺省的，更愿意合作W.R.T.直观地说，在这个参与者的最坏情况下，当所有其他参与者都叛逃时，如果该参与者投资，企业对该参与者的回报为零，因此需要一个完整的担保品来激励投资。引理2（完整担保品条件）：用k表示在企业k中有投资机会的参与者的集合。修复一组ak funkk和任何玩家i∈K\\ak。如果XKI+XJ∈AKXKJ≤Zk(5)，则假设玩家Akinvest和其他玩家在K缺陷中，玩家i更愿意合作W.R.T.另外，如果对于每一个部分抵押品CKI<xkiplayer i的效用小于xki，且参与者AKé{i}投资且其他参与者在k中有缺陷，则方程（5）必须成立。利用引理1和引理2我们证明了对于整数输入，对于任何足够大的收益率，在任何最优解中，所有抵押品都必须是满的或零的。引理3（大α):考虑具有整数输入{n,X,Z,A}的侧边极小化问题，设k∈VE为企业顶点。如果αk>zk，则对于每个i,cki∈{0,xki}，协整极小化问题的每一个解c都满足。因此，若αk>Zk，则在每个最优解中，每个正抵押品都是完全抵押品。4单个企业本节讨论具有单个投资企业和n个潜在投资者的网络情形。我们称这种类型的网络为星图；即一个网络，其单个中心顶点与n个顶点的出边相连，如图2所示。注意，在这个singleenterprise设置中，为了简单起见，我们稍微滥用了记号法，使用n来表示潜在投资者的数量（不包括不做出投资决策的单个企业顶点），并省略了该企业的指数，只保留Edgewight Xi的投资者指数i。另外，由于在星型网络中矩阵X，c只有一行，且行的条目不为零，所以我们把它们看作向量而不是矩阵。另外，由于只有一个企业，我们用Z来表示它的成本，α来表示它的利率（而不是用Z，A)。注意，这里的每个玩家都有一个单一的进入边缘，所以玩家策略的消除顺序相当于玩家的顺序。此外，在星图中，玩家不能默认，因为他们没有自己的企业。由于给予所有投资者全部抵押品的抵押品向量显然是可行的抵押品向量（因为没有违约），因此存在单个企业抵押品最小化问题的解决方案。

下一个引理展示了单个企业设置的一个有趣的性质：给定一组合作者，一旦集合外的单个参与者更愿意与零抵押品合作，那么其他参与者也更愿意与零抵押品合作。引理4（其中一个免费，其余跟随）：修复一组a玩家，并假设a玩家中的每个玩家都合作。如果存在一个具有零侧边(ci=0)的博弈者i/∈a，且对其他博弈者的任何行动方案AC\\{i}都有严格的最佳回复合作，则如果博弈者a{i}合作，则其他博弈者都有严格的最佳回复合作，即使是零侧边合作。命题2表明，对于诱导唯一纳什均衡的任何侧边矩阵，在诱导博弈中至少存在一个可能的被支配策略迭代消除顺序，从而导致该唯一均衡。下面的结果命题4在相反的方向上起作用：对于星图中玩家的任何可能的顺序，定理提供了构造最小和边向量的方法，使得这个顺序将是被支配策略的迭代消除的顺序。（译注：译注：译注：译注：译注：译注：译注：译注：译注：译注：译注：译注：译注：译注：译注：译注：译注：译注）。它是通过给每个玩家最小数量的抵押品来实现的，假设在她之前的所有玩家都按照顺序合作，而其他所有玩家都不合作。图2：一个单一企业网络。命题4（最小抵押品）：设∑是[n]的所有排列的集合。对于每一个σ∈∑，存在一个唯一的最小侧向量，使得(σ，σ，…，σn)是严格控制策略迭代消除的玩家之上的顺序，并且对于每一个i∈[n]，在玩家σi=xσi·max 0,min 1,1-(1+α)[1-zpσj≤σixσj的侧向量是cσi=xσi·max 0,min1，1-zpσj≤σixσj。（6）一方面，如果全合作是一个唯一的均衡，那么它可以通过迭代消除星图中玩家的某些排列的支配策略来达到；另一方面，命题4说明了如何为每一个排列找到一个最小的附带向量。因此，我们看到，通过遍历所有排列，我们得到了整个最小附带向量集。这表明星图中所有最小边向量的集合Cmin，即边极小化问题的搜索域，是一个有限集。具体来说，集合CMINI的基数由玩家置换集合的基数限定。即对于任意给定的n个边值极小化问题，Cmin≤n！。在这一节之后，我们证明了Cmin实际上小于n！，并且以2n为界。下面的结果定理1刻画了单企业最优解中的部分络。定理1的另一个观察是，如果我们遵循一个最优解中的支配策略的迭代消除顺序，并沿着这个顺序观察给玩家的支配策略，那么最初玩家的某个子集得到了完全的支配策略。这些参与者的合作是一种主导策略，因此他们可以有任何任意的顺序。在这些全部抵押品之后，以下获得部分抵押品的参与者将按照他们的投资顺序排列。他们的部分抵押品是单调的，他们的投资在绝对规模和每个人的投资百分比上都是单调的；也就是说，对于部分抵押品，每一美元投资的抵押品随着投资规模的增加而减少（见推论1）。定理1（最优部分抵押品）：在不丧失一般性的情况下，假设参与者被指数化，使得x≥x≥...≥xn。

修正单个企业抵押品最小化问题的任何最优解，并假设A是该解决方案中获得全部抵押品的参与者的集合。表示xa=pi∈Axi。存在一个最优解，其中有一个完整的抵押品中的玩家和其他玩家的抵押品B=[n]\\A是+i∈B,ci=max0,xih1-(1+α)1-zxa+pj≤ij∈bxji。（7）证明在附录B中。证明的思想是，方程（7）是在以下条件下由命题4得到的，即：按照占优策略迭代消除的顺序σ，游戏者A出现（以任意顺序），然后是B中的游戏者，按其指数的递增顺序排列。然后证明，无论什么时候，只要这个条件不起作用，我们总是可以减少所有的络的和，从弱的意义上说，通过按迭代消去的顺序排列任何一对具有部分抵押品的连续玩家，使得指数最小的玩家（因此投资金额较大或相等）获得。该定理的一个简单推论是，部分抵押品在投资中是单调的，无论是在绝对规模还是在每个人投资的百分比上。推论1对于两个玩家a，b在企业抵押品最小化问题的最优解中有部分抵押品，如果xa>xb，则ca>cband ca/xa>cb/xb。定理1表明，抵押品最小化问题可以归结为选择一个玩家子集给出完整抵押品的问题：因为存在一个最优解，其中一些玩家集A具有完全的抵押品，而其他抵押品是givenby方程（7）,人们只需要搜索集合A，这在下面的推论中被形式化。推论2用d playerscan在O(2dd)时间内找到单企业抵押品最小化问题的解决方案：对于游戏者的每个子集S，构造一个排序σ(S)，其中S中的玩家是预玩家（以任意顺序），预玩家之后的其他玩家Sc以投资金额的不递增顺序排序；然后，根据定理1将排序σ(S)的抵押品设置为S，并将所有抵押品设置为Sc，从而得到总抵押品c(S)。4.1计算复杂性在前一节中，我们已经看到，单个企业的抵押品最小化问题可以作为一个子集选择问题来解决，该子集是由获得全部抵押品的参与者集合来解决的。在这一节中，我们给出了单企业侧向极小化问题与背包问题之间的形式联系，证明了单企业侧向极小化问题对于整数输入是NP-hard的。证明的概要如下。首先，我们考虑一个大的感兴趣参数α的区域，其中，根据引理3，所有的抵押品要么是满的，要么是零的。然后我们证明，在这种情况下，最大的投资者（或者，在相同的最大值重复出现的情况下，这些投资者中的一个）在最优解中必须得到零抵押品（引理5）。然后，我们对均匀背包问题进行反演，在这个反演中，我们寻求一组一维尺寸的物品，这些物品在一起超过了给定的容量阈值，但以最小的方式这样做（反演8）。我们证明了这个反背包问题与标准的均匀背包问题是等价的。引理5（最大参与者）：考虑整数输入{n,{xi}ni=1,Z,α}的单企业抵押品最小化问题。

如果α>Z，那么在每个最优解中，至少有一个投资机会最大的参与者获得零抵押品。接下来，本文对背包反问题进行了研究，发现背包反问题是NP难的，并将其归结为整数输入星图的侧边极小化问题。结论8（背包反问题）：对于整数输入{xi}ni=1和整数阈值t，背包反问题要求s*∈Argmins[n]pi∈Sxi,s.t.pi∈Sxi>t。引理6背包反问题是NP难的。定理2（硬度）：整数输入{n,{xi}ni=1,Z,α}的单企业侧边极小化问题是NP难的。证明：通过背包反问题的约简证明单企业横向最小化问题。设{xi}ni=1,t∈N为背包反问题的输入，我们假定输入均为整数，且t≤pixi-maxixi（否则，该解集内必须有该玩家，该问题可以映射到一个没有该玩家且阈值较低的新问题）。接下来，我们构造了一个求解背包反问题的特例，考虑了一个具有投资{xi}ni=1的参与者集合[n]和一个附加参与者n+1的附带极小化问题的实例，该参与者集合具有投资xmax=maxixi+1,且α=2z。根据引理3，由于α>Z，最优解中的络脉要么满，要么零。通过引理4，我们知道严格地倾向于与零侧方合作的单个博弈者保证由侧方诱导的博弈具有唯一的纳什均衡；通过引理5，在最优解中，这个博弈者是最大的博弈者。在一个最优解中，具有满抵押品的玩家集S是一个满足约束条件PJ∈SX>Z-Xmax的最小和的集。通过设定边值极小化问题toZ=xmax+t的参数Z，我们得到:pj∈Sxj>t。因为S是满足此条件的最小和集，并且由于我们添加到反背包输入的xmaxthat不能在S中，所以这是反背包问题的一个解决方案。因此，具有整数输入的单企业抵押品最小化问题是NP-hard的。5投资网络在前一节中，我们研究了结构非常简单的投资网络：具有单个企业和n个投资者的星图。接下来我们回到任意有向投资网络的一般模型。在这种情况下，如第2节所详述的，如果代理人的企业违约（没有足够的资本投资来支付运营成本），代理人以零回收的方式撤回所有投资，基本上不向任何企业投资。单一企业设置与多企业投资网络设置之间的关键是违约级联风险。例如，如果A是B企业的潜在投资者，而A默认投资，那么A不投资B企业，不管A对此投资有什么动机。这反过来也可能导致B陷入默认状态，在这种情况下B不能投资于任何企业。在本节中，我们将为网络模型提供几个结果。我们证明了在无向无环图(DAG)中，一个不考虑违约级联风险的、在每个企业中诱导唯一纳什均衡的最优抵押品解实际上是在整个网络中诱导唯一纳什均衡的最优抵押品解，即使违约会引发投资失败。事实上，这些为每个企业分别计算的局部最优解在网络中产生了全局最优解。因此，我们得出结论，对于DAG，不需要NetworkExperse抵押品(NEC)，也就是说，由于潜在的违约级联导致的systemicrisk，不需要额外的抵押品。

作为这一结果的推论，我们得到，如果每个企业都可以求解抵押品最小化问题，那么我们也可以求解由这些企业构造的DAG的抵押品最小化问题。特别地，在任何一个企业最多有d个潜在投资者的DAG中，我们可以在O(2ddn)时间内解决问题，然后我们考虑一般的有向图（可能有圈），并给出两个负结果。首先，我们证明违约级联不能再被忽略，它们可能意味着诱导唯一均衡所需的总抵押品的巨大增加（即使存在）--这种增加可以是任意大的（NEC是无界的），这甚至对于具有常数代理数的网络也是成立的。最后，我们证明了循环也意味着计算的困难，即使每个单独的企业问题都可以被解决。在一般的图上，即使使用一个可以分析任何单个企业问题的甲骨文，这个问题也是NP-hard的。5.1初步研究了投资网络的星分解的概念。这一概念对于比较局部和网络在边极小化问题中的作用是有用的。认识9（星分解）：设G=(V,E）是一个有向图，用Ve={V∈V:putu∈Vs.t表示。(v，u)∈E}G中具有非零外度的顶点子集。G的星分解（以H(G)表示）被定义为G的子图族，使得每个子图包括一个顶点c∈Ve，它的所有相邻顶点{v∈v:(c，v)∈E}和连接c的边{(c，v)∈E}。注意，在我们对星分解的理解中，如果考虑多个投资，在多重星子图中可能出现同一个顶点。图3和图4是graphsand星体分解的例子。为了研究投资网络拓扑结构对最优抵押品方案的影响，我们将存在可行抵押品矩阵的网络的网络超额抵押品(NEC)定义为网络中的最优抵押品之和与其在星形分解中的最优抵押品数目之比。显然，当每个星子图是一个网络的一部分时，稳定它的代价只能微弱地高于当它不连接到一个网络时稳定同一个星子图的代价。NEC Quanti定义了将网络稳定在唯一均衡中的成本的systemicstrategic risk分量，或者克服违约级联风险所需的超额抵押品。对于具有投资图G=(V，E)的抵押品最小化问题P={n,X,Z,a}，我们将用PGT表示该问题，以明确它具有投资图G。如果Hii是G的子图，我们用PHI表示绕过子图Hi的抵押品最小化问题。对于具有投资图K的任意问题PK，当存在PK，则用CK=∞表示，否则用CK=∞表示。第10章考虑具有图G=(V，E)的PK={n,X,Z,A}的抵押品极小化问题PG={n,X,Z,A}。设H(G)是G的星分解。PGis的网络超额络(NEC)定义为:NEC(PG)=cgphi∈H(G)CHi(8)注意，由于任何hi∈H(G)是星图，CHiis总是有限的，因此分母总是有限的。5.2有向无环图我们从考虑无环投资图开始。在此背景下，我们的主要结果是，在投资图的星形分解中分别求解每个企业，可以得到无环投资网络的最优抵押品，而忽略了它是网络的一部分这一事实。在忽略违约级联的可能性时，这些抵押品显然足以诱导一个独特的均衡。

证明的主要观点是，我们实际上可以发现一个消除主导策略的顺序，这将确保当一个代理人考虑投资时，她确信没有违约会伤害她，即使是通过级联。本质上，在每个DAG中都有一个企业顶点，没有投资者，而投资者本身就是企业。因此，我们可以争辩说，我们可以把这个企业顶点和它的投资者找出消除主导战略的顺序（根据该企业作为一个独立企业的最优解的顺序和抵押品）。任何以后的代理都知道这个fireRst企业不会默认，所以我们可以在网络的其余部分递归地继续，而不必担心以前的企业会触发默认级联。图3显示了该过程。图3：左：一个有向无环图(DAG)。这些数字显示了一个拓扑顺序。顶点1、2、3是企业顶点。右图：图的星形分解。星形子图上的拓扑序归纳为序。在迭代消除玩家的占优策略中（每个决策对应一条边），消除排序较高的星子图的边。大写字母显示了这种迭代消元顺序的一个例子。迭代是从3号星图的边按拓扑顺序开始的，这些边是由该星图问题的解排序的。一旦星图3被保证在唯一的平衡中，星图2就可以作为一个独立的问题来求解，而不会有因星图3而违约的风险，并且这个过程沿着由拓扑序所诱导的星图的顺序继续下去。定理3（DAGs中的最优抵押品）：考虑图G=(V，E)的抵押品极小化问题G={n,X,Z,a}。设H(G)={Hi}i∈VE是G的星分解，其中VE是企业顶点集。如果G是无圈的，则通过分别求解H(G)中每个子图的边极小化问题，得到了边极小化问题PGcan的一个解。因此，对于图G为DAG的任何问题PG，本文认为CG=phi∈H(G)chi，且so NEC(PG)=1。证明：对于每个子图Hi∈H(G)，求出该单个企业图的边值极小化问题的解，并设Chi为该解中的总边值。我们声称，这些相同的络脉（具有适当的消除顺序，特别是下面所述）形成了问题PG的解决方案。该解具有总侧支Cg=phi∈H(G)CHi，并且没有解具有较低的总。首先，如果Pgs有一个解，总比CHi低，那么它就会导致一个子图Hi（具有相同的消序和络序）的解，总比CHi低，这是一个矛盾。其次，我们论证了对于Totalphi∈H(G)chi的PG，确实存在一个解。为了证明这一观点，我们给出了一个消去支配策略的序，设ζgbe是G的拓扑序，即对于每个有向边（i,j）,顶点i出现在j之前的顶点的序。当G是DAG时，就存在这样的排序。考虑玩家策略的以下顺序--企业顶点（Ve中的顶点）按照拓扑顺序的相反顺序排列；当考虑一个企业顶点i是这个顺序时，我们按照这个企业顶点的星图解所规定的顺序来处理投资机会（边）。这为消除PG的支配策略提供了一个决策边的顺序。我们认为，如果我们按照这种顺序消除主导策略，所有玩家确实会投资于他们所有的投资机会。

的确，通过归纳很容易看出，当一个顶点考虑投资一家企业时，上述顺序保证了在DominatedStrategies迭代消除下，同一企业的所有其他投资者永远不会违约。定理3表明，每一个具有非循环投资结构的抵押极小化问题都可以分解为O(n)个星图问题，求解这些星图问题为网络问题提供了一个解决方案。如果网络的out度为有界d，则上一节所示的星图边极小化问题的求解过程的运行时间为O(2dd)（推论2）。推论3考虑具有图G=(V，E)的旁支极小化问题PG={n,X,Z,A}。如果G是一个DAG且有界的out度d,则在O(2ddn)时间内可以解决边极小化问题。5.3一般图定理3表明，在每个有向无环图G中，对于拓扑G的每一个最小化担保问题PG，NEC(PG)=1，即不需要额外的担保来处理网络系统风险。与此形成鲜明对比的是，下面的定理显示了具有有向圈的thatin图，NEC是无界的，即使只考虑有可能通过络环诱导唯一平衡的实例。证明使用了图4所示的构造。festigure显示了一个investmentopportunities循环，其中每个循环顶点在其自己的企业中也有两个外部投资者，其中一个投资者的投资金额（大小为1)，另一个投资者的投资金额由K参数化。证明了要建立完全投资为唯一均衡，必须给至少一个循环变量的两个外部投资者提供完全抵押品，从而使总抵押品大于k+1，并且可以任意增大（通过增加k）。基本的直觉是，这些循环顶点永远不可能有一个主导策略（即使有完整的络脉，因为他们仍然可能违约），因此，只有当控制策略中的一个不被违约时，才能建立一个迭代消除控制策略的顺序。定理4（周期费用）：对于任意R>1，存在一个具有循环投资图G=(V，E)的可解边极小化问题PG={n,X,Z,a}，NEC(PG)>R。此外，即使对于所有共享相同投资图G的问题，只有3个企业顶点和常数顶点数(n=V=9)的onecycle也成立。证明：我们给出了一个循环网络来证明这一主张，见图4。左边的图说明了一个对称循环网络，有九个参与者，其中三个是投资者，也有投资企业，另外六个是投资者，没有自己的企业。潜在的投资金额被描绘在图的边缘，箭头是在投资回报的方向上。我们将以sizek>2的投资为参数，设Za=Zb=Zc=k+1和α=2k。在G的星分解中的星图的最优解中，对子图来说，投资者B和a得到全额抵押品，而a操作零抵押品。在星型分解中，每个企业的成本为2，总成本为6。在这个循环中，存在一个可行的抵押品矩阵（例如，所有参与者的全部抵押品构成一个可行的抵押品矩阵），但星形分解的这些抵押品并不是完全一致的：无论以何种顺序迭代界定主导策略，除非该投资是以全部抵押品担保的，否则参与者a、b、ccanbe的投资机会都不在其他两个之前。

因此，在这个循环中，对于其中一个星形子图，总成本为k+1，而对于另一个星形子图，总成本为2，总成本为k+5。因此，循环最优解与星形分解局部最优解之和之间的代价之比为ISK+5。所以我们可以选择足够大的kto来证明这个说法。该网络证明了在具有循环的情况下，全局最优值可以任意地比局部解之和更昂贵，NEC为θ(k)。下面的定理表明，对于一族总是存在解的实例，即使每个企业的局部解是已知的，投资网络中的循环也意味着计算困难。在循环投资网络中没有可行的旁支矩阵的情况下，可以用多项式时间来证明。见第3.2节和附录A。图4：左：循环图；右图：星形分解。定理5（循环的硬度）：循环投资网络的整数输入{n,X,Z,A}的侧边极小化问题是NP难的。此外，本文还给出了星图上最优保络问题的求解方法。证明：该证明是由反馈顶点集问题的约简得到的。设G=(V，E)是有向图。用di表示顶点i∈V的外度，取k=1+maxi∈Vdi。现在，我们希望构造一个侧边极小化问题的实例，该解决方案也解决反馈顶点集问题的优化（极小化）版本。为此，我们将通过以下步骤构造一个图G=(V,E）：首先，我们迭代地从G中移除所有具有零外度（和入射边）的顶点，直到没有其他顶点。这个过程需要多项式的多个步骤，得到一个图，它只包含G中的圈顶点V，V和由V诱导的所有边。注意，所得到的图中的圈与G中的完全相同（因此，两个图上反馈顶点集问题的解是相同的）。然后，我们给i，j∈Va的每条边（i,j）赋权xij=1。接下来，我们在Va“gadget”中的每个顶点中添加两个邻居--新顶点的OUT度为零，in度为一。一个顶点有权重为1的入边，另一个顶点有权重为K的入边。设G=(V,E）为结果图（vise vs与来自小工具的附加2V个顶点的并集）。现在我们给每个顶点指定两个参数:zi=k+1和αi=2k。注意到图G中的所有圈都是相同的圈，因为我们只添加了“尖峰”顶点，而这些顶点并不具有固定的ECT圈，因此Gis的最小反馈顶点集与G中的最小反馈顶点集相同。具有顶点性质{Zi},{αi}的加权图也定义了旁支极小化问题的一个实例PG。在这个问题的例子中，存在可行的抵押品矩阵（例如，所有玩家的全抵押品都是可行的抵押品矩阵），并且最优抵押品具有以下性质：在PG的最优抵押品中，在每个循环中至少有一个顶点其输出边的抵押品之和为k+1。另外，每个外度为非零的顶点到外边的络和要么是2,要么是k+1。证明：当αi=2k>k+1=zi，对于每一个i∈V，根据引理3，这个例子是在大α区，意味着每个络要么是满的，要么是零的。因此，对于nodesi,j∈V的每一条边（i,j）,其旁路cij等于xijor零。考虑G.中的一个任意循环，该循环中的Foreach顶点及其输出边（构成一个星形子图），如果存在缺省，那么最优抵押品是两个权重为1的玩家的完全抵押品（现在星形子图中权重为k的玩家更愿意投资，即使是零抵押品，然后所有其他玩家都跟着投资）。

然而，如果这些是一个循环中的抵押品，它们就不能在迭代消除主导策略中获得唯一的均衡。这是因为权重为k的玩家不能在这些合作的规模为1的玩家之后以任何迭代划分顺序出现，除非她获得了全额抵押品，因为在周期的某个地方有违约风险（对于没有抵押品的其他玩家也是如此）。另一方面，一旦循环中的一个sesize-k玩家有一个完整的抵押品，另一个完整的抵押品必须给同一个星形子图中规模为1的玩家以支付运营成本，然后在这个星形子图中不需要进一步的抵押品。因此，在最优解中，在每个循环中都有一个顶点，该顶点到其输出边的络和为k+1。现在假设一个星形子图，其最优解中的络和小于k+1。这些担保物诱导合作以支付Z=k+1的运营成本的一个必要的条件是，规模为k的参与者可以确信至少有两个规模为1的参与者在投资者集合中，在这种情况下，规模为k的参与者可以从与ZeroCollateral合作中受益。由于解是最优的，这样的星形子图中的络和不能大于2。用S*表示一组顶点，使得对于每个这样的顶点，其出边的络和是k+1。在边值极小化问题的解中，每个循环至少包含一个来自S*的顶点，因此边值和可以写成(k+1)S*+2(S*)C。G*中的每个圈包含S*中的一个顶点。因为G有与G相同的圈，所以S*∈Argmins对S.T。G中的每个圈包含S*中的一个顶点，它是反馈顶点集问题的一个解。因此，即使星图问题的解是已知的，抵押品极小化问题也是NP难的。上述结果揭示了投资网络中可能存在的循环和系统风险：第一，没有循环的网络更容易在有抵押品的情况下稳定；即使在有界度网络中，循环的存在通常会增加抵押品的最小代价，并增加计算量。其次，在没有循环的网络中，每一个投资者对其潜在投资者进行局部优化的最优抵押品也会产生由中央规划者计算的全球最优抵押品。相比之下，当周期存在时，有一些网络，在这些网络中，当地最优的担保物并不导致唯一的均衡，因此可能需要中央规划和干预来确保稳定。承认本项目根据欧盟的地平线2020研究和创新计划（赠款协议号740282）获得了欧洲研究理事会(ERC)的资助。参考文献[1]Acemoglu，D.Ozdaglar，a.Tahbaz-Salehi，a.:鱼类网络中的系统性风险和稳定性。《美国经济评论》105(2)，564-608(2015)[2]巴布斯，A.:《金融网络的形成》(2013),https://ssrn.com/abstract=[3]巴布斯，A.，Hu，T.W.:《场外交易市场中的内生中介》。《金融经济学杂志》125(1)，200-215(2017)[4]Ban,A.,Koren,M.：顺序筹资与社会保险。载：第21届ACM经济与计算会议论文集。第45-46页。EC\'20，计算机械协会，纽约，纽约，美国(2020)，https://doi.org/10.1145/3391403。[5]伯南克，B.Gertler，M.:金融脆弱性与经济绩效。第四版经济学杂志105（1）,87-114（1990）[6]伯南克，B.S.,Gertler,M.：代理成本、抵押品和商业价值。技术。美国国家经济研究局代表（1986）[7]Brandts,J.,Cooper,D.J.：改变会对你有好处...组织中如何克服协调失败的实验研究。