路由博弈中的混乱之路：什么时候也是无ZF状态的代价

在这项工作中，我们表明，由于总需求/人口的增加，成本函数的有效放大可能会导致质量上的差异（混乱而非平衡），因此这些影响不能通过标准化成本来安全地折现，而是需要仔细研究。该领域的理论工作很好地支持了无遗憾算法对相关平衡点的缓慢收敛。无遗憾算法在大型博弈中很难找到粗糙的相关均衡，正是因为它们的遗憾以较慢的速度消失。这就是为什么已经开发了不同的集中椭球方法算法来计算游戏中的相关均衡，其中有许多代理需要紧描述[42，67]。引用【67】，“（无遗憾）学习方法需要指数级迭代才能收敛，与（1）成比例/)k对于常数k>1。另一方面，我们的椭球基算法是对数多项式().” . . . “均衡概念的难解性将使其作为行为模型变得不可信。用卡马尔·贾因的话来说：“如果你的电脑找不到它，那么市场也找不到。”我们的分析解释了这一漫长的瞬态（亚稳态）时期的算法行为，表明这种行为可能与标准的渐近平衡分析所表明的截然不同，效率更高。事实上，对现实生活中的拥塞游戏（如无线网络）进行的计算实验似乎与我们对MWU及其变体的缓慢/不稳定和性能差的理论分析一致，我们现在讨论这些理论分析。MWU及其变体在拥塞设置的实际应用中无法有效收敛。Appavoo等人[3]通过模拟研究移动网络的资源选择问题，这些问题被描述为拥塞博弈。

他们研究了MWU和EXP3的性能，这是MWU的一种著名的多武装匪徒变体，并表明即使在相对较小的情况下（20个设备/代理和3个网络/资源），这些算法也无法达到平衡，事实上，它们的性能比天真贪婪的解更差。[4] 对这些故障进行更清晰的迭代，确定稳定速度慢是性能不佳的主要原因。路由游戏中的混乱之路25“…我们考虑了无线网络选择的问题。移动设备通常需要选择合适的网络来关联以获得最佳性能，这是非常重要的。领先的多臂bandit算法EXP3的优秀理论特性表明，它应该能很好地解决这类问题。然而，它在实践中表现不佳。一个主要限制是它的速度较慢。”稳定率。”步长为2-100现实作为人类行为的典范？不断缩小的学习步长是人类学习行为的一个相当艺术化的模型；一个足够小的步骤意味着学习几乎不会发生。更合理的是，排除不现实的无学习行为的情况，学习率的下限应该强制执行。我们将采用该确切参数作为MWU模型的固定学习率。事实上，我们使用固定的（但任意小）步长，而不是限制值为零的连续收缩步长，这是我们模型的一个特点，它并没有人为地限制代理的适应性，只是为了使理论结果在不合理的长时间范围后才具有约束力。缩小步长而增加总体。

最后但并非最不重要的一点是，我们现在展示了如何对固定学习率进行分析 只要我们允许一个动态演化的、不断增长的种群，就可以很容易地扩展到捕捉任意步长缩小序列的非平衡现象。应该已经很清楚，步长 人口规模N（或相当于最大成本M的值）是控制系统稳定性的竞争力量。人口规模越大意味着最大成本M越大，这反过来意味着MWU的时间范围越大，通过缩小步长算法获得的时间平均遗憾越小，而对于分类平衡、无ZF状态的价格分析，则恢复其预测能力。不幸的是，如果人口以足够快的速度增长，以应对不断缩小的步长率，那么时间平均后悔永远不会消失。具体而言，从我们的分析中，我们证明了控制长期动态（如平衡、极限环、或混沌）和社会成本的相关参数是a=（α+β）N ln1.-, 见第4节。只要在每个时间步n，a（n）=（α+β）n（n）ln1.-（n）如果大于混沌阈值，则系统将始终保持在混沌状态，尽管步长变为零。例如，对于（n） =1/√n、 这表明n≥ab（α+β）ln1.-1/√n其中Abi是定理3.8中定义的混沌阈值。简单计算表明，它支持N≥ab（α+β）√n≥ab（α+β）ln1.-1/√n,也就是说，缓慢（次线性）增长的人口支持系统在其非平衡、无效、混沌的状态下永远保持不变。结论探讨了两策略非原子拥塞博弈中的乘性权值更新算法。

