一个CM通信
研究突出了
无政府价格的内在稳健性
信贷:Vwork
无政府状态的价格，定义为一个博弈的纳什均衡的最坏情况目标函数值与最优结果的最坏情况目标函数值之比，量化了自私行为的无效率。对于广泛的应用程序域，该度量的良好边界是众所周知的。然而，只有当游戏参与者成功达到纳什均衡时，这种界限才有意义。这一缺陷激发了低效率边界，它更普遍地适用于较弱的均衡概念，如混合纳什均衡和相关均衡，或自然实验策略产生的结果序列，如同时遗憾最小化。
我们证明了无政府状态的价格与其看似更普遍的亲戚之间的一般的和基本的联系。首先，我们为纯纳什均衡的无政府状态的价格上限确定了一个“规范充分条件”，我们称之为平滑参数．其次，我们证明了一个“可拓定理”:通过光滑性论证推导出的关于无政府状态价格的每一个边界会自动扩展为混合纳什均衡、相关均衡和联合重复博弈各无悔序列的平均目标函数值。第三，我们证明了在路由博弈中，光滑性参数在证明理论意义上是“完整的”:尽管它们具有自动普遍性，但它们保证会在混乱状态的代价上产生最优最差情况上限。
1.简介
每个学博弈论的学生都很早就经常学到这一点平衡是无效的自主决策者的自利行为通常会导致一个不如假设的仁慈独裁者会选择的结果。这种低效率在现实环境中是普遍存在的，其原因有很多:拥塞外部性、网络效应、不协调等等。在许多情况下，消除它可能代价高昂或不可行，大型网络就是一个明显的例子。过去的十年为这种普遍存在的均衡效率低下提供了一个令人鼓舞的对照:在许多有趣的应用领域，由相互竞争的个体进行分散优化证明地接近最佳结果。
这种类型的严格保证需要一个正式的行为模型，以便定义“自我利益行为的结果”。之前的大多数研究纯战略纳什均衡，定义如下。每个玩家我选择策略年代我从一组年代我，就像网络中的路径。成本C我（年代)由玩家引起的我在游戏中是整个向量的函数年代玩家选择的策略，这叫做战略概要或者一个结果．根据定义，这是一个策略概要年代游戏是一个纯纳什均衡如果没有参与方可以通过单边偏离降低成本:
对于每一个我而且
，在那里年代我表示玩家选择的策略我在年代．这些概念可以通过收益最大化而不是成本最小化来定义;参见例2.5。
的混乱的代价(POA)测量由自我利益行为引起的次优性。给定一个博弈，一个“均衡”的概念(如纯纳什均衡)和一个目标函数(如参与者成本的总和)，博弈的POA被定义为一个均衡的最大成本和一个最优结果的成本之间的比率。POA的上限有一种最坏情况的吸引力:它适用于所有可能的均衡，无需预测自私行为的单一结果。许多研究者已经在广泛的模型中证明了POA上非常好的边界;参见Nisan等人的第1721章。17还有里面的参考文献。
1.1.需要更强健的边界
对于游戏的无政府状态的价格的一个良好的界限并不足以得出结论，即自利行为是相对良性的。只有当游戏参与者成功达到平衡时，这样的界限才有意义。然而，对于纯纳什均衡来说，有很多原因可以解释为什么这种情况不会发生:也许玩家不能协调多个均衡中的一个，或者他们正在玩一个计算纯纳什均衡是一个计算上难以解决的问题的游戏9或者更根本地说，一个不存在纯纳什均衡的博弈。这些批评激发了最坏情况的表现界限，适用于尽可能广泛的结果范围，并在对玩家如何在游戏中玩游戏和协调的最小假设下。
本文提出了无政府状态价格的“稳健”边界的一般理论。我们专注于基本均衡概念的层次结构图1；完整版本22讨论纯纳什均衡的其他推广，包括由最佳反应动力学产生的近似均衡和结果序列。我们正式定义了平衡的概念图1混合纳什均衡，相关均衡和粗相关均衡在第3.1节，但下面要提到它们的一些重要性质。
扩大平衡集削弱了证明平衡分析所需的行为和技术假设。首先，虽然有些博弈没有纯纳什均衡，但“便士匹配”是一个简单的例子，每个(有限)博弈至少有一个混合纳什均衡。16因此，纯纳什均衡的“不存在批判”不适用于任何更一般的概念图1．第二，虽然计算混合纳什均衡通常是一个计算上的棘手问题，5，8计算相关平衡则不是(参见Nisan等人的第2章)。17)．因此，纯纳什均衡和混合纳什均衡的“难解性批判”不适用于两个最大的纳什均衡集图1．更重要的是，这两组博弈是“容易学习的”:当一个博弈随着时间的推移而反复进行时，就会有自然的学习动态过程，玩家可以通过这个过程来选择下一个时间步骤的策略，作为其自身收益和博弈历史的函数，保证快速收敛于这些均衡集(见Nisan等人的第4章)。17)．
1.2.概述
我们的贡献可以分为三个部分。
- 我们确定了博弈纯纳什均衡POA上界的一个充分条件，为推导此类上界编码了一个规范证明模板。我们称这种证明为“平滑论证”。文献中的许多POA上界可以被重铸为这种规范方法的实例。
- 我们证明了一个“可拓定理”:通过光滑性论证推导出的关于无政府状态价格的每一个边界，在没有数量退化的情况下，自动扩展到图中所示的所有更一般的均衡概念图1．
- 我们证明了当成本函数被限制在某个任意集合时，路由博弈在以下意义上是“紧的”:尽管光滑性参数具有自动普遍性，但保证在POA上产生最优的最差情况上界，即使对于纯纳什均衡集也是如此。因此，在这类博弈中，每个均衡概念的最坏情况POA是相同的图1．
2.光滑的游戏
2.1.定义
由一个成本最小化的游戏，我们指的是玩家、策略和成本函数以及联合成本目标函数
．本质上，“平滑博弈”是一种成本最小化博弈，它允许规范类型的POA边界(“平滑论证”)。我们先给出正式的定义，然后解释如何解释它。
定义2.1(平滑游戏):成本最小化游戏是(，)-光滑的如果每两个结果年代而且年代*，
粗略地说，作为初始结果的函数，平滑控制了结果的一组“一维扰动”的代价年代还有摄动年代*。
如果博弈是(，)-平滑的，且>为0且< 1，那么它的每一个纯纳什均衡年代成本是否最多为最优解的/(1)倍年代*。在证明中，我们推导
式中(3)由目标函数的定义得出;不等式(4)源自纳什均衡条件(1)，应用于每个参与者一次我假设偏差
；不等式(5)来自于平滑博弈的定义条件(2)。重新排列项产生要求的界限。
定义2.1对于这个三行证明(3)(5)的最后一行已经足够了，但它要求不等式(2)成立每一个结果年代,不仅仅是纳什均衡．这就是为什么光滑论证隐含了纯纳什均衡集之外的最坏情况边界的基本原因。
我们定义健壮的小作为POA的最佳上界，可以通过光滑论证来证明。
定义2.2(鲁棒POA)无政府状态的稳健价格一个成本最小化的游戏
它总是小于1。
备注2.3(光滑性的变化):检查三线证明(3)(5)可以通过两种方式削弱假设。首先，目标函数满足的假设
可以用假设代替吗
；我们在下面的示例2.5中利用了这一点。其次，在定义2.1中，不等式(2)只需要对所有结果成立年代还有一些最优解年代，而不是所有对,年代*的结果。这种弛豫在某些应用中是有用的。4，23
最后，针对最大化目标的平滑博弈也有类似的定义;参见例2.5。
2.2.直觉
光滑性论证应该被解释为纯纳什均衡的POA的上限证明，这种证明被限制在以最小的方式使用均衡假设。为了解释这一点，回想一下经典的三行证明(3)(5)。第一个不等式(4)使用了纳什均衡假设，但只是为了证明为什么每个玩家我选择其均衡策略年代我而不是战略在最佳结果中。如果我们只关心纯纳什均衡的POA，那么我们可以自由地再次调用纳什均衡假设来证明第二个不等式(5)，或者更一般地说，用我们喜欢的任何论证来建立一个上限。使用平滑论证，即证明不等式(5)所有结果年代在纳什均衡假设被用来证明第一个不等式(4)之后，就等于抛弃了它。
2.3.两个例子
对一个定义的适用范围的关注随着其有趣后果的积累而增长。假设光滑性参数支持1.2节中讨论的扩展定理，那么有多少游戏可以(，)-光滑，且具有有趣的，值?为了减轻这种恐惧并为讨论添加一些具体内容，我们接下来挑出两个众所周知的POA分析，它们可以被重新定义为平滑论证。更一般地说，许多但不是所有已知的无政府状态边界的代价都来自于光滑证明一个；查看完整版本22详细讨论。
第一个例子是拥挤游戏的特殊类别;第四部分对一般案例进行了详细研究。第二个例子是Vetta的实用游戏，25还说明了如何在收益最大化博弈中定义和使用平滑参数，以及如何使用和目标函数的“片面”变体(参见注释2.3)。
例2.4(原子拥塞游戏):拥塞游戏是由地面集合定义的成本最小化游戏E还是资源，一套k拥有策略设置的玩家年代1、……年代k2E，和代价函数ce：
对于每个资源e
E．20.在本文中，我们总是假设成本函数是非负的和非递减的。一个典型的例子是路由游戏E是网络的边集，玩家的策略对应于其源顶点和汇聚顶点之间的路径。给定一个战略概要年代= (年代1、……年代k),年代我年代我为每一个我，我们说xe= | {我：e年代我}|是负载诱导上e通过年代，定义为在游戏中使用它的玩家数量年代．玩家的成本我被定义为
，在那里x载荷的矢量是由什么引起的年代．对于这个例子，我们假设每个成本函数是仿射，这意味着ce（x) =一个ex+be与一个e，be每个资源为0eE．
我们声称每一个具有仿射代价函数的拥塞对策都是(5/ 3,1 /3)-平滑的。基本原因由Christodoulou和Koutsoupias的引理1确定，7谁注意到
对于所有非负整数y, z．因此，对于所有人来说a、b0和非负整数y, z，
为了建立平滑性，考虑一对s, s *带有诱导负载的仿射代价函数的拥挤对策的结果x, x *．因为玩家使用资源的数量e在结果中(，年代-我)最多比那个大1年代，这一资源有助于精确
表格的条款C我（，年代-我)，我们有
从(6)到(7)，用而且xe扮演角色y而且z,分别。经典的三线论证(3)(5)暗示了在每个具有仿射代价函数的拥塞博弈中，纯纳什均衡的POA的上界为5/2。这一事实在Awerbuch等人中首次得到独立证明。2Christodoulou和Koutsoupias，7其中还提供了匹配的下界。我们的可拓定理(定理3.1)暗示5/2的界限扩展到中所示的其他三组结果图1．这些扩展最初是在两篇不同的论文中建立的3.，6在最初的POA界限之后。2，7
例2.5(有效的实用游戏):我们的最后一个例子涉及一类叫做有效的效用游戏．25这些游戏通常被称为payoff-maximization每个玩家都有一个收益函数我（年代，它努力使之最大化。我们用来表示收益最大化博弈的目标函数。我们称这种游戏为(，)-光滑的如果
每一对s, s *的结果。类似于(3)(5)的推导表明，在(，)-平滑收益最大化博弈中，每个纯纳什均衡的目标函数值至少是最大可能值的/(1 +)个分数。我们定义健壮的小作为/(1 +)除以所有合法平滑参数的最大值(，)。
一个有效的效用博弈是由一个基础集合定义的E，一个非负子模函数V的子集上定义E，以及一套策略年代我2E还有一个支付函数我对于每个玩家我= 1, 2，…，k．b例如，集合E是否可以表示一组可以建造设施的地点，以及一种策略年代我E可以表示哪个球员所在的位置吗我选择建设设施。为了一个结果年代,让U（年代）E表示联合
玩家的策略年代．结果的目标函数值年代定义为(年代) =V（U（年代))。此外，该定义要求两个条件成立:(i)对于每个参与者我，我（年代）V（U（年代)) -V（U(Ø年代-我))为每一个结果年代；和(2)
对于每一个结果年代．这种博弈的一个具体例子是，与定价市场和利润最大化公司竞争设施选址。25
我们声称每一个有效的效用对策具有一个非递减的目标函数V(1,1)-光滑。证明本质上是Vetta定理3.2中的几个关键不等式25，如下。让s, s *用非递减目标函数表示有效效用博弈的任意结果。让U我E表示所有参与人策略的并集年代，以及参与人1、2、…我在*．适用条件(i)，的子模块性V的非递减性质V收益率
根据需要。这个平滑论证意味着在每一个有效效用博弈中纯纳什均衡的POA的下界为1/2，目标函数为非递减的，这个结果在Vetta中首次得到证明，25还有一个匹配的上界。我们的可拓定理表明，这个下界更普遍地适用于文中描述的所有均衡图1这一事实最初是由Blum等人确立的。3.
3.一个可拓定理
本节阐述并证明了在第1.2节中讨论的可拓定理:纯纳什均衡的每个POA边界由光滑性论证导出，自动扩展到更一般的均衡概念图1以及随着时间的推移游戏中相应的结果序列。完整版本中讨论了平滑性参数的几个不太直接的结果。22我们研究的是成本最小化的游戏，尽管类似的结果也适用于收益最大化的游戏(参见例子2.5)。
3.1.静力平衡概念
我们从定义2.1对一次性博弈中随机均衡概念的含义开始;下一节将讨论重复游戏所产生的结果序列。
一套(1、……k)在策略集上的独立概率分布，即每个玩家在成本最小化游戏中的独立概率分布是一个混合纳什均衡在产品分配条件下，如果没有参与者能够降低其预期成本=1x……xk通过单方面的偏离:
对于每一个我而且年代我，年代我年代我,在那里-我，是产品分配的全部j其他的我．(通过线性，只考虑纯策略的单边偏差就足够了。)显然，每个纯纳什均衡都是混合纳什均衡，而不是相反的;的确，许多博弈没有纯纳什均衡，但每个有限博弈都有混合纳什均衡。16
一个相关的平衡一个最小化成本的游戏G结果的(联合)概率分布是G它的性质是
对于每一个我而且年代我，年代我年代我．一个经典的相关均衡的解释是根据一个中介者，他得出一个结果年代从公开的已知分布和私下的“推荐”策略年代我给每个玩家我．均衡条件要求遵循一个被推荐的策略总是使玩家的预期成本最小化。混合纳什均衡恰恰是相关均衡，也是乘积分布。相关平衡被广泛研究作为一个友好的中介策略，也因为他们的相对可驯服性。因为相关均衡集是由一个小的线性不等式集明确描述的，计算(甚至优化)相关均衡可以在博弈规模的时间多项式中完成(例如，参见Nisan等人的第2章)。17)．正如下一节所讨论的，它们也相对“容易学习”。
最后,一个粗相关平衡最小成本博弈是一个结果的概率分布满足
对于每一个我而且年代我，年代我．相关均衡(8)可以防止玩家意识到他们所推荐的策略的偏离，而粗略的相关均衡(9)只受玩家偏离的限制，这些偏离与抽样结果无关。因为每个相关均衡也是粗相关均衡，所以粗相关均衡“更容易”计算和学习，因此是对博弈实现的更合理的预测。
我们现在给出了一次博弈均衡概念的扩展定理:通过光滑性论证证明的每个POA界自动扩展到粗相关均衡集。有了“正确的”定义之后，证明就可以自己写了。
定理3.1(扩展定理静态版本)对于每一个具有稳健POA的最小成本博弈G（G)，G的每一个粗相关平衡和每一个结果*G的，
证明:让G是一个(，)-平滑的成本最小化博弈，一个粗糙的相关均衡，和*的结果G．我们可以写
等式(10)源自目标函数的定义，等式(11)、(13)和(15)源自期望的线性，不等式(12)源自粗相关均衡的定义(9)(每个玩家应用一次，假设偏差）和不等式(14)来自于游戏是(，)-平滑的假设。重新排列项完成证明。
3.2.重复游戏和无悔序列
扩展定理(定理3.1)同样适用于重复游戏产生的某些结果序列，因为这些序列与静态平衡概念之间有众所周知的对应关系。为了说明这一点，考虑一个序列年代1，年代2、……年代T一个(，)-平滑游戏的结果和一个最小成本的结果*游戏的。为每一个我而且t,定义
作为玩家的假设改进我的时间成本t它用过这种策略吗代替年代t我．当年代t是纳什均衡，我（年代t)不能为正;对于任意的结果年代t，我（年代t)可以是正面的，也可以是负面的。我们可以模拟(3)(5)中的推导得到
为每一个t．
假设每个玩家我经历消失的平均(外部)遗憾，这意味着随着时间的推移，它的成本可以与每一种时不变策略竞争:
一遍又一遍地重复同样的纯纳什均衡会产生一个简并的例子，但一般来说，这样的序列可以在任意大的时间范围内表现出高度振荡的行为(参见Blum等人的例子)。3.和Kleinberg等人。13)．
平均(17)除以T时间步长和颠倒结果的双求和的顺序
回顾(16)我（年代t)为玩家所产生的额外成本我在时间t由于游戏策略年代t我而不是(时不变的)策略，无后悔保证(18)意味着
上面是否有一个趋近于0的项T．因为这适用于所有玩家我，不等式(19)意味着序列中结果的平均成本不大于稳健POA乘以最小可能成本，加上接近于0的误差项T．
定理3.2(扩展定理重复版本)对于每一个具有稳健POA的最小成本博弈G（G)，每个结果序列1、……T满足（18)每一个玩家，每一个结果*G的，
当T．
Blum等人。3.是第一个考虑这类界限的人，称其为“完全无政府状态的代价”。
我们重申，与仅适用于纳什均衡的边界相比，定理3.2中的边界类型明显更有说服力，而且对博弈及其参与者的假设要少得多。虽然纳什均衡很难找到或不可能找到，但有几种计算效率高的“现成”学习算法具有良好的收敛速度，可以保证在任何博弈中生成平均遗憾消失的结果序列(例如，Nisan等人的第4章)。17)．当然，定理3.2中的保证并没有提及玩家在玩游戏时使用的学习算法(如果有的话)，无论出于什么原因，只要重复的联合游戏后悔程度较低，这个边界就适用。
注释3.3(定理3.1和3.2):定理3.1和3.2本质上是等价的，因为其中任何一个都可以从另一个推导出来。原因是博弈的粗相关均衡集恰好是(任意长)序列的经验分布的闭包，其中每个参与者的平均遗憾都是非正的。
备注3.4(相关均衡和掉期遗憾)遗憾有一个更严格的概念交换后悔在这种情况下，博弈的相关均衡与每个参与者都有非正(交换)遗憾的结果序列之间存在类似的对应关系。也有计算效率高的“现成”学习算法，保证每个玩家在任意游戏中消失平均交换遗憾。10，12
4.拥挤游戏很紧张
一组允许的结果的最坏情况POA只会随着集合的增大而增大。本节证明，在成本函数受限的拥堵博弈中，最坏POA为完全一样对于每一个平衡的概念图1．我们证明了这一点，证明了光滑性论证，尽管它们具有自动的普遍性，但在POA上提供了一个严密的边界，即使是纯纳什均衡．
更准确地说，让
表示一组成本最小化对策，并假设在这些对策的结果上定义了一个非负目标函数。让
表示参数值(，)，这样每一局Is(，)-平滑。让
表示具有至少一个纯纳什均衡的博弈，且纯（G)博弈中纯纳什均衡的POA
规范的三行证明(3)(5)表明对于每个(，)和每一个G
，纯（G) /(1)。我们称之为一组游戏紧如果(，)的合适选择相等而且．
定义4.1(紧凑的游戏类别):一组就是游戏紧如果
(20)的右边是可以通过平滑论证证明的最佳最差情况上界，它适用于中所示的所有集合图1．(20)的左边是纯纳什均衡的最坏情况POA对应于最小的集合图1至少有一个纯纳什均衡的博弈。左边是右边的上界，这让人联想到“弱对偶性”。紧类游戏的特征是min-max条件(20)，这可以被松散地解释为“强对偶型”结果。c在竞争激烈的游戏中，每一个纯纳什均衡的最坏情况POA的有效上界被合适的光滑性论证所取代。因此，每一个这样的边界，无论它是否被证明使用平滑论证“内在稳健”，因为它适用于所有的结果集图1．
回顾例2.4中拥堵对策的定义和符号。在这里，我们考虑任意的非负和非递减的成本函数ce．拥堵对策中最坏情况POA取决于允许代价函数的“非线性程度”。例如，对于系数非负且次数最多的多项式代价函数d，拥挤博弈的最坏POA是有限的，而在拥挤博弈中是指数的d．1，2，7，18
例2.4表明，如果为具有仿射代价函数的拥塞对策集，则(20)的右侧最多为5/2。Awerbuch等人的结构。2还有克里斯托多卢和库特苏皮亚斯7证明(20)的左边在这类游戏中至少是5/2。因此，具有仿射代价函数的拥塞对策形成了一个紧类。我们的最终结果表明，这一事实并非侥幸。
定理4.2:对于每一个非递减的正代价函数的非空集合C, C中包含代价函数的拥塞对策集是紧的．
除了表明光滑参数总是给出拥堵博弈的最佳POA边界外，该结果及其证明还暗示了具有非多项式代价函数的拥堵博弈的第一个POA边界，以及拥堵博弈中POA的普遍最坏情况示例的第一个结构表征。
定理4.2的证明是技术性的，我们只提供一个高层次的提纲;完整的证明可以在完整版本中找到。22对于下面的讨论，固定一个集合
成本函数。第一步是利用这样一个事实，即在拥挤游戏中，目标函数和玩家的成本函数是资源的累加E．这减少了对满足定义2.1条件(2)的参数(，)的搜索，以及每一对s, s *游戏中的结果，到搜索满足的参数(，)
对于每个成本函数c，非负整数x、正整数x*。该条件与例2.4中的(6)相同是仿射代价函数的集合。
证明的第二步是理解在“可行区域”上最小化目标函数/(1)的优化问题
，在那里表示满足上述条件(21)的值集合(，)。这个优化问题与(20)的右边几乎相同，它有几个很好的性质。首先，只有两个决策变量包含在平面内。其次，虽然有无限多的约束(21)，但每个约束在和中都是线性的。因此,是半平面的交点。第三，目标函数/(1 -)是递减的两个决策变量。因此，忽略一些可以单独处理的边界情况，使目标函数最小化的(，)的选择位于的“西南边界”上，并可表征为独特的点它相等地满足形式(21)的一对特定约束。
证明的第三部分也是最具技术含量的部分是在(20)的左边显示一个匹配的下界。构造背后的直觉是安排一个拥堵游戏，其中每个玩家有两个策略，一个使用少量资源，另一个使用大量资源的分离策略。在最优结果中，所有参与者都使用他们的小策略并产生低成本。(这个结果也是一个纯纳什均衡。)在次优纯纳什均衡中，所有的参与者都使用他们的大策略，从而“淹没”所有的资源，并产生巨大的成本。这种次优结果如何作为纳什均衡持续存在?如果一个参与方单方面偏离战略，它就能从策略中获得更少的资源，但现在每一种新资源的负载都比之前使用的每一种资源多出1个负载。在优化的情况下，这种构造产生了一个拥塞博弈和一个纯纳什均衡，其代价大于最优结果的a /(1)因子，其中(，)为证明第二步中确定的最优平滑参数。
注释4.3(所有代价函数的POA边界):定理4.2给出了代价函数为任意集合的拥塞博弈中最坏POA的第一个解．当然，精确计算最坏情况POA的确切值并非易事，即使对于简单的集合也是如此．Aland等人的论点。1和Olver18隐含了最坏情况POA的(复数)闭合表达式是系数非负的多项式的集合。对于其他一些简单的集合，类似的计算应该是可能的．更广泛地说，定理4.2的第二步和第三步表明，当存在特定集合时，如何在最坏情况POA上分别给出良好的上界和下界感兴趣的。
注释4.4(最坏情况拥塞博弈):定理4.2证明的第三步构造的细节表明，双向循环上的路由博弈是POA的通用最坏情况例子，无论允许的代价函数集是什么。这个推论是对的一个更简单的充分条件的模拟原子拥挤游戏中有连续的玩家，每个人的大小都可以忽略不计，在适度的假设下，在双节点双链路网络中，最坏情况POA总是实现的。21
5.进一步相关工作
首先研究无政府状态的代价的是库特苏皮亚斯和帕帕迪米特里欧14在游戏调度中最小化最大完成时间。这不是一个和目标函数，并且这个模型中的最坏情况POA对于不同的平衡概念是不同的。3.，14参见Nisan等人的第20章。17对于这一模型的文献调查。
首先在Roughgarden和Tardos中研究了具有和目标的POA24对于非原子的自私路由游戏。Awerbuch等人给出了(原子)拥塞对策纯纳什均衡的POA及其加权变体的第一个一般结果。2Christodoulou和Koutsoupias，7对具有仿射代价函数的博弈给出了较紧的边界，对具有非负系数多项式代价函数的博弈给出了较近的上下界;后一类的匹配上界和下界后来分别在Aland等中给出。1和Olver。18
许多以前的工作认识到更一般的POA边界的可能性和动机。纯纳什均衡的POA的基本边界几乎在所有这些情况下都可以表述为光滑性论证，所以我们的可拓定理立即暗示了，并经常加强了，这些已经证明过的鲁棒边界。具体来说，Aland等人，1Awerbuch等人，2Christodoulou和Koutsoupias，7和Vetta25纯纳什均衡的最坏情况POA上界很容易延续到混合纳什均衡。在Christodoulou和Koutsoupias，6在具有仿射代价函数的非加权和加权拥塞博弈中，相关均衡的最坏情况POA与纯纳什均衡的最坏情况POA相同。Blum等人。3.重做并推广了纯纳什均衡的最坏POA的几个边界，以证明无后悔序列的平均目标函数值也具有相同的边界。它们的应用包括有效的效用游戏25以及Awerbuch等人的(次优)界。2还有克里斯托多卢和库特苏皮亚斯7对于多项式成本函数的无加权拥挤博弈，以及常和位置博弈和公平目标，这不在我们的框架之内。
我们的双参数平滑定义在以前的几篇论文中都有隐含的版本，在每种情况下都是针对特定的模型，没有任何对健壮POA保证的一般应用:Perakis19对于具有不可分代价函数的非原子路由模型，Christodoulou和Koutsoupias6对于带有仿射代价函数的拥堵博弈，以及Harks11用于可分裂的拥挤游戏。
6.结论
纯策略纳什均衡，即每个参与人都确定地选择一个策略，通常比混合纳什均衡，相关均衡和粗相关均衡更容易解释。另一方面，对于更一般的均衡，无效率保证是至关重要的，原因有以下几点:纯纳什均衡并不总是存在;它们可能难以计算，即使它们被保证存在;即使可以通过集中算法有效地计算，它们也可以避开自然学习动态。
本文提出了一个扩展定理，它以“黑箱”的方式自动将纯纳什均衡的无政府状态价格边界扩展到上面列出的更一般的均衡概念。这种可拓定理只能在某些条件下存在，其关键思想是限制所用的证明方法来限制纯纳什均衡的无政府状态的价格。我们定义了光滑对策，以形式化规范的证明方法，其中纳什均衡假设只在最小的情况下使用，并证明了光滑对策的一个扩展定理。在我们看来，许多研究了无政府状态代价的游戏都是平稳游戏。d对于代价函数任意受限的拥塞对策基本模型，证明了该正则证明方法保证在最坏情况POA上产生最优上界。从这个意义上说，拥堵博弈的POA边界是“内在稳健的”。
致谢
这项研究得到了NSF CAREER Award CCF-0448664、ONR青年研究者奖、AFOSR MURI奖和Alfred P. Sloan奖学金的部分支持。
参考文献
1.Aland, S.， Dumrauf, D.， ging, M.， Monien, B.， Schoppmann, F.多项式拥塞博弈的无政府状态的确切价格。康普特。40， 5(2011)， 12111233。
2.aberbuch, Azar, Y.， Epstein, A.路由不可分割流的价格。在第37届ACM计算理论年会论文集(2005), 5766。
3.布鲁姆，哈加加伊，M.，利格特，K.，罗斯，A.遗憾最小化和完全无政府状态的代价。在第40届ACM计算理论年会论文集(2008), 373382。
4.Caragiannis, I.， Kaklamanis, C.， Kanellopoulos, P.， Kyropoulou, M.， Lucier, B.， Leme, r.p.， Tardos， É。关于广义二次价格拍卖均衡的效率。提交了2012条。早期版本出现在FOCS， '10, EC， '11．
5.陈X，邓X，滕善和。求解两博弈者纳什均衡的复杂性。J. acm 563(2009)。
6.王晓明，王晓明。线性拥堵对策相关均衡的混沌代价与稳定性。在第十三届欧洲算法年会论文集(ESA)，卷3669计算机科学课堂讲稿(2005), 5970。
7.有限拥塞博弈的无政府状态代价。在第37届ACM计算理论年会论文集(2005), 6773。
8.Daskalakis, Goldberg, p.w.， Papadimitriou, C.H.纳什均衡计算的复杂性。康普特。39， 1(2009)， 195259。
9.法布里康德，帕帕迪米特里欧，塔尔瓦尔，K.纯纳什均衡的复杂性。在第36届ACM计算理论年会论文集(2004), 604612。
10.福斯特，D.，沃拉，R.校准学习和相关平衡。游戏经济。Behav 21。(12)(1997)， 4055。
11.可分裂流网络游戏中的策略与共谋。第六届近似和在线算法国际研讨会论文集(WAOA'08)(E. Bampis和M. Skutella主编)。第5426卷信号(2008), 133146。
12.哈特，马斯-科莱尔，A.一个导致相关平衡的简单自适应过程。费雪68， 5(2000)， 11271150。
13.r.d. Kleinberg, G. Piliouras, Tardos， É。在拥塞游戏中，乘法更新优于一般的无后悔学习。在第41届ACM计算理论年会论文集(2009), 533542。
14.Koutsoupias, E, Papadimitriou, C.H.最坏情况均衡。在第十六届计算机科学理论方面年会论文集，第1563卷计算机科学课堂讲稿(1999), 404413。
15.平滑的极限:无政府状态价格边界的原始-对偶框架。在第六届互联网与网络经济国际研讨会(WINE)(2010), 319326。
16.纳什，J.F.平衡点在N人游戏。Proc。国家的。科学36， 1(1950)， 4849。
17.尼森，N.，罗斯加登，T.，塔多斯，É。瓦齐拉尼(Vazirani)， V。算法博弈理论。剑桥大学出版社，2007。
18.无政府状态的代价和基于优先级的路由模型。硕士论文，麦吉尔大学(2006)。
19.非线性和非对称成本下的“无政府状态的价格”。数学。③。> 32， 3(2007)， 614628。
20.具有纯策略纳什均衡的一类博弈。Int。J.博弈论， 1(1973)， 6567。
21.无政府状态的价格与网络拓扑无关。j .第一版。系统。Sci 67。， 2(2003)， 341364。
22.无政府价格的内在稳健性。在第41届ACM计算理论研讨会(STOC)(2009), 513522。
23.不完全信息游戏中无政府状态的代价。在第十三届ACM电子商务会议(EC)(2012)。
24.T. Roughgarden, Tardos， É。自私路由有多糟糕?J. acm 49， 2(2002)， 236259。
25.竞争社会中的纳什均衡，应用于设施选址、交通路线和拍卖。在第43届计算机科学基础年会论文集(2002), 416425。
脚注
a.无政府状态价格边界不能作为平滑证明的最常见原因是，纳什均衡假设被用于假设偏差这是其他参与人均衡行为的函数年代-我．在大多数情况下，混合纳什均衡的最坏POA严格比纯纳什均衡的最坏POA差，因此不存在无损扩展定理。
b.集合函数V: 2E
是子模块如果V（XY) +V（X
Y）V（X) +V（Y)X, YE．
c.参见Nadav和Roughgarden15对于平衡概念和POA界之间对偶性的形式处理。
d.从这篇文章的会议版本开始，平滑游戏的定义在许多方面得到了完善和扩展，并且在许多有趣的模型中发现了新的平滑论证。查看完整版本22有关详情及参考资料。
本文的原始版本发表在第41届ACM计算理论年会论文集2009年5月。
数据
图1。纯纳什均衡的推广。“PNE”代表纯纳什均衡，“MNE”代表混合纳什均衡，“CorEq”代表相关均衡，“No Regret (CCE)”代表粗相关均衡，它们是每个参与者都没有(外部)遗憾的重复联合博弈对应的经验分布。
©2012 acm 0001-0782/12/0700 $10.00
允许为个人或课堂使用部分或全部作品制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。除ACM外，本作品的其他组件的版权必须受到尊重。允许有信用的文摘。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，都需要事先获得特定的许可和/或费用。请求发布的权限permissions@acm.org传真(212)869-0481。
数字图书馆是由计算机协会出版的。版权所有©2012 ACM, Inc.
没有找到条目