多企业网络中的最优投资组合助于处理系统性风险

79→多企业投资网络中的最优投资组合Moshe Babaioff以色列赫兹利亚微软研究院moshe@microsoft.com约阿夫·科伦布斯以色列耶路撒冷希伯来大学kolumbus@mail.huji.ac.ilEyalWinterLancasterUniversity希伯来大学英国兰开斯特电子邮箱huji.ac.il：yal.winter@www.example.com摘要我们研究了网络上的投资市场，其中每个代理（顶点）可以投资于与她相关的任何企业，同时，从与她相关的其他代理那里为她公司的企业筹集资金。未能筹集到足够的资本导致公司违约，无法投资于其他公司。 我们的主要目标是研究抵押品合同在处理战略风险中的作用，这种风险可能在违约级联中传播到整个网络的系统性风险。 本文采用机制设计的方法，求解了融资者向投资者提供担保契约的最优方案。 这些合同的目的是维持有效的投资水平作为一个独特的纳什均衡，同时最大限度地减少总抵押品。我们的主要结果对比了网络环境与非网络环境（投资者和资本筹集者的集合是不相交的）。我们发现，对于非循环投资网络，网络环境不需要任何额外的抵押品，系统性风险可以完全由资本筹集者和投资者之间的最优双边抵押品合同来处理。不幸的是，循环投资网络的情况并非我们表明，双边合同将不足以解决系统性风险，市场将需要一个外部实体来设计一个全球抵押品计划的所有资本筹集者。此外，与相应的非网络环境相比，即使在简单的循环投资网络中，将维持有效投资水平作为唯一均衡的最小总抵押也可能任意地更高此外，我们证明了计算复杂性的结果，无论是一个单一的企业和网络。CCS概念• 计算理论;博弈论与机制设计;网络游戏。关键词机制设计，战略风险，金融网络，投资ACM参考格式：Moshe Babaioff，Yoav Kolumbus和Eyal Winter。2022年多企业投资网络中的最优协同。在ACM Web的会议记录中允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。版权的组成部分，这项工作所拥有的其他人比ACM必须尊重。允许使用学分进行摘要 以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。请求权限请发邮件至permissions@acm.org。WWW©2022计算机协会ACM ISBN 978-1-4503-9096-5/22/04。. . 十五块https://doi.org/10.1145/3485447.3512053会议2022（WWWACM，美国纽约州纽约市，11页。https://doi.org/10.1145/3485447.35120531引言企业和投资实体筹集资金从事有价值的投资企业往往面临战略风险。投资者可能会拒绝投资，因为他们担心公司将无法筹集足够的资金，因为其他投资者拒绝投资。这可能会将投资博弈锁定在一个不协调的低效率当这些公司在投资网络中相互联系时，这种战略风险可能会在整个网络中传播，并可能对整个市场产生影响本文的目的是研究这样的网络环境，揭示系统的战略风险，他们可能会暴露，并显示如何通过最佳的抵押品计划，这种风险的负面后果可以补救。与标准风险不同的是，标准风险可能来自我们几乎无法控制的各种力量，战略风险是由于均衡的多样性而产生的，通常可以通过激励措施来减轻。在我们的背景下，这些激励将采取担保的形式，担保足够的投资，因此不会在均衡路径上支付。在单个企业融资的框架内，投资者的战略考虑只涉及对该基础企业的其他潜在共同投资者的决策及其决策后果的在投资网络的框架下，参与者的考虑范围投资公司不仅应考虑共同投资者的投资动机，还应考虑共同投资者可能的破产，而破产又取决于其他公司对该共同投资者的企业进行投资的动机。我们对单个企业的正式投资模型假设，如果筹集到的资本足够高，足以支付企业的运营成本，那么筹集资本的公司有一些承诺一定回报率的企业。有一组潜在的投资者，每个人都有机会在企业中投资一些投资者特定的金额，并需要决定她是否投资。如果投资不能弥补经营成本，企业就处于违约状态，投资者如果没有违约，则企业因此，企业为了消除可能使投资者不愿投资的战略不确定性，公司向投资者提供抵押合同，限制战略风险造成的损失该公司的目标是找到一个最佳的（最低总额）抵押品计划，保证所有投资者选择投资（因此不发生违约在一个独特的均衡的投资游戏。80O（）WWW我们的网络投资博弈模型扩展了单一企业模型，并具有违约级联的基本附加问题。 与单个企业的情况不同，在投资网络中，每个投资者可能在多个企业中有投资机会，并且对于每个企业，她必须决定是否投资。此外，其中一些投资者实际上是在为自己的企业筹集资金，如果没有筹集到足够的资金，就可能违约。当一家公司违约时，它会立即撤回所有投资，我们假设违约公司零回收的最坏情况，正如文献中常见的那样（参见，例如，[9，14]）。 我们假设网络是外部给定的，代表企业之间现有的业务关系。 与单一企业案例的关键区别在于，违约的公司不能对其他企业进行投资，这可能会造成一连串的违约。因此，在网络环境中，每个投资者原则上不仅必须评估其他共同投资者的投资动机，而且还必须评估其中一些共同投资者违约和不投资的可能性。网络抵押问题寻求一个最优的（最小总的）抵押方案，保证对于有效企业的子网络，所有投资者在网络投资博弈的唯一均衡中选择投资于所有企业（因此不发生违约）。重要的是，这些抵押品必须足以克服违约级联的系统性风险。关于模型的全部细节和优化问题的正式定义，请参见第2我们的分析首先描述的最优方案，最小化的整体抵押品，以维持在一个独特的均衡有效的投资 我们表明，只要完全投资可以建立作为唯一均衡的抵押品合同，最优方案产生一个优势可解的游戏。也就是说，唯一均衡是通过迭代消除劣势策略获得的（见第3节）。在第4节中，我们将重点讨论单个企业网络。我们描述了最优方案，表明在这样的网络中，它们一定存在。此外，我们发现，找到一个最佳方案的企业与n个投资者的问题是NP-困难的。然后，我们在第5节回到一般的网络游戏。 在研究网络环境的系统性战略风险的敏感性，我们的研究结果突出了循环和非循环网络之间的重要区别。 当网络是无环的，我们表明，存在一个最佳的抵押品计划，整个市场，可以表示为一个较小的计划，一个为每个企业的集合，这样的抵押品，每个公司承诺其潜在的投资者是相同的假设下，这些投资者没有外部义务，因此所有的投资者都有能力投资，如果提供这样做的激励。换句话说，一家公司在设计其抵押品计划时，似乎整个市场都由它自己和它的潜在投资者群体组成，而忽略了其他所有人我们展示了如何计算无环网络的最优方案和控制策略的迭代消除顺序迭代的顺序取决于网络的结构，在非循环网络中，它是由具有企业的企业的拓扑顺序引起的。特别是，迭代从不持有自己企业的公司的投资开始，并以确保在做出每个决策时不再担心违约的方式继续下去从计算的角度来看，在非循环网络中的n个企业，其中每个企业最多有d个潜在的投资者，我们表明，这个解决方案可以在2ddn时间。特别地，当d是常数时，它是多项式不幸的是，在循环网络下，整体最优并行方案可能不会被简化为最优方案的集合–事实上，我们表明，对于一些（简单的）循环网络，防止系统性战略风险所需的总抵押品任意高于公司只考虑自己的投资者时所提供的总抵押品。这一发现的含义是，在循环网络下，系统性战略风险的预防可能不是分散的，因为它需要一个外部实体来解决潜在的不协调。此外，存在循环网络，其中完全投资是一个均衡，但它不能被建立为任何抵押方案的唯一均衡。 这些结果源于这样一个事实，即向潜在投资者提供抵押品，忽略违约的可能性，并不足以确保所有人都会投资。最后，我们表明，循环引入进一步的困难，在计算方面：我们表明，找到一个最佳的抵押方案在循环网络是NP-难的，即使每个公司的问题的解决方案是已知的。 我们证明了这一点，提出了一个减少最小反馈顶点集问题。 详情见第5.3节。文献讨论在单个企业的情况下，我们的模型类似于[15]。主要的区别在于，这里我们通过在均衡路径上不支付的抵押品来获得投资，而不是提供更高的投资利息。另一个不同之处在于违约的原因在[15] 违约是随机的，当筹集的资金低于一个随机阈值时就会触发违约。相反，当运营成本超过总投资资本时，就会发生违约。我们引入了更简单的单个企业模型，使我们能够专注于投资网络，而不仅仅是单个企业的问题。[5]研究了一个不同的单个企业投资博弈我们的模型和分析在基本特征上有所不同最重要的是，我们研究了具有异质投资者的网络环境，考虑这些网络的机制设计问题。系统性风险在银行间贷款风险的背景下得到了广泛的研究能力网络我们参考了对这一文献的两次调查[9，17]，并在下面提到了几部更接近我们背景的作品该调查[17]将系统性风险的来源分为两种类型：直接外部性和多重均衡系统中的自我实现反馈效应 我们的工作在概念上与后一种类型相关，然而，通常在系统风险文献中研究的均衡与我们考虑的概念不同。在负债清算模型中，均衡与清算过程的固定点有关在这个过程中，网络顶点（银行）不做决定。相反，在我们的设置中，投资机会网络诱导投资者的博弈，均衡是博弈的纳什均衡我们研究的问题是，在网络环境下的投资机会诱导的多人博弈中的激励设计，以诱导期望的均衡结果。从这个意义上说，我们的方法与机制设计和算法机制设计领域更密切相关[20]，具体来说，与作品相关。81（）∈（）∈[]（）i=1i=1.·∈∈•∈k（）下一页≥{∈∈（）∈}•（）∈多企业投资网络中的最佳合作WWW在研究用于在游戏中获得期望结果的最小干预模型的机制设计文献中（例如，[18、19]）。在[22]中，作者研究了在[21]的模型下通过银行网络中的投资组合压缩消除网络周期的效果他们对激励的讨论在概念上与我们的方法接近，但研究的问题不同。的问题[22]根据[10，21]的精神，考虑了由于外部冲击造成的系统性风险，而我们研究了投资者做出决策的战略环境，并专注于战略风险导致的系统性风险循环在解决问题中的作用也在[16]中讨论过他们的模型描述了除了负债之外还包括股权联系的银行网络，从而推广了[10，11，14]的模型。 作者表明，在他们的模型中的负债-权益清算问题的多个解决方案的存在性与循环债务关系。 考虑到所有投资都已经完成，他们在事后利用救助来修复由于冲击而导致的违约级联。与[16]的清算问题相反，我们研究了一个博弈，在这个博弈中，个人做出投资决策，抵押品被设计成影响这些投资决策。在[23]中，[10，21]的债务清算问题被扩展到讨论还包括信用违约互换（CDS）形式的与投资者购买的CDS合约不同，在我们的案例中，融资公司向潜在投资者提供抵押品，以激励他们首先参与投资。此外，通常情况下，CDS是一种比抵押品更有限的证券形式，因为合同的执行取决于出售CDS的第三方的偿付能力。事实上，在系统性风险的背景网络中其他公司的企业每个拥有投资企业的投资公司都通过向外的边连接到一组投资者代理。一条从顶点k到顶点i的有向边，其权重为xki> 0，表示智能体i有机会在k的企业中投资xki。投资者代理人决定是否接受或拒绝他们的投资机会（对于整个金额xki）。[1]一个公司有多条进入边，代表公司考虑的多个投资机会，它为每一项投资做出这种二元决策，并获得等于所有投资效用之和的效用每个拥有投资企业的公司都有一定的运营成本，如果公司没有筹集足够的资本来支付成本，公司就会违约。违约公司会立即撤回所有投资，零回收，因此它基本上没有对任何企业进行网络结构被假设为一个外生输入，代表在给定时间（比如年初）的一组投资机会2为了说服投资者投资，企业可能会向潜在投资者提供抵押品，以降低这些投资者的战略风险。 接下来，我们给出了该模型的形式定义和投资网络诱导的博弈。首先，让我们定义基本组件：有一个集合V的n公司，n表示公司指数。 有一个图G = V，E描述了投资互动的拓扑结构，其中边k，i E表示i在k中有一个投资机会。每条边k，iE都有一个权重xki，指定i可以投资于k的金额。为了方便起见，我们假设投资机会由矩阵X给出，对于每个非边缘，X为0令Z=由于违约而触发CDS合约可能与CDS卖方本身违约{Zi}n，A ={αi}n其中Zi，αi ≥ 0为企业i ∈ V成本，另一个相关的工作是关于内生网络形成模型[1，3，4，12，13]。与我们的工作的主要区别是，这些作品考虑由于外部冲击的风险，而我们专注于战略风险和由此产生的系统性风险，并在机制设计问题，抵押品合同用于诱导作为一个独特的结果有效的均衡。抵押合同是最古老和最基本的金融证券形式之一在两部经典著作中，[6，7]伯南克和格特勒强调了抵押品在投资市场中的作用，说明了抵押品的数量如何导致更高的投资，抵押品的减少可能会引发投资的减少在他们的模型中，这一机制是由于信息不完全而产生的投资者代理成本;当筹集资本的公司拥有较少的抵押品时，这些成本就会增加在我们的模型中，抵押品合同为每个投资者提供了一个明确的抵押品，因此，由于理性参与者的战略考虑，即使在完全信息环境中，抵押品和投资之间也存在类似的关系。据我们所知，我们的工作是第一个研究抵押合同作为一种机制设计工具，在战略环境中，利率参数，如下所述另外，记为Ve=v V：u V s。t. v，uE是G的企业顶点的集合，即，具有潜在投资者的顶点的子集（在G中具有非零的出度）。对于每个顶点i g Ve，αi和Zi都是不相关的，并且可以w.l.o.g. 设置为0。模型如下：设Xk=ixki表示企业k中的投资机会之和。每个公司i在k（k，iE）中有一个投资机会xki> 0，选择两个行动之一：（i）将全部金额xki投资于k，并等待在年底获得回报（与 k 合作）。 k ） ; 或 （ii ） 拒 绝 k 的 投 资 机 会 （ 缺 陷w.r.t.k）。请注意，具有多个投资机会（传入边）的代理人会分别为每个投资机会做出这样的决策企业k的运营成本由成本参数Zk0表示表示叛逃者的集合w.r.t.k乘Dk，coop的集合发电机w.r.t.k，k。边k，i称为协作边，如果我Ck和缺陷边，如果iDk.年初，每一个叛逃者，D保持全额x千分之一。3.如果公司这样做，积极应对系统性战略风险。1这个模型类似于[15，24]，旨在捕捉这样一个事实，即许多2模型2.1投资游戏考虑一个有n个顶点的投资网络，每个顶点代表一个公司。一家公司可以有一个投资活动涉及筹资公司根据其财务需要和投资者的限制以及公司希望在投资者之间分配的控制权，提前确定每个投资者的预期投资。2.网络形成的内生化问题是一个有趣的问题，但超出了本文件的范围。[3]为了简化分析，我们假设未投资的资金不计利息添加这种兴趣不会显著改变模型，并且我们的结果可以容易地适当调整··82.∈k∈（）（−）≥∈•≥（）下一页∈\∈∈{ X Z A}.{ X Z A}∅∈{X}ZAC×∀ ∀−（1）投资者的投资额为（1+αk）（i∈Ikxki−j∈Ikj∈Ikxkj每个参与人i的总效用是Ui=如果xki=0，则Uki= 0（即，如果（k，i）gE）。n，，， 。抵押品最小化问题要求找到一个可行的抵押品矩阵，如果存在的话，具有最小的抵押品总和：c∈CWWW没有筹集足够的投资来支付其企业的运营成本用Ik表示在Ck中且没有违约的参与者集合，这些参与者投资于企业k。如果对k的总投资不能覆盖运营成本（i Ixki 0，即. 例如， 这是一个很好的机会。谈话金额）∈那么玩家严格地选择投资。4这简化了写作，因为玩家永远不会对两个动作漠不关心。形式上，这种打破平局的规则相当于在合作中增加一个固定的无穷小效用显然，如果即使假设所有投资者都合作，回报也不足以向投资者分配其原始投资额，企业就不应该成立因此，只有盈利的企业才会发生（而其他企业则不会），因此我们关注盈利企业的子集，忽略不盈利的企业（通过将它们从网络中删除）。因此，在本文的其余部分，我们假设所有Zk. 企业从k到投资者i Ik的回报Rki为iKV e，1 +α kX kZ kX k。很容易看出，在这种情况下，每个人都合作是纳什均衡，没有抵押品R ki= max.0，（1 + α k）. .x kj− Zk。 中国（1）如果所有玩家都合作的话。x____________________________净回报背叛也可能是一种均衡。5、为了避免这种不好的情绪，设cki0为参与人i的抵押品，用于投资xki.如果参与者i Ik的企业回报率Rki低于投资xki，那么抵押品cki可以实现，使得参与 者 i 从 k 获 得 的 效 用 为 Rki+cki ， 上 限 为 xki ， 即 ，minRki+cki，xki.如果参与者i有利润（即，R ki> x ki）抵押品未变现。因此，背叛（i Dk）的参与者的k的效用是xki，如果她在默认情况下合作（i Ck Ik），她的效用是0，如果她投资（i Ik），抵押品cki为：所有的合作作为唯一的平衡，只要有可能。我们关注的抵押品，诱导所有合作作为一个唯一的纳什均衡，我们称之为可行的抵押矩阵。我在2号线（可行抵押矩阵）：抵押矩阵c被称为可行抵押矩阵，如果由c诱导的具有输入n的博弈具有唯一的纳什均衡，其中所有参与者合作。在本文中，我们考虑的问题，找到一个可行的collat-Uki= cki+ Rki，Rki ≤xki−ckixki，xki − cki < Rki ≤xkiRki，xki 0矩阵c ε ei j不是可行抵押矩阵，其中ei j是n n矩阵，除了第i，j '个元素等于1之外，所有元素都等于零。请注意，最小范数可行抵押矩阵也必须是最小抵押矩阵，因此是抵押品的解决方案[4]请注意，效用为零的默认结果总是由背叛主导的。5例如， 当一个企业的成本高于该企业的任何一个投资机会的金额时。当所有参与者合作时，投资企业是有利可图的然而，这个纳什均衡可能不是唯一的，所有的代理人ilibrary，我们感兴趣的是找到抵押品，将诱导k∈[n]Uki，其中在下面的过程中确定投资边缘的诱导集83X{X}ZA多企业投资网络中的最佳合作WWW最小化问题是最小化抵押品总和以下定义区分了两种类型的侧枝，这将有助于稍后描述最佳侧枝的特征。每个抵押品可以是“全部抵押品”，覆盖玩家的全部投资，也可以是“部分抵押品”，保证低于投资的最低回报。我在5楼。（全部抵押品）：对于投资机会xki>0，抵押品cki被称为完全抵押品，如果cki=xki。我在6号线（部分抵押品）：对于投资机会xki> 0，如果抵押品cki不是全部抵押品，则称为部分抵押品（注意，这包括零抵押品）。3表征在本节中，我们刻画了抵押品最小化问题的基本性质。我们首先表明，唯一的平衡意味着优势可解性。然后，我们提出了一个多项式时间的程序，以找到一个独特的平衡，可以诱导的抵押品。在论文[2]的完整版本中，我们还描述了参与者即使在零抵押品的情况下也愿意合作的条件，以及参与者只有在有充分抵押品的情况下才愿意合作的条件这些特征在后来的许多证明中是有用的。3.1单调性和优势可解性投资及其相关战略风险的一个重要特性是，投资收益随着额外潜力的增加而增加投资者决定投资，并减少合作投资者停止投资。更具体地说，对于任何参与者来说，在所有其他投资机会上投资于一个给定合作概况的企业，随着决策从缺陷转向合作，她的收益只会增加。这在以下命题中得到了证明建议我在1。（单调性）：（1）对于参与人i在企业k中的任何投资机会xki，在参与人合作的网络中，企业对i的回报在投资机会集中是单调递增的。也就是说，如果Rki（C）表示当C是合作边的集合时参与人i投资于企业k（i ∈ Ik）的企业收益，则对于每两个集合B <$A，Rki（B）≥Rki（A）成立. (2)固定任意边子集A，任意企业k∈V e，任意参与人i，使得（k，i）∈E且（k，i）gA。假设当合作边的集合是A时，则参与人i严格地偏好合作而不是背叛w.r.t. K. 然后，当合作边的集合是B ≠ A时局中人i严格选择合作而不是背叛w.r.t. K也是。一个推论是，单调性在相反的方向上也成立：如果当参与者在某组投资机会中合作时，缺陷是参与者的最佳回答，那么当参与者仅在这些机会的子集中合作时，缺陷也是最佳回答下一个结果表明，当抵押品诱导一个具有唯一纳什均衡的博弈时，所有参与者都合作，诱导博弈是优势可解的，即，通过迭代消除严格劣势策略可以达到均衡 对于完备性，我们从优势可解性的定义开始。我在7号线。（优势可解博弈）：一个博弈被称为优势可解，如果在以下策略上存在阶σ迭代消除严格劣势策略的参与人，导致单一策略配置文件。建议2. （唯一均衡条件）：如果博弈由抵押矩阵c与输入n，，，，有一个唯一的纳什均衡，其中所有的参与者合作，在所有的投资机会，那么游戏是优势可解的。3.2通过Colonial的唯一平衡抵押品最小化问题的目的是寻找最优抵押品，以诱导完全投资的唯一均衡;作为机制设计目标，这一相当强的解决方案概念旨在确保参与者之间没有不协调问题，并且游戏达到有效结果。实证文献显示，在存在战略风险的情况下，参与者往往会收敛到效率低下的均衡，这很好地推动了寻求唯一均衡的努力（例如，[8]）。有趣的是，与非网络情况（每个企业都有自己的一组投资者）不同，在一些网络结构中，抵押品不能引起独特的这些情况发生在循环投资网络中，并且是由于网络中的特殊类型的循环结构。我们的表征显示了如何识别这种情况下，并隔离这些有问题的结构。具体而言，在单一企业网络以及在所有的有向无环网络，有没有问题的结构和一个独特的平衡总是可以诱导的抵押品。下面的结果，命题3，提出了一个建设性的投资网络，其中一个独特的均衡可以通过抵押品诱导的特点。这是通过在多项式时间内运行的迭代过程来完成的。 图1给出了说明迭代过程的一个步骤的示例。命题3的证明和进一步的细节可以在论文的完整版本中找到[2]。建议我在3楼。（通过抵押品的可解决性）：考虑以下迭代过程：如果在图中存在企业k，使得来自该企业中的非企业顶点（尖峰）的总投资至少是该企业的成本（Zk），则移除该企业及其非企业投资者顶点和附带边，并将k具有的每个投资机会替换为来自新（尖峰）顶点的相同机会。然后，在新的图表上重复。当且仅当上述过程以空图结束时，才有可能通过抵押品诱导出唯一的均衡4单个企业在这一节中，我们将讨论具有单个投资企业和n个潜在投资者的网络的情况。 我们称这种类型的网络为星形图;即，一个网络，有一个中心顶点，用向外的边连接到n个顶点，如图所示4. 在这种情况下，为了简单起见，我们稍微滥用了符号，使用n来表示潜在投资者的数量（不包括没有做出投资决策的单个企业顶点），并省略了企业的指数，只保留边权重xi的投资者指数i。此外，由于在星形网络中，矩阵c只有一行非零元素，我们将它们视为向量而不是矩阵。此外，由于只有一个企业，我们用Z表示它的成本，用α表示它的利率（而不是用Z，A）。84.∈≥ ≥≥联系我们（）下一页联系我们[]∈（）下一页O（）·max 0，min 1，1 −（1 + α）。1−。Zσj≤σixσj..（四）我我WWW图1：命题3的迭代过程中的一个步骤示例。 字母表示顶点名称，有向边附近的数字表示投资机会金额。例如，在一个示例中，顶点A在顶点D的企业中具有金额2的投资机会。在本例中，未指示数字的边可以具有任何正值左：迭代步骤之前的网络顶点a是运营成本Z a= 2的企业顶点。 顶点a也是网络中的循环顶点，并且具有三个非企业投资者（尖峰顶点），每个投资额为1，总计超过成本Z a，并且因此（完全）Collaterals可以确保a不会违约。右图：迭代步骤后的新网络，捕获了一个被确保的偿付能力。 顶点a连同它的尖峰顶点（b，c，d）和关联边一起被移除。金额1和2的顶点a的投资机会被来自新尖峰顶点的相同金额的投资替换，用虚线边界指示并由a1和a2表示。注意，这里每个参与人都有一条进入的边，所以参与人策略的淘汰顺序相当于下面的结果，定理1，在一个单一的企业抵押品最小化问题的最优解的部分collaterals的特征 该定理表明，在最优解中获得全部抵押品的参与者的集合提供了足够的信息来容易地确定全部解。从定理1中得出的另一个观察结果是，如果我们遵循最优解中劣势策略的迭代消除顺序，并观察沿着这个顺序给予参与者的抵押品，那么最初一些参与者的子集得到全部抵押品。这些参与者的合作策略是优势策略，所以他们可以有任意的顺序。 在这些完整的抵押品之后，下面的玩家，谁得到部分抵押品，是按照他们的投资降序排列的。他们的部分抵押品与他们的投资在绝对规模和每个人的投资百分比方面都是单调的;即， 对于部分抵押品，每美元投资的抵押品随着投资规模而减少（见推论1）。定理1. （最优部分抵押品）：在不失一般性的情况下，假设参与者被索引，使得x1x2.xn.确定单个企业抵押品最小化问题的任何最优解，并假设A是在该解中获得全部抵押品的参与者集合。记为X A= i A x i。存在一个最优解，其中A中的参与者拥有全部抵押品，其他参与人B=[n] \A是命令球员。此外，在星图中，玩家不能违约，因为他们没有自己的企业。作为向所有投资者提供全部抵押品的抵押品载体，i∈B，ci=最大0，x i.1−（1 +α）。1−XA+。j≤ixj∈B- 是的-是的（五）一个可行的抵押品载体（因为没有违约），存在一个解决单个企业抵押品最小化问题的办法。我们接下来描述这样的解决方案。证据见附录B。下一个引理展示了星形图的一个有趣的性质，这对我们的证明很有用：给定一组合作者，一旦该组之外的单个参与者倾向于与零抵押品合作，所有其他人也会倾向于零抵押合作。让我们来看看。（ 一个免费，其余的跟随）：固定一组A的参与者，并假设A中的每个参与者都合作。如果存在具有零抵押品（ci =0）的参与者i g A，对于其他参与者的任何行动简档，Aci，那么如果参与人A i合作，其他参与人都有严格的最佳对策来合作，即使是零抵押品。命题2表明，当抵押品矩阵诱导完全投资作为唯一均衡时，诱导博弈中至少存在一个导致该均衡的劣势策略的迭代消除顺序。下面的命题在相反的方向上起作用：对于星图中参与者的任何可能的顺序，它提供了一个构造最小和附带向量的方法，使得这个顺序将是劣势策略的迭代消除顺序。 它通过给每个参与者最小数额的抵押品来诱导她合作，假设在她之前的所有参与者都合作，而其他所有人都背叛。建议我在4号线。（minimum collarisons）：设n是n的所有排列的集合。对于每一个σn，存在唯一的最小侧向量，使得σ1，σ2，.，σn是严格劣势策略的迭代淘汰的参与人的阶，对于每一个i ∈ [n]，抵押品t。哦，伙计。rσi是证据在附录B中。证明的想法是，（5）是从命题4得到的，条件是在劣势策略的迭代淘汰顺序σ中，A中的参与人首先出现（以任意顺序），然后是B中的参与人，按其指数的递增顺序排列。 然后证明，只要这个条件不成立，我们总是可以减少所有抵押品的总和，在弱意义上，通过对任何一对具有部分抵押品的连续参与者按迭代消除的顺序排序，使得具有最小指数（因此具有较大或相等的投资金额）的参与者排在第一位。该定理的一个简单推论是，部分抵押品在投资是单调的，无论是在其绝对规模上还是在每个人的投资百分比上CorollA ry 1. 对于在单个企业抵押品最小化问题的最优解中有部分抵押品的两个参与者a，b，如果xa>xb，则ca>cb且ca/xa>cb/xb。定理1表明，抵押品最小化问题可以简化为选择将获得全部抵押品的参与者的子集：由于存在最优解，其中某个参与者集合A具有全部抵押品，并且其他抵押品由等式（5）给出，因此只需搜索集合A。这在下面的推论中被形式化。Coroll A ry 2. 对于具有d个参与者的单个企业抵押品最小化问题，可以通过以下步骤在2dd时间内求解：对于参与者的每个子集S，构造一个排序σ S，其中S中的参与者是前缀（任意排序），前缀Sc之后的其他参与者按一个顺序排序投资额的非递增顺序;然后，设置顺序σ（S）的抵押品，其中全部抵押品为S，抵押品为ScZcσ=xσ85.Σ{∈}∈（）∈（）下一页{ X Z A}O（）n，{xi}n∈ H（）i多企业投资网络中的最佳合作WWW通过定理1，得到c（S）的总抵押。最后，选择一个集合S的最小总c（S）的解。根据这种直觉，我们证明了单个企业问题是NP难的（详见全文）。定理2. （硬度）：单个企业抵押品微型化，我在8号线找到了。（星分解）：设G=（V，E）是一个有向图，记为Ve=vV：uVs. t. v，u E G中出度非零的顶点子集。G的星分解，记为H（G），定义为G的子图族，使得每个子图都包含一个顶点c∈V e和它的所有邻点{v∈V：（c，v）∈E}以及连接c和它们的边{（c，v）∈E}.整数输入的最小化问题i=1是NP难的 ，Z，α5投资网络在上一节中，我们研究了结构非常简单的投资网络：只有一个企业和n个投资者的星形图。接下来，我们回到任意定向投资网络的一般模型。 在这种情况下，如第2节所述，如果代理人的企业违约（投资的资本不足以支付运营成本），代理人撤回所有投资，零回收，基本上不对任何企业进行投资。 单一企业设置与多个企业的投资网络设置之间的关键区别在于违约级联的风险。例如，如果公司A是公司B的企业的潜在投资者，而A违约，那么A不会投资于企业B，不管A对这一投资的动机如何。这反过来又可能导致企业B违约，在这种情况下，B不能投资于任何企业。在本节中，我们将给出网络模型的几个结果我们首先表明，在一个有向无环图（DAG）的最优抵押品解决方案，足以诱导一个独特的纳什均衡在每个企业，忽略违约级联的风险，实际上是足以诱导一个独特的纳什均衡在整个网络中，即使违约触发投资失败。事实上，这些为每个输入计算的局部最优解三倍的投资。 图2和图3是图及其星分解的示例。 星型分解自然会产生一组单企业抵押品最小化问题，每个子图（具有相应的参数）一个。为了研究投资网络的拓扑结构对最优抵押方案解的影响，我们定义存在可行抵押矩阵的网络的网络超额抵押（NEC）为网络中最优抵押品之和与其星分解中最优抵押品之和的比值。显然，当每个星型子图是网络的一部分时，稳定每个星型子图的成本只能略高于当它不连接到网络时稳定同一个星型图的成本。NEC量化了在唯一均衡中稳定网络的成本中的系统性战略风险成分，或克服违约级联风险所需的超额抵押品对于并行最小化问题P= n，如果Hi是G的一个子图，我们用PHi表示由PG在Hi上导出的并行极小化问题.对于任何具有投资图K的问题PK当存在最优解时，PK为最优解，否则CK=∞。价格分别在网络中产生全局最优解因此，我们得出结论，对于DAG，没有网络过剩Colombian我在9号。 考虑并行最小化问题PG =（NEC），也就是说，由于潜在的违约级联导致的系统性风险，不需要额外的抵押品。作为{n，X，Z，A}，图G =（V，E）。 设H（G）为星分解，G. PG的网络超额Cold（NEC）定义为：这个结果的一个推论，我们得到，如果有可能解决抵押品最小化问题，我们还可以NEC（P G）=.CGHi∈H（G）CHi解决由这些企业构建的DAG的问题特别地，在任意一个企业最多有d个潜在投资者的DAG中，我们可以在时间2ddn上求解问题。然后，我们考虑一般的有向图（可能有圈），并提出两个否定的结果。首先，我们表明，违约级联不能再被忽略，它们可能意味着一个巨大的增加，在总抵押品需要诱导一个独特的均衡（即使存在）-增加可以是任意大（NEC是无界的），这甚至适用于网络与常数代理人。最后，我们表明，周期也意味着计算的硬度，即使每一个孤立的企业问题可以解决。具体来说，我们表明，这个问题是NP-困难的一般图，即使访问一个甲骨文，可以解决任何单一的企业问题。5.1预赛我们首先定义了投资网络的星型分解的概念。这个概念对于在并行最小化问题中比较局部效应和网络效应是有用的。注意，由于任何HiG是一个星图，CH总是有限的，因此分母总是有限的。5.2有向无环图我们首先考虑非循环的投资图我们的主要结果是，最优抵押品的非循环网络的投资可以通过解决每个企业的星分解的投资图，分别获得，忽略了事实，它是一个网络的一部分在忽略违约级联的可能性证明的主要观点是，我们实际上可以找到一个排除劣势策略的顺序，这将确保当代理人考虑投资时，她确信没有违约会伤害她，即使是通过级联。从本质上讲，在每个DAG中，都有一个没有投资者的企业顶点，这些投资者本身就是企业顶点。因此，我们可以认为，我们可以把这个企业顶点和它的投资者放在劣势策略消除顺序的第一位（顺序和抵押品根据这个企业作为一个独立企业的最优解）。任何后来的探员都知道注意，在我们的星分解的定义中，如果考虑多个子图，则同一个顶点可能出现在多个星子图.86（）下一页O（）O（）O（）{ X Z A}DAG，它认为CG=Hi∈H（G）CHi，所以NEC（PG）= 1.WWW图2：左：DAG。数字显示了拓扑顺序。顶点1、2、3是企业顶点。右：图的星形分解。拓扑序诱导了星子图的序。在参与者的劣势策略的迭代消除中（每个决策对应于一条边），在顺序上更高的星形子图的边首先被消除大写字母显示了这种迭代消除顺序的一个例子。迭代从拓扑顺序中的星图编号3的边开始，这些边由该星图问题的解排序一旦星图3在唯一均衡中得到保证，星图2就可以作为一个独立的问题来求解，而没有星图3的违约风险，并且该过程沿着由拓扑序诱导的星图的顺序继续第一家企业不会违约，因此我们可以在网络的其余部分上递归地继续，而不用担心这些违约企业会引发违约级联。有关该过程的说明，请参见图2证据推迟到附录C。定理3. （DAG中的最优侧边）：考虑具有图G =（V，E）的侧边最小化问题PG={n，X，Z，A}。 设H（G）={Hi}i ∈Ve是G的星分解，其中Ve是企业顶点集. 若G是无圈的，则通过分别求解H（G）中每个子图的并行极小化问题，可以得到并行极小化问题PG的解. 因此，对于任意问题PG，其图G是图3：左：循环图;右：星分解。甚至对于所有共享相同的投资图G的问题也成立，其中只有一个循环，只有3个企业顶点和常数数量的顶点（n= 1）。|V|=9）。参见附录C中的证明。证明使用图3中描述的结构。 该图显示了一个投资机会的周期，其中每个周期顶点在其自己的企业中