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

为了更深入地讨论这些问题，我们请读者参考布兰查德（Blanchard）[11]、格拉斯纳（Glasner）和叶（Ye）[40]、李（Li）和叶（Ye）[49]以及吕特（Ruette）的书（76）]所做的出色调查。fa的熵，双正：在讨论之后，我们可以展示fa，b的熵是如何表现的。对于任何区间映射，我们有以下内容：定理6.2（[54]）。对于区间映射f，以下断言是等价的：i）f有一个周期不是2的幂的周期点，ii）f的拓扑熵为正。因此，定理6.2结合推论3.9加强了后者。推论6.3。如果b∈ （0，1）\\{1/2}，则存在a>abthen fa，所有周期的Bhasperic轨道，正拓扑熵和Li-Yorke混沌。计算熵：一般来说，计算熵不是一件容易的事。然而，在区间映射的上下文中，拓扑熵可以非常直接地计算出来——它等于fn的最小单调子区间数的指数增长率。定理6.4（【55】）。设f是分段单调区间映射，对于所有n≥ 1，设Cn为fn的单调划分的最小基数。Thenh（f）=limn→∞nlog cn=infn≥1nlog中国。此外，对于分段单调区间映射，在映射为单调的区间上，用任何分区计算的熵就是拓扑熵【2，Prop.4.2.3】。这为我们从博弈论的角度理解fa，B的正熵意味着什么提供了一种方法。对于a>b（1-b） 映射fa，bis是一个双峰映射，具有两个临界点xl，xr（定义于（10））和a（唯一于（0，1））平衡b∈ （xl，xr）。

