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

直观地说，该模型捕获了大量玩家如何在从a点到B点的多条可选平行路径之间进行选择。如果大部分玩家选择相同的策略，这将导致拥塞/传输，并且成本增加。我们将假设成本与负载成比例。如果我们用byc（i）表示任何玩家玩策略数i的成本，以及比例系数αi，那么我们得到（28）c（i）=αiNxi我∈ {1，…，m}。在时间n+1时，玩家已经知道时间n时策略的成本，并更新他们的选择。由于我们有一个连续的代理，我们将假设使用第一条、第二条和第m条路径的用户的分数分别等于概率x（n），xm（n）。我们将再次使用MWU更新概率。mstrategies的更新规则如下：（29）xi（n+1）=xi（n）（1- )c（i）Pj∈{1，…，m}xj（n）（1- )c（j），拥挤博弈的（Nash）均衡流（b，…，bm）是唯一的流，因此所有路径的成本彼此相等。具体而言，平衡由bi=1/αiPj{1，…，m}αj定义。由（29）引入的MWU动力学可以解释为单纯形的mapf动力学 = {（x，…，xm）：xi≥ 0，Pmj=1xj=1}到自身，由（30）f（x，…，xm）给出=yY，ymY公司,其中yi=xiexp(-aixi）且ai=Nαiln1.- Y=mXj=1yj。我们设定ai=Npi，pi=αiln（1/（1-ε） ）并查看N发生的情况→ ∞. 我们将证明，如果N足够大，则f是Li-Yorke混沌，除非m=2且p=p，即α=α。B、 1。李约克混沌存在的证明。在本节中，我们将对定理3.8进行推广，表明即使在具有许多策略的拥挤博弈中，增加人口/流量也会导致不稳定和混乱。

因此，混沌的出现无论是在游戏的规模上（在有少量或大量路径/策略的游戏中保持），还是在边缘的实际成本函数上都是稳健的（混沌的出现实际上是线性成本函数的任何元组）。定理B.1。对于模型（28）、（29）中描述的具有m个动作的非原子拥塞博弈，除了m=2且α=α的情况外，存在一个总的系统需求，如果N≥ 该系统具有所有周期的周期轨道，正拓扑性，是Li-Yorke混沌系统。假设定理3.6（周期2的周期轨道的出现）分析了m=2，α=α的情况，我们对所有情况都有完整的理解。40 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURASProof。Setp=Pm-1k=1P考虑段I=（x，…，xm）∈  : xi=pxpi，对于i<m，0≤ x个≤ 1..我们有xm=1-m级-1Xk=1Xk=1- x、 所以我确实 .我们有yi=pxpiexp(-对于i<m和y=（1- x） 经验值(-Npm（1- x） ），大豆=x exp(-Npx）+（1- x） 经验值(-Npm（1- x） ）。因此，对于i<m，我们得到y=pxpiexp(-Npx）x exp(-Npx）+（1- x） 经验值(-Npm（1- x） ）=ppi·xx+（1- x） 经验值(-Npm（1- x） +Npx）。因此，f（I） 一、 I上的映射f（在变量x中）由公式7给出→xx+（1- x） 经验值(-Npm（1- x） +Npx）。此公式可在asx 7中重写→xx+（1- x） 经验值N（p+pm）x个-pmp+pm,我们已经知道，这个映射是Li-Yorke混沌的，并且对于足够大的N，具有正的拓扑熵和所有可能周期的周期轨道，前提是pmp+pm6=。因此，在这种情况下，f是Li-Yorke混沌，总体上具有正拓扑熵对于足够大的N，现在让我们研究例外情况pmp+pm=。

然后pm=p，sopm=m-1Xk=1pk。因此，pm=mXk=1pk。然而，我们选择m作为特殊索引是任意的，因此，当我们没有得到Li-Yorke混沌和正拓扑熵时，唯一的情况是当i=mXk=1pkt时，在路由博弈41中，对于每个i=1，2，…，到混沌的路径，m、 在这种情况下，p=p=···=pm，所以我们得到pi=mpi，所以m=2，p=p。最终p=pif，并且只有当α=α时。B、 2。时间平均收敛到平衡。本节的目标是推广定理3.3，即关于流向收敛到（纳什）均衡流量的时间平均值。我们将从一个技术引理开始，该引理表明所有（内部）初始条件收敛于内部不变集。我们考虑（30）给出的映射f。如果x=（x，…，xm）∈ ,然后我们写ξ（x）=min（x，…，xm）。引理B.2。如果x∈  ξ（x）>0，则（31）infn≥0ξ（fn（x））>0。证据我们使用定义f的符号。SetA=max（a，…，am），α=min（a，…，am）。因为每一个i我们都有0≤ xi≤ 1，我们得到（32）易≥ xiexp公司(-Axi）≥ xiexp公司(-A） 。存在k使得xk≥ 1/m.然后是yk≤ xkexp(-α/米），soxk- yk公司≥m级1.- 经验值-αm.自xj起≥ YJ对于所有j，我们得到1- Y≥m级1.- 经验值-αm.SetC=mm级- 1+经验-αm.然后是Y≤ C和C<1。到（32），我们每得到一个≥xiexp公司(-Axi）C≥xiexp公司(-A） C.我们有限制→0exp(-At）C=C>1，因此ε>0，因此xi≤ ε然后yi/Y≥ xi此外，如果xi≥ ε然后yi/Y≥εexp(-A） /C.这证明（31）成立。我们已经准备好证明平均流量的时间收敛于平衡流量。m策略的更新规则由（29）给出。定理B.3。如果x=（x，…，xm），则给定模型（28），（29）中描述的具有m个动作的任何非原子拥塞博弈∈ , 最小值（x，…，xm）>0，然后（33）极限→∞TT-1Xn=0xi（n）=bi。其中（b，…，bm）是拥挤博弈的（纳什）均衡流，即bi=1/αiPj{1，…，m}αj.42 T.CHOTIBUT，F.FALNIOWSKI，m.MISIUREWICZ和G。

PILIOURASProof公司。通过划分两个类型（29）的方程，一个用于策略i，一个用于策略j，我们得出：（34）xn+1（i）xn+1（j）=xn（i）xn（j）（1- )cn（一）-cn（j）通过展开此关系，我们得出：（35）xn+1（i）xn+1（j）=x（i）x（j）（1- )Pnτ=1cτ（i）-cτ（j）通过引理B.2，给定任何初始条件（x（1），x（2），x（n））使得minix（i）>0，存在δ>0，使得infn≥0min xn（i）>δ和supn≥0最大xn（i）<1-δ.那么δ1- δx（j）x（i）<（1- )Pnτ=1cτ（i）-cτ（j）<1.- Δδx（j）x（i）和ln（1- )自然对数δ1 - δx（j）x（i）<nXτ=1cτ（i）- cτ（j）<ln（1- )自然对数1.- Δδx（j）x（i）.用n除以不等式的所有边，我们得到ln（1-)自然对数δ1-δx（j）x（i）n<Pnτ=1cτ（i）- cτ（j）n<ln（1-)自然对数1.-Δδx（j）x（i）n、 通过取极限，我们得到了任何i的极限，j limnPnτ=1cτ（i）-cτ（j）n=0。对于极限limnPnτ=1cτ（i）nexist的任何子序列，对于所有i，我们有：（36）limn→∞Pnτ=1cτ（i）n=limn→∞Pnτ=1cτ（i）- cτ（j）+Pnτ=1cτ（j）n=limn→∞Pnτ=1cτ（j）n由于成本函数是线性的，即cn（j）=ajNxn，方程（36）意味着：（37）ailimn→∞Pnτ=1xτ（i）n=ajlimn→∞Pnτ=1xτ（j）与点limnPnτ=1xτ（1）n，limnPnτ=1xτ（m）n是拥挤博弈的唯一均衡流。显然，可以对任何其他子序列进行相同的论证，使得limnpnτ=1cτ（i）nexists可能通过定义其自身的子序列，从而使所有其他限制也存在（由于紧凑性，这总是可能的）。根据（36），（37），价值必须再次与博弈的唯一均衡相一致。因此，对于任何i，limnPnτ=1cτ（i）nexist和limnPnτ=1xτ（1）n，limnPnτ=1xτ（m）n是唯一的平衡流。路由博弈中的混沌路径43附录C。多项式代价拥塞博弈的扩展为了简单起见，我们将返回到正好有两个动作/路径的情况。通常，我们将用c（j）表示选择策略编号j的成本（当代理的x分数选择第一个策略时）。

我们将重点讨论具有相同阶数（38）c（x）=αNpxpc（x）=βNpxp，p∈ N、 （纳什）均衡流对应于唯一分割（x*b、 1个-x个*b） 使得c（x*b） =c（x*b） 。C、 1。具有多项式代价的乘法权重。再次应用乘法权重更新规则，我们得到公式（2）。通过将（38）中多项式成本函数的值代入（2），我们得到：（39）xn+1=xn（1- )αNpxpnxn（1- )αNpxpn+（1- xn）（1- )βNp（1-xn）p=xnxn+（1- xn）（1- )Np（β（1-xn）p-αxpn）。我们引入了新变量（40）a=（α+β）Npln1.- , b=βα+β。我们再次看到，b=1/2当且仅当两条路径完全对称（samecost函数）。在这种情况下，x*b=1/2，并且平衡流量在两条路径中平均分配总需求。因此，我们将研究由一维映射生成的动力系统：（41）fa，b（x）=xx+（1- x） exp（aPb（x））。明确fa，b：[0，1]→ [0，1]，其中0<b<1，a>0，Pb（x）=（1- b） xn公司- b（1- x） n.我们有Pb（0）=-b、 Pb（1）=1- b、 PBS正在严格增加。因此，存在唯一的点x*b∈ （0，1）使得Pb（x*b） =0。观察fa、b（x*b） =x*正是平衡流。此外，（42）fa，b（x）=（1- ax（1- x） Pb（x））exp（aPb（x））（x+（1- x） exp（aPb（x）））。从（42）我们得到fa，b（0）=exp(-aPb（0））=exp（ab）>1和fa，b（1）=exp（aPb（1））=exp（a（1- b） ）>1。因此0和1是排斥的。

这一事实意味着（这一事实的证明与[20]中的引理3.1相同）单位区间存在不变吸引子集Ia，bof。虽然水流的时间平均收敛不一定收敛到平衡流，但我们仍然可以证明一个类似于定理3.3的定理，该定理反映了这一点，这很方便，因为它立即意味着无ZF状态的代价等于1，由于这些博弈中的社会成本函数的势函数等于+1，因此均衡流最小化了势函数和社会成本。44 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.Piliourasteme不同路径的平均成本。非正式地说，尽管直通路径每天都在混乱地演变，但如果外部观察者要跟踪实时平均成本，所有路径似乎都会经历类似的延迟。正是由于无法学习首选路径，混沌（我们将在下面讨论）即使在多项式成本函数下也是自我维持的，尽管应用了学习/优化动力学。定理C.1。如果成本函数c，则由（38）给出，然后由（43）limn给出→∞nn型-1Xk=0（c（xk）- c（xk））=0。证据有一个闭合间隔Ia、b （0，1）对于fa，b是不变的和吸引的。因此，存在δ∈ （0，1）使Ia，b (δ, 1 - δ).固定x=x∈ [0，1]并使用我们的符号xn=fna，b（x）。通过归纳，我们得到（44）xn=xx+（1- x） 经验值aPn公司-1k=0（c（xk）- c（xk））.假设x=x∈ Ia，b。

因为δ<xn<1- δ、 我们有X1- δ<x+（1- x） expan公司-1Xk=0（c（xk）- c（xk））<xδ，soδ<xδ1- δ< (1 - x） expan公司-1Xk=0（c（xk）- c（xk））！<x1- δδ<δ.因此（45）δ<表达式-1Xk=0（c（xk）- c（xk））<δ、 所以一-1Xk=0（c（xk）- c（xk））< 2对数（1/δ）。这个不等式可以改写为nn型-1Xk=0（c（xk）- c（xk））<2对数（1/δ）an和（43）如下。如果x∈ （0，1）\\Ia，b，然后根据Ia的定义，b这里是fna，b（x）∈ Ia、b、so（43）也适用。C、 2。李约克混沌存在的证明。定理C.2。对于任何b∈ (0, 1/2) ∪ （1/2，1）存在一个假设，如果a>athenfa，则由（41）驱动的B具有周期3的周期轨道，因此它具有所有周期的周期轨道，正拓扑熵，并且是Li-Yorke混沌。路由游戏中的混乱之路45Proof。修复b∈ (0, 1/2). 这足以表明，如果a足够大，则存在x，x，x，x，fa，b（xi）=xi+1和x<x<x。我们的点xi将取决于a。我们从x=1开始-A和y=x*b、 请注意，y不依赖于a，且Pb（y）<0。不等式fa，b（y）>xis等价性>（a- 1)(1 - y） exp（aPb（y）），它适用于足够大的a。此外，对于足够大的a，我们有fa，b（x*b） <x.因此，对于足够大的a，存在x∈ （y，x*b） 这样的fa，b（x）=x。特别是，我们有x<x。Setb*=-b、 由于b<1/2，我们有b*< 1.- b、 因此，如果a足够大，那么Pb（x）>b*, thusx=fa，b（x）=xx+aexp（aPb（x））≤aexp（ab*)= a经验值(-ab公司*).自Pb（x）起≥ -b、 我们得到x=fa，b（x）=xx+（1- x） exp（aPb（x））≤xx+（1- x） 经验值(-ab）=xexp（ab）xexp（ab）+1- x个≤ xexp（ab）≤ a经验（a（b- b*)).自b起- b*= b-+b=3（b-)< 0，我们有利马→∞a经验（a（b-b*)) = 0，因此，如果a足够大，则x<y<x。因此，fa，bha是周期3的周期轨道。我们有fa，1-b（1- x） =1- fa，b（x），so fa，1-bis与fa，b共轭。因此，该定理也适用于b∈ (1/2, 1).

我们没有使用太多的Pb属性，因此该定理适用于更大一类的ThoseFunction。推论C.3。对于模型（39）描述的具有多项式代价函数的非原子拥塞博弈，除了α=β的对称情况外，存在一个总系统需求Nsuch，如果N≥ 该系统具有所有周期的周期轨道，正拓扑熵，是Li-Yorke混沌系统。附录D.异构用户拥塞博弈的扩展这是异构人口情况下的模型。我们将从最简单的情况开始，其中只有两个子种群。我们将考虑一个具有两个连续的玩家/代理的双策略拥塞游戏，其中所有玩家/代理都使用乘法权重更新。每个参与者控制一小部分流量。在总流量/需求中，第一个种群的N为Nη，而第二个种群的总流量为Nη。一个典型的例子是η=η=0.5.46 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURASWe将在时间n使用第一种策略时第一（第二）人群中的参与者分数表示为xn（第二）。第二种策略由1选择- xn（分别为1- yn）玩家的分数。直观地说，该模型捕捉到了两大群玩家/汽车（例如出租车和普通汽车）如何在从A点到B点的两条备选平行路径之间进行选择。如果大部分玩家选择相同的策略，这将导致拥挤/交通，成本增加。我们假设成本与负载成比例。如果我们用c（j）表示玩策略数j的玩家的成本，并且比例系数是α，β，那么我们得到（46）c（1）=αN（ηx+ηy），c（2）=βN（η+η- ηx- ηy）对于乘法权重更新（MWU），对于第一个（分别为。

其次），有一个参数∈ （0，1），（分别为。∈ （0，1）），可以将其视为该人群中所有玩家的共同学习率。因此，我们得到（47）xn+1=xn（1- )c（1）xn（1- )c（1）+（1）- xn）（1- )c（2），yn+1=yn（1- )c（1）yn（1- )c（1）+（1）- yn）（1- )c（2）。通过组合方程式（46）和（47），（48）xn+1=xnxn+（1- xn）（1- )N（β（η+η）-（α+β）（ηxn+ηyn）），yn+1=ynyn+（1- yn）（1- )N（β（η+η）-（α+β）（ηxn+ηyn））。在同质情况下，变量发生类似变化后，公式（48）变为（49）xn+1=xnxn+（1- xn）exp（a（ηxn+ηyn- b） ），yn+1=ynyn+（1- yn）exp（a（ηxn+ηyn- b） ）。在最简单的等份/混合物情况下（即η=η=0.5），我们有：（50）xn+1=xnxn+（1- xn）exp（a）（0.5（xn+yn）- b） ），yn+1=ynyn+（1- yn）exp（a（0.5（xn+yn）- b） ）。降维：虽然非均质模型比均质模型包含更多的独立变量，但动力学约束在较低的维度模型中。也就是说，我们将显示函数I（x，y）=（1-x） aya（1-y） Axai是种群混合的不变函数。这意味着曲线I（x，y）=c对于任何时间步n都是不变的，其中c参数化不变曲线族。引理D.1。函数I（x，y）=（1-x） aya（1-y） Axas是动力学的不变函数（第一个积分）。路径混乱中的路径游戏47Proof。很容易检查方程组（49）是否等于（51）xn+11- xn+1=xn（1- xn）exp（a（ηxn+ηyn- b） ），yn+11- yn+1=yn（1- yn）exp（a（ηxn+ηyn- b） ）。通过将第一个方程提升为A的幂，将第二个方程提升为A的幂，并将其除以，我们得出：xan+1（1- yn+1）a（1- xn+1）ayan+1=xan（1- yn）a（1- xn）ayanThat是函数I（x，y）=（1-x） aya（1-y） Ax是动力学的不变函数（第一个积分）。混合模型对纳什均衡b的时间平均收敛性。

