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

进化博弈动力学中的三体问题：收敛性、周期性和极限环。在第17届自主智能体和多智能体系统国际会议记录中。国际自主代理和多代理系统基金会，685–693。【58】诺姆·尼桑、蒂姆·劳夫加登、伊娃·塔多斯和维杰伊·瓦齐拉尼。2007年，《算法游戏理论》。美国纽约州纽约市剑桥大学出版社【59】Shayegan Omidsha fiei、Christos Papadimitriou、Georgios Piliouras、Karl Tuyls、MarkRowland、Jean Baptiste Lespiau、Wojciech M Czarnecki、Marc Lanctot、Julien Perolat、30 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.Piliourand Remi Munos。2019年{\\alpha}-排名：多智能体进化评估。arXiv预印本arXiv:1903.01373（2019）。[60]乔治·奥斯特罗夫斯基和塞巴斯蒂安·范斯特林。与零和博弈相关的分段线性哈密顿流：转移组合学和遍历性问题。规则与混沌动力学16，1-2（2011），128–153。[61]乔治·奥斯特罗夫斯基和塞巴斯蒂安·范斯特林。2014年，游戏的支付绩效。《动力学与游戏杂志》，第1篇（2014），621-638页。【62】Gerasimos Palaiopanos、Ioannis Panageas和Georgios Piliouras。2017年。拥挤游戏中乘法权重更新，步长不变：收敛、极限周期和混沌。神经信息处理系统的进展。5872–5882.【63】马可·潘加洛、托尔斯滕·海因里希和J·多因·法默。2019年。一般游戏中的最佳回复结构和均衡收敛。《科学进步》5，2（2019），eaat1328。【64】马可·潘加洛、詹姆斯·桑德斯、托拜厄斯·加拉和多恩·法默。2017年，《2 x 2游戏中学习动态的分类》。arXiv电子印刷，文章arXiv:1701.09043（2017年1月），arXiv:1701.09043页。arXiv:q-fin.EC/1701.09043【65】克里斯托斯·帕帕迪米特里欧和乔治·皮利奥乌拉斯。2018

从纳什均衡到链递归集：博弈论的算法解概念。熵20，10（2018）。【66】克里斯托斯·帕帕迪米特里奥和乔治·奥斯·皮利奥乌拉斯。2019年。游戏动力学作为游戏的意义。ACM SIGecom交易所16、2（2019）、53–63。【67】克里斯托斯·H·帕帕迪米特里奥和蒂姆·劳夫加登。计算多人博弈中的相关均衡。J、 ACM 55，3，第14条（2008年8月），29页。【68】乔治·皮利奥乌拉斯（Georgios Piliouras）、卡洛斯·尼托·格兰达（Carlos Nieto Granda）、亨里克·克里斯滕森（Henrik I.Christensen）和杰夫·沙玛（Je ffs.Shamma）。2014，《持久模式：超越均衡和效用的多智能体学习》。伊纳马斯。181–188.[69]乔治·皮利奥乌拉斯（GeorgiosPiliouras）和伦纳德·舒尔曼（LeonardJ.Schulman）。2018年。学习动力和竞争性物种的共同进化。在ITC中。【70】乔治·皮利奥乌拉斯和杰夫·沙玛。2014。混沌优化：通过庞加莱递推对复杂极限集的凸松弛。第二十届ACM-SIAM离散算法年度研讨会论文集。暹罗，861-873年。【71】J.罗宾逊。一种求解博弈的迭代方法。数学年鉴54（1951），296-301。【72】R.W.罗森塔尔。1973。一类具有纯策略纳什均衡的对策。《国际博弈论杂志》2，1（1973），65–67。蒂姆·劳夫加登。无政府状态代价的内在稳健性。过程中。STOC的。513–522.蒂姆·劳夫加登。2016年，二十场算法博弈论讲座。剑桥大学出版社。[75]蒂姆·劳夫加登和伊娃·塔多斯。sel fish路由有多糟糕？《美国医学会杂志》（JACM）49，2（2002），236–259。【76】西尔维·吕特。2017年，区间混乱。大学系列讲座，第67卷。美国数学学会。[77]詹姆斯·B·T·桑德斯、J·多恩·法默和托拜厄斯·加拉。2018年，在众多玩家参与的游戏中，混沌动力学的盛行。科学报告8（2018年）。[78]William H.Sandholm。2010年，《人口博弈与进化动力学》。