我们发现，标准的博弈论均衡分析，如无ZF状态的代价，无法捕捉我们简单模型中极其丰富的非均衡现象。即使无ZF状态的代价等于1，当总需求N增加时，系统也会动态不稳定。每个系统都有一个承载能力，超过该承载能力，动力学将变得不平衡。事实上，如果平衡流是不对称的，当N足够大时，它们就会变得混乱。26 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.Piliourast这种需求驱动的不稳定性是一种强大的现象，适用于许多不同的拥塞博弈设置（许多路径、原子/非原子拥塞博弈、不同的成本函数等）。在线性成本函数的情况下，我们在这里研究的动力学也表现出显著的时间平均特性；也就是说，在由大量总需求驱动的任何非平衡状态下，路径的时间平均流量/成本精确收敛到纳什均衡值，这一特性让人想起零和博弈中后悔最小化动态的行为。在多项式成本函数的情况下，时间平均成本表现出类似的规律性，即没有任何一条路径比平均成本便宜得多。有趣的是，当我们不断增加系统总需求时，拥塞博弈会逐渐“分解”，并将其特征变得更像零和博弈。另一方面，即使无ZF状态的价格等于1，时间平均收敛性也不能保证后悔少或社会成本低。事实上，时间平均出口和时间平均社会成本随着平衡值的波动而增加，在非平衡状态下，平衡值可能最大。

在对称平衡流的情况下，波动是由极端摆动引起的；当人口规模较大时，几乎所有用户都会选择相同的路线，同时在两条路线之间切换。因此，在这种情况下，时间平均社会成本可能会尽可能高。我们的游戏学习模式看起来很好，充满了惊喜和困惑。动态系统方法提供了一个有用的框架来研究非均衡动态与经典博弈论（均衡）指标（如后悔和无政府状态价格）之间的异常联系。例如，我们在附录中表明，在某些非均衡制度中，尽管存在唯一均衡，但系统可能有多个不同的吸引子，因此时间平均后悔和社会成本严重依赖于初始条件。同样在附录中，我们还报告了其他有趣的观察结果，讨论了未来的方向，甚至包括对许多设置的扩展。还介绍了周期轨道的显著性质，如两个吸引周期轨道的共存，以及Feigenbaum\'speriod-double分岔到混沌的路径。确认Thiparat Chotibut和Georgios Piliouras确认SUTD grant SRG ESD 2015 097、MOE AcRF Tier 2 grant 2016-T2-1-170、grant PIE-SGP-AI-2018-01和NRF 2018联谊会NRF-NRFF2018-07。Fryderyk Falniowski感谢波兰国家科学中心、grant 2016/21/D/HS4/01798和COST Action CA16228“欧洲博弈论网络”的支持。西蒙斯基金会（Simons Foundation）的426602号赠款部分支持了米夏米修韦奇兹（MichaL Misiurewicz）的研究。参考文献[1]Roy L.Adler、Alan G.Konheim和M.H.McAndrew。拓扑熵。《美国数学学会学报》114（1965），309–319。[2] Llu Alsed a、Jaume Llibre和Micha l Misiurewicz。2000

一维组合动力学与熵。第5卷。世界科学出版公司。[3] Anuja Meetoo Appavoo、Seth Gilbert和Kian Lee Tan。2018年。精明的选择速度问题：使用Smart EXP3！。2018年IEEE第38届分布式计算系统（ICDC）国际会议。IEEE，188–199。路线游戏中的混乱之路27【4】Anuja Meetoo Appavoo、Seth Gilbert和Kian Lee Tan。2019年，合作速度问题：使用联合强盗！arXiv电子印刷，文章arXiv:1901.07768（2019年1月），arXiv:1901.07768页。arXiv：cs。NI/1901.07768【5】桑杰夫·阿罗拉、埃拉德·哈桑和萨蒂恩·卡勒。乘法权重更新方法：元算法和应用。《计算理论》8，1（2012），121–164。[6] 詹姆斯·贝利（JamesP.Bailey）和乔治·皮利奥乌拉斯（GeorgiosPiliouras）。2018年。零和游戏中的乘法权重更新。在ACM经济学和计算会议上。[7] 詹姆斯·贝利（JamesP.Bailey）和乔治·皮利奥乌拉斯（GeorgiosPiliouras）。2019年。零和游戏中快速而激烈的学习：用非消失步长消除遗憾。arXiv电子印刷，arXiv:1905.04532（2019年5月），arXiv:1905.04532页。arXiv：cs。GT/1905.04532[8]詹姆斯·P·贝利和乔治·皮利奥乌拉斯。网络零和博弈中的多智能体学习是一个哈密顿系统。在AAMAS。[9] P.Berenbrink、M.Hoefer和T.Sauerwald。2014年，分布式Sel fish负载平衡网络。在ACM算法事务中（TALG）。[10] 维托里奥·比洛、安吉洛·法内利和卢卡·莫斯卡德利。2017年，《关于消化游戏中的前瞻均衡》。《计算机科学中的数学结构》27，2（2017），197–214。[11] 弗朗索瓦·布兰查德。拓扑混乱：这意味着什么？《差异方程与应用杂志》15，1（2009），23–46。[12] 弗朗索瓦·布兰查德、埃利·格拉斯纳、谢尔盖·科利亚达和安东尼奥·马斯。2002年，关于LiYorke pairs。

