原子拥塞博弈中的最优税收

ACM Transactions on Economics and Computation，卷。号93、第十九条。出版日期：2021年8月原子拥塞博弈中的最优税收Dario PACCAGNAN，英国伦敦帝国理工学院布莱斯·拉胡尔·钱丹FERGUSON和JASON R. 马登，美国加州大学圣巴巴拉分校我们如何设计促进有效利用共享资源的机制在这里，我们回答这个问题的原子拥塞游戏，用于模拟各种问题，包括交通路由的研究类在这种情况下，设计收费机制，最大限度地减少系统效率低下（无政府状态的价格），利用本地信息的方法是迄今为止失踪，尽管科学的兴趣。在这篇文章中，我们解决了这个问题，通过一个易于处理的线性规划公式，适用于和超越多项式拥塞游戏。当我们的方法专门的多项式的情况下，我们得到紧的无政府状态和相应的通行费的最优价格的值，发现一个unexpected链接与负载平衡游戏。我们还推导出最佳收费机制，是恒定的拥塞水平，概括Caragiannis等人的结果[8]多项式拥塞博弈及其他。最后，我们应用我们的技术来计算边际成本机制的效率令人惊讶的是，仅使用局部信息的最佳收费机制与利用全局信息的现有机制（例如，而边际成本机制在连续流模型中被认为是最优的，其效率低于不征收通行费的机制所有的结果是紧的纯纳什均衡和扩展到粗糙的相关均衡。CCS概念：·计算理论→数学博弈论;均衡质量;网络博弈;附加关键词和短语：拥塞游戏，最优税收机制，价格无政府状态，纳什均衡，粗相关均衡，自私路由，近似算法ACM参考格式：放大图片作者：Dario Paccagnan，Rahul Chandan，Bryce L. Ferguson和Jason R.马登2021.原子拥塞博弈中的最优税收ACM跨经济计算9、3、第十九条（2021年8月），33页。https://doi.org/10.1145/3457168本手稿于2019年11月22日存放于arXiv。一个初步版本出现在“Proceedings of the 14th Wo rksho pon th eEconomic sof Net works，S s and d Computation“（NetEco n ' 19）中，参见参考文献[ 9 ]。本研究是在D.帕卡南隶属于加州大学圣巴巴拉分校。这项工作得到了SNSF Grant P2EZP2_181618，ONR Grant #N00014-20-1-2359，AFOSR Grant #FA9550-20-1-0054的支持。作者Paccagnan，Department of Computing，Imperial College London，South Kensington SW7 2AZ，UK; email：d.imperial.ac.uk; R.昌丹湾L. Ferguson和J. R. Marden，加州大学圣巴巴拉分校，控制，动力系统和计算中心，圣巴巴拉，CA，93105，USA;电子邮件：{rchandan，blf，jrmarden}@ ucsb.edu。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明必须尊重作者以外的其他人拥有的本作品组件的版权。允许使用学分进行摘要以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2021版权归所有者/作者所有。授权给ACM的出版权。2167-8375/2021/08-ART19 $15.00https://doi.org/10.1145/345716819ACM Transactions on Economics and Computation，卷。号93、第十九条。出版日期：2021年8月十九：2D. Paccagnan等人∈A→≥..{}E∈A <$∈ E{}→×›→1介绍现代社会是基于大规模的系统，通常为最终用户服务，例如，运输和通信网络。由于这种系统的性能很大程度上取决于用户道路交通网络上的驾驶员），这种系统的操作需要在经济学、工程学和计算机科学之间的交汇处进行跨学科的在这些设置中出现的常见问题是当用户的个体操作不与“grater goo d“相关联时引起的性能降级。道路交通路线选择提供了一个关于用户行为如何降低性能的初步示例：当驾驶员选择最小化其个人旅行时间的路线时，与集中强加的路线相比，总拥堵可能要高得多。解决这个问题的一个富有成效的范例是采用适当设计的收费机制，这在经济和计算机科学文献中得到广泛认可[5，22，26]。追求类似的研究路线，这篇文章的重点是设计收费机制，最大限度地提高系统效率与自利决策的原子conges- tion游戏，即，最小化无政府状态的代价[21]。在此背景下，我们开发了一种方法来计算最有效的本地收费机制，即，最有效的机制，其对每种资源征收的费用仅取决于该资源的本地属性我们这样做的两个收费感知和收费独立的设置，其中收费有或没有访问当前的拥堵水平。我们的结果总结，包括与文献的比较，见表1。也许令人惊讶的是，最佳的地方通行费提供的无政府状态的价格接近使用全球信息设计的现有通行费[6]。1.1拥塞博弈、局部机制和全局机制拥塞博弈于1973年由Rosenthal [31]引入，从那时起，拥塞博弈在不同的领域得到了应用，例如能源市场[29]、机器调度[35]、无线数据网络[36]、传感器分配[23]、网络设计[2]等等。虽然我们的研究结果可以应用于各种问题，我们认为交通路由作为我们的主要应用。在拥塞博弈中，我们给出一组用户N=1，.，n和一组资源。每个用户可以选择她打算使用的资源集合的子集。我们列出用户i N在集合i中的所有可行选择2大肠使用每种资源的成本e仅取决于同时选择该资源的用户的总数，并且用4e：NR0表示。一旦所有用户都做出了选择aii，每个用户就产生了通过将她选择的所有资源的成本相加而获得的成本。最后，系统成本代表所有用户产生的成本，C=0（|一|（e）、（1）i∈Ne∈aiWhe re|一 |e是在所有位置a=（a1，. . . ，an）。Wente与G的集合包含所有拥塞游戏与最大的n个代理和所有资源成本{4e}e∈E属于一个共同的一组功能L。本地和全球收费机制。我们假设用户是自利的，并观察到自利决策通常会导致高度次优的系统成本[30]。因此，人们对应用收费机制来影响结果产生了相当大的兴趣[5，6，8，14，18，26]。形式上，收费机制T：G e τe是关联实例G的映射以及资源e到相应的tollτe。这里τe：1，.，nR是依赖于业务的收费，即，τe将资源e中的用户数映射到相应原子拥塞博弈中的最优税收十九：ACM Transactions on Economics and Computation，卷。号93、第十九条。出版日期：2021年8月.i=1EA∈ E∈通行费因此，用户i∈N产生的成本是资源成本和通行费成本的因数，即，Ci（a）=[4e（|一|（1）A+B（|一|e）]。（二）e∈ai设计使用全局信息（例如所有资源的知识）的收费机制成本，或可行集{Ai}n）的知识通常是困难的，因为这可能需要中央规划者访问私人用户信息，除了相关的计算负担。在交通路由的上下文中（参见下面的示例1），全局机制可能会在边e上产生通行费，该通行费取决于网络的结构、所有边上的旅行时间以及每个用户的确切起点和目的地。相反，本地收费机制需要少得多的信息，是可扩展的，适应动态添加或移除的资源，并且对许多变化是鲁棒的，例如，司机修改目的地的常见情况。因此，很大一部分的文献集中在设计收费，利用当地的信息。形式上，我们说收费机制T是局部的，如果每个资源上的收费仅使用相同资源e的成本函数4e的信息，而没有其他信息。在这种情况下，我们写τe=T（4e），稍微滥用符号。相反，如果该机制利用了额外的信息，那么我们说它是全局的。示例1（业务路由）。在交通路由的上下文中，表示定义用户希望行驶的基础道路网络的边集。为此，每个用户N可以选择连接她的起点到目的节点的任何路径，从而产生一个列表可行路径I.用户在边e上过境所花费的旅行时间捕获函数4e和仅取决于通过该边缘的用户的数量。在在这种情况下，函数4e考虑了边缘的几何特性，例如其长度、车道数和速度限制[37]。等式（1）中的系统成本表示所有用户在网络上花费的时间，并且在边缘上施加通行费以激励用户选择使总行驶时间最小化的路径（1）。1.2性能度量收费机制的性能通常通过在性能最差的紧急分配处产生的系统成本与最小系统成本之间的比率来测量由于假设用户是自利的，因此紧急分配由以下任何均衡概念描述：纯纳什均衡或混合纳什均衡，相关或粗相关均衡-每个都是前一个的超集[32]。1当考虑纯纳什均衡时，机制T的性能，称为无政府状态的价格[21]，定义为：PoA（T）= supNECost（G，T），（3）G∈GMinCost（G）其中MinCost（G）是如等式（1）中定义的实例G的最小社会成本，并且NECost（G，T）表示当在博弈G上采用机制T时获得的纳什均衡处的最高社会成本。类似地，可以定义混合纳什均衡、相关均衡和粗相关均衡的无政府状态的代价。虽然这些不同的指标一般不需要相等，但它们在我们的设置中确实是一致的，我们稍后会澄清。因此，在下文中，我们将使用PoA（T）来表示任何和所有这些均衡类别的效率值。[1]对于一个拥挤博弈，即使存在通行费，也能保证纯纳什均衡（以及上述所有其他均衡概念）的存在，这是因为所产生的博弈是潜在的。十九：4D. Paccagnan等人ACM Transactions on Economics and Computation，卷。号93、第十九条。出版日期：2021年8月≈1.3相关工作对收费设计的兴趣可以追溯到20世纪初[30]。从那时起，交通、经济和计算机科学领域的大量文献研究了这种方法[5，14，18，26，33]。设计优化效率的收费机制在（原子）拥塞游戏的上下文中特别具有挑战性，如所观察到的，例如，[16]这是因为，这是一种多重性的平衡。虽然大多数研究[1，3，13，32]都集中在为给定的方案或在不收费的情况下提供效率界限，但对设计问题知之由于技术上的困难，只有部分结果可用于全局收费机制[6，8，15]，而局部机制的结果仅限于仿射拥塞博弈[8]。参考文献[8]在拥塞博弈的背景下开始了收费机制的研究，将他们的注意力限制在仿射资源成本上。相对于这种设置，他们展示了如何计算一个独立于交易的全球通行费，为混合纳什均衡产生一个（紧）价格为2的无政府状态，以及一个独立于交易的本地通行费，产生一个（紧）价格为2的无政府状态。1+ 2/2/3的Chy2.155的纯纳什均衡。我们的结果与最优设计有关独立的本地收费推广这一发现的任何多项式（和非多项式）的拥塞游戏，并严格持有纯纳什和粗糙的相关均衡。最近，参考文献[6]研究了纯纳什均衡和粗相关均衡的依赖于交易的全局通行费，以及从空状态开始的一轮行走相对于未加权的拥塞游戏，他们得出收费机制产生的价格为粗糙的相关均衡等于2仿射资源成本和类似的高阶多项式的无政府状态虽然后者的工作提供了一些有趣的见解（例如，一些封闭形式的无政府表达式的价格），所有导出的收费方案都需要全局信息，例如网络和用户知识，这通常是不切实际的情况。相比之下，我们的最优本地通行费的结果集中在设计的最优机制，只利用本地信息，从而更广泛地即使利用少得多的信息，最佳的本地机制仍然具有竞争力。例如，对于粗糙的相关均衡和仿射拥塞博弈，依赖于最优通行费的最优当地通行费产生的无政府状态价格为2.012（与值2相比相关的工作也探索了这里考虑的设置的修改：参考文献[8]也研究了单例拥塞游戏，参考文献[15]关注对称网络拥塞游戏，参考文献[25]关注利他拥塞游戏，而参考文献[17，19，20]考虑对资源的子集收费。参考文献[34]关注于原子拥塞博弈中近似纳什均衡的计算。其中，作者设计了与参考文献[9，12，27]中开发的方法类似的最后，我们注意到，收费机制的设计是更好地理解时，原来的拥塞游戏被取代的连续流近似，作为唯一的纳什均衡是有保证的。在这种情况下，边际成本通行费产生的均衡总是最优的[4]。在原子的设置，我们的工作表明，边际成本收费不改善，而是显着恶化，由此产生的系统效率。1.4预览我们的贡献我们的工作的核心是集中在设计最佳的本地收费机制，并得出相应的价格的无政府状态下的各类拥堵游戏。我们的工作在平行的方向上发展，贡献包括：(i) 最佳地方收费机制(ii) 最佳独立于收费的当地收费机制的设计(iii) 边际成本收费及其无效率的研究。原子拥塞博弈中的最优税收十九：ACM Transactions on Economics and Computation，卷。号93、第十九条。出版日期：2021年8月≈A≤表1.资源费用最多为d的拥塞对策无政府值的代价D免费[1]全球通行费[6，8]最佳市话费(this工作）最佳固定市话费(this工作）边际成本收费(this工作）12.5022.0122.153.0029.5855.1015.3313.00341.541515.55118.3657.364267.645255.45289.41391.0051513.57203220.401469.742124.21612345.20877967.5333325.5821337.00所有的结果都是紧的纯纳什均衡，也持有粗糙相关的平衡。这些列的特点是无政府状态的价格，没有通行费，全球通行费来自参考文献[6，8]，最佳当地通行费，最佳常数（即，拥堵无关）的本地通行费，以及边际成本通行费。第四、五和六列是由完全新颖的结果组成的，除了d=1的常数通行费的情况，它恢复了[8]。注意，（i）仅依赖于局部信息的最优通行费的表现接近于使用全局信息设计的最优通行费，对于d=1，性能差异低于1%;（ii）与拥塞无关的通行费产生的无政府状态的代价与使用低次多项式的拥塞感知局部通行费获得的无政府状态的代价相当用于生成此表的代码可以在参考文献[10]中找到表1突出了我们的研究结果的影响，不同程度的多项式成本函数的拥塞游戏，虽然我们的方法进一步扩展以下段落更详细地描述了我们的贡献，而支持代码可以在参考文献[10]中找到最佳的本地收费。在定理1和2中，我们提供了一种方法来计算最优的本地收费机制的拥塞游戏。表1（第四列）给出了多项式拥塞博弈情况下的无政府状态下的价格，其中我们提供了与参考文献[6，8]（第三列）中得出的价格的比较，参考文献[6，8]利用了全局信息，例如，让资源e的收费函数取决于所有其他资源成本。也许出乎意料的是，仅使用本地信息设计的最佳通行费的效率几乎与使用全局信息的现有通行费的效率相匹配[6，8]。除了通过更少的信息提供类似的性能之外，当地收费对于不确定的情况是稳健的（例如，源/目的地对中的修改）并且可以被有效地计算。大量的工作集中在量化负载平衡游戏的无政府状态的代价，即所有动作集都是单例的拥塞游戏，即，I.在这种情况下，当所有资源成本都是仿射和相同的时候，无政府状态的价格是2.012 [7，35]。我们的研究结果与这一系列的工作，表明最佳收费仿射拥塞游戏有一个无政府状态的价格匹配这个值，并在这个类已经紧换句话说，具有相同资源的未收费和最佳收费仿射负载平衡游戏的无政府状态的代价是相同的。我们认为这种说法更普遍地适用最佳的独立于收费的本地收费。我们的方法也可以用来获得最佳的本地机制下更严格的结构约束。在许多情况下研究的一个这样的约束包括使用独立于操作的机制，这是因为它们的简单而吸引人。在定理3中给出了一个线性程序来计算最优的独立于竞争的局部机制，而在多项式拥塞博弈的情况下，相应的无政府状态的最优价格在表1（第五列）中给出，并在推论1和第5节中导出。所有结果都是新的，除了d=1的情况，它恢复了[8]。我们观察到，性能的独立的机制是可比的低次多项式（D3）的独立的机制，仍然是一个很好的改善，在高次多项式的untolled设置。在这些情况下，拥塞无关机制不仅健壮且易于实现，而且相对高效。十九：6D. Paccagnan等人ACM Transactions on Economics and Computation，卷。号93、第十九条。出版日期：2021年8月j=1j=1j=1∈j=12（bj），具有用于定义4的相同系数αj值得注意的是，这第一个结果j=1j=1边际成本收费比不收费更糟糕。在非原子拥塞博弈中，应用边际贡献机制产生的任何纳什均衡都是最优的，即，无政府状态代价等于1推论2展示了如何利用我们的方法来计算原子设置中的边际成本机制的效率对于多项式拥塞博弈，无政府状态的代价的结果值在表1的最后一列中给出虽然边际成本机制确保纳什均衡是最优的（即，稳定的代价是1），在原子模型上利用边际成本机制产生的无政府状态的代价比完全不征收通行费的代价更糟糕（比较表1中的第二列和最后一列）。换句话说，从连续流模型导出的设计原理并不适用于原始的原子设置。这种现象已经在非常简单的设置中表现出来，如图3所示。我们得出结论，观察到我们的结果与参考文献[24]中的结果有很大不同，在参考文献[ 24 ]中，作者表明，随着代理人数量的增加，边际成本费用变得最优。这种差异源于这样一个事实，即在参考文献[24]中，随着代理数量的增长，网络是固定的，而这里最坏的情况是代理数量的函数1.5技术和高层次的想法上述发展的基础是一些技术成果，这些成果来自于观察到，在大多数现有文献中，集合L包含所有资源形式4（x）的成本=。Mαjbj（x），其中αj≥0，gi ven基函数{b1，. . ，bm}。这是描述了这样一个事实，即每个资源成本属于一个已知的函数类。例如，在最大度为d的多项式拥塞博弈中，每个资源都与形式α1+α2x+···+αd+1xd，对应于基函数{1，…，xd}。更通常，组合物4（x）=。Mαjbj（x）都让我们得到一个共同的框架，研究不限于多项式拥塞博弈的不同类别的问题在这种情况下，我们首先在定理1中表明，最优的本地收费机制是线性的，从资源成本集合到通行费集合的耳映射更准确地说，我们表明，对于每一个资源成本4（x）=.Mαjbj（x），则x是满足Topt（4）=Top t（.M不αjbj）=.MαjTopt（bj），其中该机制作为以下的线性组合获得：对于一个d e耦合变元，所有的都是0，因此，可以为每个基b j分别计算最优的跟踪函数Topt（bj）。 支持最优收费线性结果的关键思想在于观察到任何利用系数αjR>0的资源成本函数和可能的非线性收费机制T的拥塞博弈可以映射到相应的拥塞博弈，其中（i）所有系数αj都等于1，（ii）仅使用收费机制T的线性部分，以及（iii）无政府状态的价格与原始博弈的价格相同（随着资源数量的增加）。与此互补，我们在定理1中的第二个结果减少了设计最优基础费用{Topt（bj）}m的问题 多项式可解线性规划这也返回了无政府状态的最优价格的紧值。我们通过建立在参考文献[11，28]中的结果来实现这一点，这使得我们能够通过线性规划的解（参见等式（11））来确定收费机制的性能，其精神与参考文献[6]类似，尽管对于任何数量的代理和收费函数具有可证明的严格特征。我们利用这一结果，并构造了一个多项式大小的线性规划，对于一个给定的基bj，搜索所有的线性工具，以找到Topt（bj）。当基函数是凸的并且是递增的（例如，在充分研究的多项式的情况下），我们能够显式地解决线性规划，并提供一个解析表达式，2作为警告，我们注意到，在上述意义上的最佳机制的线性并不意味着相应的通行费在拥挤程度上是线性的，即，并不意味着对于某个ae，be，τe（x）=a ex+be。opt原子拥塞博弈中的最优税收十九：ACM Transactions on Economics and Computation，卷。号93、第十九条。出版日期：2021年8月j=1≥0j=1JJJJJM最优收费函数，以及无政府状态下最优价格的半解析表达式（定理2）。的基本思想在于表明，在解决方案的主动约束的集合引起了一个伸缩递归，从而最佳通行费被征收时，u+1代理选择一个资源可以被写入作为一个功能的最佳通行费被征收时，只有u代理存在。这是手稿中最具技术性的部分，表达-无政府状态下的最优价格的选择揭示了一个意想不到的联系，在相同的机器上进行负载平衡游戏[7，35]。在定理1和定理2中，程序的大小随着代理的数量n而（多项式地）增长，在第4节中，我们将展示如何设计适用于任何n（可能是无限的）的最佳收费机制。我们的方法包括两个步骤：我们首先解决一个有限维线性规划，然后将其解扩展到任意n。拥塞无关的最优局部机制以及边际成本效率机构也可以通过线性规划计算（定理3和推论2）。在第一种情况，容许tolls基{Topt（bj）}m保持与拥塞一致的应变，而在第二种情况下，使用边际成本通行费的表达式我们提供了分析解决方案，这两个方案的情况下，多项式拥塞游戏。1.6组织在第二节中，我们推导出线性规划来计算最优的本地收费机制。我们还提供了最优价格的无政府价值的多项式拥塞游戏。在第3节中，我们得到了这些方案的显式解，该解适用于资源成本是凸的和增加的情况。第4节将以前的结果推广到任意大的代理人数量在第五节和第六节中，我们推导了与拥挤无关的收费机制，并评估了边际成本机制的效率在这些部分中，我们还将结果专门用于多项式情况。2最佳收费机制在本节中，我们开发了一种方法来计算最佳的本地收费机制，易处理的线性规划的解决方案为了简化符号，我们定义三元组的集合I={（x，y，z）∈ Z3s.t. 1≤x+y+z≤n且xyz=0或x+y+z=n}，对给定的n∈N.第一条。 一种最小化无政府代价的局部机制代理人，资源成本4（x）=.Mαjbj（x），αj≥0，基函数{b1，. . ，bm}由y给出Topt（4）=.αj·τopt，其中τopt：{1，.，n}→R，τopt（x）=fopt（x）−bj（x）（4）且ρopt∈ R，fopt：{1，. ，n}→R求解以下线性规划（每个bj一个）：J J最大ρf∈Rn，ρ∈RS. t.bj（x+z）（x+z）−ρbj（x+y）（x+y）+f（x+y）y−f（x+y+1）z≥0n（x，y，z）∈I，（5）其中我们定义bj（0）= f（0）= f（n +1）= 0。相应地，PoA（Topt）= max j{1/ρopt}。3这些结果是严格的纯纳什均衡，并扩展到粗糙的相关均衡。如果我们需要非负通行费，则最优机制如等式（4）所示，其中我们设置τopt（x）=fopt（x）·PoAopt-J Jbj（x）.j=1十九：8D. Paccagnan等人ACM Transactions on Economics and Computation，卷。号93、第十九条。出版日期：2021年8月JJL≤≤L作为τopt（x）的线性组合，j=1αj用于定义4TL.αjbj\n =.αjT（bj），图1.一、图解说明最佳收费设计的主要结果输入由表示为基bj（x）与系数αj的组合的资源成本4（x）组成。对于每个基，我们计算为-联合通行费最优通行费τopt（x）=fopt（x）−bj（x），通过求解方程中的线性规划（LP）j j选择（五）、得到的最优通行费是τj的线性组合，（x）具有相同的系数αj。可以预先计算量τ opt（x）并将其存储在库中，从而卸载线性方程组的解。程序.上述陈述包含两个基本结果。声明的第一部分显示，最优的tolling机制适用于函数4（x）=.Mαjbj（x）可以得到edJ相同与此相关，陈述的第二部分提供了一种实用的技术来计算每个基bj（x）的τ opt（x）作为易处理的线性规划的解。图1中包含了图形表示，而设计最佳收费的Python/Matlab代码可以在参考文献[10]中找到我们解决了后者的线性规划为n=100和多项式的次数1d6。相应的结果如表1所示，而第4节表明，对于任意大的n，这些结果同样成立。在d=1的情况下，无政府状态的最优价格约为2.012，与相同机器上的未收费负载平衡游戏相匹配[7，35]。我们观察到，在这种受限的环境中，通过地方收费机制根本无法改善无政府状态的代价。事实上，无论我们选择什么非负收费，我们总是可以构建一个负载在相同的机器上进行平衡游戏，无政府状态的价格不低于2.012。4我们得出结论，观察到资源成本分解为基函数的线性组合，严格地说，定理1不需要成立。然而，追求这种方法将需要为中的每个函数求解线性规划，当包含无限多个函数时，任务变得令人生畏，例如，在多项式拥塞博弈的情况下在这种情况下，定理1允许通过求解多个程序来计算最优通行费P屋顶。我们把证明分成两部分以便于说明。部分1. 我们表明，任何本地机制最小化无政府状态的价格在所有线性本地机制，这样做也在所有线性和非线性本地机制。我们让Topt是一种机制，它使所有线性局部机制中无政府状态的代价最小化，即，在所有T满足M mZj=1lj= 14为此，利用参考文献[35，Thm 3.4]中的实例就足够了，其中使用的资源成本x被替换为x+τ（x）。纳什均衡和最优分配将保持不变，产生相同的无政府价值价格。系数. 补充-原子拥塞博弈中的最优税收十九：ACM Transactions on Economics and Computation，卷。号93、第十九条。出版日期：2021年8月≥≤≥MM≤M∈j=1G{}JJJ联系我们对于所有的αj0。 我们打算证明PoA（Topt） PoA（T）对于任何可能的T（线性或非线性）。为了实现这一目标，假设存在一个收费机制T，使得PoA（Topt）> PoA（Topt）。（六）设Gb是一类博弈，其中任何资源e只能利用一个资源成本4e∈{b1，.，bm}。自GbG以来，我们有PoA（T） supG∈ GbNECost（G，T）.（七）最小成本（G）另外，设G（Z≥0）<$G是αj∈Z≥0的对策类，对所有j∈ {1，.，m}，对于E.通过“线性化”机制T"来构造机制T作为我知道jj\n.吉吉T（4）=Tα b=Zj=1lj=1αT（b）。我们观察到，任何实例G∈Gb的效率，对它应用收费机制T′，与实例G∈G（Z≥0）的效率一致，反之亦然。因此，在本发明中，sup NECost（G，T）=supNECost（G，T<$）=PoA（T<$），（8）G∈ Gb 最小成本（G）G∈G（Z≥0）最小成本（G）其中最后一个等式由于附录A.1中的引理1而成立。将等式（6）-（8）放在一起PoA（Topt）> PoA（T<$）。（九）由于Topt使所有线性机制的无政府状态代价最小，并且由于T <$在构造上是线性的，所以它必须是PoA（Topt）PoA（T <$），这是方程（9）的矛盾。因此，Topt使无政府状态的代价最小化。部分2. 我们将推导出一个线性规划来设计最佳的线性机构。把这一点与第一部分中的主张结合起来，证明就结束了。为了实现这一目标，我们将证明，任何形式T（4）=.αjτ opt，其中τopt（x）= λ·fopt（x）− bj（x）（10）是最优的，regard小于λ的值R>0。 虽然这比一般的定义稍微更一般，但设置λ = 1将给出第一个声明。此外，设置λ=PoAopt将给出第二个声明，因为该选择将确保通行费的非负性在证明之前，我们回顾参考文献[11]中的一个结果，该结果使我们能够：对给定的线性收费机制T（4）=.Mαjτj。在定义时增加fj（x）=bj（x）+τj（x）对于所有1x n和j 1，.，m，作者表明，价格的-在拥塞博弈中计算的T的结构对于纯纳什和粗相关平衡，由PoA（T）=1/ρopt给出，其中ρopt是以下程序的值最大ρf∈Rn，ρ∈RS. t. bj（x+z）（x+z）−ρbj（x+y）（x+y）+v[fj（x+y）y−fj（x+y+1）z]≥0<$（x，y，z）∈I，j1，.，m.j=1十九：D. Paccagnan等人ACM Transactions on Economics and Computation，卷。号93、第十九条。出版日期：2021年8月（十一）原子拥塞博弈中的最优税收十九：ACM Transactions on Economics and Computation，卷。号93、第十九条。出版日期：2021年8月j=1--- -- -JJ关于我们--J我们还注意到，当所有函数{fj}m都是非减函数时，只考虑一组减少的约束，遵循类似的论点，在参考文献[28，Cor.1]。在这种情况下，线性规划简化为最大ρρ∈R，ν∈R≥0S.T.bj（v）v−ρbj（u）u+v[fj（u）u−fj（u+1）v]≥ 0u，v∈ {0，.，n}u+v≤n，n∈ {1，.，m}，bj（v）v−ρbj（u）u+v[fj（u）（n-v）−fj（u+1）（n-u）]≥ 0u，v∈ {0，.，n}u+v>n，n∈ { 1，.，m}。（十二）我们现在利用等式（11）来证明等式（10）中的任何机制都是最优的，如所要求的。为了实现这一目标，我们首先观察到，当使用所有基函数b1，.，bm不小于当每次使用单个基函数bj生成资源成本时获得的无政府状态的最优价格（因此不小于无政府状态值的这些最优价格中的最高者这很容易遵循，因为前一类博弈是后者的超集此外，观察到使用单个基函数bj生成的使游戏上的无政府状态的代价最小化的一组费用正好是等式（10）中的费用。这是因为最小化无政府状态的代价相当于设计fj以最大化等式（11）中的ρ，即，解决以下问题：最大最大ρf∈Rnρ∈R，ν∈R≥0S. t. bj（x+z）（x+z）−ρbj（x+y）（x+y）+ν[f（x+y）y−f（x+y+1）z]≥0 （x，y，z）∈I，它可以等效地写为最大ρf∈Rn，ρ∈RS. t.bj（x+z）（x+z）−ρbj（x+y）（x+y）+f<$（x+y）y−f<$（x+y+1）z≥0（x，y，z）∈I，这里我们定义f=v·f。虽然f_opt在等式（5）中被精确地定义为该等式j选择opt最后一个程序，导致无政府状态的代价为1/ρj 注意，λ·fj也是一个解，因为其无政府状态的代价与1/ρopt匹配（实际上，它可以使用等式（11）计算，其中J（ρ，ν）=（ρopt，1/λ）是可行的）。上述推理表明，对于一个资源成本由b1，...，bm必须不小于max j1/ρopt。我们现在证明，这在平等的情况下也成立。为了实现这一目标，我们注意到，由于公式（11），利用公式（12）中的通行费，（6）对于由{b1，.，bm}导致精确地maxj{ 1/ρopt}的无政府状态的代价。如下所示：（最小）optjρj，1/λ）是可行的，对于这个程序的任何选择，Jλ> 0。这证明，如所要求的，等式（10）中定义的任何收费机制都是最优的。我们现在验证选择λ=PoAopt= maxj{ 1/ρopt}确保了通行费的正性，这是相当于fopt（x）−bj（x）/λ≥J0对于所有x∈ {1，.，n}。这很容易得出，因为设置x=z=0在等式（5）中，对于所有的y∈ {1，.，n}。由于fopt和ρopt必须是可行的，我们有opt选择j joptoptoptfj（y）−ρjbj（y）≥0.最后，我们观察到，opt十九：D. Paccagnan等人ACM Transactions on Economics and Computation，卷。号93、第十九条。出版日期：2021年8月Jfj（y）−bj（y）/λ ≥ fj（y）−ρjbj（y）≥0，因为λ ≥ 1/ρ。我们观察到，所有结果都适用于Nash和粗相关均衡，如它们从等式（11）导出的。□原子拥塞博弈中的最优税收十九：ACM Transactions on Economics and Computation，卷。号93、第十九条。出版日期：2021年8月J（十三）≤JJ{}→−（n−vn）δu+δn−1（ρ，fopt）对于原+b（n）n、3显式解与简化线性方程组在这一节中，我们推导出一个简化的线性规划以及设计最佳收费机制问题的解析解我们这样做的假设下，所有的基函数是积极的，增加，并在离散意义上凸5第二章. 考虑有n个代理的拥塞博弈，其中资源成本采用4（x）=Mj=1 αjbj（x），αj≥ 0，且基bj：{1，. ，n}→ R是正的、凸的、严格递增的。6(i) 使无政府状态的代价最小化的收费机制如等式（4）所示，其中每个f_opt：{1.，n}→R求解以下简化的线性规划：ρopt=最大ρjf∈Rn，ρ∈RS.T.bj（v）v−ρbj（u）u+f（u）u−f（u+1）v≥ 0<$u，v∈ {0，.，n}u+v≤n，bj（v）v−ρbj（u）u+f（u）（n-u）−f（u+1）（n-u）≥ 0<$u，v∈ {0，.，n}u+v>n，其中f（0）= f（n +1）= 0。对应的无政府状态的最优价格是max j{1/ρopt}。opt选择j(ii) 每个fj的显式表达式由以下递归给出，其中fj（1）=bj（ 1），fopt（u+1）=minβ（u，v）fopt（u）+γ（u，v）−δ（u，v）ρopt，jv∈{1，.，n}jJ（十四）β（u，v）=min{u，n-v}，γ（u，v）=b（v）v，δ（u，v）= b（u）u ，min{v，n−u}min{v，n−u}min{v，n−u}opt（n−vn）。.n−1βubj（1）+.n−2。.n−1nu=1i=u+1βiβi<$γu+γn−1<$+b（vn）vnρj=min（v1，.，v）∈{1，.，n}n−1×{0，...，n}u=1u=1. .n − 2。.n−1i=u+1Σ Σ其中我们使用简记法βu代替β（u，vu），对于γu和δu也是如此。在深入研究证明之前，我们注意到，设计最佳通行费的关键困难在于在公式（15）中的ρopt表达式然而，对于任何可能的p′ j选择，近似选择j可以直接使用Equa中的递归从 下面的ρ j，即， ρj ρj（14）设计有效的收费机制。无政府状态的最终代价将等于maxj{ 1/ρ<$j}>maxj{ 1/ρopt}。这是从随后的证据得出的。P屋顶。如定理1所示，计算最佳收费机制相当于利用等式（4），其中每个τopt已经通过等式（5）中的程序的解来设计。有鉴于此，我们证明定理如下：首先，我们考虑一个简化的线性规划，其中只考虑方程（5）中强制约束的子集第二、我们证明了这个简化程序的解由上面定义的（ρopt，fopt）给出。第三、我们证明了opt是非递减的，从而确保选择j jj jjoptopt方程（5）中的过约束程序 由此我们得出结论：（ρj ，f，j）也必须是等式（5）的解，即，定理中的第二个命题我们以一些化妆品作为结束并将解由（ρopt，fopt）给出的简化线性规划转化为方程J J5我们说一个函数f： 1、... ，nR是凸的，如果f（x+1）f（x）在其定义域中是非递减的。6如果bj（x）的凸性和严格递增性减弱为bj（x）x的严格凸性，b j（n）> b j（n− 1）。一个这样的例子是bj（x）=x。.（十五）F十九：D. Paccagnan等人ACM Transactions on Economics and Computation，卷。号93、第十九条。出版日期：2021年8月{−}–{−}∈{}–−（十六）∈ {−} ∈ {}≤≥..−−uu− 1–≥−uu−1..L.––−−vn−1vn−2v1vn−1vn−2v1（13），从而获得第一项权利要求。在整个证明过程中，我们从bj中删除索引j，因为证明可以分别对每个基重复□简化线性规划。我们开始重写等式（5）中的程序，其中，代替索引（x，y，z），我们使用定义为u = x + y，v = x + z的对应索引（u，v，x）。以（u，v，x）为索引的约束读作b（v）v ρb（u）u+f（u）（ux）f（u+1）（v x） 0。我们现在只考虑约束条件，其中x被设置为x=min 0，u+v n，并且u，v0，.，n，这样的约束读作b（v）v ρb（u）u+