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

相似文件 换一批

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《The route to chaos in routing games: When is Price of Anarchy too
  optimistic?》
---
作者：
Thiparat Chotibut, Fryderyk Falniowski, Micha{\\l} Misiurewicz,
  Georgios Piliouras
---
最新提交年份：
2019
---
英文摘要：
  Routing games are amongst the most studied classes of games. Their two most well-known properties are that learning dynamics converge to equilibria and that all equilibria are approximately optimal. In this work, we perform a stress test for these classic results by studying the ubiquitous dynamics, Multiplicative Weights Update, in different classes of congestion games, uncovering intricate non-equilibrium phenomena. As the system demand increases, the learning dynamics go through period-doubling bifurcations, leading to instabilities, chaos and large inefficiencies even in the simplest case of non-atomic routing games with two paths of linear cost where the Price of Anarchy is equal to one.   Starting with this simple class, we show that every system has a carrying capacity, above which it becomes unstable. If the equilibrium flow is a symmetric $50-50\\%$ split, the system exhibits one period-doubling bifurcation. A single periodic attractor of period two replaces the attracting fixed point. Although the Price of Anarchy is equal to one, in the large population limit the time-average social cost for all but a zero measure set of initial conditions converges to its worst possible value. For asymmetric equilibrium flows, increasing the demand eventually forces the system into Li-Yorke chaos with positive topological entropy and periodic orbits of all possible periods. Remarkably, in all non-equilibrating regimes, the time-average flows on the paths converge exactly to the equilibrium flows, a property akin to no-regret learning in zero-sum games. These results are robust. We extend them to routing games with arbitrarily many strategies, polynomial cost functions, non-atomic as well as atomic routing games and heteregenous users. Our results are also applicable to any sequence of shrinking learning rates, e.g., $1/\\sqrt{T}$, by allowing for a dynamically increasing population size.
---
中文摘要：
路由游戏是研究最多的游戏类别之一。它们的两个最著名的性质是，学习动力学收敛到平衡点，并且所有平衡点都近似最优。在这项工作中，我们对这些经典结果进行了压力测试，通过研究不同类别的拥塞博弈中无处不在的动力学、乘性权重更新，揭示了复杂的非均衡现象。随着系统需求的增加，学习动态会经历倍周期分岔，导致不稳定、混乱和效率低下，即使在最简单的情况下，无政府状态的价格等于一的具有两条线性成本路径的非原子路由博弈也是如此。从这个简单的类开始，我们证明每个系统都有一个承载能力，超过这个承载能力，系统就会变得不稳定。如果平衡流是对称的$50-50\\%分裂，则系统表现出一个倍周期分岔。一个周期为2的周期吸引子代替吸引不动点。尽管无政府状态的代价等于1，但在人口众多的情况下，除了零测度初始条件集外，所有初始条件的时间平均社会成本都会收敛到其可能的最差值。对于非对称平衡流，需求的增加最终迫使系统进入具有正拓扑熵和所有可能周期的周期轨道的Li-Yorke混沌。值得注意的是，在所有非平衡状态下，路径上的时间平均流精确收敛于平衡流，这一性质类似于零和博弈中的无遗憾学习。这些结果是可靠的。我们将其推广到具有任意多个策略的路由博弈、多项式代价函数、非原子和原子路由博弈以及异构用户。我们的结果也适用于任何学习率下降的序列，例如，考虑到人口规模的动态增长，1美元/sqrt{T}$。
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Computer Science and Game Theory        计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Economics        经济学
二级分类：General Economics        一般经济学
分类描述：General methodological, applied, and empirical contributions to economics.
对经济学的一般方法、应用和经验贡献。
--
一级分类：Mathematics        数学
二级分类：Dynamical Systems        动力系统
分类描述：Dynamics of differential equations and flows, mechanics, classical few-body problems, iterations, complex dynamics, delayed differential equations
微分方程和流动的动力学，力学，经典的少体问题，迭代，复杂动力学，延迟微分方程
--
一级分类：Physics        物理学
二级分类：Chaotic Dynamics        混沌动力学
分类描述：Dynamical systems, chaos, quantum chaos, topological dynamics, cycle expansions, turbulence, propagation
动力系统，混沌，量子混沌，拓扑动力学，循环展开，湍流，传播
--
一级分类：Physics        物理学
二级分类：Physics and Society        物理学与社会
分类描述：Structure, dynamics and collective behavior of societies and groups (human or otherwise). Quantitative analysis of social networks and other complex networks. Physics and engineering of infrastructure and systems of broad societal impact (e.g., energy grids, transportation networks).
社会和团体（人类或其他）的结构、动态和集体行为。社会网络和其他复杂网络的定量分析。具有广泛社会影响的基础设施和系统（如能源网、运输网络）的物理和工程。
--
一级分类：Quantitative Finance        数量金融学
二级分类：Economics        经济学
分类描述：q-fin.EC is an alias for econ.GN. Economics, including micro and macro economics, international economics, theory of the firm, labor economics, and other economic topics outside finance
q-fin.ec是econ.gn的别名。经济学，包括微观和宏观经济学、国际经济学、企业理论、劳动经济学和其他金融以外的经济专题
--

