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

回想一下，时间平均后悔是（13）TRT=TTXn=1αNxn+βN（1- xn）- 最小值（TTXn=1αNxn，TTXn=1βN（1- xn））考虑（14）TTXn=1αxn-TXn=1β（1- xn）=TTXn=1[（α+β）xn- β] =（α+β）TTXn=1xn-βα + β!.第6节讨论了这一定义背后的直觉以及动力系统混沌行为的其他性质。事实上，我们可以加强这一结果，见第6节。路由博弈中的混沌路径13数量βα+β是系统平衡b。在不丧失一般性的情况下，我们假设前面提到的α+β=1。那么，b=β和limT→∞TPTn=1xn= b、 根据定理3.3。因此，在极限T→ ∞, （13）最小项中的两项重合，我们通过替换α=1得到- β，记住β=blimT→∞RTT=极限→∞NTTXn=1(1 - β） xn+β（1- xn）- β(1 - β)= 限制→∞NTTXn=1xn公司- 2βxn+β= 限制→∞NTTXn=1（xn- b） 。观察，如果x是遍历不变概率测度u的一般点，则可观测的时间限制（x-b） 等于其空间平均值（x-b） du（x）。该数量是随机变量恒等式（我们将表示该变量X，soX（X）=X）相对于u的方差。一般点集具有正Lebesgue测度的此类测度u的典型情况是，存在吸引周期轨道，并且u是在P上等分布的测度，并且u是相对于Lebesgue测度绝对连续的遍历不变概率测度[28]。类似于二次区间映射族[51]，我们有理由认为对于Lebesgue几乎每对参数（a，b）Lebesgue几乎每一个点x∈ （0，1）是这两种类型之一的度量的泛型。时间平均后悔上限：设a>4，b∈ (0, 1). 回顾（10）thatfa，bhas两个关键点xl=1.-第一季度-一和xr=1- xl码=1+q1-一.Letymin=fa，b（xr），ymax=fa，b（xl）。引理4.2。

对于a>b（1-b） 区间I=[ymin，ymax]是不变的，并且在（0，1）上全局吸收。证据修复b∈ (0, 1). 简单计算表明b∈ （xl，xr）当且仅当a>1/b（1-b） 。从现在起，我们假设a>1/b（1- b） 。回想一下，b是fa的固定点，bso我们有b=fa，b（b）∈ fa，b（[xl，xr]=[ymin，ymax]=I。因此b∈ 我∩ （xl、xr）和I∩ （xl，xr）6=.因为fa，bis在临界点之间递减，我们有fa，b（b）=ab- ab+1<0。后者和（0，1）中固定点的唯一性意味着fa，b（x）>x代表x∈ （0，b）和fa，b（x）<x表示x∈ （b，1）。显然，如果x∈ 我∩ （xl，xr），然后是fa，b（x）∈ fa，b（[xl，xr]）=I.对于x∈ 我们有fa，b（x）<fa，b（xl）=ymax。假设fa，b（x）<ymin，然后fa，b（x）<ymin≤ 但这是不可能的，因为对于x，fa，b（x）>x∈ （0，b）。因此fa，b（[ymin，xl]） 一、 同样的理由表明，fa，b（[xr，ymax]） 一、 因此fa，b（I） 一、 现在让x∈ （0，xl）。显然，fa，b（x）<ymax，因为xl<b，我们有fa，b（x）>x，因为x<xl。为了证明x的轨道最终落入I，有必要证明存在n，使得fna，b（x）>ymin。假设不存在这样的n，即fna，b（x）<yminforall n。序列（fna，b（x））n≥1是递增且有界的，因此它有一个限制。表示因此b∈ （xl，xr）当x=b排斥时（对于a>2/b（1-b） ）。14 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURASlimit由c∈ （0，xl）。那么fa，b（c）必须等于c，但这与（0，xl）上没有fa，b的固定点这一事实相矛盾。因此，（0，xl）中的每个点的轨道最终将落入不变集I。类似的推理将表明，x中的每个点的轨道∈ （xr，1）最终将落入I。引理4.2表示方差的以下界。备注4.3。

对于a>b（1-b） X的方差在var（X）=limT上有界→∞TTXn=1（xn- b） 哦！≤ （ymax- b） （b）- ymin）。为了了解平均时间后悔是如何随着总需求N的增加而变化的，我们让 = 1.- 1/e，因此a=N ln1.-= N、 定理4.4。对于N>b（1-b） 时间平均后悔在（15）limT以上→∞RTT=NlimT→∞TTXn=1（xn- b） 哦！≤ N（ymax- b） （b）- ymin）。5、时间平均社会成本分析本节从时间平均社会成本的极端情景开始；对于非对称均衡流（b=0.5），时间平均社会成本可以任意接近其最差可能值！与在平衡点mb=0.5时获得的最佳社会成本相比，长期动态在周期二的有限周期的两个周期点之间交替，在较大的人口规模下，可以任意接近1或0，见图2（上图）或图5。这意味着几乎所有用户都将占用同一条路线，同时在两条路线之间交替使用。因此，在较大的人口规模下，时间平均社会成本会变得更糟，在有限的人口范围内接近其最差的可能值。定理5.1。当b=0.5时，时间平均社会成本可以任意接近其最大可能值，即对于足够大的人口规模。形式上，对于任何δ>0，存在一个这样的a，对于任何初始条件x，除了可数的多个点，其轨迹最终落入固定点b，我们有lim infT→∞TTXn=1SC（xn）>maxxSC（x）- δ证明。对于对称平衡b=0.5，两个成本函数在相同速率α=β下随载荷增加而增加。回顾第2.2节，当部分人口x采用第一种策略时，社会成本为SC（x）=αNx+αN（1- x） 。该严格凸函数在平衡点x=b=0.5时达到其最小值，其最大值αNat x=0或x=1。

根据定理3.6，我们知道，对于a＞8，存在一个周期跟踪轨道{σa，1-σa}，其中0<σa<0.5。该轨道吸引（0，1）所有点的轨迹，除了可数的多个点，这些点的轨迹最终落入（5）的排斥调用，即a=N ln1.-.路由游戏中的混乱之路15图4。分岔图（上图）显示了由总需求N的增加驱动的路由博弈的不稳定性。这里的纳什均衡设置为b=0.7。像往常一样，我们确定学习率 = 1.- 1/e，为简单起见，a=N。在小N时，动态趋近固定点b，即纳什均衡。然而，当N超过N的承载能力时*b=2/b（1- b） ，纳什均衡变得排斥，动力学不再收敛。倍周期混沌之路开始了。值得注意的是，所有轨道的时间平均值正好是b，从追踪蓝色轨道质量中心的绿线可以明显看出这一点。（中）时间平均再沉降率以紫色显示。它在第一个分岔处突然变得严格正，这与（12）的预测一致，即时间平均后悔与纳什均衡的波动成正比。绿线显示了等式（15）中时间平均后悔的上限。（底部）归一化的时间平均社会成本（即时间平均社会成本除以最优值）在第一次分叉时也突然大于1，这与方程（8）的预测一致。因此，在第一次分岔出现之前，无政府状态界限（1）的价格只是系统效率的有效上界。非平衡动态的时间平均成本与其偏离纳什均衡的程度成正比。

切线（蓝色虚线）描述了归一化时间平均社会成本在第一个分岔点高于单位的增长率，该切线由方程（18）计算得出。固定点0.5。确定轨道吸引的所有轨迹{σa，1- σa}社会成本的时间平均极限可以任意接近αN，这表明两个周期点（唯一吸引周期-2极限环）16 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.Pilioura到最近边界的距离为零→ ∞. 因此，必须证明，给定任何δ>0，存在σa<δ的a。为简洁起见，我们将映射fa表示为0.5byfa。那么，由于σais是周期2的极限环的周期点，我们有fa（σa）=σa。最后一个等式意味着fa（σa）=1- σa，简单计算后，表示σa1- σa= exp[a（σa- 0.5)].考虑函数φ（x）=x1-x个-exp[a（x-0.5）]，则φ（0）=-经验值[-0.5a]<0。另一方面，对于任何δ∈ (0, 0.5), φ(δ) =δ1-δ- exp[a（δ- 0.5)] >δ1-δ> 0表示非常大的a>0。中值定理暗示σa∈ （0，δ），理论如下。更一般地说，当平衡流量不对称时（b 6=0.5），我们可以将标准化时间平均社会成本与平衡流量的非平衡流量联系起来。从（8）中，我们得到（16）归一化时间平均社会成本=TPTn=1xn公司- 2βxn+ββ(1 - β） =1+Var（X）β（1- β).如果动力学收敛到固定点b，方差消失，标准化时间平均社会成本与无政府状态的价格一致，即1。然而，随着总需求N的增加，系统在N=N时突然分叉*b≡ 2/b（1- b） ，即网络的承载能力。承载能力N以上*b、 系统是非平衡的，方差变为正。