因为x是选择第一种策略的概率，所以我们可以说，如果x<xlor x>xr，那么其中一种策略被过度使用，如果x接近b，那么x∈ [xl，xr]，则系统大致处于平衡状态。现在，我们可以把一个分区{[0，xl），[xl，xr]，（xr，1]}分成三个区间，在这三个区间上，fa，bismonentine。对于每个x∈ [0，1]和每n≥ 1如果系统大致处于平衡状态，即如果fna，b（x），我们为x:x[n]=A的n-迭代编码三个事件∈[xl，xr]；x【n】=B如果第二种策略被过度使用，即fna，B（x）∈ [0，xl）和x[n]=到岸价第一种策略被过度使用，fna，b（x）∈ （xr，1）。对于每个x∈ [0，1]我们得到了字母表{A，B，C}上的20个T.CHOTIBUT，F.FALNIOWSKI，M.MISIUREWICZ和G.PILIOURASin有限序列x。现在，h（fa，b）>0的事实意味着长度n的不同块的数量，我们可以通过观察以这种方式生成的不同x来观察，将呈指数增长。6.2. 不变测度和遍历定理。我们还可以根据概率空间上定义的保测度变换讨论离散动力系统。这种方法不仅可以处理纯粹的数学概念，而且可以处理自然界中的物理现象。本小节专门讨论不变测度、绝对连续测度和遍历理论中最基本的思想——Birkhoff遍历定理，该定理指出，概率为1时，沿遍历变换轨道的函数平均值等于给定函数的积分。定义。设（X，B，u）为概率空间，f:X 7→ X是一个可测量的地图。如果u（f），则度量u是f不变的（映射f是u不变的-1E）=u（E）对于每个E∈ B、 对于f-不变测度u，如果E∈ B满意度f-1E=Eif且仅当u（E）=0或1时。

度量u相对于Lebesguemeasure是绝对连续的当且仅当对于每个集合E∈ 零Lebesgue度量值的Bu（E）=0。我们现在可以陈述遍历定理。定理6.5（Birkhoff遍历定理）。设（X，B，u）为概率空间。如果f是u不变的，g是可积的，则→∞nn型-1Xk=0g（fk（x））=g*（x） 对于一些g*∈ L（X，u）和g*（f（x））=克*（x） 对于几乎每个x。此外，如果f为isergodic，则g为*是常数和极限→∞nn型-1Xk=0g（fk（x））=ZXg du几乎每x一个。最后，为什么绝对连续不变度量很重要？基于计算机的研究被广泛用于深入了解混沌现象的动力学。然而，在解释计算机模拟时必须谨慎。通常，混沌系统表现出多个遍历不变测度[38]；因此，区分实际轨道显示的测量值和计算机模拟获得的轨道测量值非常重要，这可能会由于累积的计算舍入误差而有所不同。但如果存在关于Lebesgue测度的绝对连续测度，那么计算机模拟将产生我们期望的测度[16]。因此，理论测量和计算测量在这项工作中是一致的。7、相关工作博弈论中的学习动力学研究历史悠久，可以追溯到布朗（Brown）[17]和罗宾逊（Robinson）[71]关于零和游戏中的实际游戏的研究，该研究紧随着诺依曼（Dvon Neumann）关于零和游戏的开创性工作[88，89]。一组具有代表性的参考书如下：塞萨·比安奇（Cesa Bianchi）和卢戈西（Lugoisi）[18]，福登堡（Fudenberg）和莱文（Levine）[36]，霍夫鲍兰（Hoffauerand Sigmund）[41]，桑多姆（Sandholm）[78]，塞尔古（Sergiu）和安德烈（Andreu）[80]，杨（Young）[。路由游戏中的混乱之路是21个主要的先兆。Palaiopanos等人[62]提出了拥塞博弈中乘性权重更新（MWU）学习产生的混沌动力学研究。

他们建立了具有线性代价函数的两个主体和两个环节的原子拥挤对策中周期为2的吸引极限环和Li-Yorke混沌的存在性。博弈的对称性（即对称均衡的存在，其中双方以0.5的概率选择每条路径）导致了周期2的极限环。他们还研究了一个具有不对称均衡的游戏的特定实例，如果代理以足够大的学习率（步长）调整策略，MWU会导致Yorke混乱 （相当地，如果代理使用固定的学习率 但他们的成本规模很大）。不久之后，Chotibut等人[20]确定，如果均衡是不对称的，则Li-Yorke-chaosis普遍存在于具有两个平行链接和线性代价函数的任何两代理原子拥塞博弈中。也就是说，在任何具有非对称均衡的2×2拥塞博弈中，当成本函数增长到足够大时，Li-Yorke混沌就会出现，但前提是初始条件是对称的，即两个代理从相同的初始条件开始。此外，[20]首次确定，尽管存在周期性或混沌行为，但两个代理的时间平均策略始终精确收敛到内部纳什均衡。虽然我们目前的工作利用了[20]中的技术，但它还研究了混沌的其他定义，例如正拓扑熵，研究非原子拥塞博弈，并将结果与无政府状态和系统效率分析的价格相关联。此外，尽管在[20，62]中，混沌行为包含在二维空间的一维变子空间中，但在本文中，系统的维数已经等于1，因此混沌结果与整体状态空间相关。

最后，在附录中，我们提供了在具有多个自由度的更大、更复杂的拥塞博弈中学习动态的初步结果。博弈论中的混沌。在完全理性假设下，纳什均衡是博弈论的核心概念，这并不奇怪。然而，在现实中，玩家通常不会遵循纳什均衡策略进行游戏。Satoet等人的开创性工作【79】通过计算系统的Lyapunov指数分析表明，即使是在一个简单的两人游戏中的岩石纸剪刀，复制器动力学（MWU的连续时间模拟）也会导致混沌，使平衡策略无法实现。对于具有大量可用策略的两人博弈（复杂博弈），Gallaand Farmer[37]认为，经验加权吸引（EWA）学习，一种学习动力学的行为经济学模型，在大参数空间中也表现出混沌行为。正如最近的后续研究所表明的那样，这些混沌动力学的普遍存在也持续存在于许多玩家的游戏中【77】。因此，仔细的研究表明，许多游戏（小游戏或大游戏）中存在着复杂的行为景观，目前没有单一的理论框架适用。Sparrow等人【83】和van Strien and Sparrow【87】证明了一类3x3游戏的实际播放学习动力学，包括Shapley游戏和zero-sumdynamics，具有丰富的周期和混沌行为。Cheung和Piliouras【19】证明了许多在线学习算法，包括MWU，当应用于零和博弈时，步长恒定的是Lyapunov混沌。最后，Pangallo等人【64】通过实验证明，强化学习的一种变体，即经验加权吸引（EWA），会导致具有负相关支付的两个代理博弈中的极限环和高维混沌。

这有力地表明，混沌、非平衡的结果可以进一步推广到零和对策的其他变体。22 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURASOther近期博弈论中的非均衡现象。近年来，（算法）博弈论界产生了一些非均衡结果。Daskalakiseet al.（27）表明，在一个特定的c3×3游戏中，MWU即使在时间平均意义上也不会收敛。Kleinberg等人[43]在2×2×2博弈中建立了复制子动力学的非收敛动力学，结果表明，系统社会福利收敛到支配所有纳什均衡的状态。Ostrovski和van Strien【61】分析了3×3游戏中的连续时间竞争，并类似地表明，动态支配着绩效纳什均衡。我们的结果为这一方向增添了新的一章，提供了对非原子拥挤博弈中MWU产生的非均衡现象的详细理解，以及它们对后悔和社会成本的重要影响。在进化博弈论背景下，通常研究连续时变的WU（复制子动力学），许多非收敛结果是已知的，但通常仅限于小博弈[78]。Piliouras和Shamma【70】以及Piliouras等人【68】表明，（网络）零和游戏中的复制子动力学表现出一种特殊类型的重复行为，称为庞加莱复发。最近，Mertikopoulos等人[53]证明了Poincar'e递归也出现在一类更一般的连续时间动力学中，称为跟随正则化领导者（FTRL）。Mai等人[52]建立了复制子的递归结果扩展到动态演化的零和博弈。复制子动态的完美周期（即循环）行为可能出现在团队竞争中【69】以及网络竞争中【57】。

这一类的作品结合了体积守恒和运动常数的存在（“能量守恒”）等论点，以显示循环或重复的行为。Pangallo等人[63]根据经验确定了游戏中大量学习动态中周期和更普遍的非平衡行为的出现，并显示了它们的行为与更简单的最佳反应动态行为之间的相关性。[65]中发展了complexlearning动力学的极限行为和更好的响应动力学之间的一些形式联系。游戏动力学如物理学。最近，Bailey和Piliouras【8】在博弈论、在线优化和经典物理学中普遍存在的一类系统（称为哈密顿动力学）之间建立了一种稳健的联系，哈密顿动力学自然表现出守恒定律。对于离散时间动力学，如MWU或梯度下降，系统轨迹是连续动力学的一阶近似值；守恒定律和循环不再成立。相反，正如Bailey和Piliouras【6】所示，我们得到了边界的“能量”增加和发散，以及零和博弈中的体积膨胀和Lyapunov混沌，如Cheung和Piliouras【19】所示。尽管存在这种发散、混沌的行为，步长固定的梯度下降在零和博弈中仍有消失的遗憾【7】。到目前为止，还不清楚哈密顿动力学的联系可以推广到什么程度；然而，Ostrovski和van Strien[60]考虑了一类分段哈密顿向量场，其轨道是分段直线，并发展了与最佳回复动力学的联系。

博弈论和物理学之间的联系有望使我们理解并可能利用非平衡博弈动力学中的隐藏结构，类似于本文中我们如何正式证明混沌动力学的时间平均值收敛于平衡值。作为动力系统的博弈动力学。最后，Papadimitriou和Piliouras【65，66】提出了一个将博弈论与动力系统拓扑联系起来的程序，特别是康利的动力系统基本定理【25】。这种方法将注意力从纳什均衡转移到更一般的递归概念，称为链递归。路由博弈23中的混沌路径概念概括了周期性和庞加莱循环，因此可以在单个框架中表达上述结果。该框架是否有用以及在多大程度上有用取决于许多因素，包括将其成功纳入计算、实验框架的可能性（当前方法见[59]）。注意，我们的论文还试图与动力系统文献，特别是与发展迅速的区间映射理论以及遍历理论建立一座桥梁。8、关于固定步长与收缩步长和重设步长的讨论关于收缩步长和消失遗憾的讨论是什么？在本文中，我们用固定的步长检验EMWU 那有着不可磨灭的遗憾。如果代理利用缩小的步长（这取决于游戏历史的长度），我们的结果是否可以忽略。 = 1/√T，其结果是O（1）的消失遗憾/√T）？应用缩小步长是一种快速、无痛的方法吗？答案是否定的。

原因在于大O符号。O（1/√后悔：O里面是什么？当代理使用收缩步长大小实现MWU时（T）=1/√T，每个时间步的成本为cn:A→ R、 带cn（s）∈ [0，M]，那么它的遗憾是xt=1Ean~xncn（an）{z}MWU，带1/√T步长<mina∈ATXn=1cn（a）{z}最佳固定动作+（M+1）pT log（| a |），其中| a |是代理可用的策略数量（关于为什么术语O（MpT log（| a |））在一般优化设置中无法进一步改进的讨论，另请参见[18][第2.6、2.8节，备注2.2]）。因此，时间平均遗憾为（M+1）√日志（| A |）√T、 当T消失时→ ∞. 然而，对于足够大的M，后悔变得可以忽略的时间T可能是不切实际的大。在游戏的情况下，由于在线支付流的稳定性，我们可以证明更强大的遗憾边界[33，85]，包括所有（连续时间）的Θ（1/T）[53]，遵循正规化领导者（FTRL）动力学，其中包括MWU。然而，这些界限意味着为了达到一种小小的后悔状态, 我们仍然需要一些M为多项式的步骤/, 其中，M是我们游戏中可能的最大成本值。在我们设置的拥挤游戏中，M的价值是什么？这是最坏的可能成本M=N max{α，β}。所以，对于一个大的人口规模N，甚至对于MWU, 等到遗憾小到可以忽略不计时，等待的时间可能会很长，这是不切实际的。对于任何有意义的时间范围，代理的遗憾可能仍然很大，以至于无法应用（λ，u）-稳健性类型的结果【73】。

需要一个新的理论框架来研究这些具有巨大遗憾的长过渡期。成本标准化“把戏”只掩盖了收敛速度慢的问题。在任何游戏中，包括与多个代理的拥挤游戏中，都可以将成本标准化，使其位于[0，1]而不是[0，M]，事实上，这是分析无遗憾动态时Archy文献价格的标准做法。在这种情况下，后悔一词似乎更为无害：24 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURASTXt=1Ean~xncn（an）{z}MWU，带1/√T步长<mina∈ATXn=1cn（a）{z}最佳固定动作+2pT log（| a |）{z}以最坏可能成本为单位的遗憾当然，这并不能解决问题，因为遗憾项看起来很小，但实际上是以非常大的单位表示的。这种成本标准化表明，如果在纽约，所有司机都使用同一条道路，那么他们所经历的成本等于1。当然，这种噩梦般的情景，如果能够实施的话，将转化为一场可怕的交易，需要数百或数千小时才能解决。因此，在这种情况下，真正令人遗憾的是2pT log（| A |）×（在一个有数百万人口的城市中，最严重交通堵塞的持续时间）。这是一个巨大的数字，只能通过提前运行系统来摊销。g、 纽约市的情况已经持续了数百年。使用与被测问题成比例的测量单位（就像一根卷尺，不断调整米的概念）会造成相当多的混淆，即在合理的时间范围内，状态的可及性如何。