英文标题：
《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下载：
-->