金融网络中的战略支付

因此，我们的构造不需要多条边，并且表示不会产生开销。附录A.1给出了以下定理的证明。定理9。对于硬币排名游戏的给定策略文件f，决定给定的FIMV是否具有导致资产至少为k的最佳响应是强NP完全的。这甚至可以在没有外部资产和所有边权重为{0，1}的情况下进行incoin排名游戏。3.3均衡的总收入在本节中，我们分析了纯纳什均衡和str-on-g均衡的总收入。我们将该价值与社会最优值相关联，即最佳战略文件中所有公司的资产总额。显然，由于我们证明了系统最优强均衡的存在性，纳什均衡和强均衡的稳定性代价都是1。我们为纳什均衡和斯特龙均衡确定了无政府状态的代价。附录A.2给出了下一个提案的标题。提案10。纳什均衡的无政府状态代价是无限的，甚至是没有外部资产的硬币排名游戏。总收入主要取决于战略文件中周期的出现。这需要一种内在的联盟效应，因此，通常纳什均衡无法提供良好的收入保证，这可能并不奇怪。为了分析强均衡的性质，我们再次考虑了单位权重多边形式的硬币排名博弈。考虑最佳循环f*流通网络G′的最大总收入。由于我们有单位权重边，我们可以假设最优循环在每条边上都有二元流。让C（f*) = {C，…，Ck}是f的分解*进入单位流量循环。我们表示byd=minf*,C（f*)最大值C∈C（f*)|Ci |任何分解C（f）中任何循环的最小-最大大小*) 任何最佳循环f*.定理11。在硬币排名游戏中，强大的价格是无政府状态最多是d证明。

考虑最佳循环f*和分解C（f*) 所有流动周期Ci的此类th∈C（f*) 最大尺寸为| Ci |≤ d、 总收入（单位：f）*由EV（f）给出*) =XCi公司∈C（f*)|Ci |-十五∈Vaxv因为流通量也占了辅助来源s的资产。现在考虑在与清算状态a的硬币排名游戏中的强平衡π。它会在网络中产生一个二进制货币流。假设有一个循环Ci∈ C（f*) 对于alle=（u，v），fe（^au）=0时的th∈ Ci。然后，这一周期中的企业有动机共同偏离并将首席信息官的优势放在其排名的第一位。然后，清除状态^a将像以前一样出现，沿循环Ci增加1的流量。这是Ci公司的可证明偏差。因此，始终y周期Ci∈ C（f*) e必须至少在e边上e=（u，v）∈ Cisuchthe fe（au）=1。因此，强平衡下的收入πisRev（π，^a）≥XCi公司∈C（f*)而且这个比率最多是d.VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV- 1 = 4.提案12。每d≥ 2、存在以d的无政府状态为代价的货币排名游戏- 1.证明。游戏由一个带d+（d）的图给出- 1） （d）- 2） 企业。G的结构如下。公司v，VD被称为中心企业，它们形成一个长度为d的循环。对于每个i=1，d- 1，有企业（vi，j）j=1，。。。，d-2与边缘（vi，vi+1）形成长度d的附加循环。因此，边集被赋予byE={（vi，vi+1）| i∈ {1，…，d- 1}} ∪ {（vd，v）}∪[i=2，…，d（六、六）∪ {（vji，vj+1i）| j=1，…，d- 3} ∪ （vd+2i，vi-1).所有边都具有非it权重。图1中描绘了d＝5的实例的示例。仅观察表vi，i=2，d有多个输出边。我们声称πi=（六，六+1），（六，六）和πd=（vd，v），（vd，vd）是一个stron g平衡。

为了证明这一点，设^a为π对应的清除状态。清除状态由^av=（1，如果v=v，v，…，vd，0，否则，即Rev（π，^a）=d给出。现在，假设存在玩家的非emp-ty联盟 （v，…，vd）所有人都严格按照共同偏离的方式减少资产。请注意，vd只有一个单一的传入边，因此vd/∈ S、 因此，循环vd，vd，vd公司-2d、vd-1不能携带任何气流。我们得出结论，vd-1只有一条边缘可以承载水流。重复此参数会产生S=, 矛盾。然而，最佳流量出现在πi=（六，六），（六，六+1）和πd=（vd，vd），（vd，v）. 很容易观察到，这产生了（d）的总收入- 1） 因此，在这种情况下，无政府状态的强大代价是- 1.4边缘排名博弈4.1均衡的存在与计算通过硬币排名策略，我们假设企业在分配单个资产单元时具有灵活性。在本节中，我们将重点讨论一类更受限制的策略，即企业模拟其外向优势，并按照这种排名的顺序分配资产，直到他们耗尽所有VVVVVVvFigure 2的资产：一个没有纯纳什均衡的优势排名博弈。债务得到偿还。与硬币排名游戏不同，对边缘排名的限制（不同权重）会破坏（最优）稳定状态的存在。事实上，甚至有没有一个纯纳什均衡的博弈。提案13。有一个没有纯纳什均衡的边缘排名博弈。证据考虑图2中的游戏。边的容量在边的旁边显示。公司和veach的外部资产为2，其他公司的外部资产为0。公司v、vandvare是唯一一家具有多个传出边缘的es公司。其他公司的战略方针已确定。由于网络的对称性，我们可以假设w.l.o.g.πv=（（v，v），（v，v））。