因此，归一化时间平均社会成本变得大于1。无ZF状态预测误差的代价，即（归一化时间平均社会成本）-（无ZF状态的代价）>0，取决于方差在第一个分岔点突然增加的速度，我们接下来分析。5.1. 第一周期倍增分岔的方差扩散分析。我们研究了a穿过倍周期分岔点时方差的行为。我们首先考虑模型情况，其中map为g（x）=（γ- 1） x+γx+γx。注意，这里的γ和γ不是成本函数的系数。在这种模型情况下，分岔发生在γ=0时。如果γ>0，则固定点x=0是吸引的，如果γ<0，则是排斥的，但在某些系数条件下，存在周期2的吸引周期轨道。我们只对γ为零时的极限行为感兴趣，在x=0的小邻域中。因此，我们可以忽略x大于3的所有幂和γ大于1的所有幂。周期2点是方程x=（γ）的非零解-1)[(γ-1） x+γx+γx]+γ[（γ-1） x+γx+γx]+γ[（γ-1） x+γx+γx]。忽略高阶项并除以x，我们得到方程（2γγ- 2γ+ 4γγ- 2γ）x- γγx- 2γ= 0.其判别式为（忽略γ中的高阶项后） = -16γ（γ+γ），sox=γγ±4p-γ(γ+ γ)4(γγ- γ+ 2γγ- γ).路由博弈17中的混沌路径假设γ+γ>0。这相当于Sg（0）<0，因此我们可以将其应用于我们的地图（见命题3.1）。如果γ接近于零，则分子中的γ与√γ、 与常数相比，分母γ可以忽略不计。

因此，大约我们有x=±r-γγ+ γ.因此，方差为Var（X）=-γγ+γ.泰勒展开方程（6）在固定点b附近的映射，并将系数与g的系数进行比较后，我们得到γ=2+ab（b- 1） ，γ=a（b-)（1+ab（b- 1） ）和γ=a（1+a（+b（b- 1） ）（3+ab（b- 1))). 回顾第一次分叉发生的时间*b=2/b（1- b） 因此，我们推导出第一周期加倍分岔时方差的（右）导数：（17）dVar（X）daa=a*+b=-dγγ+γda公司a=a*+b=3b（1- b） 2- 6b（1- b） ，这是区间[0，1]内的单峰函数，围绕b=0.5对称，最大值为0.09375。这使我们能够推断出标准化时间平均社会成本在第一个分岔处的增长速度，表明无政府状态度量的均衡价格如何随着我们增加a或等效增加N而失效。即，从方程（8）中，我们发现标准化时间平均社会成本相对于a的导数读取（18）dda（标准化时间平均社会成本）a=a*+b=b（1- b） dVar（X）daa=a*+b=3b（1- b） 2- 6b（1- b） 。当a<2/b（1-b） ，系统平衡，归一化时间平均社会成本统一。但是，当a超过2/b（1-b） ，系统处于不平衡状态，标准化时间平均社会成本突然以一定的速度增加，如等式（18）所示。在第一倍周期分岔时，关于a的二阶导数变得不连续，类似于统计物理中的二阶相变现象。图4证实了方程（18）的预测。同样，当方差变为正时，时间平均后悔也变为非零。

