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

这项工作证明了上述陈述，并研究了非均衡动力学对无政府状态分析标准价格的影响。附录中研究了混沌吸引子和倍周期分岔的性质，以及对更复杂拥塞博弈的扩展。6 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURAS2。模型我们考虑了一个两策略拥塞博弈（见[72]），其中有一个连续的参与者（代理），所有参与者都应用乘法权重更新来更新他们的策略[5]。每个玩家控制一小部分流量。我们将假设所有参与者的总流量等于N。我们将在时间N时采用第一种策略的参与者的分数表示为xn。第二种策略由1选择- X球员的吸引力。该模型在物理上封装了大量通勤者如何在连接起点和终点的两条备选路径之间进行选择。当大部分参与者采用相同的策略时，就会出现拥塞，选择相同策略的成本也会增加。线性路由博弈：我们关注线性成本函数。具体而言，此处假设每条路径（链路、路由或策略）的成本与负载成比例。通过表示c（j）选择策略编号j的成本（当x部分代理选择第一个策略时），如果比例系数为α，β>0，我们得到（1）c（1）=αNx，c（2）=βN（1- x） 。我们对分岔、极限环和混沌出现的分析将立即延续到αx+γ形式的代价函数。正如我们将看到的，唯一重要的参数是均衡分割的值，即均衡时使用第一策略的参与者的百分比。

该公式的第一个优点是，在均衡状态下使用每种策略的代理的细分与流量无关。第二个优点是，这些博弈的无政府状态的价格正好是1，与α、β和N无关。因此，我们的模型提供了一个比较均衡分析的自然基准，均衡分析提出了最佳社会成本，而非均衡学习动态产生的时间平均社会成本，正如我们所展示的，可以尽可能大。2.1. 具有乘法权重的拥塞博弈中的学习。在时间n+1时，我们假设参与者知道时间n时策略的成本（相当于概率xn，1- xn）并更新他们的选择。由于我们有一个连续的代理，实现的流量（分割）由概率（xn，1）精确描述- xn）。我们关注的概率更新算法是乘法权重更新（MWU），这是一种普遍存在的学习算法，广泛应用于机器学习、优化和博弈论[5、58、74]。也就是说，有一个参数 ∈ （0，1），这可以被视为所有玩家的共同学习率，因此每个概率都乘以（1-) 力量，即给定玩家使用给定策略的成本。以这种方式获得的数字通常不是概率，因此我们必须对其进行归一化。

因此，我们得到（2）xn+1=xn（1- )c（1）xn（1- )c（1）+（1）- xn）（1- )c（2）=xnxn+（1- xn）（1- )c（2）-c（1）。这样，在时间n的大成本将降低在时间n+1选择相同策略的概率。通过将（1）中的代价函数值代入（2），我们得到：（3）xn+1=xn（1- )αNxnxn（1- )αNxn+（1- xn）（1- )βN（1-xn）=xnxn+（1- xn）（1- )βN-（α+β）Nxn。我们引入了新变量（4）a=（α+β）N ln1.- , b=βα+β。事实上，我们可以假设α+β=1（即，通过变换α=αα+β，β=βα+β，以及= 1.-(1-)α+β). 在这些假设下，方程（4）简化为（5）a=N ln1.- , b=β。因此，我们将研究由一维映射生成的动力系统：（6）fa，b（x）=xx+（1- x） exp（a（x- b） ）。通常采用的标准假设是，学习率 在以下分析中可以视为一个小的固定常数，但常数的准确值 由于我们的分析/结果适用于任何固定的选择 不管多小。背景 = 1.- 1/e，以便ln1.-= 1在此假设下简化符号a=N。然后，我们将研究其余两个参数对系统性能的影响，即a（标准化）系统需求和b（标准化）平衡流量。当b=0.5时，路由博弈是完全对称的；然而，当b接近0或1时，路由实例变得接近于庇古网络，几乎所有代理都在平衡时选择相同的边。2.2. 遗憾、无政府状态的代价和时间平均的社会成本。现在，我们将从每个代理的角度考虑这个游戏，将其作为在线优化问题的一个实例。考虑2个动作的集合A={1，2}和时间范围T≥ 1、在每个时间步n=1，2，T：决策者选择概率分布xn=（xn，1- xn）关于她的行为A。