vand v的每个节点都有两种可能的战略选择。检查所有四种结果的战略结果会得出vand v公司的效用矩阵。检查效用，我们发现不存在纯纳什均衡。πvπv（（v，v），（v，v））（（v，v），（v，v））4（（v，v），（v，v））4 4（（v，v），（v，v））3下一个定理表明，边缘游戏中的许多自然决策和优化问题确实在计算上很难解决。请注意，对于硬币排名游戏，这些问题要么微不足道（强均衡总是存在），要么可以在多项式时间内解决（强均衡也代表总收入最大的文件，可以在强多项式时间内计算）。下列定理的证明推迟到附录A.3。定理14。给定一个边排名博弈，以下问题是强NP难问题：1。决定是否存在纯纳什均衡。2、判断是否存在强均衡。3、计算一个保证存在的纯纳什均衡。计算一个强平衡，当它保证存在时。5、计算总收入最大的战略文件。备注15。目前尚不清楚在边缘排名游戏中决定纯纳什均衡是否存在的问题是否在NP中，因为NP难以验证一家公司是否发挥了最佳反应（见定理9）。很容易看出决策问题在∑p中。该问题可以是∑p-完全的，类似于str-ategic-max-flow游戏中的相关决策问题【18，23】。证明这样的结果是一个有趣的公开问题。VVVVVVV WWWMMM-2图3：具有无约束稳定价格的边缘排名游戏。4.2均衡的总收入对于边缘排名游戏，硬币排名游戏观察到的无政府状态价格的下限适用，即无政府状态的价格可以是u-nbund ed。

即使存在最佳均衡，对边缘排名策略的限制也会对其质量产生影响。特别是在边缘排名游戏中，稳定性的强概率可以高达Ohm（n） 稳定的代价甚至可能是无限的。提案16。对于每一个ε>0，存在一个稳定价格至少为n/2的边缘排名博弈- ε.证据我们考虑对命题12中的实例进行轻微修改。与命题12的证明中描述的实例不同，边（v，vn），（vn，v），（v，v）的权重为M+1，所有其他边的权重为M。唯一具有多条移动边的节点仍然是v。如果πv=（（v，vn），（v，v）），则玩家v获得M+1的资产，这是最优的。π的总收入为200万+2。π是唯一的纳什均衡和唯一的强均衡。相反，对于π′v=（（v，v），（v，vn））的π′文件，公司的收入仅为M，但总收入为nM。因此，稳定性的强大代价是nM/（2M+2）=n/2- n/（2M+2），至少为n/2- ε表示M≥ n/（2ε）- 1、提案17。这是一个具有无限稳定代价的边缘排名游戏。证据考虑图3中的博弈，它使用了图2中没有纯均衡的博弈。我们增加了三家公司。外部资产等于2，而非外部资产。这些公司有一个边（w，w）和（w，w）的循环C，权重为M>> 1，以及带权重m的边（w，w）- 此外，还有权重2的边（w，v）和（w，v）。在最佳循环中，wand wprioritize the Edge of C，导致总收入为Θ（M）。相反，只有当w-fi公司确保外部资产为v时，纯纳什均衡才能发展，在这种情况下，纳什均衡可以存在（如上文第14条的证明所示）。很明显，这两个魔杖都有动机偏离C。