在第一次倍周期分岔时，方程式（12）给出的时间平均后悔随着a的增加而突然增加（我们使用典型的归一化a=N）（19）dda（时间平均后悔）a=a*+b=d（aVar（X））daa=a*+b=3b（1- b） 1个- 3b（1- b） 。因此，在第一阶段加倍分岔时，均衡分析开始下降，以下等式成立（20）dda（时间平均后悔）a=a*+b=2dda（标准化时间平均社会成本）a=a*+b、 6。混沌和Birkhoff遍历理论本节使读者熟悉这项工作所必需的动力系统的关键概念，例如混沌行为、绝对连续不变测度、拓扑向性和遍历定理。18 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURASIt似乎对动态系统的混沌行为没有公认的定义。混沌的大多数定义涉及以下方面之一：o轨迹的复杂行为，如Li-Yorke混沌；o长度为n的可分辨轨道数量的快速增长，例如具有正拓扑熵；o绝对连续不变测度的存在性；o对初始条件的敏感依赖，如Devaney或Auslander-Yorke混沌；o重复属性，例如传递性或混合。在本文中，前三项至关重要。此外，在混沌存在的情况下，研究精确的单轨道动力学可能很困难；我们研究的是轨迹的平均行为。因此，了解平均值是否收敛很重要。这就是遍历理论发挥作用的时候。6.1. 李约克混沌与拓扑熵。Li Yorkechaos定义的由来（见定义3.7）见Li和Yorke的开创性文章【50】。