MITPress公司。路线游戏中的混乱之路31【79】佐藤裕如、秋山荣三和J.Doyne Farmer。2002年。学习简单双人游戏中的混乱。《国家科学院学报》99，7（2002），4748–4751。【80】哈特·塞尔朱和马斯·科勒尔·安德烈。简单的适应性策略：从后悔匹配到解耦动态。第4卷。《世界科学》（World Scientifi fic）[81]Aleksandr N.Sharkovsky。直线到自身的连续映射的循环共存。乌克兰。数学中弘。16 (1964), 61–71.[82]雅罗斯拉夫·斯米塔尔。零熵混沌函数。美国数学学会学报297，1（1986），269–282。科林·斯派洛、塞巴斯蒂安·范斯特林和克里斯托弗·哈里斯。3x3games中的虚拟游戏：周期性行为和混沌行为之间的过渡。《游戏与经济行为》63，1（2008），259–291。史蒂文·斯特罗加茨。非线性动力学与混沌。珀尔修斯出版社。【85】瓦西里斯·塞尔卡尼斯、阿列赫·阿加瓦尔、罗海鹏和罗伯特·E·夏皮雷。2015年，游戏规则化学习快速融合。第28届神经信息处理系统国际会议记录（NIPS\'15）。麻省理工学院出版社，马萨诸塞州剑桥，美国，2989–2997。[86]迈克尔·塔博尔。非线性动力学中的混沌与可积性：导论。威利，纽约。塞巴斯蒂安·范斯特林和科林·斯派洛。2011年，3x3游戏中的虚拟游戏：混乱和抖动行为。《游戏与经济行为》73，1（2011），262–286。约翰·冯·诺依曼。1928年的今天，Zur Theorie der Gesellschaftspiele。数学安。100 (1928),295–300.【89】约翰·冯·诺依曼和奥斯卡·摩根斯坦。博弈论与经济行为。普林斯顿大学出版社。【90】本杰明·韦斯。2000年，《单轨动力学》。CBMS区域会议系列《数学》，第95卷。美国数学学会，普罗维登斯，RI。[91]熊金成。一个具有拓扑熵的混沌映射。

数学学报，英语系列6，4（1986），439–443。[92]H Peyton Young。战略学习及其局限性。牛津大学出版社。32 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURASAppendicesAppendix A.吸引轨道的性质在本节中，我们研究了与区间映射fa，b相关的吸引周期轨道的性质：[0，1]→ [0，1]（21）fa，b（x）=xx+（1- x） exp（a（x- b） ）。我们在正文中指出，当b=0.5时，当a<8时，动力学将向固定点b=0.5收敛。对于任何a≥ 8，长时间动力学将收敛于周期2的吸引周期轨道，位于{σa，1- σa}。因此，分叉图围绕b=0.5对称，如图5的顶图所示。在这种情况下，时间平均后悔很好地接近其上限，归一化时间平均社会成本逐渐逼近最大值2。当b与0.5不同时，我们在正文中指出，如果a足够大，混沌的出现是不可避免的。到chaosis的倍周期分岔路线肯定会出现。正文的图2显示了Nb=0.7时的混沌分岔图。在这种不对称情况下，标准平衡分析仅适用于当执行点b稳定时，即当| fa，b（b）|≤ 1，或当≤ 2/b（1- b） 。Feigenbaum的混沌通用路径：图6显示了作为两个自由参数a和b函数的周期图。对于我们的双峰映射fa，b，报告费根鲍姆的混沌路径的数值观测很有趣。虽然费根鲍姆的普适性已知适用于具有二次最大值的一维单峰区间映射[30，48，86]，但我们也观察到了费根鲍姆的双峰区间映射的倍周期混沌路径。

