多人（对称）纳什均衡R-完备性：决策问题的新研究成果

ACM Transactions on Economics and Computation，卷。号61.第1条。出版日期：2018年1月∃∃∃∃∃∃∞多人（对称）Nash均衡R-完备性Jugal GARG和Ruta Mehta，伊利诺伊大学香槟分校维贾伊五世Vazirani和SAGARYAZDANBOD，佐治亚理工学院作为一系列重要工作的结果[7-现在已经很好地理解了，即使当需要具有特殊性质的均衡时，当博弈是对称的时。然而，对于多人博弈，当需要具有特殊性质的均衡时，唯一已知的结果是由于Schaefer和Štefankovi [28]：检查一个三人纳什均衡（3-Nash）实例是否在半径为l-范数的一半的球中具有均衡是R-完全的，其中R是一类决策问题，可以在多项式时间内归结为实数的势理论。在他们的工作的基础上，我们证明了3-纳什的以下决策版本也是R-完全的：检查是否（i）有两个或更多的均衡，（ii）存在一个均衡，其中每个玩家至少得到h个回报，其中h是一个有理数，（iii）一组给定的策略是以非零概率进行的，以及（iv）所有的策略都属于一个给定的集合。接下来，我们给出了从3-Nash到对称3-Nash的约化，从而解决了Papadim- itriou [25]的一个公开问题这产生了上述最后两个问题的对称3-纳什的R-完备性，以及FIXP a类的完备性，FIXP a是强逼近的变体。我们的所有结果扩展到k-Nash，对任意常数k≥3。CCS概念：·计算理论→平衡的精确和近似计算;附加关键词和短语：纳什均衡，对称博弈，决策问题，实数存在论，FIXPACM参考格式：放大图片作者：Jugal Garg，Ruta Mehta，Vijay V.瓦齐拉尼和萨德拉·亚兹丹博德2018年多玩家（对称）纳什均衡决策版本的R-完备性 ACM Trans. 经济Comput. 6，1，第1条（2018年1月），23页。https://doi.org/10.1145/31754941介绍纳什均衡（NE）可以说是博弈论中最重要和研究最充分的解决方案概念，理解其复杂性导致了一个令人印象深刻的理论，该理论在过去十年中大部分被发现我们用k-Nash表示在一个这项工作的扩展摘要出现在第42届自动机、语言和编程国际研讨会（ICALP）的会议记录中。这项工作得到了NSF Grants CCF-0914732和CCF-1216019的支持作者地址：美国伊利诺伊大学香槟分校工业与企业系统工程系; Mehta，计算机科学系，伊利诺伊大学厄巴纳-香槟分校，厄巴纳IL 61801，美国;诉Vazirani和S.Yazdanbod，计算学院，佐治亚理工学院，亚特兰大GA.30332美国;电子邮件：{jugal，rutameht}@illinois.edu，{vazirani，yazdanbod}@ cc.gatech.edu。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。本作品的版权归ACM以外的其他人所有，必须予以尊重。允许使用学分进行摘要。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2018 ACM 2167-8375/2018/01-ART1 $15.00https://doi.org/10.1145/31754941ACM Transactions on Economics and Computation，卷。号61.第1条。出版日期：2018年1月一曰：J. Garg等人≥∃∃≥∃n≥{−}∃∃k-玩家博弈中的常数k。对于2-Nash问题，Daskalakis，Goldberg和Papadimitriou [9]以及Chen，Deng和Teng [7]的开创性结果这就引出了另一个基本问题：找到一个满足特殊性质的k每个参与人的收益至少是h对于两个参与者的情况，这些问题首先由Gilboa和Zemel针对非对称博弈进行了研究[15]后来由Conitzer和Sandholm为对称游戏[8]。这两篇文章都考虑了2-纳什在许多特殊性质下的问题，并证明它们都是NP完全的。最近，毕尔巴鄂和马夫罗尼科拉斯[3]将吉尔伯亚和泽梅尔的结果扩展到所有收益都是0或1的输赢博弈。因此，两个玩家案例的复杂性是很好理解的。虽然两个玩家的情况下是最经典的和充分研究的情况下，它也是重要的研究的多个玩家的情况下，特别是在互联网和其他大型网络上出现的新的应用程序的背景下，多个玩家被锁定在战略局势的复杂性事实上，在这方面已经开展了许多活动，例如，参见参考文献[2，17，26]，但图像不像两个玩家的情况那样清晰对于k3，2-Nash和k-Nash之间的一个根本区别是，前者总是允许可以用有理数来写的均衡[18]，后者通常需要无理数，正如纳什自己所示[22]（我们将假设给定实例中的所有数字都是有理数）。很容易看出，在后一种情况下，均衡是代数数。这种差异使得多人游戏更加困难。Daskalakis，Goldberg和Papadimitriou [9]证明了对于k-玩家博弈，k3，找到n-近似纳什均衡是PPAD-完全的。Etessami和Yannakakis [11]解决了精确均衡的复杂性，他们证明了这种情况对于他们的类FIXP是完全的。找到一个满足特殊性质的k-纳什解的复杂性又如何呢由于处理无理数的固有困难，这个问题一直悬而未决，直到2011年，Schaefer和Štefankovi[28]正式定义了类R，并表明检查如果一个三人博弈有一个NE，其中每一个策略的概率都不超过0。5（InBox）是R-完全的。 R是以+，=，，>为基的存在量化公式的“是”实例的类< 我们注意到，这个类是非正式的，[28]前有《明史》，后有《明史》。参见参考文献[6]。在参考文献[10]中，Datta证明了任意半代数集可以编码为三人博弈的完全混合然而，约简不是多项式时间的，因此不适用于证明3-Nash决策问题的R-完全性。最近，在参考文献[19]中，Levy给出了另一种构造，以精确地捕获一个博弈的混合策略的任何紧致半代数集，作为另一个具有额外二元参与者的博弈的纳什均衡策略的投影;然而，没有提供额外参与者的数量。我们的第一组结果将R-完全性扩展到NE计算，并在3人游戏中具有一些特殊性质：（i）检查游戏是否有多个NE（NonUnique）。其中，（ii）每个玩家至少获得h个收益（MaxPayoff），（iii）一组给定的策略以正概率进行（Subset），或（iv）所有策略都属于给定的集合（Superset）。我们的第二组结果涉及对称博弈。对称性在许多战略情况下自然出现，并且随着互联网的发展，用户通常是无法区分的，这样的情况只会变得越来越普遍。在对称博弈中，所有参与者都在相同的情况下参与，即，策略集和收益因此，参与人i只取决于她所采取的策略s和其他人所采取的策略的多集S，而不涉及他们的身份。此外，如果任何其他参与人j和其他参与人S都选择S，j的收益将与i相同。对称纳什均衡（SNE）是一个所有参与者都采取相同策略的均衡纳什[22]在为博弈论提供中心解概念的同时，还定义了对称博弈的概念，并在一个单独的定理中证明了这种博弈总是允许对称均衡。多人Nash均衡的完全性一曰：ACM Transactions on Economics and Computation，卷。号61.第1条。出版日期：2018年1月≥∃∃∃∃CP× ×× ×表1.NE的二分法2-纳什均衡k-Nash，k≥3溶液性质理性的[18][22]第二十二话复杂性PPAD-完成[7，9，23][11]第十一话实用算法Lemke-Howson [18]？决策问题NP完全[8，15][28]第二十八话CP（定理4.20，4.26）表2.对称NE对称2-Nash对称k-Nash，k≥3溶液性质理性的[18]代数;无理数例子CP与[22]复杂性PPAD-完成[7，9，23]FIXPa-完全：CP（定理7.4）实用算法Lemke-Howson [18，27]？决策问题NP-complete [8]CR-完全：CP（定理7.2）一个简单的约简是已知的从2-纳什对称2-纳什，它表明，后者也是PPAD-完全的。Gilboa和Zemel [15]研究的两人博弈问题由Conitzer和Sandholm [8]研究对称博弈，并被证明是NP完全的。另一方面，从3-Nash到对称3-Nash没有已知的约化。事实上，在给出了从2-纳什到对称2-纳什的简化之后，Papadimitriou [25]指出，为了得到对称k-局中人对策的结果，对于k =3，我们首先给出了从3-Nash到对称3-Nash的一个约化，从而解决了文献[25]中的公开问题.这也使我们能够证明，对称3-纳什是完整的类FIXP，强逼近FIXP，这是一个变种的FIXP，仅限于与有理数它还产生R-完备性的超集和子集在这样的游戏。一旦三个玩家的情况是解决，我们证明类似的结果对称k-玩家游戏，k>3。参考文献[14]给出了NE的二分法，显示了2-Nash和k-Nash之间沿着三个不同标准的定性差异;参见表1。本文的结果增加了第四个标准，即决策问题的复杂性。此外，我们得到对称NE的类似二分法;见表2。当前文章的结果在表中表示。我们注意到，本文的结果首先在参考文献[13]中提出。在那篇文章中，我们留下了将R-完备性结果扩展到其他3-纳什和对称3-纳什问题的决策版本的开放问题。自那时以来，在这个悬而未决的问题上取得了很大进展。首先，Bilbery和Mavronicolas [4]证明了Gilboa和Zemel [15]研究的所有问题的三人版本都是R-完全的;而且，他们通过一个统一的减少Inbox。接下来，相同的作者[5]证明了对称3-纳什的几个决策版本的R-完备性，这次是通过子集的约简。1.1技术概述我们首先给出我们从3-Nash到对称3-Nash的简化背后的主要思想（定理5.5）。我们将把给定的博弈（A，B，C），其中每个张量的大小为m n p，简化为大小为l l l的对称博弈D，其中l=m+n+p（关于（对称）博弈的描述，见2.1节）。在这个博弈中，在每个对称NE下，每个参与者的策略可以分解为一曰：J. Garg等人ACM Transactions on Economics and Computation，卷。号61.第1条。出版日期：2018年1月.∃...∃∃∃××≤× ×× ×...∃∈|−|∞≤三个向量，比如分别为m、n、p维的x、y、z。恢复原始博弈（A，B，C）的纳什均衡的一个必要条件是这三个向量中的每一个都不为零;这也是约简中最困难的部分。为了实现这一点，我们构造了一个3 3 3对称博弈G，它的所有对称NE都是完全支持的，即使它只是部分指定的（见等式（6））。 我们“吹”G得到D，它的大小为lLl，G的未指定项创建了张量A，B，C的空间，“插入”现在，如果（x，y，z）是D的对称NE，那么G的（ixi，jyj，kzk）也是.因此，每个向量x，y，z都是0。接下来，我们证明了如果这些向量被缩放为概率向量，则它们形成（A，B，C）的NE。额外的参数产生子集和超集的R-完全性，对称k-Nash（定理5.6和5.7）。接下来，我们给出了证明类FIXPa的对称3-Nash是完备的想法（定理6.4）。注意，我们无法证明对称3-Nash对于类FIXP本身是完备的，因为我们在FIXPa下，给定一个实例I和一个有理数ε>0，我们需要计算一个向量x，在与某个解的（相加）距离内，即， X轴Sol（I）使得x≠X在时间多项式的大小[I]和log（ 1/1）。在上述约简中，获得（A，B，C）的解包括，例如，x除以ixi。如果后者非常小，那么这可能会给我们一个非常远离（A，B，C）的解的向量，即使x可能接近D的解。我们通过对上述约简进行一个小的改变来解决这个问题，即，我们需要将张量A，B，C乘以一个小常数J，然后将它们这确保了向量（ix i，jy j，kzk）近似为 （1/ 3， 1/ 3， 1/3）。因此，给定一个接近D的解的点，我们可以得到一个“接近”（A，B，C）的解的点接下来，我们描述如何证明上一节提到的四个k-纳什决策问题的R-完备性。为了显示三个玩家的情况下的硬度，我们将InBox（已知对于3-Nash是R-完全的）减少到MaxPayoff，Subset和Superset中的每一个，然后从MaxPayoff到NonUnique。k-纳什的硬度，k>3，如下，因为3-纳什通过引入虚拟参与人简化为k-纳什均衡。为了证明R中的包容性，我们给出了一个非线性互补问题（NCP）公式，它精确地捕获了给定游戏的NE（定理3.1和3.2）。接下来，我们简要解释两个玩家情况下从InBox到MaxPayoff的减少（请参见第4.1节的细节）;三人的情况是它的扩展（第4.2节）。假设给定的博弈由两个大小为m的支付矩阵（A，B）表示n，每个玩家一个。InBox问题是检查它是否有一个NE，其中所有策略都最多为0。5概率。我们将其简化为检查另一个游戏（C，D）是否有一个NE，其中每个玩家都获得至少h>0（MaxPayoff）的收益。不失一般性（wlog），我们可以假设A，B>0。我们构造m（n+1）n（m+ 1）个矩阵C和D，其中左上方的块分别设置为A+h和B+h。这确保了如果每个参与者在NE处获得收益h，则该块中的策略以非零概率进行，并且将它们归一化得到NE（A，B）。后者如下，因为NE集保持不变下添加剂缩放的回报。在0中检索NE。5球，我们确保如果这些策略中的任何一个（相对）使用大于0。5概率则一系列偏差导致两个参与者仅在他们的最后MN个策略中进行博弈，其中收益为零（H）。特别地，假设第二个玩家在左上方的方块中玩y。行玩家的最后mn个策略被分成大小为m的n个块，每个块对应于y j，j n，使得如果y j> 0。那么第一个参与人的最佳对策是偏离到第j个区块。第二个参与人的收益是固定的多人Nash均衡的完全性一曰：ACM Transactions on Economics and Computation，卷。号61.第1条。出版日期：2018年1月–∃∃≥ ∃∃i=1∈ ×∈SI∈−∈∈∈ ∀ ∈∈|∈到 所以y，j取的是 1和第二个玩家被迫偏离到她的最后一个mn两个都为零的策略第一个玩家也是如此。组织：在第2节中，我们正式定义了（对称）k-Nash问题及其决策问题，并讨论了复杂性类R和FIXP。在R中的成员资格的决策问题在（对称）k-Nash是显示在第3节。 在第4节中，我们证明了k人对策中的决策问题，对于任何常数k， 3的完成对称3-Nash决策问题的R-完备性在第5节中给出。在第六节中，我们证明了计算对称3-Nash中的均衡是FIXPa-完全的.由于对称3-纳什不平凡地减少到对称k-Nash，我们推广了第7节中关于后者的α-完全性结果，其中k≥3。2预赛在本节中，我们正式定义了（对称）k-Nash问题及其决策问题.此外，我们还讨论了复杂性类FIXP和FIRR。表示法：向量用黑体字表示，向量x的第i个坐标用xi表示，x−i表示去掉第i个坐标后的向量x1和0分别表示适当维数的全1和全zeros向量。对于整数k<1，x（k：1）=（x k，x k+1，.，xl）。我们使用[n]来表示集合{1，.，n}和[k：l]来表示{k，k+1，.，l}。如果x是m维的，则由σ（x）wean。M xi，且nd η（x）=x/σ（x）。向量x和y的连接用y表示（x y）。给定一个矩阵A和hR，A+h表示矩阵A，h加到它的每个元素上。此外，A（i，：）是其第i行，A（：，j）是其第j列。2.1（对称）k-Nash对于给定的k人对策，设Si，i [k]是局中人i的纯策略集，S = i[k]Si.参与人i的收益可以用一个k维张量A i来表示，A i（s）表示参与人在s ∈ S时的收益. 玩家可以随机选择他们的策略。令Δi表示局中人i的混合策略剖面集，令Δ=×i∈[k]Δi.参与人的期望收益if rom x=（x1，. . . ，xk）∈Δ是πi（x）=.s∈S（εi∈[k]xi）Ai（s）.定义2.1. （纳什均衡（NE）[22]）x∈Δ被称为NE，如果没有参与者通过单边偏离获得收益。形式上，i，xJi∈Δi，πi（x）≥πi（xJi，x−i）。设πi（s，x−i）表示当她选择s Si而其他人选择x−i时，i得到的收益。很容易看出x是NE当且仅当[22]<$i∈ [k]，<$s∈Si，xi>0 <$π i（s，x−i）= max π i（t，x−i）.（一）st∈ Si对称k-Nash：在对称博弈中，参与者是不可区分的.他们的策略集是相同的（S），收益是对称的，由一个张量A表示。对于一个参与人来说，当其他人采用s S（k-1）时，通过采用s j S得到的是A（s J，s）。此外，谁在玩s中的什么并不重要。形式上，对于（1，. ，k 1），其中sτ是对应的置换向量。Aprofile xΔ称为对称的，如果xi= xj，i、j[k]，因此一个向量xΔ足以表示对称轮廓。在对称策略下，所有参与者都得到相同的收益，我们用π（x）表示。对称对策的对称NE（SNE）的计算问题称为对称k-Nash.注意，（对称）k人博弈的描述需要O（kmk）空间，其中m=马锡|SI|，它是m和k的e×幂。在求解多项式时，我们把k看作常数。一曰：J. Garg等人ACM Transactions on Economics and Computation，卷。号61.第1条。出版日期：2018年1月∈×....∃∃•⊂ ∀ ∈•⊂ ∀ ∈联系 我们∧ ∨ ¬n∈S2，yj>0i∈S1，k∈S3Bijkxizk =maxl∈S2i∈S1，k∈S3Bilkxizk，此外，wlog（A1，...，A k）> 0，因为向张量添加常数不会改变NE的集合。2-纳什：在两人博弈的情况下，收益张量是矩阵，比如（A，B），A代表参与人1，B代表参与人2。如果第一个参与人选择i，第二个选择j，那么他们各自的收益是Aij和Bij。如果B=AT，则称博弈是对称的。一个混合策略是（x，y）Δ1Δ2，在这种策略下的相应收益是xTAy和xTBy。2-Nash是找到这样一个博弈的Nash均衡的问题，即，策略（x，y），使得xTAy≥xJTAy，且xTBy≥xTByJ，nyJ∈Δ2.等式（1）的NE表征简化为：<$i∈S1，xi> 0 <$（Ay）i= max（Ay）k;<$j∈S2，yj> 0 <$（xTB）j= max（xTB）k.（二）k∈S1k∈S23-纳什均衡：这是k=3个参与人的k-纳什均衡问题我们将用三个三维张量（A，B，C）来表示这样一个博弈A代表参与人1，B代表参与人2，C代表参与人3.如果参与人1选i，2选j，3选k，那么他们各自的收益是Aijk，Bijk和Cijk。如果这个博弈是对称的，那么我们有Aijk=Aikj=Bjik=Bkij=Cjki=Ckji。混合策略表示为（x，y，z）∈Δ1×Δ2×Δ3。因此，等式（1）的NE表征简化为：i∈S1，xi>0j∈S2，k∈S3Aijkyjzk =maxl ∈S1j∈S2，k∈S3 Aljkyjzk，i∈S1，j∈S2Cijkxiyj= maxl ∈S3i∈S1，j∈S2Cijlxiyj.决策问题：许多决策问题的计算复杂性已经研究了2-Nash和3-Nash [8，15]。在本文中，我们考虑以下内容：非唯一：是否存在多个NE？最大收益：给定一个有理数h，是否存在一个NE，每个玩家至少得到h的收益？子集：给定集合T iS i，i [k]，是否存在NE，其中参与人i以正概率使用T i中的每个策略？超集：给定集合Ti Si，i [k]，是否存在一个NE，参与人i参与的概率为零？InBox：是否存在一个NE，其中每个策略的概率小于或等于0。五个？除了最后一个问题之外，所有问题在2-Nash的情况下都是NP完全的[8，15]，最后一个问题在3-Nash的情况下是R完全的[28]。在这篇文章中，我们证明了前四个k-Nash决策问题的R-完全性，以及对称k-Nash的第三和第四个决策问题的R-完全性，其中在两种情况下k≥2.2实数势理论（ETR）实的存在论（ETR）的实例I由以下形式的句子组成：（x1，.，xn）n（x1，.，xn），其中，R1是一个无量词的（，，）-布尔公式，用于由签名0， 1， 1，+，=定义的谓词（句子），用于取实值的变量。问题是检查句子是否正确。问题的大小是n+size（n），其中n是变量的数量，size（n）是表示n所需的签名的最小数量。舍费尔和斯特凡科维奇···（多人Nash均衡的完全性一曰：ACM Transactions on Economics and Computation，卷。号61.第1条。出版日期：2018年1月∃∃∈∞∃S∈{−}∈→∈∈∃∀ ∈≥| −|∃SSSs∈ Si[28]将复杂性类R定义为这些问题在多项式时间多-一约简下的向下闭包（我们请读者参考参考[28]以了解R的更多细节，以及它与其他类如PSPACE的关系）。请注意，代表任何有理数在其位长度上都是线性的。Schaefer和Štefankovi证明了对于3-Nash，问题InBox是ABR-完全的。2.3FIXP类及其变体FIXPaEtessami和Yannakakis [11]定义了FIXP类来捕获具有代数解的精确不动点问题的复杂性。一个FIXP问题是寻找函数F：D的不动点在一个凸的紧致域D上，即，Find XDs.t. F（x）=x.该函数由具有最小、最大、+、、/门、有理数常数和n个输入/输出的算术电路C给出;大小[C]=n+#门+位长度（常数）。给定λD到C作为输入，其所有门都是明确定义的。F的不动点可能是无理数。因此，为了忠实于图灵机计算，Etessami和Yannakakis [11]定义了一个离散类FIXPa。（强）逼近FIXP a：给定电路C定义函数F，且有理函数f> 0，计算向量x，该向量x在l范数下与x的（加性）π距离内，其中F（x_∞）=x_∞（不动点），在大小为[C]和log（1/∞）的时间多项式中.第2.2节. [11]给定一个三人博弈（A1，A2，A3），计算它的NE是FIXP完全的。相应的（强）逼近对于FIXP a是完备的。为了在约简中处理无理解以显示FIXP-硬度，约简必须提供一个线性函数，该线性函数将约简实例的解映射到原始实例的解。线性函数中使用的常数必须是给定实例大小的多项式[11]。3（对称）K-NASH：含药血清在这一节中，我们证明了2.1节中描述的前四个决策问题是在R中的，对于k-纳什和对称k-纳什。 对于k-玩家游戏（A1，. ，A k），等式（1）的NE特征可以被重新表述为如下的一组多项式不等式，其中变量xi捕获参与者i玩S i的概率，并且变量λ i捕获她的最佳收益。回想一下2.1节中的函数πi（s，x−i），它表示参与人i在选择s Si时的收益其他人则按照x-i来玩：[k ]中的πi ∈ [k]，πs ∈ Si，xi≥ 0; π i（s，x−i）≤ λ i; xi（π i（s，x−i）− λ i）= 0; .x i= 1。（四）很容易看出，当且仅当策略曲线xΔ满足等式（4）时，它才满足等式（1第3.1节. 给定一个k-玩家游戏（A1，. ，Ak），对于常数k，NonUnique，MaxPayoff，Subset和Superset的问题都是在BRR中。P屋顶。要将NonUnique问题定义为R问题，可以将等式（4）复制两份，每一份都有不同的变量集，比如x和y，然后加上xy2>0。这个系统有一个可行解（x，y）当且仅当这个博弈有两个NEx∈y。因此，R中NonUnique的包容性如下。对于MaxPayoff，将i[k]，πi（x）h添加到系统方程（4）。它有一个可行解x当且仅当x是博弈的NE，其中每个参与人的收益至少为h，意味着MaxPayoff是一个在Pwr。一曰：J. Garg等人ACM Transactions on Economics and Computation，卷。号61.第1条。出版日期：2018年1月SS−∃B×≥∃.∃∈∈×≥B∞–×−≤D=[B+h]1，1+[（−1）mn×n]m+1，1+i∈[m][B（i，：）+2h]1，in+1.类似地，为了公式化Subset，将i∈[k]，s∈Ti，xi> 0添加到（4）。对于超集，添加[1：k]，其中x∈Si\Ti，x i= 0为等式（4）。□给定一个对称博弈A，下面的多项式不等式系统（类似于等式（4））精确地捕获了它的对称NE，其中变量xs捕获了策略s∈S的概率，λ捕获了收益：π（s，x）≤λ; x s（π（s，x）− λ）= 0且x s= 1。S下一个定理的证明类似于定理3.1。第3.2节. 给定一个对称k人对策A，对于常数k，对称NE的非唯一性、最大收益、子集和超集问题都在R中。4K-NASH：决策问题的完备性在本节中，我们将证明对于任何常数k3，MaxPayoff、Subset、Superset和NonUnique在k人博弈中是R-完全R中的包容性由第3节的定理3.1得出。我们接下来在三人博弈的情况下证明了这四个决策问题的R-困难性，由于三人博弈可以简单地简化为k人博弈，当k>3时，通过添加k3个虚拟玩家，每个虚拟玩家有一个策略，结果也会遵循后者。为了显示MaxPayoff ， Subset 和 Superset 的 硬 度 ， 我 们 从 InBox （ 在 4.1 节 中 ） 减 少 ， 对 于NonUnique，我们从MaxPayoff（在4.3节中）减少。4.1硬度：InBox到MaxPayoff、Subset和Superset为了表达主要思想，我们首先描述了两人博弈中的缩减，然后在4.2节中将其推广到三人博弈中。我们展示了从InBox到MaxPayoff的简化，以及从中间引理到Subset和Superset的简化。设给定的两人博弈用m个n维支付矩阵（A，B）>0表示.对于a0，设a=[0，a]m+n是一个球，其原点的半径为a，范数为 我们将构造另一个具有m（n+1）n（m+1）维矩阵的博弈（C，D），并证明当且仅当博弈（A，B）的NE为0时，它有一个NE，其中每个参与者至少得到h> 0的收益（MaxPayoff）。5（InBox）.首先，我们定义构造所需的几个符号定义4.1. 设i和j是整数，其中i[m]和j[n]，h是实数。我们定义以下操作符：A（i，：）+h：矩阵A，其中h被添加到其第i行中的条目，以及A（：，j）+h：矩阵A，h加到第j列的元素上。定义4.2. 给定一个矩阵M，大小为ab，整数r和s，使得a+r 1 m（n+1），b+s1n（m+1），定义[M] r，s为m（n+1）n（m+1）维矩阵，其中M从位置（r，s）开始复制，所有其他坐标设置为零。使用上述符号，我们如下构造矩阵C和D，其中h>0：C=[A+h]1， 1+[（−1）m×mn]1，n+ 1+j∈[n][A（：，j）+2h]jm+1， 1，且从C、D的结构开始，下面是一个新的例子。 Recallthatσ（x）=.ixi.多人Nash均衡的完全性一曰：ACM Transactions on Economics and Computation，卷。号61.第1条。出版日期：2018年1月.J（Cy） =i×≤∃ ∈∗..B4.3.BLOG给定对策（C，D）的一个策略（XJ，YJ），设x=XJ（1：m），y=YJ（1：n），α=h∈σ（y）− σ（yJ（n +1：（m +1）n）），以及β = h <$σ（x）− σ（x J（m +1：（n +1）m））。然后，α+（Ay）i如果i∈[m]2hy·（i−1）/m]+（Ay）r如果i∈[m+1，m（n+1）]，r=（（i−1）modm）+1.（xJTD）jβ+（xTB）j如果j∈[n]2hx·（j−1）/n]+（xTB）r如果j∈[n+1，n（m+1）]，r=（（j−1）modn）+1.在正式的还原之前，这里有一个简短的直觉。注意在（C，D）中，我们在左上方的m n块中复制了（A+h，B+h），我们现在称之为第一个块。由于添加一个常数不会改变博弈的NE，如果只有第一个块的策略在NE为（C，D）时以非零概率进行，那么它们也会给出NE为（A，B）。此外，在这样的NE处实现的收益至少是h，使用引理4.3的MaxPayoff的解。为了保证NE为0。5对于游戏（A，B）（InBox的解决方案），我们在两个方向上使用第一个块之后添加的块。特别地，在引理4.3中，如果j [n]，y j> 0。5σ（y），那么对于第一个参与者，她的前m个策略比来自块[mj+1：mj+m]的那些策略更差，迫使她仅从她的最后mn个策略来玩。这将迫使第二个玩家也离开第一个区块（否则他得到负收益），从而导致一个NE，其中两个玩家都从最后一个mn策略开始游戏，并且都得到零收益-也不是最大收益的解决方案。我们将在还原中使用这些观察结果。我们证明了InBox在博弈（A，B）中的解，即，（x，y），使得x，y 0。5，保留为（C，D）的NE。证明使用的事实是，在C和D中，左上方的块分别编码A和B4.4.BLOG （A，B）有一个NE（x，y）∈ B0. 5当且仅当（XJ，YJ）=（（x，0mn），（y，0mn））是（C，D）的NE.P屋顶。为了证明向前方向，只需检查策略配置文件（xJ，yJ）是否满足博弈（C，D）的等式（2）。 我们展示了第一个参与者的条件，即涉及C，第二个参与者的证明也类似。 由于yj中的最后一个mn策略根本不被采用，我们有α=hj∈[n]yi−j∈[n+1， n（m+1）]yjJ=h<$1−0=h. 这与引理4.3一起给出了i ∈ [m]，（C yJ）i=h+（A y）i =max（C yJ）i= h + max（A y）i.i∈[m]i∈[m]对于i∈[m+1，m（n+ 1）]，令r=（（i−1） modm）+ 1且k=·（i−1）/m]。然后，使用引理4.3和y k≤ 0的事实。5、我们有（C yJ）i≤ 2 h（0. 5）+（Ay）r=h+（Ay）r=（Cyj）r。.=一曰：J. Garg等人ACM Transactions on Economics and Computation，卷。号61.第1条。出版日期：2018年1月k∈[m]BBBBσ（y）≥≥i≤∀ ∈ ≤≤∀ ∈ ≤≤换句话说，[1：m]策略的收益至少和其他策略一样多 由于（x，y）是gam e（A，B）的一个NE，所以ifxij=xi> 0thn（Cyj）i=h+（Ay）i=h+maxk∈[m]（Ay）k=maxk∈[m（n+1）]（Cyj）k.对于反方向，则τi∈[m] s. t。xiJ>0，因此<$j∈[n]，（CyJ）i≥（CyJ）mj+i<$2hyj≤h∈y j≤ 0. 5.同样，x≤ 0。5跟随。□引理4.4将博弈（A，B）中的InBox的解映射到博弈（C，D）的NE，其中参与者仅分别在他们的前m，n个策略显然，在这样的NE下，博弈（C，D）中的两个参与者都至少得到h个收益，因此它也是（C，D）中最大收益的解。接下来，我们展示了一个反向映射：一个NE的（C，D），其中两个玩家都采取一些前m，n策略，给出了一个NE的游戏（A，B）。回想一下，对于向量x，η（x）=x/σ（x）。4.5. 如果（x J，yJ）是博弈（C，D）s. x = x J [1：m]和y = yJ [1：n]不为零，则（η（x），η（y））是N∈f或对策（A，B），且nd（η（x），η（y））∈B0. 五、P屋顶。当σ（x），σ（y）>0时，要证明（η（x），η（y））是（A，B）的NE，只需证明以下内容即可<$i∈[m]，xi> 0<$（Ay）i=maxk∈[m]（Ay）k，且<$j∈ [n]，yj> 0 <$（xTB）j=max k∈[n]（xTB）k.我们表明，第一个持有和第二个类似的证明如下。让λ=maxk∈[m（n+1）]（CyJ）k和λJ=maxk∈[m]（CyJ）k=α+max（Ay）k（使用引理4.3）。当λi∈[m]，XIJ> 0时，有λJ=λ.因此，我们得到<$i ∈ [m]，xi> 0 <$（Cyj）i=λ<$α+（Ay）i=α+ max（Ay）k<$（Ay）i= max（Ay）k.k∈[m]k∈[m]对于第二部分，相反地，假设<$j∈[n]， （η（y））j=yj>0。5~2yj>σ（y）。则对于某个i[m]，我们有XJ>0和（CYJ）ihσ（y）+（Ay）i2hyj+（Ay）i=（CYJ）jm+i<λ，与（x J，yJ）是博弈（C，D）的NE的矛盾。□引理4.4和4.5意味着博弈（A，B）的NE在0。5当且仅当博弈（C，D）有一个NE，其中两个局中人分别采取前m，n个策略中的一些。如果我们证明，要在后一个博弈中获得至少h的收益，参与人必须采取前m，n个策略中的一些，那么很明显，减少将随之而来。4.6.BLOG 给定一个策略配置文件（x J，yJ），如果x JTC yJh和x JTD yJh，则x=xJ（1：m）并且y=YJ（1：n）是非零的。P屋顶。如果y=0，则使用引理4.3，我们有i[m（n +1）]（C yJ）i0，并且依次x JTCyJ0.类似地，如果x= 0，则j[n（m+1）]我们有（XJTD）j0，然后XJTD yJ0。引理遵循使用h> 0的事实。□下一个定理由引理4.4、4.5和4.6推出。第4.7章.博弈（A，B）的NE为0。5当且仅当博弈（C，D）有一个NE，每个参与人的收益至少为h。下一个定理使用引理4.4展示了从InBox到超集的归约。第4.8章.博弈（A，B）的NE为0。5当且仅当博弈（C，D）有一个NE，其中第一个和第二个参与者以非零概率采取的所有策略分别来自T1=[1：m]和T2=[1：n]。引理4.4和4.5意味着如果博弈（A，B）中有NE，则在博弈（C，D）中，前m，n个策略中的一个策略被随机博弈者以非零概率采用。0。五、这个定理给出了从InBox到Subset多人Nash均衡的完全性一曰：ACM Transactions on Economics and Computation，卷。号61.第1条。出版日期：2018年1月的图灵约简。一曰：J. Garg等人ACM Transactions on Economics and Computation，卷。号61.第1条。出版日期：2018年1月××.关于我们× ×B∈ ∈- ≤ − ≤ × ×× ×−≤.∈1E=[B+h]1，1，1 +[（−1）mn，n，（m+1）p]m+ 1，1，1+.k∈[p][B（：，：，k）+2h]1，kp+ 1，1，如果i∈[m]，则α+πA（i，y，z）11D=[A+h]1，1，1+[（−1）m，n（p+1），mp]1，1，p+ 1+j∈[n][A（：，j，：）+2h]jm+1，1，1，第4.9章. 博弈（A，B）中有一个NE0。5当且仅当我[m]，J[n]使得对于T1=i和T2=j，博弈（C，D）具有NE，其中T1和T2的所有策略都以非零概率进行。利用对两人博弈的归约的直觉，接下来我们将定理4.7、4.8和4.9扩展到三人博弈，以获得相同的硬度结果4.23-Nash：InBox到MaxPayoff、Subset和Superset就像在两个参与人的情况下，给定一个三人博弈， p维收益张量（A，B，C），我们将创建一个大小为m（n+1）n（p +1）p（m+1）的博弈（D，E，F），并将原始博弈插入第一个块中，并添加h。我们从定义开始，类似于4.1和4.2。定义4.10. 对于i∈[m]，j∈[n]，k∈[p]和实数h，定义A（i，：，：）+h：张量A，h加到条目AijJkJ<$j∈[n]，<$kJ∈[p]，A（：，j，：）+h：张