因此，如果其中一个将边缘放置到vin等级，而另一个未放置，则单边偏差将关闭C，从而使v节点不稳定。然而，如果wand-wplaystrategiesπw=（（w，v），（w，w））和dπw=（（w，v），（w，w）），则没有任何非平行偏差会导致沿C流动。在这种情况下，会形成纯纳什均衡。显然，这种均衡状态下的总收入最多是一个常数。因此，稳定的代价是Ohm（M） 。5结论在本文中，我们研究了金融网络的清算机制，并从计算和博弈论的角度分析了其性质。我们的主要结果表明，在这些博弈中，有偿付能力的企业没有战略激励，即博弈只在破产企业之间进行。如果企业使用硬币排名策略，则网络中所有资产总和最大化的每一个社会优化都构成了一个强大的均衡。此外，它可以在强多项式时间内进行计算。这一结果表明，集中破产解决方案可以实现一个清算状态，在这个状态下，社会福利最大化，没有企业联盟受到激励而偏离。相反，当考虑非集中清算和任意强均衡时，社会福利取决于社会最优货币流通周期的长度。对于纯纳什均衡，由于企业之间缺乏协调，社会福利的恶化可能是严重的。或者，当将策略空间限制为边缘排名策略时，我们发现纯纳什均衡和强均衡可能不存在，难以计算，并且在社会福利方面非常不受欢迎。我们的工作中出现了许多悬而未决的问题。例如，现实生活中的市场涉及大量复杂的金融产品（如衍生品、信用违约掉期等）。

它们对金融市场稳定性和计算复杂性的影响才刚刚开始吸引文献的关注。在这种情况下，有许多重要的博弈论方面，涉及定价、信息披露或网络创建，这些方面对于理解金融市场至关重要，并代表了未来工作的有趣途径。感谢Pascal Lenzner和Ste ffen Schuldenzucker对本文结果进行了宝贵的讨论和反馈。参考文献【1】Daron Acemoglu、Asuman Ozdaglar和Alireza Tahbaz Salehi。内生金融网络中的系统性风险。SSRN提供：https://ssrn.com/abstract=2553900，2015年1月22日。哥伦比亚商学院研究论文第15-17号。[2] Nizar Allouch和Maya Jalloul。金融网络中的战略违约。肯特大学经济学院技术报告，2017年。经济学研究1721年。[3] Sanjeev Arora、Boaz Barak、Markus Brunnermeier和Rong Ge。金融产品的计算复杂性和信息不对称。通信ACM，54（5）：101–107，2011年。[4] Yoram Bachrach和Je ffrey Rosenschein。阈值网络流量游戏中的电源。自动。Agent和多Agent系统。，18(1):106–132, 2009.[5] 保罗·巴鲁卡、马尔科·巴多西亚、法比奥·卡奇奥利、马尔科·德里科、加布里埃尔·维森丁、斯特凡诺·巴蒂斯顿和圭多·卡尔达雷利。金融系统网络估值，2016年。[6] Mark Braverman和Kanika Pasricha。复合期权定价的计算难度。过程中。第5次研讨会。因诺夫。Theoret。计算机。Sci。（ITCS），第103-104页，2014年。[7] Rodrigo Cifuntes、Gianluigi Ferrucci和Hyun Song Shin。流动性风险和传染。英格兰银行，第264号工作文件，2005年。[8] Rama Cont和Eric Schaanning。间接传染和系统性压力测试。

atSSRN可用：https://ssrn.com/abstract=2541114，2017年6月13日。[9] Agnes Cseh、Jannik Matuschke和Martin Skutella。随时间稳定的水流。算法，6（3）：532–5452013。[10] 邓晓铁、茨城东芝和长垣弘。算法方面的核心组合优化游戏。数学操作。第24（3）号决议：751–7661999年。[11] Pradeep Dubey和Lloyd Shapley。由受控编程问题产生的完全平衡的游戏。数学掠夺。，29(3):245–267, 1984.[12] Larry Eisenber g和Thomas Noe。金融系统中的系统性风险。管理。Sc i.，47（2）：236–2492001。[13] 玛丽亚姆·法布迪。调解和自愿承担对方风险。atSSRN可用：https://ssrn.com/abstract=2535900，2014年8月1日。[14] 汤姆·菲舍尔。系统性风险下的无套利定价：交叉所有权会计。数学《金融》，24（1）：97–124，2014年。[15] 塔姆·阿斯·弗莱纳。在稳定的匹配和流上。算法，7（1）：2014年1月14日。[16] Prasanna Gai和Sujit Kapadia。金融网络中的传染。P roc。皇家Soc。伦敦A：数学。物理。工程科学。，466(2120):2401–2423, 2010.[17] 丹尼尔·格拉诺和弗里达·格拉诺。在一些网络流量游戏上。数学操作。第17（4）号决议：792–8411992年。[18] Shibashis Guha、Orna Kupferman和Gal Vardi。多人FLOW游戏。过程中。第17形态自动。Agent和多Agent系统。（AAMA S），第104–112页，2018年。[19] Brett Hemenway和Sanjeev Khanna。金融网络的敏感性和计算复杂性。算法金融，5（3-4）：95–1102016。[20] Ehud Kalai和Eitan Zemel。产生完全平衡对策的广义网络问题。操作。第30（5）号决议：998–10081982年。[21]Ehud K alai和Eitan Zemel。完全平衡的游戏和流动游戏。数学操作。第7（3）号决议：476-4781982年。[22]理查德·卡普。组合问题之间的可约性。在R.E.Miller和J.W.Thatcher的《编辑》中，计算机计算的复杂性。