具体而言，通过选择a和改变b，我们数值测量比率（22）δn≡bn+1- bnbn+2- bn+1，αn≡dndn+1，其中bn表示周期2n轨道出现的值，dn=fn-1a、b（xl）-左临界点xl=1.-第一季度-一（fa达到最大值的点）属于2n轨道。随着n变大（我们在n=12时截断观察值），我们发现（23）δn=12≈ 4.669 . . . , αn=12≈ -2.502 . . . ,这与费根鲍姆的普适常数δ=4.669201609102990一致，为4位数。和α=-2.502907875 . . . , 例如，在逻辑图中出现在通往朝圣的倍周期路线中。两个吸引周期轨道的共存以及遗憾和社会代价的非唯一性：当a>4时，映射fa，bha是一个负的Schwartzian导数，因此它有两个吸引或中性周期轨道。虽然每个周期轨道的时间平均值精确收敛到纳什均衡b，但方差极限→∞TPTn=1（xn- b） 同时存在的周期轨道可能会有所不同。因此，依赖于方差的归一化时间平均社会成本和时间平均后悔可以是多值的。获得的值取决于动力学渐近达到的吸引周期轨道的方差，其本身取决于初始条件x。通过这种方式，我们可以数值近似有符号的第二费根鲍姆常数α[84]。路线游戏33中的混乱路线图5。即使在b=0.5的对称情况下，分叉图（上图）也表明了总需求N增加所驱动的路由博弈的不稳定性， = 1.-1/e正常情况下，soa=N。在这种对称情况下，长时间动力学平衡时，网络的容量为N*b=8。在容量以上，吸引周期2的周期轨道出现。

（中）紫色圆圈符号所示的时间平均后悔在分岔处突然变成了严格的正后悔。遗憾界限也非常接近实际值。（下图）在分叉处，标准化时间平均社会成本也突然变得大于1。即使在对称的情况下，无ZF计量的经典价格在N>N时失败*b=8。图7揭示了两个共存的初始条件相关吸引周期轨道是如何交织在一起的，图8报告了两个共存周期轨道的证据，它们的变量不同，导致多值时间平均后悔和社会成本。轨道的稳定性：除了周期图之外，我们还通过考虑Lyapunov指数hlog | fa，b | i来研究吸引轨道的稳定性，其中h·i表示时间平均值。图9（底部）显示了与不同牵引轨道相关的李雅普诺夫指数，揭示了延伸支腿结构产生于theorbits变为超稳定的情况，即两个临界点之一是theorbits的元素。在相同周期（相同颜色）的区域内，如果其中一个临界点是轨道的一个元素，则称轨道为超稳定，因此fa，b（xc）=0。这意味着李雅普诺夫指数原则上是-∞, 可视为白色明亮的颜色。34 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURASFigure 6。与地图（21）相关的小周期吸引周期轨道的周期图。这些颜色将吸引周期轨道的周期编码如下：周期1（固定点）=黄色，周期2=红色，周期3=蓝色，周期4=绿色，周期5=棕色，周期6=青色，周期7=暗灰色，周期8=洋红色，周期大于8=白色。只有当固定点b稳定时，即当a≤ 2/b（1- b） 。

在相空间的其他区域，出现了非平衡动力学，系统通过倍周期分岔路径进入白区的混沌。图片由以下算法生成：放弃20000次初步迭代。如果| fn（x），则认为一个点是周期n的周期-x |<0.0000000001，并且它不是小于n的任何周期的周期。由于起点是左临界点xl=1/2，因此会导致轻微的不对称-p1/4- 1/a.此外，对于固定的a，当我们改变b并从外层渗透到混沌区域（白色）时，我们通过数值观察Feigenbaum的混沌普遍路径，如下所述。两条超稳定延伸支腿曲线相交。当两个临界点都是周期轨道的元素时，就会出现这种情况。此外，请注意，图6揭示了周期图中定性相似的延伸支腿结构分层出现，混沌状态夹在两层之间。请注意，连续层的周期相差1。为了理解这些周期递增的层出现的原因，我们研究了这些层中的超稳定周期轨道，发现除了左临界点xl=1/2之外，轨道的所有元素-p1/4- 1/a和它的图像fa，b（xl）约为0，与轨道周期无关。通过这一观察，我们现在利用推论3.4的纳什均衡性质的时间平均收敛性，近似每个层中的一个超稳定区域。也就是说，设xl是周期p的周期轨道的元素，只有xl和fa，b（xl）显著大于0，那么从推论3.4我们得到（24）xl+fa，b（xl）+fa，b（xl）+···+fp-1a、b（xl）| {z}≈ 0=pb。路由游戏中的混乱之路35图7。两个依赖于初始条件的吸引周期轨道的共存。