对手选择成本向量cn:a→ [-1, 1]. 根据分布xn选择行动，决策者获得奖励rn（An）。决策者学习rn，即整个奖励向量。在线决策算法，如概率分布xn中每个n的MWU规格，作为成本向量c的函数，中国大陆-1和已实现的行动a，一-第一个n中的1个-1时间步。该算法的对手是成本向量cn中的每一个，作为概率分布x，…，的函数，xA在第一天使用，以及实现的行动a，一-第一个n中的1个- 1天。例如，A的元素可能代表不同的投资策略、不同的家庭和工作之间的驾驶路线、不同的无线路由器等。我们不是事后将算法的预期回报与最佳行动序列的预期回报进行比较，而是将其与最佳固定行动产生的回报进行比较。也就是说，我们将基准从ptn=1mina更改为∈Acn（a）至mina∈APTn=1cn（a）。8 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURASRegret：固定成本向量c，计算机断层扫描。（随机）算法根据x选择动作的（预期）遗憾，xTis（7）TXn=1Ean~xncn（an）{z}我们的算法-米纳∈ATXn=1cn（a）{z}最佳固定动作，其中Ean~xncn（an）表示算法在时间段n内的预期成本，此时操作an∈ 根据概率分布xn选择A。在博弈论背景下，每个参与者的成本向量CNO是通过与其他参与者进行（拥挤）博弈而产生的。形式上，每个代理在timen的成本向量是cn=αNxn，βN（1- xn）. 时间段1，…的预期累积成本（任何symmetricin小型）代理人。

，T等于toPTn=1αNxn+βN（1-xn）.该算法的预期遗憾由公式txn=1给出αNxn+βN（1- xn）- 米纳∈ATXn=1cn（a），或等效地，TXn=1αNxn+βN（1- xn）- 最小值（TXn=1αNxn，TXn=1βN（1- xn））。无政府状态的代价：博弈的无政府状态的代价是所有纳什均衡的社会成本的上界除以最优状态的社会成本的比率，其中状态的社会成本是所有代理的成本之和。在我们的案例中，如果总流量（需求或人口规模）为N，而人口的分数x采用第一种策略，则社会成本为SC（x）=αNx+βN（1- x） 。在非原子拥挤博弈中，众所周知，所有均衡都具有相同的社会成本。此外，对于线性成本函数c（x）=αx，c（x）=βx，很容易看出无政府状态的价格等于1，因为唯一的均衡流β也是社会成本的唯一最小值，其值为Nαβ。考虑到上述术语，我们将研究在某些初始条件下的时间平均社会成本。由于社会成本的时间平均值可能不会收敛到特定值，算法博弈论的研究通常集中在所有收敛子序列的所有初始条件上的上确界。如果我们只考虑具有消失时间平均遗憾的时间序列，则它们的时间平均值由最优状态的社会成本归一化，称为总无政府状态的价格，而对于非原子拥塞博弈，它等于无政府状态的价格，在我们的情况下，该价格等于1，表明系统性能最优[14]。由于MWU不是在步长减小的情况下运行的，因此时间平均遗憾可能不会消失，需要进行更仔细的分析。

