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

除以T并通过极限，我们得到（54）limT→∞TT-1Xn=0（ηxn+ηyn）=b。我们在这里以数值结果结束，以证明这类博弈不仅具有复杂的非平衡行为，而且允许立即推广到更现实、更大维度的系统，其中可能出现新的甚至更复杂的非平衡现象，这也许并不奇怪。要对这些问题形成更完整的理论理解，可能需要引入新的工具和技术。图（11）和（12）显示了从地图（50）（η=η=0.5）中生成的a、a、b固定值的吸引轨道。其中，5000个随机起始点被初始化。为了接近吸引子所在的位置，前1000次迭代没有绘制图；接下来的200个是可视化的。路由游戏中的混乱之路49图12。a=10，a=30，b=0.7的两个子种群模型中的图（50）的吸引子。白点是从单位平方域中随机初始化5000个（x，y）生成的坐标（x，y），用（50）1000次迭代它们，然后可视化接下来的200次迭代。附录E：通过对非原子酪蛋白的约化，大型原子拥塞博弈中的混沌。本文重点分析了（主要是线性的）非原子拥塞博弈中的MWU。在这些设置中，假设每个代理控制总流量的最小帐户。在原子设置中，每个代理控制不可分割的流量，即大小为1的数据包。现在有N个代理需要在其可用的不同路径中进行选择。在本节中，我们将展示如何将非原子拥塞博弈的结果转换为原子对应的结果。

为此，我们将证明线性原子拥塞博弈中的MWU映射可以简化为非原子博弈的MWU映射，我们已经分析了这一点。我们将在最简单的信息理论模型下研究线性拥挤博弈中的MWU，其中MWU每天都会收到所有动作/路径的预期成本作为输入。此外，我们将假设所有N个代理都是用完全混合（内部）策略x初始化的。这当然不是一般的初始条件，但由于我们正在努力实现负/复杂/混沌类型的结果，我们可以以对抗的方式选择初始条件。由于初始条件的对称性，代理在任何一天经历的支付向量在所有代理中都是常见的。因此，保持了初始条件的对称性。对于这样的轨迹，我们只需要跟踪单个概率分布（所有代理都是相同的），这已经让人想起了非原子环境，我们只需要跟踪不同路径/策略上总需求的比率/分割。让我们用x表示所有N个代理的公共概率向量。我们已经准备好详细定义我们的模型。50 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURASAtomic模型，其中包含N个代理/参与者。我们有N个特工。每个代理可以在m个策略/路径之间进行选择。每个策略/路径的成本函数是使用该路径i的代理数量的线性函数，即其负载的线性函数。设αibe为策略i的相应乘法常数。假设所有代理使用相同的概率分布x。使用策略i的任何代理的预期成本为（55）c（i）=αi（1+（N- 1） xi）我∈ {1，…，m}。鉴于此支付向量，MWU更新遵循与往常相同的格式。

在时间n+1时，玩家已经知道时间n时策略的预期成本，并更新他们的选项。m策略情况下的更新规则如下：（56）xi（n+1）=xi（n）（1- )c（i）Pj∈{1，…，m}xj（n）（1- )c（j），我们现在准备陈述两个正式结果。一个用于具有两种策略的游戏，另一个用于更一般的具有m策略的游戏。定理E.1。让我们考虑一个包含N个代理和两条线性成本函数路径的原子拥塞博弈，如等式（55）、（56）所述。设x为内部概率分布，这是所有N个代理的共同初始条件。只要拥塞博弈具有对称的内部纳什均衡，其中两个代理都扮演分布（p，1-p） 0<p<1 MWU动态下概率分布x的更新规则，如非原子模型图（6）的情况，其中a=（N- 1） （α+α）ln1.-因此，只要p6=0.5，就存在一个阈值容量Nsuch，即如果代理数N超过N，则系统具有所有可能周期的周期轨道、正拓扑熵，并且是Li-Yorke混沌。如果p=0.5，尽管博弈无政府状态的代价收敛为1，如N→ ∞, 时间平均社会成本可以任意接近其最差可能值。证据通过将（55）中的成本函数值代入（56），我们得到：（57）xn+1=xn（1- )α（1+（N-1） xn）xn（1- )α（1+（N-1） xn）+（1- xn）（1- )α（1+（N-1)(1-xn））=xnxn+（1- xn）（1- )αN-α-（α+α）（N-1） xn。我们引入新变量（58）a=（N-1） （α+α）ln1.- , b=αN- α（α+α）（N- 1).请注意，所有代理都按照（b，1）进行操作的对称策略-b） 是内部纳什均衡。考虑到这个新公式，我们可以看到该映射与非原子情况下的映射相同（6）。