《f¨ur die reine und angewandte Mathematik杂志》547（2002），51–68。[13] 弗朗索瓦·布兰查德、文黄和卢博米尔·斯诺哈。2008。置乱集的拓扑大小。数学学术讨论会110，2（2008），293–361。[14] Avrim Blum、Eyal Even Dar和Katrina Ligett。无遗憾路由：路由博弈中遗憾最小化算法纳什均衡的收敛性。第二十届ACM分布式计算原理年度研讨会的筹备工作。ACM，45–52。[15] 鲁弗斯·鲍恩。拓扑熵与公理A.过程。Sympos。纯数学14（1970），23–41。[16] Abraham Boyarsky和Pawel Gora。2012，《混沌定律：一维不变测度和动力系统》。施普林格科学与商业媒体。[17] G.W.布朗。通过虚拟游戏的迭代解。《生产和分配的活动分析》，T.C.Koopmans（编辑），纽约：Wiley。(1951).[18] Nicol\'o Cesa Bianchi和G\'abor Lugoisi。2006.预测、学习和游戏。剑桥大学出版社。[19] Yun Kuen Cheung和Georgios Piliouras。2019年，《极小值优化中的漩涡而非平衡：零和游戏中在线学习的混沌和奶油效应》。骑着小马。[20] Thiparat Chotibut、Fryderyk Falniowski、Micha l Misiurewicz和Georgios Piliouras。2018年，博弈论中的混沌地图家族。arXiv:1807.06831[数学DS]手稿可在https://arxiv.org/abs/1807.06831.[21]G克里斯托杜鲁和E.库特索皮亚斯。有限拥挤博弈的无政府代价。STOC（2005），67–73。【22】里卡多·科里尼·巴尔德斯基、罗伯特·科米内蒂、帕纳约提斯·梅尔蒂科普洛斯和马可·斯卡西尼。2017年，无政府状态价格的渐近行为。在网络和互联网经济学国际会议上。斯普林格，133–145.28 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURAS【23】里卡多·科里尼·巴尔德斯基、罗伯特·科米内蒂和马可·斯卡西尼。2016

高度拥挤的非原子网络游戏的无政府代价。在算法博弈论国际研讨会上。斯普林格，117–128。[24]Riccardo Colini Baldeschi、Roberto Cominetti和Marco Scarsini。2018年，平行网络中高度拥挤的路由游戏的无政府代价。《计算系统理论》（2018），1-24。[25]查尔斯·康利。孤立不变集与莫尔斯指数。38号。美国数学Soc。[26]Jos\'e Correa、Jasper de Jong、Bart de Keijzer和Marc Uetz。2018年。网络路由的非效率和子博弈完美均衡。运筹学数学（2018）。【27】C.达斯·卡拉基斯（C.Daskalakis）、R.弗隆吉罗（R.Frongillo）、C.帕帕迪米特里欧（C.Papadimitriou）、G.皮耶拉科斯（G.Pierrakos）和G.Valiant。关于纳什均衡的学习算法。算法博弈论研讨会（SAGT）（2010），114–125。[28]曼弗雷德·登克、克里斯蒂安·格里伦伯格和卡尔·西格蒙德。2006，《碰撞空间的遍历理论》。第527卷。斯普林格。[29]Eyal Even Dar和Yishay Mansour。鱼类改道的快速收敛。第十六届ACM-SIAM离散算法年度研讨会（SODA’05）的筹备工作。772–781.[30]米切尔·J·费根鲍姆。非线性变换的普遍度量性质。《统计物理学杂志》第21期（1979年）。[31]Michal Feldman、Nicole Immorlica、Brendan Lucier、Tim Roughgarden和VasilisSyrgkanis。2016年，大型游戏中无政府状态的代价。第四十八届ACM计算理论年度研讨会论文集（STOC’16）。ACM，美国纽约州纽约市，963–976年。[32]Simon Fischer、Harald R¨acke和Berthold V¨ocking。通过自适应采样方法快速收敛于Wardrop平衡。《三十八年一度的ACM计算理论研讨会论文集》（STOC’06）。653–662.[33]Dylan J Foster、Thodoris Lykouris、Karthik Sridharan和Eva Tardos。2016年，《游戏中的学习：快速收敛的稳健性》。

