可在www.sciencedirect.com在线获取理论计算机科学电子笔记342（2019）21-38www.elsevier.com/locate/entcs非单局中人的公平成本设施选址对策F'EscarvalhoR o drigue s 1，2EduardoC. Xavier1，3坎皮纳斯大学计算机学院巴西坎皮纳斯GuidoSch？afer4网络和优化（N O）组Centrum WiskundeInformatica（CWI）荷兰阿姆斯特丹摘要在公平成本设施选址博弈中，玩家控制终端，并且必须打开并连接每个终端，一个设施，同时支付连接费用，并平均分担与设施相关的开放费用它连接到。 在大多数文献中，假设每个玩家控制单个终端。 我们探索游戏的更通用版本，其中每个玩家可以控制多个终端。我们证明了这个游戏并不总是具有纯纳什均衡，并决定是否有一个实例的均衡是NP-难的，即使在度量的情况下。此外，我们提出的结果关于均衡的效率，表明这个游戏的稳定性的价格是等于无政府状态的价格，在无能力和能力的设置。关键词：稳定价格，设施选址，算法博弈论1介绍设施选址问题涵盖了广泛的优化问题，在许多不同的领域，如公共政策，城市规划，电信和计算机网络的实际应用在一般意义上，设施选址问题可以表述如下。设F是设施的集合，T是终端的集合，每个设施f∈F的开通费用为cf，连接费用为dtf1这项工作得到了Capes、CNPq和Fapesp的部分支持。2电邮地址：邮箱：fellow. ic.unicamp.br3电子邮件：ecx@ic.unicamp.br4电子邮件：g. cwi.nlhttps://doi.org/10.1016/j.entcs.2019.04.0031571-0661/© 2019作者。出版社：Elsevier B.V.这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。22F.C. Rodrigues等人/理论计算机科学电子笔记342（2019）21用于将终端t∈T连接到设施f∈F。问题是找到一个子集的设施，以打开和建立从终端到这个子集的连接，使所有成本的总和最小化。考虑一个场景，多个超市或商店共享为他们储存物资的大 每家店都离他们支付与在仓库中维护其产品相关的成本以及将其运输到特定位置的运输成本。这样的场景可以被看作是一个设施选址问题，其中每个商店是一个终端，每个仓库位置是一个可能的设施。在经典的优化版本中，仓库公司的观点被优先考虑，每个终端可以被视为由一个中央机构控制，以最大限度地减少全球的开放和连接成本。当我们考虑到每个超市相互竞争的事实，这种全局优化的方法是不可能再被采用。为了分析这种情况，我们可以使用博弈论。非合作博弈是一种决策场景，在这种场景中，代理人或玩家在没有其他玩家协调的情况下，选择一种策略以最大化自己的效用（或最小化自己的成本），这反过来又我们说，如果没有参与者有任何动机单方面改变自己的策略，则游戏处于纯纳什均衡（PNE）。为了比较纯均衡和社会最优的社会成本，我们使用文献中的标准度量：无政府状态的价格（PoA）和稳定的价格（PoS）。游戏的PoA被定义为社会成本最低的PNE与社会成本最优的PNE之比，而PoS是社会成本最优的PNE与社会成本最优的PNE之比。在我们的示例场景中，每个商店传统上被视为选择要连接的设施（仓库）的参与者，以便其自身的成本最小化。然后，每个商店将平均分担与将货物储存在它们所连接的仓库中有关的费用，以及单独支付连接到这种仓库的费用。这个场景举例说明了单公平成本设施选址博弈，其中每个商店由单个玩家控制。然而，这种情况无法适应多个超市或商店是同一连锁店的一部分的常见情况。当商店是同一个大集团的一部分时，每个商店的行为不能 可以说是独立的和不协调的，但是一个整体组不与其他竞争对手商店或连锁店协调，因此通过允许玩家控制多个商店或终端来分析这种情况在我们分析的公平成本设施选址博弈中，每个玩家控制多个终端，并且可以同时移动它们以最小化自己的成本。对于单例游戏，终端平均分担开场费用意味着玩家平均分担这些费用，因为玩家和终端在这些场景中实际上是相同的。然而，当玩家控制多个终端时，情况就不一样了。在我们的论文中，我们使用公平成本一词来表示，在任何策略剖面中，每个设施的开放成本在所有连接到它的终端之间均匀分摊，即。如果在某个策略中，玩家A有两个终端连接到A，F.C. Rodrigues等人/理论计算机科学电子笔记342（2019）2123设施F和不同的玩家B具有连接到它的单个终端，玩家A将支付F的三分之二的开启成本，而玩家B仅支付开启成本的三分之一。在这项工作中，我们研究了在这些公平成本的设施选址博弈中找到纯纳什均衡有多难，以及与社会最优成本相比，这些均衡有多有效。最后，我们将我们的结果扩展到这些游戏的加权和容量限制的版本2相关工作和组织从博弈论的角度来研究设施选址问题的研究成果很多.有效效用博弈[12，14，18]的类别可以被视为设施博弈，当设施和玩家都由单个体玩家控制时。博弈论中有一个完整的领域集中在合作博弈上，Goemans和Skutella[8]研究了合作设施选址博弈。设施选址也从机制设计的角度进行了广泛的研究，在设施选址问题的变体的防策略机制中有多项相关工作[5，13，15]。本文研究了局中人控制终端的非合作设施选址博弈，每个终端在所有连接到f的终端之间平均分担其所选设施f的开放费用。这些博弈与连接和网络设计博弈有很大的相似性，因此这些博弈的多个结果对于公平成本设施选址博弈是有效的对于单例公平成本设施选址博弈，网络设计[1]的结果扩展到设施选址，PoA的界为k，PoS的界为Hk=Θ（logk）[17]。对于度量版本，其中每个连接都服从三角不等式，Hansen和Telelis[9]证明了PoS和强PoA的常数界此外，当存在与终端相关联的权重确定每个终端支付多少开通成本时，它们表明总是存在e-近似均衡，并且PoS可 以 在 Θ （ logW ） 中 ， 其 中 W 是 所 有 终 端 权 重 的 总 和 。 在 [3] 中 ， Chen 和Roughgarden证明了加权网络设计博弈中存在不存在可能的PNE的情况，但这是否同样适用于加权公平成本设施选址博弈仍然是一个悬而未决的问题，即使是非单例版本。对于设施选址博弈，参与者在如何分担开放成本方面没有任何限制，无政府状态的代价和稳定性的代价已经被Cardinal和Hoefer证明为Θ（k）[2，11]，其中k是博弈中参与者的数量。此外，对于非单例游戏，决定一个实例是否有PNE是NP困难的[2]。Rodrigues和Xavier[16]考虑了这个游戏的能力限制版本。结果表明，对于度量单点公平成本设施选址博弈，PoA可以是无界的，而PoS是Hk，其中k是参与者的数量.此外，他们表明，这是NP-难决定是否有PNE在单容量限制的设施选址游戏与任意开放的成本分担。24F.C. Rodrigues等人/理论计算机科学电子笔记342（2019）21对于设施位置的顺序版本，他们表明，度量版本有界PoA和PoS。本文将Cardinal和Hoefer [2]的结果推广到公平成本设施选址问题，证明了即使在度量的情况下，只要允许局中人控制多个终端，在这个博弈为此，我们证明了有公平成本的设施位置游戏的情况下，没有PNE。我们在Chen和Roughgarden在[3]中使用的加权网络设计游戏中没有PNE的情况下证明了这一点。最后，我们证明了这个游戏的PoS可以作为无效的PoA无能力限制度量的情况下，一般的能力限制的情况下。在第3节中，我们给出了理解我们的论文和定义我们的游戏所需的正式定义。在第四节中，我们提供了没有PNE的实例，证明了PNE存在的NP-困难性，并将这些实例与加权博弈联系起来。在第5节中，我们证明了在无能力和有能力的公平成本设施选址博弈中，稳定性的代价和无政府状态的代价一样低。最后，在第6节中，我们提出了我们的最后意见，并讨论了未来的工作。3预赛首先，我们从非合作博弈论中定义一些关键概念在博弈论中，非合作博弈是一种参与者独立选择策略的场景，试图最大限度地降低成本或最大限度地对于每个参与人i，都有一组行动Ai，它可以选择进行。一个纯策略Si由Ai的一个动作组成，而一个混合策略对应于Ai上的概率分布。 在一个纯博弈中每个玩家选择一个行动而在混合博弈中，每个参与者根据概率分布随机化其行动。在本文中，我们假设纯策略游戏，除非另有说明。一组策略S=（S1，S2，...，S n）由每个参与者的一个策略组成，称为策略配置文件。 设S = A1×A2×.. . ×An是所有可能的策略分布的集合，令c：S →Rn是一个成本函数，它为给定策略分布S的每个参与者i赋予成本ci（S）。 定义S−i=（S1，...，Si−1，S i+1，.，S n）一个没有i策略的策略剖面S，这样我们可以写S =（Si，S-i）。如果除i之外的所有参与人都选择S−i，那么参与人i面临的问题是如何确定S − i的最佳对策。参与人i的一个策略S i是对S − i的最佳对策，如果没有其他策略可以给参与人带来更好的结果，即。ci（Si，S−i）≤ci（Si，S−i），<$Si∈Ai.如果没有参与者可以通过选择不同的策略来降低成本，则策略剖面处于纯纳什均衡（PNE）中，即对于每个参与者，策略剖面中的策略是最佳对策。社会福利或社会成本是一个函数，它将一个策略配置文件映射到一个实数，表示游戏的总成本或支付的度量。效率分析的两个最重要的概念是无政府状态的价格（PoA）和F.C. Rodrigues等人/理论计算机科学电子笔记342（2019）2125ΣΣ稳定的价格（PoS）。PoA是具有最坏可能社会成本的纳什均衡与具有最优社会成本的战略分布之间的比率，而PoS是最好可能纳什均衡与社会最优之间的比率。有了这些概念，我们定义了公平的设施选址博弈费用分摊（FLG-FC）。定义3.1设G=（T<$F，T×F）是一个二部图，F有n个设施，T有m个终端。每个设施f∈F有一个开放成本cf，每个终端t∈T有一个连接成本dtf。令K={1，...，k}是参与者的集合。每个参与者i控制终端Ti~T的子集（也形成分区T），每个终端必须连接到一个开放的设施。 当一个播放器只控制一个终端时，它被命名为单例播放器。参与人i选择策略SiTi×F.令S =（S1，...，S k）是一个战略配置文件。我们滥用符号，用表达式f∈S来表示策略剖面S中连接到终端的任何设施f，用（t，f）∈S来表示在S中连接的任何一对终端和设施，而f∈Si表示参与人i用来连接策略Si中的一个终端的任何设施。每个玩家都试图将自己的支付额降到最pi（S）=（t，f）∈Sicf+xf（S）（t，f）∈Sidtf，其中x f（S）=|{（t j，f）∈ S i|1 ≤ i ≤ k <$1 ≤ j ≤ m}|是策略配置文件S中连接到设施f的终端的数量。策略S的社会福利成本定义为所有参与者支付的总和，即，C（S）= p i（S）= c f+ d tf。在具有一般连接成本的博弈中，某些连接（t，f）应该在任何解中避免，因为它们不存在。在这种情况下，我们假设他们有一个非常大的常数成本Ud。对于一般成本，如果连接未显示，则假定其成本等于Ud，除非另有说明。对于度量连接成本，其中连接成本必须服从三角不等式，假设任何未示出的连接（t，f）的成本等于从显式示出的连接形成的无向图中从t到f在处理容量受限的FLG-FC时，我们将此定义扩展为包括每个设施的能力，以及强制玩家提出有效解决方案的方法。定义3.2设G=（T<$F，T×F）是一个二部图，F有n个设施，T有m个终端。每个设施f∈F都有一个开放成本cf和一个容量uf，表明在任何给定时间有多少终端可以连接到f此外，对于每个对（t，f），存在连接成本dtf，其中t∈T，f∈F。i∈Kf∈S（t，f）∈S26F.C. Rodrigues等人/理论计算机科学电子笔记342（2019）21ΣΣ给定一个策略轮廓S，对于具有公平成本分摊的能力限制设施选址博弈，参与者i支付的定义pi（S）和社会成本C（S）与之前的无能力限制博弈相同。然而，为了确保遵守容量限制，如果解决方案S中的参与者i的终端之一连接到f，其中xf（S）> uf，则向参与者i的支付添加过大的恒定成本Uc，即，它支付pi（S）+Uc。4关于纯平衡的存在性纯纳什均衡是博弈论中最著名的解的概念之一虽然不能保证在所有游戏中都存在，但在一些实际场景中，它在更大程度上反映了玩家的行为。FLG- FC的单例版本是一个潜在的游戏，因此总是存在PNE[17]。我们表明，这并不延伸到每一个公平的成本设施的位置游戏，通过显示的情况下，没有PNE时，玩家控制多个终端和开放的成本分摊发生在终端。 我们构建这些实例松散的基础上的一个例子，用于证明不存在的PNE在加权网络设计游戏[3]。我们首先证明了加权公平成本设施选址博弈的结果，然后将此结果推广到未加权度量博弈。4.1加权对策的均衡存在性在经典的设施选址博弈中，假设每个终端对同一设施的货物需求量相同，因此分摊成本的“公平”方式是在在几个实际场景中，一些终端可能需要更多的设施，平均主义的共享可能不会反映公平。在加权公平成本设施选址博弈中，每个终端t都有一个相关的正整数权重wt≥1，每个参与者i都在一个策略剖面S中支付，pi（S）=（t，f）∈Sidtf +（t，f）∈Siwtcf，Wf，S其中Wf，S是策略配置文件S中连接到f的所有终端的权重之和。在这里，我们提供了一个开放的问题，是否有实例没有PNE加权FLG FC的部分答案。我们提供了一个没有PNE的实例，允许玩家控制多个终端。是否存在没有均衡的单例加权实例仍然是开放的定理4.1存在一个只有六个终端的加权FLG-FC博弈的三人度量实例，其中没有PNE。证据F.C. Rodrigues等人/理论计算机科学电子笔记342（2019）2127w3C=W 3f1w2+w+1 -εPBC为w3+εF2w2+w+1f1dt1，f1= 1+3εt1F2dt1，f 2=1Pat2t4Pc332Cf4 =w+w+C=W+Ww2+w+1F3w2+w+1− F3不ε（2w+12ε（2w+13F42w+22周2 +2t5F5t6考虑图1中的实例，这里命名为I。设w > 1为该实例的参数，ε为远小于1的常数。让玩家A控制终端t2和t5，玩家B控制终端t1和t3，玩家C控制终端t4和t6。允许玩家A控制的每个终端具有相同的权重wA=w2，B控制的每个终端具有单位权重wB= 1，并且玩家C控制的每个终端具有权重wC=w。5= 1Fig. 1.没有PNE的加权FLG-FC的游戏实例。除dt1，f1外，所有边的代价都为零.对于参与人P a，只有两种可行策略：要么所有终端都连接到f3，要么t2连接到f1，t5连接到f5。 对于参与人Pc也是如此：要么所有终端都连接到f4，要么t4连接到f2，t6连接到f5。对于玩家P b，终端t1必须在f1和f2之间选择，而终端t3将始终连接到任何PNE中的f5。 该证明是基于玩家P a和P c具有不同的设施偏好时，从玩家P b的镜像选择。为了实现这一点，我们利用了参与人Pa的权重的平方乘以Pc的权重的事实请注意，所有直接连接成本对于Pa和Pc都是相等的，因此不会干扰它们的选择。它们只是确保Pa和Pc在没有直接连接的情况下将其终端连接到设施是没有好处的对于Pb，连接成本的唯一影响是选择连接到f1还是f2。由于参与者Pa的终端的权重为w2，参与者A将总是支付它帮助打开的任何设施的大部分费用。考虑到这一点，我们可以对参与人Pa的五种可能的情况进行排序，按照每种情况产生的成本递增：（i）参与人Pa与Pb共享f1 ，与所有参与人共享f5;（ii）它只连接到f1，与所有参与人共享f5;（iii）它只连接到f3;（iv）它与Pb共享f1，只与P b共享f5;（v）它只连接到f1，只与Pb共享f5下面的不等式说明了为什么会出现这种情况：28F.C. Rodrigues等人/理论计算机科学电子笔记342（2019）21≤f5.Σ.Σ≤f5w2+w+1−ε+w2+ 1=1++1个cf5≤cf1+cf5.+1个+ w+1w2w22cf1+2cf5≤（1）w+1w+w+1w21+C（2）w2+w+1w3+w2w2+w+1−ε2w2 +12周2 + 2=cf3≤（3）w2 .w3w2w 2 w2w2w2+1W2+1个W2W2（四）由此我们推断，对于参与人Pa，优选的情况是参与人Pc连接到f5，即使参与人Pb不连接到f1。对于参与人Pc，我们也这样做，观察到现在决定其策略的设施是f2，因为即使参与人Pa不连接到f5，如果参与人Pb连接到f2，Pc最便宜的是连接到f2和f5。参与人Pc可以从最便宜到最贵，(i)与Pb共享f2，与所有玩家共享f5，（ii）仅与Pb共享f2和f5，（iii）仅连接到f4，（iv）仅连接到f2，与所有玩家共享f5，(v)单独连接到f2，只与Pb共享f5 证明参与人Pc是这种情况的不等式是：wwcf2+2cf5≤（5）w+1Wcf2+w+w+1Wcf5=w3+ww2+ε≤（6）w3+ww2+w+1+εw32w + 12w +2W=cf4≤（7）Ww2+w+1+ε+w2+w+1=cf2+WC（8）w2+w+1cf2+c f5.（九）w+1现在我们用反证法证明这个定理假设存在用于该实例的端子t1可以连接到f1或f2。首先假设t1与f1相连。然后，参与者Pc没有动机连接到f2或f5，如（7）和（8）所示，并将其所有终端连接到f4。由于参与人Pc没有连接到f5，参与人Pa也没有足够的动力连接到f1和f5，如（3）和（4）所示，并将其所有终端连接到f3。这样，玩家Pb单独为f1付费，并且由于f2连接起来更便宜，所以它不在PNE中，因此t1不能连接到任何PNE中的f1现在假设t1和f2相连。参与人Pc现在将通过t4连接到f2，t6连接到f5，如（6）和（7）中的不等式所示。由于参与人Pc连接到f5，现在参与人Pa也将选择连接到f5，因此也将打开f1，如（2）和（3）所示因为f1有参与人Pa和它相连w+1w+1Ww+1F.C. Rodrigues等人/理论计算机科学电子笔记342（2019）2129C =f1w3w2+w+1 -εf1t1F2C =F2w3w2+w+1 +εPat122tw2Pbt3t14tw4PcC =W+W32F3w2+w+1 2w2 + 2-ε（）2周 +12F3F4cf=4w2+w+12w+2W + W +ε（2w+1）3t15t5w2F5t16tw6w2W5=1w32Pb现在有足够的动机将t1连接到f1而不是f2，因此我们的假设不成立。由于将t1连接到f1和f2都不会导致PNE，因此与我们声称在这种情况下存在PNE的说法相矛盾，因此我们已经证明了不存在纯平衡。Q4.2FLG-FC中平衡点的存在性现在我们将定理4.1的结果推广到无权情形。为了实现这一点，我们首先进行关键观察，对于任何具有m个终端的加权公平成本设施选址博弈实例G，存在具有W个终端的公平成本设施选址博弈实例GJ，其具有等价的PNE，其中W是权重w1+···+wm的总和。这是因为对于每个终端t由权重wt>1的参与者i控制，我们可以在GJ中添加终端tj，对于j∈[2，wt]，所有终端都由i控制，具有与t相同的连接和成本。由于它们在成本计算方面在各个方面都是相等的，参与人i在选择连接设施t和增加的终端t j时没有理由分裂策略。定理4.2存在FLG-FC博弈的度量3人实例，其中不存在PNE。证据考虑我在图2中描述的实例。设w >1是这个图上的一个参数，ε是一个比1小得多的常数，这样参与人Pa控制终端 t1，...， t w21周2222和T5，…，t5 ，共2wterminals. 玩家Pb控制两个终端t1和t3，而玩家PC控制终端t1，.， t w和t1，...， t w，4 4 6 6总共2W终端。所有连接成本都是单位成本，dt1，f1，其代价为1 + 3ε. 所有开业费用如图2所示。dt1，f1=1 +3εdt1，f2=1图二.没有PNE的FLG-FC的游戏实例。除了dt1，f1，所有边的代价都等于1.任何未绘制的边（t，f）的成本等于从t到f的最短路径成本。我们通过证明定理4.1中所见的实例（此处命名为I0）可以转化为图2中所见的实例I而不改变参与者的总体策略来证明该定理，因此定理4.1的证明适用于实例I。 首先将I0改为IJ，这样我们就可以分别添加连接到与t2和t5相同的设施（以及相应的连接成本）的终端tJ2和tJ5。2有效地，同时将玩家A的所有终端的权重wA改变为w。在任何纯{{30F.C. Rodrigues等人/理论计算机科学电子笔记342（2019）21在这种情况下，如果我们将任何终端连接到设施f3，那么来自A的所有终端都将连接到它，因为A将支付f3的全部费用。因此，如果t2连接到f3，则终端tJ2也将连接到f3，并且如果t2连接到f1，则tJ2也将这样做。对于TJ5与t5的关系也是如此。 既然如此，如果参与人A到f或f，它仍然会支付完全相同的开业成本份额w2，1 5W（f，S）设施f如I中，其中W（f，S）是连接到的所有终端的权重之和。f在战略配置文件S。因此，实例IJ引起与实例I0相同的玩家决策。对参与者C及其终端t4和t6也可以这样做。因此，为了在保持相同的可能均衡的同时将I0转换为实例I，需要为参与者A和C递增地添加具有相同连接的终端，同时将这些参与者的权重除以添加的终端的数量，直到A控制的终端的数量为2w2（w2的因此，定理4.1适用于未加权度量实例I，并且存在没有任何均衡的3人加权实例IQ使用这个实例的一个版本，其中w= 2作为一个小工具，我们可以证明决定FLG-FC的实例是否有PNE是NP难的。定理4.3判定度量FLG-FC的实例是否有PNE是N P 难 的 。证据首先注意，当玩家控制多个设施时，验证FLG-FC实例的给定解S是否是PNE是NP难的，因为对于每个玩家，我们需要解决仅限于该玩家的实例上的优化设施位置问题。 为了验证参与人的策略 对于最佳对策，我们必须确定所有其他参与人的策略，并检查仅限于此参与人的解决方案是否最小，这是一个NP难题。为了证明PNE存在的NP-困难性，我们将3-SAT问题转化为判定度量FLG FC对策实例是否存在PNE的问题。假设我是来自3-SAT的实例，具有子句C1，...， C q，其中每个子句C j由来自决策变量x1，...， x p在子句范式中，因此子句中的每个文字都可以采用x i或x i的形式来表示决策变量x i。然后，我们如下形成公平成本设施位置实例G：对于每个决策变量xi，我们创建由单个参与者控制的终端ti，并且设施f xi和f xi，并将t i链接到它们，如图3a所示。 每个设施f xi和f xi的开放成本等于可以直接乘以1 +ε。我们在这里直接使用这个术语来区分未显示的连接，这些连接被假设为从终端到设施的最短路径我们为每个子句Cj创建两个小工具：一个没有均衡，除非被第二个小工具稳定，第二个小工具又链接到决策小工具，如图3b所示。对于底部的小工具，注意它与定理4.2中使用的例子完全相同，参数w=2。我们有三名球员在F.C. Rodrigues等人/理论计算机科学电子笔记342（2019）2131AIAIx1的决策小工具x2的决策小工具x3的决策小工具cfx我不是= 4（1+ε）fxiCF我fxi= 3（1+ε）包含xi的子句小工具包含xi的子句小工具(a) 一个用于xi的决策小工具，立场有三个条款，xi和包含xi的两个。(b) Cj=（x1<$x2<$x3）的子句小工具图三.一个决定（a）和一个条款（b）小工具。没有显式成本的绘制边的连接成本为1，任何未绘制的边（t，f）的成本等于从t到f的最短路径成本。这个小工具用于每个条款C，其中玩家Pj控制终端tj，...， TJ和ja2， 1二、四t j，.，t j，玩家P j控制终端t j和t j，玩家P j控制终端五，一5、 4b1 3CJ四、一J四，二J六、一J六、二. 这个小工具的打开和连接成本遵循相同的在定理4.2中，当参数w等于2时，对于链接小工具，每个玩家控制一个终端，对于每个文字，xi或xi在Cj中有一个终端tj可能直接连接到决策小工具中的设施x i（f xi或f xi），连接成本为1，中央设施f j，连接成本为ε，开放成本为2。此外，我们创建另一个终端t bi，它可以直接连接到中心设施fj，连接成本为1，或者连接到设施f j，连接成本为2。现在我们加上AI2从每个终端t到每个设施f的连接服从三角不等式通过将成本dtf设置为由终端和设施之间的连接形成的无向网络中从t到f的最短成本路径假设I有一个真值赋值。然后我们可以为实例G构建以下PNE：如果决策变量xi= 1，则将ti赋值给fxi，否则将ti赋值给f x i。到fx。现在，对于每个出现文字xi的子句小工具Cj，将tj连接到fxTJ的1TJ一个2TJ一个3dtj，fj =ε的1的1dtj，f j =ε一个2一个2dtj，fj =ε一个3一个3CJ = 2个FaFja1CJ = 2Fja2FJ一个3 CJ = 2个1Fa2fa3TJB1TJB2TJB3dtj，fj=2B12dtj，fj=2B22D Jj= 2tb3，f2dtj，fj =1 +3ε11dtj，fj =1个128cj=−εfjf171TJJcj=8+ε1f2f27PJ 一个TJtjt jTJPJ BPJ二，一二、二人二、三二、四TJ四、一tjc四，二TJ3c=−ε 12 9cj=+ε105F37 10FJ3FJ4F47 6TJ五，一 tjt jTJ五、四FJ5TJ六、一TJ六、二五，二五，三cfj =1个5fx1fx2fx3我X不 得双曲余切值.得双曲余切值.得双曲余切值.32F.C. Rodrigues等人/理论计算机科学电子笔记342（2019）21一我如果xi= 1，或到fj如果xi= 0。此外，连接tj艾伊如果xi= 1，则为fj，如果艾比2艾x i= 0。对出现文字xi的子句执行相同的操作最后，连接Cj中的其余端子如下：参与人Pj连接它的终端连接到fj和fj，参与者Pj连接到fj和fj，参与者Pj连接到15b到fj和fj。25c2 5F.C. Rodrigues等人/理论计算机科学电子笔记342（2019）2133AIAIAIbiCbi2biAIAIAIAIAI首先，注意如果xi= 1，则fxi是开路的，并且与所有端子连接 可以直接连接到它，这意味着每个终端支付1 +ε开口成本 同时，在每个出现x i的子句中，f j没有打开，因此终端Tj的最便宜的替代方案成本为2+ε，用于连接到fxi。 或者，如果xi= 0，则设施fxi连接到最便宜的设备上不是开的，tj是因为I有一个令人满意的任务，所以至少有一个终端tj将连接对fj，支付至多2 +2+ε，稳定局中人Pj，Pj诱导的博弈27 4a b和P j. 此外，当xi= 1时，终端t j平衡连接到f j，由于备选设施Fj将要求Tj在开通和连接中支付3AI成本或者，如果xi= 0，则终端tjbi也通过连接到fj而处于平衡状态，因为在这种情况下，它与tj分担开口成本，总共支付2。因此，我们有一个PNE G给定一个令人满意的分配I。现在假设G中存在一个PNE。对于任何条款Cj，至少一个端子tj必须连接到fj，因为否则参与者Pj，Pj和Pj将不会在bi2aBC均衡然后，对于连接到fj的每个端子tj，端子tj必须连接双艾按排一下再（或者f x，如果表示文字x i）。 这是因为如果t，j要爱爱连接到f j，终端t j将不平衡地连接到f j。艾比2注意对于终端tj在连接到设施fxi的条款Cj中，即使当除了T1之外具有直接可能连接的所有端子都连接到它，终端tj仍然不处于平衡状态，因为它打开fj会更便宜支付ε连接成本和2打开成本比支付1作为连接成本，l（1+ε）开口成本，其中l是可以直接l−1到f xi。因此，任何PNE中的终端t i必须连接到f xi或f xi。这表明在G中的任何PNE中，每个子句的至少一个文字在I中的相应赋值中被设置为true。此外，它还表明，不可能有决策变量xi，其中xi= 1和xi= 1。 如果决策变量xi为设xi= 0和xi= 0，则它必须与I的真值赋值无关，因为G处于平衡状态，因此我们可以将xi或xi赋值为1。因此，G中的任何PNE都是一致的，并且可以用于为I.Q请注意，虽然我们在证明中使用了几个参与人，但可以将参与人的总数减少到只有六个。推论4.4即使对于有6个玩家的游戏，确定一个度量FLG-FC是否有PNE也是NP困难的。证据首先注意，在定理4.3的实例G中，对于每个子句Cj，有三个参与者控制多个终端，以及六个单例参与者。此外，对于每个决策小工具，都有一个额外的玩家。我们形成一个新的实例GJ，它具有与G相同的终端、设施和成本，但只有六个玩家。我们注意到，G中的每个子句Gadget是“事实上”彼此隔离的，因为子句Gadget中的终端连接到不同子句Gadget中的设施Cj+1或决策Gadget中的设施所需的连接成本不是直34F.C. Rodrigues等人/理论计算机科学电子笔记342（2019）21接地F.C. Rodrigues等人/理论计算机科学电子笔记342（2019）2135f1t1t2t3F2tk2连接到Cj的能力大于打开它可以直接连接的任何可能的设施因此，我们可以在实例GJ中形成参与者Pa、Pb和Pc，它们控制由参与者Pj、Pj和Pj在任何子句C中控制的终端。此外，我们可以使abcjGJ中的参与者Pa1、Pa2、Pa3和Pb1、Pb2、Pb3控制每个终端tj，tj，tj和j j j的1一个2一个3在任何条款小工具Cj中，tb1、tb2、tb3。类似地，我们可以将决策小工具中的所有参与者加入到GJ中的单个参与者Px中，该参与者控制任何决策小工具xi中的任何终端ti。现在，本副本的玩家总数减少到10人。为了达到六个玩家的数量，我们注意到玩家Pa1与Pb2可以直接连接的设施没有直接连接，因此可以安全地合并为单个玩家Pa1b 2。类似地，参与者Pa2可以安全地与Pb3合并，Pa3可以与Pb1合并，从而导致GJ中的参与者Pa2b 3和Pa3b1。 最后，注意参与者P a在任何子句gadget C j中与f j没有直接联系，因此可以安全地与Pa1 b 2、P a2 b 3或P a3 b 1合并。因此，我们有一个玩家控制所有的决策工具，五个玩家控制条款工具，总共有六个实例GJ中的玩家，同时保持与实例G相同的特征和可能的PNE。Q5非单点公平成本区位对策均衡在本节中，我们将分析由于玩家行为而导致的效率损失非合作博弈最著名的效率度量是PoA和PoS。在一些博弈中，无政府状态的代价可能很高，有时甚至是不现实的，这是因为只将社会成本或福利方面最差的可能均衡与最优的社会福利或成本进行比较。对于设施选址博弈，我们可以证明无政府状态的代价至少是k，其中k是博弈的参与者数量。要了解这一点，请参见图4。在这个例子中，所有玩家都连接到右边的设施的策略是PNE，并且具有社会成本k，而在最优社会解决方案中，所有玩家都连接到左边的设施，总成本等于1（连接成本为零）。cf1 =1cf2=k图四、FLG FC的博弈实例，PoA等于k。在[1]中，Anshelevich等人认为，在同一篇论文中形式化的PoS概念更好地捕捉了网络设计游戏中的效率损失，从而更好地捕捉了单公平成本设施位置游戏。他们展示了一个绑定的PoS36F.C. Rodrigues等人/理论计算机科学电子笔记342（2019）2128Kcf′ =ε4f4′fk′ cf′=εKP4t′4PK特克cf′ =ε3f3′P3t′3fscfs=1P2t′2P1t′1cf′ =ε2f2′Dt，f11 = 3ε +ε2dt1，f2=εC=ε（ −ε）8F17f1t1F2cf=ε（8+ε）27Pat21t22t32t24Pbt3t1Pc4t24c=ε（−ε）f129F37 103f4cf=ε（10+5ε）47 6t154F12t2t55t6t65t35cf5 =ε对于这些网络设计游戏，Hk= 1 +1+···+1游戏中玩家的数量，可以扩展为单次公平成本设施位置游戏[17]。在本文中，我们表明，这是不正确的公平成本设施选址游戏中，玩家可以控制多个终端，即使当连接成本服从三角不等式。我们证明了存在PoS为Θ（k）的情况，其中k是参与者的数量，与PoA相同定理5.1存在度量FLG-FC的允许PNE但在Θ（k）中具有稳定性代价的实例，其中k是参与者的数目。证据考虑图5中所示的实例。设ε是一个比1小得多的常数。对于i∈[1，k]，每个参与者Pi控制终端tJi。玩家Pa控制终端t1到t4和t1到t4，玩家Pb控制终端t1和t3，而2 2 5 5玩家PC控制终端t1、t2、t1和t2。全黑线有连接4466成本为1，而虚线的连接成本为ε，除了dt1，f1BB成本为3ε2+ε。图五、度量FLG-FC的实例，其中PoS在Θ（k）中。虚线表示连接成本ε（除dt，f，其成本为3ε2+ε），全黑线的成本为1。终端旁边的标签指示哪个玩家1 1控制终端。请注意，图5左侧的子博弈只由参与人P2到Pk及其连接组成，它有两个纯均衡：要么每个人都连接到中心设施fs，要么每个参与人Pi将其终端连接到设施fiJ。的F.C. Rodrigues等人/理论计算机科学电子笔记342（2019）21371 1777另一方面，由参与人Pa、Pb和Pc以及他们之间的联系组成的子博弈与定理4.2中的例子相同，当w= 2时，成本以ε为尺度，因此它没有均衡，除非改变博弈，允许其他参与人稳定它。参与人P1在这个例子中可以稳定这两个子博弈.回想定理4.2，只要有终端连接到f2，参与人Pc将连接到f2和f5。由于f5中有多个终端，玩家Pa也会想要连接到f1和f5。 这就意味着参与人P b想要连接到f2和f5. 因此，在任何PNE中，P1必须连接到f2。对于P1来说，这是最好的可能移动，没有玩家可以打开中心设施fs，因此唯一可能的PNE是每个Pi连接到fiJ，而Pa，Pb和Pc如上所述。注意，对于所有i/=j/=r∈[2，k]，参与人Pa、Pb和Pc可以与任何参与人Pi、Pj和Pr合并，因为它们具有不相交的策略集。因此，我们可以假设在这种情况下有k个最优策略的成本如下。在左侧，参与者P1到Pk连接到中心设施fs，成本为1+kε。在右侧，玩家Pb和Pc连接到f2和f5，而玩家Pa连接到f1和f5，也为每个终端支付连接成本ε，总成本为1 +kε+ε。8−ε + 1 +8+ε +14ε=1+kε+16ε +15ε =1+ε。k+15 +16m。7 7 7 7在唯一的PNE中，playersP2到Pk连接到它们的单个设施f2J到fkJ并且玩家P1连接到f2，而玩家Pa、Pb和Pc连接到设施f2，f5和f1（其中Pb使用连接dt，f花费3 ε2+ ε）。因此，PNE的总成本为k+（k − 1）ε +ε。8−8ε+1+7 +ε+3ε + 14ε=k+kε162-ε+7ε+15ε +3ε=k+ε。k+14 +16+3ε。因此，该实例的PoS是k+ε（k+ 14+16+3ε）T= Θ（k）。1+ε（k+ 15+16）由于FLG-FC的PoA为Θ（k）（因此PoS为O（k）），因此这种情况使得FLG-FC的PoS的界限渐近紧，因此度量FLG-FC的PoS为Θ（k）。Q5.1有容量限制的设施选址对策稳定性的代价到目前为止，我们只考虑了设施可以提供的终端数量没有限制的情况然而，实际情况并非总是如此。在[16]中，Rodrigues和Xavier表明，即使是度量设施位置游戏也有无界的PoA，除非考虑序列性。而且他们38F.C. Rodrigues等人/理论计算机科学电子笔记342（2019）21BBdt1，f1=3εdt1，f 2=08C=−ε8ufa= 2u= 1uf =
我的内容管理
展开