最后，从动力学系统的角度来看，我们还将研究典型的动力学轨迹，因为仿真能够识别这些轨迹的时间平均值的极限，这些极限出现在具有正贝格测度的初始条件下。正如我们将要展示的那样，随着总需求的增加，系统将偏离灰平衡；时间平均社会成本将严格大于其最优值。在归一化假设α+β=1下，这一说法是正确的。路由游戏中通往混乱的路径是9value（事实上，它可以巧妙地接近其最坏的可能值）。无政府状态的代价不再能够预测真实系统的非均衡行为。我们现在陈述稍后将使用的公式。在假设α+β=1的情况下，我们将标准化时间平均社会成本定义如下：（8）时间平均社会成本最优社会成本=TPTn=1αNxn+βN（1- xn）Nαβ=TPTn=1xn公司- 2βxn+ββ(1 - β).3、极限环和混沌，时间平均收敛到纳什均衡。本节讨论了（6）定义的一维映射的行为及其显著的时间平均特性，我们稍后将在第4节和第5节中使用这些特性来分析时间平均梯度和归一化的时间平均社会成本。这里由非原子拥塞博弈生成的映射简化为[20]中研究的映射，其中研究了两个代理线性拥塞博弈。在重新定义参数以及对称初始条件（即对角线上）之前，两种场景中的一维地图是相同的。因此，在本节中，我们重申了地图的一些关键属性。关于校样，我们请读者参考[20]。我们将首先研究由（9）fa，b（x）=xx+（1）给出的图（6）下的动力学- x） exp（a（x- b） ），a>0，b∈ (0, 1).

该图通常是不对称的，除非b=1/2，请参见图3的中间列。它有三个固定点：0、b和1。三个执行点的衍生工具为fa，b（0）=exp（ab），fa，b（1）=exp（a（1- b） ），fa，b（b）=ab- ab+1。因此，固定点0和1是排斥的，而当a>b（1）时，b是排斥的-b） 。fa的关键点，ax的裸解决方案- ax+1=0。因此，如果0<a≤ 4，然后fa，bis严格增加。如果a>4，则有两个临界点（10）xl=1-r1级-一xr=1- xl=1+r1-一所以fa，bis双峰。让我们研究fa，b的规律性。很明显，它是解析的。然而，区间映射的优良性质不是由解析性保证的，而是由负Schwarzian导数保证的。让我们回顾一下，f的Schwarzian导数由公式SF=ff给出-ff公司.一个“元定理”指出，几乎所有自然的不可逆区间映射都有负的Hwarzian导数。请注意，如果≤ 4那么fa，bis是同胚，所以我们不应该期望负的Schwarzian导数。提案3.1。如果a>4，则映射fa，BHA为负Schwarzian导数。10 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURASFigure 3。人口增长导致倍周期不稳定和混沌。虽然我们的拥塞博弈有一个相关的凸势函数Φa，b（x）=N（αx+β（1- x） ）=a（（1- b） x+b（1- x） ，其唯一的全局最小值是纳什均衡b（在不损失一般性的情况下，我们设置α+β=1 = 1.- 1/e，使a=Nand b=β），大a的MWU，或相当大的N，固定, 不要收敛到平衡点，这与步长很小的类梯度更新不同。左列中带有箭头连接ΦA，b（xn）到ΦA，b（xn+1）=ΦA，b（fa，b（xn））的线用表示时间步n的颜色进行编码。后面的时间以红色显示，而前面的时间以蓝色显示。

