文献翻译(一) 负载均衡博弈中稳定平衡低效比的更严格约束
Tighter bounds on the inefficiency ratio of stable equilibria in load balancing games
作者信息及概要
作者： Akaki Mamageishvili, Paolo Penna
作者单位： Department of Computer Science, ETH Zurich, Switzerland
刊名： Operations Research Letters, 2016, Vol.44 (5)
来源数据库： Elsevier Journal
DOI： 10.1016/j.orl.2016.07.014
关键词： Nash equilibria; Load balancing games; Potential games; Price of anarchy
概要：在本文中，我们研究了由Asadpour和Saberi（2009年）提出的负载平衡游戏平衡稳定的低效率比。我们证明更严格的上限和下限分别为7/6和4/3。将该问题中最知名的边界（分别为19/18和3/2）进行了改进。相当于得到了如何令 L2的范数可以近似与L∞的范数(最大完工时间)相同的机器调度达到最佳的问题的结果。
关键词：纳什均衡 负载均衡博弈 潜在博弈 无政府状态的价格
简介
负载均衡问题是在参与者都自私而理性博弈环境中仍旧被积极研究的经典的优化问题。这些博弈的资源分配问题是典型的使用者(参与者)不会因为无私的行动导致系统次优分配。自然地，人们可以认为最优的社会是最大完工时间的最小分配，也就是说，所有机器的最大负载（一种经典的效率估算）。与此相反，在博弈论的分配中，每个参与者努力优化自己的工作成本。这通常将导致所谓的纳什均衡，即没有参与者能通过将工作转移到其他机器受益的一种分配。在这项工程中，我们认为这是纯纳什均衡，也就是参与者选择的策略分配和单边偏差是没有益处的。一般情况下，博弈也可以拥有混合纳什均衡中参与者根据概率分布选择分配的情况。纳什均衡的效率低下是算法博弈论的核心主题，它测定了多么自私时会妨碍优化。
Asadpour和Saberi 提出并研究了在几种博弈中的低效比例稳定平衡(IRSE)，包括负载平衡的人（见 2）。这个概念量化了在博弈中 当参与者选择某些噪音最优反应动态时的效率损失（见 1.2）。对于负载均衡博弈，IRSE还有一个非常简单和自然的解释（利益更独立而且研究的更早）：
L2范数（机器负载的平方和）的最小分配对于 L∞范数（最大完工时间）来说也足够好吗？
直观上，当社会成本是通过L∞范数（最大完工时间）测量时，参与者共同减少L2范数（博弈可能性）。因此，如果每一个最小分配L2范数自动成为L∞范数的近似c值，负载平衡博弈的IRSE等于一定值c。也就是说，这种分配的最多完工时间就是c的最优完工时间。相对于其他措施相关的低效平衡来说，IRSE的准确约束是不可知的（见 1.2）。Asadpour和Saberi证明了IRSE的上限3/2上IRSE并观察了Alon等人的例子，证明了IRSE的下限19/18。
我们的贡献
在这项研究中，我们改进了负载平衡博弈的IRSE的上限和下限：
• 在第三节，我们展示了改进后的下限的7/6。以前Alon等人的下限是通过一个含有三个机器和六项工程的简单实例获得，而我们的结果是通过基于及其数目的族实例得到。值得注意的是，我们的解释改进了以往三机器的下限13/12。随着机器数量的增加，下限趋近于7/6。
• 在第四节，我们将上限提高至4/3。直观地说，证明由分配的费用超过4/3最佳的完工时间的所有分配方式构成，我们通过减少潜在的方式重新分配工作，比如L2范数。这是和Asadpour、Saberi相同的数据。我们的技术贡献是证明有两种方式来“改组”这些工作，从而使其中的一个减少潜在。
综上所述，这些结果可以通过所有工程的L2范数的最小分配被证明近似等于4/3所重申，而在某些情况下，L2范数的最小分配至少是最佳完工时间的7/6。将上限和下限之间的差距缩小仍然是一个悬而未决的问题，我们将在第四节讨论这个问题。在下一节中，我们将讨论与从前的研究的进一步的关系，包括博弈中均衡质量的研究。
结果意义及相关工作
纳什均衡的效率往往是通过两种经典概念衡量：由Koutsoupias和Papadimitriou为了基于机器的负载均衡博弈引进的无政府状态的价格（POA），和Anshelevich等人引进的稳定状态价格（POS），即分别将最好和最差纳什均衡与最优社会进行比较。在某些情况下，这些概念可以被视为太极端，因为它们可能包含“不现实”均衡。
IRSE研究了被某些噪音最优反应动态选择的均衡数量。直观地，这些动态最可能停留在博弈潜能的纯纳什均衡，并且IRSE可以被看作是这些选定均衡的无政府状态价格。该IRSE也在潜在最优的POA的名义下的濑和牧野的文献中被提及，被认为是类似于Correa等人的《潜在最优POS》中研究的初期潜在最优POA的生产配送网络路由模型，尽管名称不同。在负载平衡博弈（和其他几种博弈）中，我们知道 ，这在一定意义上证明了POS和POA要么是过于悲观，要么是过于乐观。具体地说，在m台机器中，在IRSE介于19/18和3/2之间时， 且 。后者的约束在现在的论文中被提高至 。这意味着参与者可以很容易地通过这些简单的动态计算出一个4/3（或更好）的最佳近似值，而且在某些情况下的动态是不可能选择最优或近似最优的解决方案的（也就是说在有元素小于7/6的情况下）。
上限4/3被也有一个有趣的比较。在Hassin和Yovel的著作《顺序POA》中，对于这些博弈：参与者在一个各个参与者能推断其他参与者的未来的举动的扩展形式博弈中。这是一个有趣的问题，在这个问题中，两个动态能在最后得出更好的完工时间。
预备知识
在负载均衡中有重为W1，……，Wñ的有n个工程，把他们放在m个机器中（每个工程分配给一台机器）。工程的分配决定了每台机器j的负载lj，这是被分配给这台机器的工程权重的总和。目标是找到具有最低完工时间的分配方式，即所有的机器中的最大负载。
在负载均衡博弈中，每个工程是一个参与者，他们可以选择m种可能中的任何机器。参与者i的成本是参与者选择的机器的负载，并且每个参与者的目的是最大限度地降低自己的成本。所有参与者的工作分配形成总体的策略（在博弈论的术语中，这是策略组合）。
令完工时间最小的分配方式被称为“社会最优”，其完工时间被称为“社会最优跨度”。与这种“潜在”有关的分配方式是对应的机器的负载的平方的总和，l12+…+1m2，其中，lj是机器j在这个分配方式中的负载。令潜在函数最小的分配方式被称为潜在的优化配置，或者是简单的“潜在优化”。
众所周知，负载平衡博弈等同于带有上述潜在函数的潜在博弈。这意味着所有的纯纳什均衡（没有参与者能通过将工作转移到其他机器受益的一种分配），实际上是潜在的“局部最优”（不能降低潜能的单个工作转移）。Asadpour和Saberi 提出并研究IRSE，也就是最差的潜在优化分配方式工作时间和社会最优工作时间之间的最大比率（包括博弈中的所有例子）。
潜在最优分配方式满足下述条件（参见图1）。将每台机器的总负载划分两部分工程，也就是lj=xj+yj。其中，xĴ是分配给j的工程子集（可能为空）的负载总和。如果两台机器i和j满足xm<xj，那么ym≥yj否则将xm和xj交换。纯纳什均衡满足这个宽松的条件，也就是如果移动到另一台机器j中的话，在机器i中的单个工程k不会增加，即lm-wķ≤lĴ。
改进下限
在本节中，我们改进了IRSE的下限19/18。证明的思路是构建一个实例，也就是在单个机器具有“更高”负载的情况下，潜在最优是可以达到的，并且所有其他机器具有相同负载（图2左）。当最优完工时间相反：一个机器含有“更低”负载，其他所有机器含有同样的更高负载（图2右）。
### 定理3.1
负载平衡博弈的IRES至少为 7/6。
证明：
考虑图2中的实例，其中M=K+1≥3，N=2K+2，并且工程的负载是K，K，K，K+1，K+1，…，2K-1,2K-1，(5K-1)/2。我们证明了当右侧具有最佳完工时间时，在左侧令潜在函数最小（见图），因此得出：
它令m趋近于无穷时IRSE趋近于6/7。首先要注意，两种分配方式的潜能是相同的。考虑所有工程分配并且不遗漏一般性假设，负载最大的工程在机器1上。如果我们机器1上固定负载，那么，平衡了其他机器的负载的任何工程的潜能达到最小（包括机器1上所有带有固定负载的分配方式）。因此，如果最大的工程是单独在机器1上的，那么潜能是社会最优情况下的最小值，而如果它与负载最小的工程一同位于机器1上，那么在工程分配像图二左侧一样时，潜能达到最小。如果机器1上的负载严格大于(5K-1)/2+ K，那么由于图1中的属性描述，这种分配方式不是潜在最优。我们推断两种分配方式都是潜在最优的，尤其是在给出了下限IRS的E左侧。
改进上限
在不遗漏一般性假设的情况下，社会最优完工时间等于1，并且在潜在最优中的机器负载根据非增顺序进行分类：
l1 ≥l 2 ≥⋯≥l m。
定理4.1
负载平衡博弈的IRSE最多为 4/3。
证明：
我们必须证明l1 ≤4/ 3。假设它不成立，即l1=1+α>4/3，这意味着α>1/3。机器1包含至少两个工程，否则最优完工时间不会是1。我们将机1上最小的工程称为s，它严格大于α，否则由于lm<1，我们可以通过将s移动到最后的机器上来降低潜能。假设s的负载是α+β，其中β> 0，并且由于α+β≤l1-α-β=1-β，这意味着β<1/3 <α。该定理的证明是基于潜在最优分配方式的属性（其证明推迟）（参见图3）。
引理4.2
对于任何 α> 1/3，在潜在最优分配方式中，每台机器必须具有负重至少为1-β的一个工程，或负重严格大于α的两个工程。
注意，因为α>1/3与最优完工时间为1的事实相矛盾，任何机器1的工程负重大于α并且这些工程不能在超过1的情况下分配给m-1台机器（显然在机器1中的工程不能放在一起，几个三个负重为α的工程、一个1-β的工程和一个α的工程也分别不能放在一起）。
证明:
接下来我们证明了引理4.2。首先观察到lm≥1-β，否则，我们将工程s从机器1移动到机器i并且降低潜能。将机器i中的工程依据负重增加进行排序，并考虑一部分小的工程，这样负载在把他们移回机器后仍大于或等于1-β（这一部分可以为空）。设x为该部分的总负重，并且y是那些由于移动负载减小到低于1-β的工程的尺寸。那么
（1）
还要注意
X + y ≥ α + β （2）
否则，我们可以将机器1的工程s和机器i上的负重为x+y的工程集群进行交换，并且严格减少潜能。如果y是移除x后的唯一工程，那么显然y≥1-β并且引理成立。否则，我们表明y≥α。我们接下来基于机器i的负载li区分两种情况（见图4）：
（li<1）
从第一个不等式（1）我们得到x<β，再由（2）得出y>α。
（li≥1）
如果点x<β，那么y>α> 1/3使用与前面的情况相同的参数。因此，假设x≥β和y≤1/ 3 <α。设z为机器i的负载，在除去尺寸为x+y的部分后，则li =x+y+z。我们在潜在最优中重新排列工程，并显示，这将进一步降低潜能，从而产生矛盾。工程重新排列如下：
1、工程s从机器1移至机器i。
2、x到y中最小的移动到机器m，最大的移动到机器1。
首先考虑x≤y的情况。然后原始分配方式的潜能和新分配方式的潜能的区别为：
（3）
他们中间的不同是由于lm<1。我们接下来证明了，这个数是正的，并且得到了所需的矛盾。需要注意的是y+z≤lm，否则将负重为x的部分移动到机器m会降低潜能。因此（3）在x中是线性的，斜率为y+z-1≤0，并且由于x≤y，我们可以通过以下公式将其结合：
2(α+y2+2yz+β+βy-(β2+y+αz+αβ+zβ+y） （4）
这个数据是在z中以2y-(α+β)≥x+y-(α+β)≥0。此外，我们有z≥1-β-γ，否则我们可以将工程s和负重为y的部分交换并降低潜能。我们因此可以结合（4）通过以下公式将z和1-β-γ交换：
2(α+2y-βy-y2+β-(β2+y+α-αy+β-β2-βy+y))= 2(y-βy-y2+β -( -αy+β -βy+y))= 2(αy-y2)
由于y<α，它严格为正。这证明，（3）是严格为正。这种情况y<x，与前一个相似。具体而言，现在潜能差距是严格大于更（3） ，将x和y交换，
2(α+xy+yz+xz+β+βx-(β2+x +αz+αβ+zβ+y)) (5)
而这个量在y中为线性，斜率x+z-1≤0，否则将y部分移动到机器m并将降低潜能。在x<α的情况下剩余的证明在将x和y互换后与前面的情况完全相同。如果x≥α我们令y<α并将（5）中y与α交换以达到更低的下限，然后令z为1-β-α：
2(α+αx+xz+β+βx-(β2+x+αβ+zβ+α))= 2(α+αx+x-x(α+β)+β+βx-(β2+x+αβ+β-β(α+β)+α))= 0
其中，在步骤2中，我们从β<α起令x≥β， 正如之前的引理得到的。
这样就可以完成引理4.2的证明。
备注4.3
我们相信，我们的下限的例子不能再被改进。为了证明这种说法人们必须考虑潜在优化的全局属性，而在我们的证明只需要使用本地属性。特别是在引理4.2中，我们只使用了一个只包含三组工程和三台机器的简单的工程“改组”。
致谢：
我们要感谢一位指出引理4.2中错误的一位匿名读者。这项研究由瑞士国家科学基金会（SNF）部分支持，授权号200021_143323 / 1。
参考文献：
1 Noga Alon, Yossi Azar, Gerhard J. Woeginger, Tal Yadid,
Approximation schemes for scheduling
Proc. of the 8th Annual Symposium on Discrete Algorithms, SODA, 1997, pp. 493–500.
2 Elliot Anshelevich, Anirban Dasgupta, Jon M. Kleinberg, Éva Tardos, Tom Wexler, Tim Roughgarden
The price of stability for network design with fair cost allocation
SIAM J. Comput., 38 (4) (2008), pp. 1602–1623
3 Arash Asadpour, Amin Saberi
On the inefficiency ratio of stable equilibria in congestion games
Proc. of the 5th International Workshop on Internet and Network Economics, LNCS, (WINE), vol. 5929 (2009), pp. 545–552
4 Lawrence E. Blume
Population Games
Addison-Wesley (1998)
5 José R. Correa, Andreas S. Schulz, Nicolás E. Stier-Moses
Selfish routing in capacitated networks
Math. Oper. Res., 29 (4) (2004), pp. 961–976
6 Ronald L. Graham
Bounds on multiprocessing timing anomalies
SIAM J. Appl. Math., 17 (2) (1969), pp. 416–429
7 Refael Hassin, Uri Yovel
Sequential scheduling on identical machines
Oper. Res. Lett., 43 (5) (2015), pp. 530–533
8 Yasushi Kawase, Kazuhisa Makino
Nash equilibria with minimum potential in undirected broadcast games
Theoret. Comput. Sci., 482 (2013), pp. 33–47
[9] Elias Koutsoupias, Christos H. Papadimitriou
Worst-case equilibria
Proc. of the 16th Annual Symposium on Theoretical Aspects of Computer Science, LNCS, (STACS), vol. 1563 (1999), pp. 404–413
[10] Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani
Algorithmic Game Theory
Cambridge University Press, New York, NY, USA (2007)