对于所考虑的异质模型，我们可以给出一个类似于定理3.3的结果，即b是吸引Ces\'aro轨迹的混合轨迹。定理D.2。对于每个a，a>0，b∈ （0，1）和（x，y）∈ （0，1）我们有（52）个极限→∞TT-1Xn=0（ηxn+ηyn）=b.证明。设f（xn，yn）=（xn+1，yn+1）由（49）定义，其中η，η∈ （0，1）和η+η=1。地图t 7→t1级-是（0，1）到（0，∞), 其逆式由t 7给出→t1+t。因此，我们可以引入新变量，z=x1-X和w=y1-y、 在这些变量中，sour map将是g：（0，∞)→ (0, ∞), 如果g（zn，wn）=（zn+1，wn+1），那么（53）zn+1=znexp-一ηzn1+zn+ηwn1+wn- b,wn+1=wnexp-一ηzn1+zn+ηwn1+wn- b.如果wn=cza/anthen wn+1=cza/an+1。这表明，如果zn接近于0，则Wniscle也接近于0，并且通过（53）我们得到zn+1>zn。类似地，如果zn接近于完整性，那么Wn也接近完整性，到（53）时，我们得到zn+1<zn。与（53）中的另一个不等式一起，znexp(-a（1- b） 这证明了如果z，w∈ (0, ∞) 然后输入≥0zn>0和supn≥0zn<∞.（53）的第一个方程可以改写为Zn+1=znexp（a（ηxn+ηyn- b） ，所以通过归纳，我们得到zt=zexpaT-1Xn=0（ηxn+ηyn）- T b！！。48 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURASFigure 11。a=20，a=30，b=0.8的两个子种群模型中的图（50）的吸引子。白点是从单位平方域中随机初始化5000个（x，y）生成的坐标（x，y），用（50）1000次迭代它们，然后可视化接下来的200次迭代。因此，存在一个实常数M（取决于参数和初始点（x，y）），因此T-1Xn=0（ηxn+ηyn）- T b≤ M每T。