这些图片的生成过程与图6中所述的过程相同，只是这里顶部和底部图片的初始条件分别位于左侧和右侧临界点。还有，b∈ [43/80、51/80]和∈ [4, 54]. 颜色方案与图6相同：周期1（固定点）=黄色，周期2=红色，周期3=蓝色，周期4=绿色，周期5=棕色，周期6=青色，周期7=暗灰色，周期8=洋红，周期大于8=白色。数值结果表明，对于周期较大的周期轨道，除xl和fa外，b（xl）的各元素均接近0的近似值变得越来越好；因此，我们对 1、至主导订单ina、xl≈aandfa，b（xl）≈1+ae1-绝对值（24）为A+1+ae（1-ab）≈ pb。定义（25）S（a，b）=ab+b+（ab）e（1-ab），我们得到了条件（26）S（a，b）≈ p、 作为一个 1，对于xl，在具有上述性质的周期p的周期轨道上。图10显示了p=2，3，…，的S（a，b）水平集，10随着周期的增加，精确跟踪延伸支腿结构，表明这些超稳定轨道是图6.36 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURASFigure 8所示延伸支腿层的骨架。在b=0.61时，两个吸引周期轨道与两个不同的变量共存，意味着时间平均后悔和归一化时间平均社会成本的非唯一性。像往常一样，我们开始 = 1.- 1/e，因此N=a.（顶部）Shaddegreen区域中的N范围显示两个吸引周期轨道共存。如果初始条件为左（右）临界点xl（xr），则选择蓝色（红色）周期轨道。正如我们的双峰映射fa，b的负Schwartzian导数所保证的那样，存在最多2个共存的吸引周期轨道。

两个周期轨道的方差明显不同；因此，依赖于方差的时间平均后悔（中间）和归一化时间平均社会成本（底部）是多值的。获得哪些值取决于初始条件。此外，我们可以近似地得到临界点xl和xrbecometh都是这些超稳定周期轨道元素的条件。在这些特定的轨道排列中，我们需要xr=fa，b（xl）。从（24）中，我们得到xl+fa，b（xl）≈ pb。由于xl+xr=1，我们得出结论，当（27）b≈p、 anda[2 ln（a- 1) + 1] ≈p、 其中a上的条件遵循（26）和b≈p、 因此，如果我们绘制关系图=a[2 ln（a- 1） +1]，该图将包含两个临界点都位于具有aforementoEnd特性的周期轨道上的情况。如图9所示，路径游戏37中的破折号“通往混乱的道路”。（下）Lyapunov指数hlog | fa，b | i通过tptn=1log | fa，b（xn）|数值近似，T=2000，以灰度显示，叠加在图7（上）中采用的周期图（上）上。Lyapunov指数的配色方案是hlog | fa，b | i<-1.5显示为白色（非常稳定的轨道），hlog | fa，b | i>0显示为黑色（不稳定或混乱）。我们可以清楚地看到，延伸支腿结构是由超稳定轨道作为每个吸引周期轨道的骨架而形成的。当两个临界点都是吸引轨道的元素时，两条延伸的支腿相交。正如所料，在分岔边界附近和混沌区域，轨道生态不稳定，如黑色所示。图10中的橄榄绿线穿过每个period-p区域内两条超级稳定曲线之间的交点。附录B。

具有多种策略的拥塞对策的扩展在这一节中，我们将关于Li-Yorke混沌和时间平均收敛toNash均衡的结果推广到了多种策略的情况。我们将考虑一个具有连续的参与者/代理的m策略拥塞博弈，其中所有参与者/代理都使用乘法权重更新。每个参与者都控制着流量的一小部分。我们假设所有试剂的总流量等于N.38 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURASFigure 10。随着周期的增加，延伸支腿结构的层由超稳定周期轨道的特定公式产生。如轨道稳定性部分所述，S（a，b）=p定义了周期p的超稳定周期轨道，其性质是只有xl和f（xl）是周期轨道中不接近0的唯一两个元素。p=2，3，…，时S（a，b）的液位设置，10以不同颜色显示（底部），精确跟踪具有较大负Lyapunov指数的延伸腿部曲线（顶部）。theLyapunov指数的配色方案为hlog | fa，b | i<-1.5显示为白色（非常稳定的轨道），hlog | fa，b | i>0显示为黑色（不稳定或混乱）。虚线橄榄绿曲线B=a[2 ln（a- 1） 从（27）中获得的+1]包括两个临界点都是周期轨道的两个非近零元素的情况，即相同周期p的每个区域中的两条超稳定曲线相交的情况。这些结果提供了一个合理的答案，解释了为什么在图6的周期图中出现了周期增加的延伸支腿结构层。路由博弈中的混沌之路39我们将在时间n使用m策略之一i的玩家的分数表示为xi（n），其中i∈ {1，…，m}。