从直觉上看，来自置乱集的两个点的轨道必须聚集在一起，任意闭合，并多次跳出，但（如果X是紧的）它不能同时发生在每个点的周围。为什么具有这种性质的系统会变得混乱？显然，置乱集的存在意味着点的轨道以不可预测的、复杂的方式运行。更多的论据来自区间变换理论，鉴于此，区间变换被引入。对于此类映射，一个Li-Yorke对的存在意味着一个不可数的置乱集的存在[47]，而这离暗示在本文中被称为混沌的所有其他属性不远，参见例[76]。一般来说，Li-Yorke混沌已被证明是许多其他“混沌”性质得以保持的必要条件。Li-Yorke混沌系统的性质可以在[13]中找到。动力系统混沌行为的一个重要特征是可分辨轨道数的指数增长。当且仅当系统的拓扑熵为正时，才会发生这种情况。事实上，拓扑熵的正性被证明是混沌的一个重要标准【39】。这种选择来自这样一个事实，即如果确定性（零熵）动力系统的过去是已知的，那么它的未来是可以预测的（见【90，第7章】），而正熵与随机性和混沌有关。对于紧相空间上的每个动力系统，我们可以定义一个数h（f）∈[0, ∞] 称为变换f的拓扑熵。

Adler、Konheim和McAndrew首次将该量作为度量（和Shannon）熵的拓扑对应物引入。对于给定的正整数n，我们定义X上的第n个Bowen-Dinaburg度量，ρfnasρfn（X，y）=max0≤i<ndist（fi（x），fi（y））。如果ρfn（x，y）>ε对于任何不同的x，y，我们说集合E是（n，ε）分离的∈ E和bys（n，ε，f）表示（X，f）中数量最多的（n，ε）分离集的基数。定义6.1。f的拓扑熵定义为ash（f）=limε和0lim supn→∞nlog s（n，ε，f）。我们从对想法的直观解释开始。让我们假设我们以ε>0的精度观察动力学系统，也就是说，我们可以区分任意两点，只有当它们至少相隔ε时，路由博弈19中通向混沌的路径。然后，我们只能看到最大（1，ε）分离集的基数。因此，在n次迭代之后，我们将看到最多s（n，ε，f）不同的轨道。如果变换f是混合点，则s（n，ε，f）将增长。取n的上限将给出（可分辨）轨道数渐近增长的指数比率，将ε取零将给出可作为指数速度度量的量，轨道数随指数速度增长（随n）。正拓扑熵和Li-Yorke混沌都是局部性质；事实上，熵仅依赖于相空间的特定子集，并集中于所谓的非游荡点集【15】。正拓扑熵是否意味着Li-Yorke混沌的问题一直悬而未决，但最终证明是真的；见【12】。另一方面，存在拓扑熵为零的Li-Yorke混沌区间映射（如Sm'ital[82]和Xiong[91]所示）。