神经信息处理系统的进展。4727–4735.[34]Dimitris Fotakis、Alexis C.Kaporis和Paul G.Spirakis。原子充血游戏：快速、近视和并发。在算法博弈论中，Burkhard Monineand Ulf Peter Schroeder（编辑）。计算机科学课堂讲稿，第4997卷。海德堡斯普林格伯林，121–132。[35]Dimitris Fotakis、Spyros Kontogiannis和Paul Spirakis。2005年。Sel fish unsplitable flow。理论计算机科学348，2–3（2005），226–239。《自动机、语言和编程：算法和复杂性》（ICALP-A 2004）。[36]德鲁·福登伯格和大卫·K·莱文。1998年，《游戏学习理论》。按键。【37】Tobias Galla和J.Doyne Farmer。2013年，《学习复杂格言的复杂动力学》。110, 4 (2013), 1232–1236.[38]高兵和沈卫晓。2014年，Summability意味着Collet–Eckmann几乎可以肯定。遍历理论与动力系统34，4（2014），1184–1209。[39]Eli Glasner和Benjamin Weiss。对初始条件的敏感依赖。非线性6，6（1993），1067–1085。路线游戏中的混乱路线29[40]伊莱·格拉斯纳和叶向东。2009年，《局部熵理论》。遍历理论与动力系统29，2（2009），321–356。【41】J.Hobbauer和K.Sigmund。进化博弈与种群动力学。剑桥大学出版社，剑桥。[42]Albert Xin Jiang和Kevin Leyton Brown。紧对策中精确相关均衡的多项式时间计算。第12届ACM电子商务会议记录。ACM，119–126。【43】R.Kleinberg、K.Ligett、G.Piliouras和E.Tardos。2011年，超越纳什均衡。在计算机科学创新研讨会上。【44】罗伯特·克莱因伯格、乔治·皮利奥乌拉斯和伊娃·塔多斯。乘法更新在拥塞游戏中执行通用无悔学习。在ACM计算理论研讨会（STOC）上。【45】R。

Kleinberg、G.Piliouras和E.Tardos。2011年，公告板模型中的负载平衡无悔。分布式计算24，1（2011），21–29。【46】Elias Koutsoupias和Christos H.Papadimitriou。最坏情况均衡。InSTACS。404–413.【47】米兰·库赫塔和雅罗斯拉夫·斯米塔尔。两点置乱集意味着混沌。欧洲迭代理论会议论文集ECIT 87（Caldes de Malavella（西班牙），1987）。世界Sci。出版，新加坡。[48]奥斯卡·E·兰福德。费根鲍姆不动点存在的一个简短证明。《数学物理通讯》96（1984）。【49】李健、叶向东。2016。拓扑动力学混沌理论的最新发展。数学学报，英文系列32，1（2016），83–114。[50]Tien Yien Li和James A.Yorke。第三阶段意味着混乱。《美国数学月刊》82、10（1975）、985–992。米哈伊尔·柳比奇。作为混沌定性可解模型的二次族。通知AMS 47（2000），1042–1052。【52】T.Mai、I.Panageas、W.Ratcliff、V.V.Vazirani和P.Yunker。2018年，零和差异博弈中的周期与生物多样性。在ACM EC中。【53】Panayotis Mertikopoulos、Christos Papadimitriou和Georgios Piliouras。2018年，Cyclesin对抗性正规化学习。在ACM-SIAM离散算法研讨会上。[54]Micha l Misiurewicz。1979年，用于绘制间隔的马蹄铁。公牛Acad。波隆。Sci。谢尔。Sci。27 (1979), 167–169.[55]Micha l Misiurewicz和Wies law Szlenk。分段单调映射的熵。数学研究67，1（1980），45–63。【56】Dov Monderer和Lloyd S Shapley。1996年。具有相同利益的虚拟游戏财产。《经济理论杂志》68，1（1996），258–265。【57】塞加内什·纳加拉扬（Sai Ganesh Nagarajan）、萨梅·穆罕默德（Sameh Mohamed）和乔治·皮利奥乌拉斯（Georgios Piliouras）。2018