全会出版社，纽约，1972年。【23】奥尔纳·库普费尔曼、加尔·瓦迪和莫斯·瓦迪。流游戏。过程中。找到第37个形态。SoftwareTech。理论。计算机。Sci。（FSTTCS），第38:38–38:16页，2017年。【24】伊万杰洛斯·马卡基斯和阿明·萨贝里。在多物品FLOW游戏的核心。十进制。支持系统。，39(1):3–10, 2005.[25]Christos Papadimitriou。算法、游戏和互联网。在过程中。第33届研讨会。理论计算。（STOC），第749–7532001页。[26]L.C.G.罗杰斯和L.A.M.维拉特。银行间网络的故障与救援。管理。Sc i.，59（4）：882–8982013年。【27】斯特芬·舒尔登祖克、斯文·塞肯和斯特凡诺·巴蒂斯顿。使用信用违约掉期在金融网络中查找清算付款已完成PPAD。过程中。第8次研讨会。Innov公司。Theoret。计算机。Sci。（ITCS），第32:1–32:20页，2017年。【28】劳埃德·夏普利和赫伯特·围巾。关于核心和不可分割性。J、 数学。E con。，1(1):23–37, 1974.【29】铃木泰鲁。评估公司债务：股票和债务交叉持有的影响。J、 操作。Soc决议。日本，2002年2月。[30]'伊娃塔多斯。一种强多项式最小费用循环算法。Combinatica，5（3）：247–256，1985年。缺少证据A。1定理9vxi，1,0zi，0zi，1xi，1,1xi，2,0xi，2,1xi，3,0xi，3,1xi，4,0xi，4,1zi（a）变量小工具VCCCCX1,1,1x2,1,1x3,1,0x1,2,1x2,2,0x4,2,1x3,1x4,4,1x5,4,1（b）网络结构示例图4：定理证明中使用的结构9。对于具有恒定边权和外部资产的硬币排名博弈，决策问题同样包含在NP中。我们可以用单位权重多边表示网络，将Everysttrategy表示为边上的排名。这种转换需要花费大量的时间。然后，我们计算^a的算法在多项式时间内运行。对于强NP-硬度，我们给出了具有n个变量和d m子句的合取范式的可满足性的任何实例I。

我们构造了一个边缘排名表示的硬币排名游戏，其中有一个玩家v和一个策略文件π-vfor the other player s，so the following hold：有一个策略πvwith assets av≥ k=k′+n in（πv，π-v） 当且仅当我有一个变量分配，至少填充k′子句。我们将博弈构造为如下s。我们用x表示I的变量，X和byC条款，厘米对于每个变量xi，我们为所有j创建xi、j、0和xi、j、1表格∈ {1，…，m}，以及一个固定的zi。对于每一条cj，我们添加一条正式cj。此外，还有一家全球公司v、f，我们力求找到最佳的回应。对于每个条款Cj，如果xi在Cj中出现，我们将单位重量边缘从xi，j，0添加到Cj，如果xi在Cj中出现，我们将单位重量边缘从xi，j，1添加到Cj。传入Cj的流最终将指示一个文字，该文字将填充Cj子句。所有j都有一条边（cj，v）∈ {1，…，m}。我们将在下面说明，thisedge确保满足条款CJ的要求，为av添加了一个资产单位。对于每个变量xi，我们设计了一个变量gadget。它由节点v、xi、j、0和xi、j、1组成，用于所有j∈ {1，…，m}，以及辅助节点zi，zi，0和zi，1。所有j都有单位权重边（v，xi，j，0）和（v，xi，j，1）∈ {1，…，m}，ed ges（xi，j，0，xi，j+1,0），（xi，j，1，xi，j+1,1）表示j∈ {1，…，m-1} ，以及边（v，zi，0），（zi，0，xi，1,0）和（v，zi，1），（zi，1，xi，1,1）。坚固的zi有边（xi，m，0，zi），（xi，m，1，zi）和（zi，v）。图4a中描绘了为变量xind m＝4构造的小工具的示例。请注意，对于v的每个策略，这个小工具中最多出现一个循环，因为所有循环mus都不包括zi的传出边缘。在图4b中，我们展示了一个网络示例，其中包含用于满足性实例I=（x）的可变小工具∨ x个∨ §x）∧ （十）∨ §x∨ x）∧ （x-x）∧ （十）∨ §x∨ x个∨ x） 。我们构建了一个战略文件π-vas紧随其后。