关于混沌的主张随后直接应用推论3.9。在p=0.5的情况下，我们发现均匀分布是一个内部纳什，这意味着α=α（=α），即两条路径具有相同的成本函数。就代理的价格而言，在纳什均衡条件下，任何代理的预期成本最多为α（1+N-1） =αN+1。因此，任何纳什均衡的社会成本最多为αN（N+1）。另一方面，博弈具有对称的内部纳什当且仅当α<Nα和α<Nα。路由博弈51社会最优状态下的混沌路径尽可能平均地分配负载，代价至少为αNand，两者之比收敛为1，即N→ ∞. 最后考虑到原子和非原子情况下更新规则的等效性，以及当（预期几乎）所有用户/流量都使用同样的策略。定理E.1适用于具有多个代理但只有两条路径的原子拥塞博弈。正如我们接下来所展示的，混沌是健壮的，并且在原子拥塞游戏中出现，与可用路径的数量无关。定理E.2。让我们考虑一个由N个代理和m条线性成本函数路径组成的原子拥塞博弈，如等式（55）、（56）所述。设所有路径的代价函数为αx，其中x是相应路径的负载，α是公共乘法常数。设x为内部概率分布，这是所有N个代理的共同初始条件。MWU动力学下概率分布x的更新规则与非原子模型图（30）的情况相同，其中ai=（N- 1） αln1.-.

因此，对于任何这样的原子拥塞博弈，都存在一个阈值容量Nsuch，即如果相邻的代理数n系统具有所有可能周期的周期轨道，则正拓扑熵为Li-Yorke混沌。证据一旦我们观察到MWU，即map（56）对costvector的位移保持不变，则很容易将等式（55）、（56）描述的map简化为非原子模型map（30）。也就是说，对于任何γ，如果我们将向量c（i）=c（i）+γ应用于map（56），它保持不变。因此，不是将成本函数c（i）=α（1+（N）的值代入（56）中-1） x），我们替换值c（i）=α（N-1） 然而，这正是ai=（N）的非原子模型映射（30）的映射-1） αln1.-.定理的其余部分紧接着应用定理B.1。（T.Chotibut）朱拉隆功大学理学院物理系，Bangkok10330，ThailandEngineering Systems and Design，Singapore University of Technology and Design，8 Somapah Road，Singapore 487372电子邮件地址：Thiparat。C@chula.ac.th, thiparatc@gmail.com（F.Falniowski）克拉科夫经济大学数学系，拉科维卡27,31-510克拉科夫，波兰德，邮箱：fryderyk。falniowski@uek.krakow.pl（M.Misiurewicz）印第安纳大学普渡大学印第安纳波利斯分校数学科学系，印第安纳波利斯N.Blackford Street 402号，邮编：46202，美国电子邮箱：mmisiure@math.iupui.edu（G.Piliouras）工程系统与设计，新加坡技术与设计大学，新加坡索马帕路8号，邮编：487372电子邮件地址：georgios@sutd.edu.sgThis不变性也适用于大多数标准的遗憾最小化动力学，例如遵循RegulatizedLeader。