---
PDF下载：
--> The_route_to_chaos_in_routing_games:_When_is_Price_of_Anarchy_too_optimistic?.pdf (8.49 MB)

2022-6-24 02:58:01 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Quantitative Differential Coordination Bifurcations Environments

路由博弈中的混乱之路：无政府状态的代价何时过于乐观？THIPARAT CHOTIBUT、FRYDERYK FALNIOWSKI、MICHA L MISIUREWICZ和GEORGIOS PILIOURASAbstract。路由游戏是研究最多的游戏类别之一。它们最著名的两个特性是学习动力学收敛到平衡，而等位平衡近似为最优。在这项工作中，我们对这些分类结果进行了压力测试，通过研究拥塞博弈不同类别中普遍存在的动力学、乘性权重更新，揭示了复杂的非平衡现象。随着系统需求的增加，学习动态会经历倍周期分岔，导致不稳定性、混沌和巨大的效率，即使在最简单的情况下，非原子路由博弈具有两条线性成本路径，其中无政府状态的价格等于一。从这个简单的类开始，我们证明每个系统都有一个承载能力，超过这个承载能力，系统就会变得不稳定。如果平衡流为对称50-50%分裂时，系统表现出单倍周期分岔。一个周期为2的周期吸引子取代了吸引固定点。尽管无政府状态的代价等于1，但在大人口限制下，除了零测度初始条件集外，所有初始条件的时间平均社会成本都会收敛到其可能的最差值。对于非对称平衡流，需求的增加最终迫使系统进入具有正拓扑熵和所有可能周期的周期轨道的Li-Yorke混沌。值得注意的是，在所有非平衡状态下，路径上的时间平均流恰好收敛到平衡流，这是零和博弈中无遗憾学习的一个特性。这些结果是可靠的。我们将其推广到具有任意多个策略的路由博弈、多项式代价函数、非原子和原子路由博弈以及异构用户。

我们的结果也适用于任何学习率下降的序列，例如，1/√T，允许动态增加人口规模。图1：。如果两条路线之间的平衡流是对称的（b=0.5），则总需求量N较大会导致周期2的极限环。在任何具有不对称平衡分裂（b 6=0.5）的博弈中，混沌都会出现在大N处。有关详细讨论，请参见图2.2 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURAS1。简介拥塞和路由博弈[72]是ingame理论中研究最为深入的一类博弈。拥塞博弈同构于潜在博弈[56]，是一类新的博弈，其中已知各种学习动态会收敛到纳什均衡[9、29、32、34、44、45]。证明收敛到平衡点通常利用势函数的存在性，该势函数作为学习动力学的（强）李亚普诺夫函数；当系统失去平衡时，该函数严格递减。拥挤博弈在无ZF价格研究中也起着关键作用[10、21、26、35、46、75]。无ZF状态价格（PoA）定义为worstNash均衡的社会成本与最优社会成本的比率。无ZF状态的代价很小，这意味着所有的纳什均衡都是接近最优的，因此任何均衡的学习动态都有助于达到近似最优的系统性能。无ZF价格研究的一个标志是，为拥塞博弈制定了严格的无ZF价格界限，这与网络拓扑或用户数量无关。具体而言，在线性成本函数的原型假设下，非原子主体（其中每个主体控制一个极小的流量）的无ZF状态价格为4/3【75】。

在原子情况下（每个代理控制一个离散的流量单位），Archy的价格最多为5/2[21]，小型网络支持提供严格的下限。此外，拥塞博弈为无政府状态研究的最新发展铺平了道路，扩展了我们对系统性能的理解，甚至是对非平衡动力学的理解。Roughgarden[73]表明，无政府状态结果的大部分代价可以在一个称为（λ，u）-平滑的共同框架中组织。对于满足这一性质的博弈类，如拥塞博弈，最坏情况下纳什均衡的无政府边界价格立即转移到后悔最小化算法的最坏情况实例。据说，（在线）算法可以最大限度地减少遗憾，只要其时间平均性能大致与事后最佳固定动作的性能一样好。这类算法中最普遍的成员可以说是乘法加权日期（MWU）[5]。上述无政府状态结果的代价很容易适用于任何学习动态或任何战略游戏序列，只要算法实现短时平均后悔。在拥塞博弈的情况下，即使在学习不平衡的情况下，也能渐近保证接近最优的时间平均性能，然而，正如我们在第8节中讨论的那样，收敛速度慢，这降低了此类结果在某些感兴趣的应用中的适用性，包括具有多个代理的拥塞博弈。所有这些积极的结果都激励着越来越多的人实现更高的效率保证。

