广播游戏中时间问题的在线动态研究

ACM Transactions on Economics and Computation，卷。号92、第十一条。出版日期：2021年5月时间问题：广播游戏中的在线动态SHUCHI CHAWLA，威斯康星大学麦迪逊分校约瑟夫（SEFFI）NAOR，计算机科学系，TechnionDEBMALYAPANIGRAHI，计算机科学系，杜克大学MOHIT SINGH，H。佐治亚理工学院米尔顿·斯图尔特工业与系统工程学院SEEUN WILLIAM UMBOH，悉尼大学计算机科学学院本文通过自然博弈动力学研究了网络设计博弈中可以达到的均衡状态首先，我们表明，一个任意交错序列的到达和离开的球员可以导致一个多项式效率低下的解决方案在平衡。这意味着中央控制器必须对代理到达和离开的时间进行一定的控制，以确保系统在平衡时的效率。事实上，我们给出了一个补充的结果表明，如果中央控制器被允许恢复平衡后，每一组的到来/离开通过改善移动，然后最终达到平衡状态具有指数更好的效率。CCS概念：·计算理论→近似算法分析;在线算法;均衡质量;网络游戏;网络形成;附加关键词和短语：广播游戏，游戏动态，在线算法11ACM参考格式：Shuchi Chawla ， Joseph （ Seffi ） Naor ， Debmalya Panigrahi ， Mohit Singh ， and Seeun WilliamUmboh.2021年时间问题：广播游戏中的在线动态 ACM Trans. 经济Comput. 9，2，第11条（2021年5月），22页。https://doi.org/10.1145/34344251介绍在多智能体系统中，不同的智能体有竞争的目标，这是众所周知的，自私的行为导致次优的系统性能在平衡。无政府状态的代价这项工作的部分支持是由以下赠款提供的：S。来自NSF的Chawla授予CCF-1101429和CCF- 1320854;Naor来自ISF赠款1585/15和BSF赠款2014414; D.来自NSF的Panigrahi授予CCF-1527084和CCF- 1535972，NSF职业奖CCF-1750140，以及谷歌和雅虎的教师研究奖;Singh来自NSF grant CCF-1717947; S.Umboh来自ERC整合者资助617951和NSF资助CCF-1320854。作者地址：S。Chawla，计算机科学系，威斯康星大学麦迪逊分校，1210 W。DaytonStreet，Madison，WI53706，USA;电子邮件：shuchi@cs.wisc.edu; J.（Seffi）Naor，Computer Science Department，CS Taub Building- ing，Technion Israel ， Institute of Technology ， Haifa 3200003 ， Israel; 电 子 邮 件 ： naor@cs.technion.ac.il;D.Panigrahi，杜克大学，校园框90129，308研究驱动器（LSRC大楼），室D203，达勒姆，北卡罗来纳州27708，美国;电子邮件：deb-malya@cs.duke.edu; M。辛格，H.米尔顿斯图尔特工业与系统工程学院，755弗斯特驱动器，西北，亚特兰大，GA，30332-0205，美国;电子邮件：mohitsinghr@gmail.com; S。W. Umboh，悉尼大学计 算 机 科 学 学 院， Building J12/1 Cleveland St ， Camperdown NSW 2006 Australia; 电 子 邮 件 ： william.umboh@sydney.edu.au。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用本作品的版权归ACM以外的其他人所有，必须予以尊重。允许使用学分进行摘要 以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2021计算机协会。2167-8375/2021/05-ART11 $15.00https://doi.org/10.1145/3434425ACM Transactions on Economics and Computation，卷。号92、第十一条。出版日期：2021年5月十一：2S. Chawla等（PoA）和稳定性价格（PoS）分别对应于最差和最佳均衡状态，在文献中被广泛用于量化相对于由中央权威机构设计的最优解的次优性。 如果这两个度量彼此接近，那么它们提供了对系统预期达到的稳定状态质量的满意理解。然而，当这些措施显着不同，系统可以表现出多个平衡，ria与高度变化的性能。但是，这些均衡中的哪一个可以在实际的博弈动态中实现呢？ 更一般地说，中央权威的最低指导是什么，可以保证接近最优的系统性能在平衡？在这篇文章中，我们研究这些问题的背景下，表现出一组特别丰富的均衡，即广播游戏。一个广播游戏被定义在一个有根的无向图上，成本在边上。图中的每个顶点都有一个代理，其目标是选择一条到根的路由路径，使自己的成本最小化。每条边的成本在使用它的所有代理之间平均分担，并且代理的成本是她沿着到根的路径中的边的成本份额的总和。系统处于纳什均衡（NE），如果没有代理可以降低自己的成本，单方面改变她的路由路径。均衡的成本是至少一个主体使用的所有边的总成本。均衡的质量是相对于社会最优，这对于广播游戏是最小的生成树（M S T）的图形。广播游戏是一种潜在的游戏和存在的NE在任何情况下都可以证明通过一个潜在的功能参数，最初由罗森塔尔[33]（见Monderer和Shapley [29]）。Anshelevich等人[4]观察到广播游戏中不同的NE可以表现出截然不同的性能：PoA可以大到Ω（n），而PoS（他们引入的一个概念来显示这个差距）的边界是O（logn）;这里，n表示图中的顶点数[1]随后，一系列的工作[10，18，26，27]将PoS绑定到O（1）。鉴于这种分歧的界限，Chekuri等人。[12]提出了分析通过自然动力学实际可达到的均衡的质量的问题-一系列单个代理移动，其中移动的代理总是选择一条新路径，该路径相对于当前路径严格降低其成本从Rosenthal [33]的势函数论证可以得出，任何这样的移动序列最终都会收敛到NE。Chekuri等人[12]考虑了以下受限的两阶段过程：在第一阶段，从一个空图开始，代理人以任意顺序依次到达，并在到达时选择各自的最佳响应路径;在第二阶段，代理人以任意顺序进行改进移动2，直到它们达到平衡。他们证明了通过这个过程达到的均衡有一个成本为O（nlog2n）倍的msT，一个显着的改进，超过PoA界。这Charikar等人[11]随后将相同两阶段过程的结合改进为O（log3n）稳定的动态价格。这些以前的作品激励扩展的概念的价格稳定在线动态。在我们的问题的静态（或“一次性”）版本中，参与者最初处于空的配置中，中央计划者可以迫使参与者进入任何配置，特别是实现稳定代价的配置。然而，在动态的情况下，中央计划者不能这样做，因为一些参与者已经选择了一条路线。因此，中央计划者必须为现有参与者提供更好的策略来激励变革。非正式地，稳定的动态是由在线动态产生的均衡解决方案的成本，同时允许[1]参见附录B，以获得说明这些界限的示例。[2]观察到，当一个智能体到达或采取改进行动时，其他智能体的路径可能对他们来说不是最优的时间问题：广播游戏中的在线动态十一：3ACM Transactions on Economics and Computation，卷。号92、第十一条。出版日期：2021年5月中央计划者的算法干预动态稳定价格的概念可以应用于任何游戏，其中需要描述哪些均衡可以通过在线动态达到，同时最大限度地减少中央计划者的干预力量如果能找到这一新概念的进一步应用，将重申Charikar等人的一种方法[11]的结果是，当所有到达都发生在任何改进移动之前时，动态PoS是多对数的但是，如果一些代理人在所有其他代理人到达之前做出改进动作，即，改进移动的序列与到达的序列交错？不幸的是，参考文献[12]和[11]中提出的分析强烈地建立在这样一个事实上，即所有代理人都提前到达并在此后留在系统中，因此代理人必须等待所有人到达才能对其策略进行任何更改。Charikar等人提出的问题，分析动态中的到来和改善行动是交错作为一个“诱人的和困难的”开放的问题。 在他们工作之后的十年里，尽管广播游戏的PoS界限取得了巨大的进步，但在理解更一般的游戏动态方面没有取得任何进展。3更多的动力学。自从Charikar et al.[11]，我们的工作是第一个研究更一般的广播游戏动力学我们考虑两种扩展的两阶段过程。首先，我们考虑的系统与流失代理到达以及离开随着时间的推移。第二，我们允许多个交错阶段的到来，离开，并提高移动。我们的第一个结果表明，如果我们对上面研究的两阶段动态进行最小的改变，即在第一阶段增加偏离，那么就有可能达到一个比社会最优状态差的多项式（n）的均衡，将其置于与PoA界限相同的制度据我们所知，这是广播游戏的任何游戏动态的第一个多项式下界1.1. 对于任何足够大的整数n，存在具有n个顶点和到达和离开序列的广播博弈的实例，该到达和离开序列终止于成本为所有顶点上的最小生成树的成本的Ω（n 1 / 3）倍的NE。重要的是要注意，因为我们允许离开，不是所有的顶点在游戏结束时都有代理这为OPT创建了两个候选：剩余代理上的最优Steiner树，或所有顶点上的msT[4]前者会导致平凡且无趣的下界（参见附录B）;因此，我们在本文中使用msT作为选项这种选择较弱的最优值会导致较强的下限。干预的力量。给定上述下限，一个自然的问题是，来自中央计划者的有限干预是否会导致博弈的更好结果在一个极端，如果允许中央计划者同时向每个参与者建议策略，则可以实现任何NE，特别是对应于O（1）的PoS的最佳NE这种控制水平是不现实的。一个更合理的控制水平是中央计划者一个接一个地向玩家建议改进这种干预的时机如何正如我们的下限所表明的那样，如果干预的时机3Charikar等人。[11]还研究了一种变体，其中到达以均匀随机顺序发生，并与逆向排序的最佳响应移动交织对于这种设置，他们能够证明O（n ×npolylogn）的上界的均衡达到的质量，但没有提出任何下限。[4]另一个界限是代理在动态中的某个点到达的所有顶点上的最优Steiner树由于我们可以假设度量成本，我们可以将注意力限制在这些顶点上，然后msT成本在最佳Steiner树成本的两倍之内十一：4S. Chawla等ACM Transactions on Economics and Computation，卷。号92、第十一条。出版日期：2021年5月如果在初始到达/离开阶段，则系统可能以不良NE结束 为了绕过这个下限，我们考虑动态，允许中央计划者在每次对抗性到达/离开后采取一系列改进措施。 观察到到达和离开的序列仍然可以逆向排序，并且确实可以依赖于先前的算法干预。我们称这种动态为平衡保持（equilibrium-preserving，EQ-P）动态，因为中央计划者在每次敌对的到达/离开之后都会将系统恢复到一个良好的平衡具体地说，EQ-P动力学从一个空组态开始，并在历元中继续在每一个纪元的开始，系统都处于平衡状态。新纪元以到达或离开开始，随后是一系列改善运动以恢复平衡。一旦平衡恢复，时代结束。事实上，我们的分析允许在一个时期的开始时有多个同时到达，并且在该时期的任何时间点有多个离开形式上，我们定义了一个时期内的三种不同类型的移动：(1) （抵达。一组新的参与者到达，并且每个参与者相对于在前一个时期结束时达到的配置选择最佳响应路径（到达集合的选择是对抗性的。）(2) （照片。）一组玩家离开系统。（选择离开的球员是敌对的。(3) （恢复平衡。中央权威机构为参与者提供策略，可以提高他们的（共享）连接成本。这一步骤一直持续到系统恢复平衡。我们的第二个结果表明，这种有限的中央干预水平足以保证NE具有指数级更好的性能：1.2. 使用EQ-P动态的广播博弈的每个实例都收敛到成本的NEO（log n）的最小生成树。观察到，对于我们的下限结果，我们将EQ-P动力学的性能与所有顶点6上的msT进行比较，而不是系统中剩余顶点上的最优Steiner树当没有偏离时，这两个基准是相同的，但是当有许多偏离时，ms T基准可能会弱得多。然而，如前所述，Steiner树基准并不有趣，因为它会导致平凡的多项式下界（参见附录B）。此外，上述定理提供的保证在每个时期结束时成立，与已经到达该时期结束的顶点上的ms t相比，不包括未来的到达。一个自然的开放性问题是，相对于EQ-P动态，是否可以通过较少的算法干预来实现多对数动态PoS;例如，允许玩家做出最佳反应移动而不是改进移动。相关工作。我们已经提到了改善广播游戏PoS边界的长期工作[4，10，18，26]，以及Chekuri等人研究的游戏动力学[12]和Charikar et al.[11 ]第10段。Balcan等人采用了不同的方法[6]，他考虑了影响广播游戏动态以实现社会有效均衡的问题在他们的模型中，参与者使用专家学习，在最佳反应专家和中央权威专家之间进行选择，建议（接近）最佳的全局行为。广播游戏属于一个更广泛的类别，[5]请注意，虽然单个时期内的到达是同时的，因为每个到达的参与者在时期开始时选择相对于平衡状态的最佳响应路径，但不同时期的到达是顺序的。从这个意义上说，我们的模型捕获了具有交错改进移动的顺序到达。6由于与msT的比较，我们更喜欢术语游戏。”时间问题：广播游戏中的在线动态十一：5ACM Transactions on Economics and Computation，卷。号92、第十一条。出版日期：2021年5月×→| |⊆∈网络设计游戏（参见，例如，参考文献[2，4，9，10，13，14，17，19，25，27]），其又是广泛研究的拥塞和潜在博弈的特殊情况（参见，例如，参考文献[1，7，16，23，28，29，32，33，35]）。本文中的博弈动力学分析主要依赖于多个对偶解的层次族的构建这种分析方法在设计网络设计问题的在线算法方面具有很大的影响力。这种方法的隐式使用可以追溯到Imase和Waxman[24]对在线Steiner树的工作以及Awerbuch等人的后续工作。[5]，Berman and Coulston[8]，Naor et al.[30 ]第30段。最近，该方法已被显式地用于在线设置中解决一系列节点和边加权Steiner网络设计问题[3，15，20 就确切的技术而言，也许最接近我们工作的是Umboh [36]，他使用分层树嵌入来分析网络设计问题的贪婪在线算法。在竞争分析中，决策是不可撤销的，与此相反，博弈动力学允许双重解的临时过度收费，这是我们在本文中使用的关键。一个有趣的相关问题，我们的工作是确定计算状态找到一个NE解决方案的广播游戏。据我们所知，这个问题是开放的，既不硬度的结果，也不算法的上限，是已知的。我们提到几个相关的结果。Chekuri等人证明了这一点。[12]计算多播游戏的全局潜在最小值是NP困难的（其中并非所有顶点都必须包含代理）。西尔卡尼斯[34]证明了在网络成本分担博弈中计算NE解是PLS完全的在这些游戏中，没有共同的根，而是每个代理人的不同目的地因此，这些游戏比我们的广播游戏更普遍我们注意到PLS-硬度证明似乎强烈地使用了这样一个事实，即在网络游戏中有许多目的地。文章的组织。在第2节中，我们首先定义了一个广播博弈模型，以及一个分析均衡成本的收费方案。 我们在第3节中给出了我们的下界（定理1.1）的证明，在第4节和第5节中给出了我们的上界（定理1.2）的证明。2模型和技术基础广播游戏定义在一个完全图G=（V，E），V=n上，度量成本7c：V V R+定义在边和一个根顶点r上.我们假设，不失一般性，每个顶点有一个独特的代理，或终端，居住在它。8个代理人在一段时间内到达和离开。由于边成本满足三角不等式，在一个代理到达之前，没有其他代理通过对应于这个代理的顶点路由他们的路径然而，如果已经在系统中的代理离开，则其他代理可以继续通过其顶点路由它们的路径，并且该顶点保留在图中。如果一个顶点上的智能体仍然在系统中，我们就称该顶点为活动的让t索引时间。我们用Vt表示G中到时间t为止出现的所有顶点的集合。设AtVt表示它们之间的活动端子的集合。每个终端v At具有将其连接到公共根r的当前路由路径pv。沿着该路径的v的成本份额是v在路径中的边上的成本份额的总和任意时刻t的路由定义为路由路径的集合（pv）v∈At。终端v的最佳响应路径具有路由的可能性，即dpv，是从v到r的具有最小共享成本的p，如果v移动到该路径。如果有多个这样的路径，那么我们打破束缚，7三角不等式可以被假设而不失一般性，因为每个顶点都包含一个代理;如果一条边违反三角不等式，那么它将不会被任何代理使用。8这不失一般性，因为顶点v处的多个代理可以通过在距离处添加额外的顶点来建模。从v到十一：6S. Chawla等ACM Transactions on Economics and Computation，卷。号92、第十一条。出版日期：2021年5月∈i=1.∈ .•∈∈•∪∈ ∈ ∩∅路径具有较少的边，除了使用它们的v之外没有终端请注意，这可能不会打破所有联系，在这种情况下，这些路径中的任何一条都可以被指定为最佳响应路径。如果终端v A通过从其当前路径pv移动到新路径qv严格地降低了v的成本份额，则称终端v A相对于路由具有改进的移动给定一个路由，它的潜在[33]被定义为Φ=e ENece/i，其中Ne是使用e的代理的数量。一个标准的论点表明，任何改进的移动减少了一个值，这是一致有界远离零的潜力，导致任何改进的移动为基础的动态有限收敛。下面的著名引理指出，在平衡状态下，路由路径形成树：在均衡中，广播游戏的路由路径形成树。PR oF. 引理是下面的向下闭包性质的直接结果，保持在平衡状态。假设w是分别出现在两个终端u和v的路由路径pu和pv上的顶点（不一定是终端）那么，pu和pv在w和r之间的线段必须相等。为了矛盾起见，假设这个说法是错误的，让qu和qv表示pu和pv在w和r之间的不同段。不失一般性地假设qu的当前分担成本至多是qv的当前分担成本。如果v现在移动到一条新的路由路径，该路径跟随pv直到w，然后使用qu到达r，则v的成本变化将是qu的新共享成本与qv的当前共享成本之差。根据我们对qu和qv当前分担成本的相对顺序的假设，这显然是非正的。事实上，我们认为这种差异是负面的。首先，注意至少有一条边在qu中，但不在qv中，因为这两条路径不相同。现在，设（x，y）是qu中离u最近的边，它不出现在qv中，其中x比y离u近。那么，x也必须出现在qv上，因此，不能出现在v和w之间的pv的线段中。因此，edge（x，y）不出现在pv中v和w之间的线段中，因此不存在于整个路径pv中。当v移动到它的新路径时，（x，y）上的共享成本降低到低于它的当前值，因此，qu的共享成本整体上降低这意味着v有一个改进的移动，这与终端处于均衡状态的前提相□2.1树木砍伐的收费方案我们的目标是比较广播博弈中均衡的成本与图的msT的成本在达到平衡的任何时间点t，我们将比较当前路由的成本与顶点集Vt上的msT为此，我们考虑标准MsT线性规划及其对偶。我们现在详细描述我们的收费方案对偶定义了顶点切割到边的填充没有必要理解msT程序或其对偶。我们直接用切割填充的形式来描述它。我们称一个划分为P =（S1，. ，Sm）是整数j的水平-j对偶，如果它满足以下条件：P是一个划分：SPS=V，并且对于任何Sa，SbP，Sa Sb=。对于任意S P和任意顶点x，y S，c（x，y）<2j。•组件彼此远离：每个组件中存在Si，使得对所有Sa，Sb∈P，c（sa，sb）≥2j−1。我们使用术语割来表示分量（S1，. ，Sm）。下面的引理直接来自于这样的观察，即V上的任何生成树必须连接一个水平-j对偶P中所有割的中心。2.2. 对于任意的-j层对偶P，最小生成树oPT的代价至少为01-02-0|P |− 1）。时间问题：广播游戏中的在线动态十一：7ACM Transactions on Economics and Computation，卷。号92、第十一条。出版日期：2021年5月∈∈{}∈∈| ||− |−∈ −−为了约束任何树路由均衡的成本，我们将解决方案中使用的边的成本设Z=PjjZ表示一个划分族，其中Pj是一个水平-j对偶.我们的收费计划路由解决方案，形成一个树的收益如下：路由树中的每个顶点负责其父边的成本考虑一条边e=（v，parent（v）），其长度为[2j+2， 2j+3），其中j为Z。我们将该边的成本计入包含v的level-j对偶中的切割：即，使得v S。我们最终的解的代价界将取决于树中的边对族中的每一次切割充电的次数，如下面的引理所形式化的。对于非EQ-P动力学，我们将构建一个具有均衡树路由的示例，其中在每个尺度下，我们可以找到许多非常接近的顶点，这些顶点具有相似长长度的父边这意味着任何家庭的消费者都将被多次收取费用，从而导致巨大的总成本。然而，对于EQ-Pdynamis，我们将证明，算法干预产生的解总是对特定家族中的每个切割收取最多一次费用。2.3. 假设我们的收费方案对族中的每个切割收取至多α倍的费用。这样的话，问题的时间复杂度为O（log n）OPT。PR oF.设D表示图中的最大边长。然后，我们首先注意到，我们可以忽略我们的解决方案的长度在最多D/n。这是因为在这样的边中存在m个R，并且根据边长度的度量性质，OPT至少为D对于剩余部分，我们对j收取（logg（D/n）3，loggD2]。 这种情况在mosn+1处出现。总成本在电平-j处充电到对偶的边缘的最大值为2j+3P 32 2j−1（P 1）。<引理2.2则意味着结果。□对于我们的大部分分析，我们假设提供给我们的是对偶家庭在附录A中，我们讨论了如何在终端联机时用算法构造这个族2.2分析eq-p动力学的技术挑战广播博弈展示了系统的一组丰富的均衡和一组丰富得多的中间状态在博弈的任何均衡点上，路径选择总是形成一棵树，而中间状态，甚至是通过一系列最佳对策移动所达到的状态，都可能包含一个复杂的相互连接的循环结构。分析动力学的一个主要障碍是在中间状态上保持任何结构不变 我们的工作克服了这一挑战，算法保持这样的结构不变。 每当到达或离开的结构不变被打破，我们恢复它的算法。重要的是，我们表明，这总是可以通过一系列的改进举措来实现。我们的结构不变式是一个国家的成本收费（即，路径的集合）针对如上所定义的底层图的分区簇来因此，我们的收费方案可以解释为双重拟合方法。可行的充电是分区中的每个切口最多充电一次。执行这种方法的一个挑战是，随着代理人到达和离开，我们的分析必须允许在中间状态下充电变得非常不可行这反过来又导致非常昂贵的中间（非平衡）状态。我们的论点的关键是一个精心构建的改进举措，确保系统在一小部分状态之间循环，其中稳定的状态对应于可行的充电。3非eq-p系统在这一节中，我们将证明，如果在非平衡态允许到达和离开，那么没有动力学可以导致一个好的平衡（定理1.1）。十一：8S. Chawla等ACM Transactions on Economics and Computation，卷。号92、第十一条。出版日期：2021年5月≥j，∈j，图1.一、 例如m = 4。辅助顶点显示为红色，结束顶点显示为蓝色。椭圆表示聚类。集群内边缘被示出为虚线边缘。从同一个簇开始的两条粗路径依次分叉到不同的簇中，并在通往根的途中会聚到同一个簇中。我们构造了一个家庭的下界参数化的整数m1的情况下。第m个实例使用由加权图Gm导出的度量（参见图1）。这个图的顶点集由根r和m +1层V 0，. 、V m. 对于1 ≤ i≤ m，层Vi由m个簇组成C i，.，Ci，其中的每一个是m个顶点上的团。我们用vi表示Ci的第k个顶点;1mj，kj回想一下，i、j和k中的每一个都取[m]中的整数值层V0也由m2个顶点组成其中j，k∈[m]被标记为v0，但这些顶点之间没有边顶点m的顶点称为端点，V0的顶点称为辅助点。注意，Gm有n=m2（m+1）+ 1个顶点.接下来，我们描述边缘。相同聚类Ci内的每对顶点通过以下连接：长度为1/m的边缘对于所有层，除了JV0。图中的其余边连接顶点在相邻的层中，并且都是长度1。V0中的每个辅助顶点v0都连接到根及其对应的顶点1在层1中。持续1j，ki i+1为每个vj，k≤i≤m−1，我们有一条边（vj，k，vk，j）j，k[m]。换句话说，层i中的第j个聚类的顶点连接到层i+1中的聚类的第k个顶点;具体地，层i中的第j个聚类的第k个顶点连接到层i+1中的第k个聚类的第j个顶点例如，请参见图1中离开V1的第一个（顶部）簇的边.观察到正好有m2（m+1）个层间边缘，并且exm3（m−1）/2簇内边缘。注意，每个端顶点vm具有到根的唯一路径Pj，k，该路径仅由间-层边缘（见图1）。我们称这些路径为典型路径。注意每个层间边只属于一条规范路径，换句话说，层间边的集合是所有规范路径Pj，k的不相交并集。最终均衡的代价。在描述码头到达和离开的顺序之前，让我们分析最终的平衡状态及其相对于最优成本的成本设OPT表示Gm中所有顶点上的最小生成树的代价.注意，这是一个时间问题：广播游戏中的在线动态十一：9ACM Transactions on Economics and Computation，卷。号92、第十一条。出版日期：2021年5月j，j，MFFFFJJMj，≺M≤ ≤−M+1M最后任何最优解的成本上限我们序列的最后一个状态的到达和离开，表示为F，由m个玩家组成，位于每个端点vm，层m;每个参与者使用规范路径Pj，k来路由到根。下面的引理表明，这是一个平衡状态，相对于OPT.com，它的成本以多项式方式更大3.1. blog 状态F是一个均衡，F的代价是Ω（m）OPT。PR oF. 首先，我们证明F是一个均衡。考虑一个局中人在终点vm处，Pj， k和交替路径PJ。对于每个簇内边缘，我们具有Ne（对于层间边缘e，我们具有Ne（）=m，其中Ne表示使用边缘e的终端的数量。 因此，计划者的当前成本是m +1。 路径PJ包含至少一个簇内边缘和至少m+1个层间边缘。因此，当1 +m+1=m+1。因此，F是一个平衡态。接下来，我们证明了c（）=Ω（m）OPT.由所有单位长度的层间边缘组成，因此其成本为m2（m+1）。然而，构造Gm的生成树的一种方法是在m2个团中的每一个内选择任意生成树，从层0到根的所有边，如以及每个团的一个层间边缘将其连接到其前一层，即边缘（vi，vi+1）将Ci+1连接到Ci为所有i，j∈[m]。这个解决方案的总成本是1m3+m2 +m2j，j，j，j=3m2。 □到达和离开的顺序。该序列被构造成m个阶段，每个阶段由m个2轮组成，每个端顶点vm一轮，并且由（j，k）索引。非正式地说，每一个项目的目标j、 k、m舍入是在每个端顶点vj，k处再增加一个终端。在所有阶段结束时，将有m3终端。在一个阶段的循环（j，k）中，我们使用一组唯一的目的是迫使到达该轮结束的在vm处的终端选择规范的路径作为最佳对策。临时端子在倒圆角期间沿规范路径在中间顶点处引入，并在倒圆角结束时移除。形式上，设是对（j，k）的任意全序。序列σ被构造为保持以下不变量：在阶段4的轮（j，k）结束时，将有4个玩家在MjJ，kJ对于（jJ，kJ）<$（j，k），剩余的端顶点上有4-1个玩家此外，每个玩家mj，k使用路径Pj，k。我们现在指定每个回合的子序列考虑阶段4的轮（j，k）。为了简化符号，我们使用vi来表示Vi在Pj，k上的顶点。我们还使用Pi来表示Pj，k中从vi开始到根结束的线段该轮由m+1次迭代组成。在迭代0i m 1，m2玩家到达vi在迭代i=m中，一个参与者到达vm。最后，v 0上的参与者，...，vm−1出发。我们现在可以证明，通过对终端到达的归纳，对于每个终端，到达时的最佳响应路径是连接它到根的规范路径的一段。3.2. hot water 考虑终端在阶段4中的round（j，k）的迭代i中到达顶点vi。终端到根的最佳响应路径是其规范路径Pi的段。PR oF. 我们证明了不变量的诱导序列的终端到达，即，over（4，j，k，i）. 此外，我们将只证明归纳假设对迭代中到达的第一个终端成立;每个后续终端将明确选择与第一个终端相同的路径，因为它们到达相同的顶点。在阶段1的第1轮开始之前，不变量平凡地保持现在考虑阶段4中round（j，k）的迭代i的开始，并假设在先前的迭代、轮次和阶段中保持不变让我们计算一下每条边上的端子数量到目前为止，在每个端点上，有4个或4-1个终端，每个终端都选择了它们的规范路径v对v十一：S. Chawla等ACM Transactions on Economics and Computation，卷。号92、第十一条。出版日期：2021年5月≥F∈\|| ≤\n{}∈t在到达时，通过归纳假设。归纳假设还告诉我们，对于每个iJi，viJ上至少有m2个终端使用路径PiJ。<因此，属于Pi-1的每个层间边缘具有至少m2个端子，并且不属于Pi-1的每个层间边缘具有至多4个端子。此外，没有一个簇内边缘被任何终端使用请注意，Pi由层间边缘（vi，vi−1）和Pi−1组成。由于Pi−1m，成本在Vi处的新末端（c都是其末端a）在Pi上的份额至多为1/4+m/（m2+1）<1/4+1/m。a的任何其他路径Q包含不属于Pi-1的至少两个层间边缘和至少一个簇内边缘，soa的成本分担Q至少为2 /（4 + 1）+ 1 /m1/4+1/m。参与人a□引理3.2表明，上述到达和离开的序列终止于最终状态，其通过引理3.1消耗Ω（m）OPT。因为m是关于顶点数的多项式，所以定理1.1成立。4Eq-p半导体在这一节和下一节中，我们将描述和分析广播博弈的EQ-P动力学我们首先证明一些基本的结构性质，这些性质将在本文的其余部分中使用在EQ-P动力学中，图G是通过一个在线过程来揭示的，该过程被划分为多个时期（以时间t为索引）。在历元t的开始，到目前为止已经出现的所有顶点的集合和活动顶点的集合分别被表示为Vt和At在历元开始时，我们进一步强制路径pv的集合在NE中的不变量，即，没有终端具有单方面偏离到不同路由路径的动机我们假设，我们的干预算法没有知识的顶点对应的代理尚未到达。在这个过程中的任何时间点，我们的算法只考虑子图诱导顶点的代理已经到达之前的时间。4.1路由树和改进移动每个时期t被分成几个阶段。第一阶段包括到达或离开事件。在前一种情况下，一组新的终端UtV Vt到达，并在Ut中的终端上的所有边缘事件的成本被揭示。每个新终端u，t选择最佳响应路由路径p，u。在后一种情况下，终端集合离开，从而从终端集合At中移除对应的顶点。（请注意，相应的顶点仍保留在Vt中。）引理5.2建立了到达或离开之后的路由路径集合的结构保持为树。到达和离开事件都会导致边的成本份额发生变化在EQ-Psce- nario中，这可能导致对先前保持的平衡状态的破坏在这种情况下，系统执行一系列改进移动，在每个改进移动中，终端改变其路由路径以减少其成本份额。改进移动可能会在路由路径pvvA的集合中临时创建循环。我们将改进移动排序并分组为连续的块或阶段，使得每个阶段以形成树的路由路径结束。此外，在相位的开始和结束处的树在单个边缘对中不同。在每个这样的阶段中的移动的集合被称为树跟随移动。定义4.1（树跟随移动）。T中从u到v的树跟随移动是从路由树T开始并以路由树T J= T（u，parent（u））（u，v）结束的改进移动序列，其中parent（u）是T中u的父顶点。注意，在T中以u为根的子树中的每个终端根据T j将其路径重路由到根。（见下图2。）由于出发事件，路由树可能包含非终端顶点作为Steiner顶点。将改进移动的概念扩展到不是终端的顶点是方便的时间问题：广播游戏中的在线动态十一：ACM Transactions on Economics and Computation，卷。号92、第十一条。出版日期：2021年5月{}∈tEQ-P动力学（1）非对称性。 t=1，V0={r}，T0={r}，A0=0.(2) 对于t= 1，2，.• （抵达。设Ut是到达的终端的集合设At<$At−1<$Ut。对于每个v∈Ut，letpv=pv其中repv是v的最佳响应路径，其响应于Tt−1。LetTt=• （照片。设Dt是出发的终端的集合。设At=At\Dt。设Tt=Tt−1<$v∈Utpv<$。• （树木跟随移动。当Tt不处于平衡状态时：v∈Atpv。使用算法s elecTTREE moveE来确定要在Tt中实现的树跟随移动;令该移动为从u移动到v，并令parent（u）表示Tt中u的父节点。对该树跟随移动执行改进移动序列以获得新路由树Tt←Tt\（u，parent（u））<$（u，v）。图二、左侧面板显示了从u到v的树跟踪移动。右边的小图说明了构成这个树跟踪移动的各个改进移动设wgA是一个非终结点。我们说w有一个改进的移动，如果以下性质成立：（1）存在一个终端v，其路由路径pv包括w;让pw表示pv在w和r之间的段;（2）在w和r之间存在一条路径qw，使得如果v要保留其当前从v到w的路由路径，但从pw移动到qw，则v的成本份额将严格减少。先验地，不清楚改进的移动是否总是可以被分组为树跟随移动。在引理5.3中，我们证明了在每个不处于平衡的路由树T中，存在一系列改进移动，这些改进移动共同形成了对于某些顶点u和v从u到v的树跟随移动。当有多个这样的移动，我们使用一个仔细的收费计划，以确定顺序，其中树跟随移动应该实施。（参见本节末尾定义的算法选择树模型由于树中的每个顶点都有一条到根的唯一路径，因此只需指定树本身而不是所有路由路径即可。但是，我们将使用Tt来表示由pvvA诱导的树，而不显式地指定路径本身。十一：S. Chawla等ACM Transactions on Economics and Computation，卷。号92、第十一条。出版日期：2021年5月{}∈算法选择树移动(1) BAlAncE D-EqIl 系统只能通过到达或离开事件从平衡态脱离。(2) BAlA ncED：在这种状态下，对于任何具有改进树移动的顶点u，将u移动到它具有改进移动的最近顶点。(3) lEAF-unBA lA ncED：(a) 如果存在一个具有非叶移动的叶终端u，则对u进行任何这样的移动。(b) 否则，如果存在具有非叶移动的非叶顶点u，则将u移动到最近的这样的非叶v。4.2状态分类与树跟随移动然而，我们将假设该算法维护一个分区族，其中Pj是一个水平j对偶。这可以通过附录A中讨论的在线方式构建。我们分类的树路由可达通过E-Q-P动态到四个状态之一，根据对家庭的解决方案定义的收费结构。我们注意到，不是所有的树路由是可达的通过EQ-P动态，事实上，即使是一组得到的均衡是小于所有的均衡。设T是某组活动终端A的路由树。我们说一个顶点u是一个叶（非叶），如果它是T中的一个叶（非叶）。请注意，所有叶必须是终端，但非叶顶点可能是也可能不是终端。(1) BAlAncED-EqIl i lL I N：在此状态中，没有终结符（并且reforre，T中没有非终结符vertex）具有改进移动。此外，每次切割最多收费一次。（注意，并非每个NE都是最佳的。）(2) BALAncED：在这种状态下，一些终端（和潜在的非终端）可能具有改进的移动，但是每个切割最多被充电一次。(3) lEAF-unBA lA ncED：在此状态下，每个切割最多由一个非叶顶点（以及任