地图fa的蛛网图，中间一栏显示为裸体，而地图的动态显示在右一栏。从上到下，增长whileb的值保持在0.7，表明人口规模驱动的不稳定性。在这些参数值下，映射fa，bis双峰（中间列中的蓝色曲线）。对于小a（顶行），动力学收敛到纳什均衡b。随着a的增加，动力学收敛到周期2吸引子（第二行）、周期4吸引子（第三行）和混沌吸引子（底行）。然而，如第3节所示，这些轨道的时间平均值正是灰分平衡b，由右栏的水平绿色虚线表示。此处的初始条件设置为x=0.2。与b=0.7相关的分岔图如图4所示。对于具有负Schwarzian导数的映射，每个吸引轨道或中性周期轨道在其直接吸引盆中都有一个临界点。因此，我们知道，如果a>4 thenfa，BCA最多可以有两个吸引轨道或中性周期轨道。路线游戏113.1中的混乱路线。时间平均收敛到纳什均衡b。虽然我们知道被执行点b通常是排斥的，尤其是对于a的大值，但我们可以证明它在时间平均意义上是吸引人的。定义3.2。对于区间映射f，如果存在一个集，则点p是吸引的∈ U平均值t-1Xn=0fn（x）收敛于p。我们可以证明b是全局吸引的。这里所说的“全球”是指定义中的集合U是区间（0，1）。定理3.3。每a>0，b∈ （0、1）和x∈ （0，1）我们有（11）个极限→∞TT-1Xn=0fna，b（x）=b。推论3.4。对于每个周期轨道{x，x。

，xT-1} 对于fa，bin（0，1）其质心（时间平均值）x+x+·····+xT-1等于b。应用Birkhoff遍历定理（见第6节），我们得到了一个更强的推论。推论3.5。对于每个概率测度u，fa不变，带u（{0，1}）=0，我们有z[0,1]x du=b。这些陈述表明，fa，b生成的轨道的时间平均值实际上接近纳什均衡b。接下来，我们讨论当我们乘以b并通过让a变大来增加总需求时会发生什么。3.2. 周期轨道和混沌行为。当b=0.5时，成本函数的系数相同，即α=β。定理3.6。如果0<a≤ 8然后（0，1）所有点的fa，0.5轨迹收敛到执行点0.5。如果a＞8，则fa，0.5具有周期吸引轨道{σa，1-σa}，其中0<σa<0.5。该轨道吸引（0，1）所有点的轨迹，除了可数的多个点，这些点的轨迹最终落入排斥固定点0.5。现在我们继续处理b 6=0.5的情况，即成本函数不同的情况。如上文第3节所述，如果≤ 4然后fa、bis严格增加，有三个执行点：0和1排斥和b吸引。因此，在这种情况下，（0，1）所有点的轨迹都以单调的方式收敛到b。我们知道，固定点b是排斥的，只有当a>b（1-b） 。这是一个简单的情况，因此我们转向大型a的情况。我们∈ （0，1）\\{0.5}并让a进入实体。我们将证明，如果a变得足够大（但大小取决于b），那么fa，bis-Li-Yorke是混沌的，并且具有所有可能周期的周期轨道。12 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURASDe定义3.7（Li Yorke混沌）。

设（X，f）为动力系统，且（X，y）∈ X×X。我们说（X，y）是一对Li-Yorke对iflim-infn→∞dist（fn（x），fn（y））=0，lim supn→∞距离（fn（x），fn（y））>0。如果存在不可数集S，则动力系统（X，f）是Li-Yorke混沌系统 X（称为crambled set）使得每对（X，y）都具有X，y∈ S和x 6=y是一对Li-Yorke。这一分析的关键因素是周期3的周期轨道的存在。定理3.8。如果b∈ （0，1）\\{0.5}，则存在一个absuch，如果a>Ab，则fa，周期3的Bhasperic轨道。根据Sharkovsky定理（[81]，另见[50]），周期3的周期轨道的存在意味着所有周期的周期轨道的存在，并且根据[50]的结果，它意味着映射是Li-Yorke混沌的。因此，我们得到以下推论：推论3.9。如果b∈ （0，1）\\{0.5}，则存在一个假设，即如果a>abthen fa，则bhasperic轨道是所有周期的，并且是Li-Yorke混沌。这一结果在非原子路由博弈中具有显著的意义。回想一下，参数a表示标准化总流量/需求；因此，推论3.9意味着当博弈是不对称的，即当内部均衡流量不是50%- 50%的拆分，增加了系统的总需求，无论成本函数的形式如何，都将不可避免地导致混沌行为。换言之，在大量需求下出现混沌是一种强劲的现象。4、时间平均后悔分析在上一节中，我们讨论了映射fa，b的时间平均收敛到纳什均衡。我们现在利用这个性质来研究MWU学习的时间平均后悔。定理4.1。时间平均后悔的极限是总需求量N乘以可观察极限（x- b） （前提是存在此限制）。这是（12）极限→∞RTT=NlimT→∞TTXn=1（xn- b） ！。证据