无政府状态的代价有多接近1？例如，在线性拥挤游戏中，最终的正确答案到底是什么？它是原子模型所建议的5/2，还是4/3结合的非原子结合更好？在多项式代价函数的情况下，这些预测之间的差距随着多项式的阶数呈指数级增长，这使得这个问题更加紧迫。在最近的一项发展中，[31]认为，即使代理是原子的，只要代理的数量N很大，原子拥塞游戏的行为近似于非原子游戏；因此，4/3是正确的界限。也就是说，更小的非原子束缚毕竟是正确的。随后出现了一系列相关结果[22-24]，表明在需求量较大的假设下，无政府状态的价格有很强的界限。原子和非原子拥塞游戏之间有什么联系？让我们考虑一下最简单的拥塞博弈示例。具有两种策略和两个代理的游戏，其中每个策略的成本/延迟等于其负载。路由博弈中最坏的纳什路径3该博弈的均衡使得两个代理一致随机选择策略。每个代理的预期成本为3/2，即，由于其自身的负载，成本等于1，由于采用与其他代理相同的策略的可能性为50%，因此预期额外成本为1/2。另一方面，在最佳状态下，每个代理选择不同的策略ata成本为1。因此，这场游戏的无政府状态代价是三分之二。假设现在我们将代理的数量从2个增加到N个。最坏的均衡仍然是每个代理以（N）的预期成本均匀随机地选择策略-1） /2+1=（N+1）/2。最优配置将两个代理进行决定性的、平等的拆分，每个代理的成本为N/2。

无政府状态的代价是1+1/N，随着N的增加，会收敛到1。事实上，随着人口规模的增长，原子博弈更容易由其有效的非原子对应物来描述，具有连续的用户群，以及在两种策略之间均衡分配总需求N的独特均衡。因此，平衡实际上是最优的。然而，这种巨大的需求如何影响动态？非正式元定理：我们分析了路由/拥塞博弈中在不同设置范围及其组合（两条/多条路径、非原子/原子、线性/多项式等）下的MWU。给定任何这样的游戏G和任意的小学习率（步长）, 我们证明了存在一个系统容量N（G，) 因此，如果总需求超过该阈值，则系统是不稳定的，具有复杂的非平衡行为。证明了周期行为和混沌行为，并给出了它们出现的条件的形式保证。尽管非平衡状态具有这种不可预测性，但时间平均成本/流量表现出规律性，对于线性成本，则趋于平衡。然而，由于时间平均成本可以任意高，即使对于所有均衡都是最优的简单博弈，由此产生的非均衡流的差异也会导致效率的提高。不稳定背后的直觉：为了建立不稳定为什么会出现的直觉，让我们用两种策略重新审视这个简单的例子，并让我们考虑一个连续/大量的用户根据学习动态更新他们的策略，例如具有步长的MWU. 在任何非均衡初始条件下，过度拥挤策略上的代理都有很强的迁移动机。

由于它们的行为是一致的，如果总需求非常大，对其他策略的纠正偏差将过于激进，导致其他策略变得过于拥挤。有了这种启发性的考虑，一种自我维持的非均衡行为，即用户承担的平均成本要高于处于均衡流的用户，确实是合理的。在这项工作中，weshow证明了这是事实，即使对于具有任意多个策略的游戏也是如此。结果的重要性：什么时候（稳健的）PoA分析过于乐观？在我们的simpleexample中，有两个平行链接和一个连续/大量用户，我们知道游戏的POAO等于1。所有线性非原子拥塞博弈的PoaO上界为4/3，对于具有多个代理的原子拥塞博弈，最近的工作[31]简化了相同量级的（λ，u）-平滑鲁棒PoA界。然而，对于任何任意球固定 （例如。 = 2.-100），我们可以选择一个足够大的需求/人口规模，使时间平均成本尽可能低，这离最优值还有2倍的距离（理论5.1和E.1）。因此，在任意小的固定学习率下，稳健的PoA边界不一定反映MWU实际行为的上界。应用递减学习率 也不是一件容易的事。我们的研究表明，步长的大小/学习率之间存在一种有效的张力 为了简单起见，让N是一个偶数。4 T.CHOTIBUT、F.FALNIOWSKI、M.MISIUREWICZ和G.PILIOURASdemand/人口规模N。

尽管PoA分析和（λ，u）平滑鲁棒PoA具有不可否认的有用性，但在与许多代理的游戏中，即使步长减小，无政府状态的保证价格也不会对后悔最小化动力学产生约束，直到出现可能具有任意高时间平均社会成本的任意长的混沌历史之后。我们的分析准确地考察了这些非均衡制度，通过了解它们的计量和方差，表明它们确实可以暗示最坏情况下的社会成本。此外，如果我们加入缓慢增长的人口规模，那么即使步长减小，系统也将永远处于其混乱、无效的状态。有关这些问题的详细讨论，请参见第8节。基本模型和结果：我们首先关注具有两条边和总需求N的线性非原子拥塞博弈的最小情况。假设所有代理都以任意小的固定学习率使用乘法权重更新来演化其行为. 在第3节中，我们证明了每一个这样的系统都有一个临界阈值，一个隐藏的系统容量，当超过该阈值时，系统会出现分岔，不再收敛到其平衡流。如果唯一平衡流量为50-50%分裂（双重对称），系统通过一个倍周期分岔，其中周期二的单吸引周期轨道取代吸引固定点。在博弈具有不对称平衡流的情况下，分岔图要复杂得多（图1、2和3）。随着总需求的变化，我们将看到不同时期周期吸引子的诞生和消亡。考虑到巨大的总需求，所有此类系统都可证明具有很好的性能。

这意味着存在一个不可计数的初始条件集，使得该集被“置乱”，即给定该集中的任意两个初始条件x（0），y（0），lim inf dist（x（t），y（t））=0，而lim sup dist（x（t），y（t））>0。在非平衡状态下，MWU的时间平均行为让人想起其在零和博弈中的行为。也就是说，策略的时间平均流量和成本精确收敛到其平衡值。然而，与零和博弈不同，这些非均衡动力学表现出巨大的遗憾（第4节），以及（可能是任意的）高时间平均社会成本（第5节），即使无ZF状态的代价等于1。在第6节中，我们论证了系统表现出混沌行为的另一个特征，即正拓扑熵。我们提供了一个直观的解释，表明如果我们对三个事件进行编码：A）系统大致处于平衡状态，B）第一个策略过度拥挤，C）第二个策略过度拥挤，那么字母表{A，B，C}上可能的序列数（封装了可能的系统动力学）随时间呈指数增长。显然，如果系统达到（近似）平衡，任何序列都必须以以下形式的有限字符串终止。AAA。相反，我们发现该系统可能无法预测。在附录A中，我们表明该系统可能具有多个distinctattractors，因此时间平均后悔和社会成本主要取决于初始条件。还提供了周期轨道的性质，即非单峰映射中费根鲍姆到混沌的普遍路径的证据。扩展：我们通过检查我们发现的稳健性来总结本文。在附录B中，我们证明了我们的结果不仅适用于具有两条路径的图，而且适用于任意数量的路径。

在附录C中，我们证明了多项式代价的Li-Yorke混沌、正拓扑性和时间平均结果。在附录D中，我们为具有异构用户的游戏提供了扩展。最后，在附录E中，我们给出了从原子拥塞博弈到非原子拥塞博弈的WU动力学简化形式。这使我们能够将混沌和效率的证明扩展到具有多个代理的原子拥塞游戏。路线游戏5中的混乱路线图2。这些分岔图总结了本研究中发现的非平衡现象。将乘性权值更新（MWU）学习应用于具有两条路径的非原子线性拥塞对策时，种群增长会导致周期加倍的不稳定性和混沌。标准平衡分析仅适用于较小的种群规模，如浅青色区域所示。随着种群规模N（达到最佳学习率的重缩放因子）的增加，后悔最小化MWU算法不再收敛到纳什均衡流b，如绿色水平线所示；使用第一条路线的用户比例明显偏离纳什均衡流。当两条路线之间的平衡流对称（b=0.5）时，大N会导致非平衡动力学，该动力学被吸引到周期2的极限环。对于大N，两个周期点可以接近1或0任意闭合，这意味着几乎所有用户都将占用相同的路由，同时在两条路由之间交替。因此，时间平均社会成本可能会变得尽可能糟糕。在任何具有不对称平衡流（b 6=0.5）的博弈中，随着N的增加，李-约克混沌是不可避免的。虽然动力学是非平衡或混沌的，但轨道的时间平均值仍然精确收敛到平衡b。