论文标题
随着时间的流逝，溢出的影响对流动的无政府状态价格
The Impact of Spillback on the Price of Anarchy for Flows Over Time
论文作者
论文摘要
随着时间的流逝，流量可以随着时间的流逝而变化的流量进行数学建模。为了从游戏理论角度评估这些动态流，我们考虑了无政府状态的价格（POA）。在本文中，我们研究了溢出效应对POA的影响，事实证明这很重要。众所周知，总的来说，POA在溢出环境中是无限的。我们通过证明它仍然没有基础来扩展这一点，即使考虑具有单位边缘能力的网络，并且胸罩比可以任意大。与此相比，我们表明，在固定网络上，POA随着流量的函数的函数是由常数和上限的POA界定的，而POA对于一组网络的POA限制了流出能力根据最快的流量满足某些约束。该上限仅取决于给定网络的纳什流动的最坏溢出因子。因此，它提供了一种量化溢出对动态平衡质量的影响的方法。此外，我们表明了一个令人惊讶的事实，即溢出行为的引入实际上可以加快某些网络中的动态平衡。
Flows over time enable a mathematical modeling of traffic that changes as time progresses. In order to evaluate these dynamic flows from a game theoretical perspective we consider the price of anarchy (PoA). In this paper we study the impact of spillback effects on the PoA, which turn out to be substantial. It is known that, in general, the PoA is unbounded in the spillback setting. We extend this by showing that it is still unbounded even when considering networks with unit edge capacities and that the Braess ratio can be arbitrarily large. In contrast to that, we show that on a fixed network the PoA as a function of the flow amount is bounded by a constant and also upper bound the PoA for the set of networks where the outflow capacities satisfy certain constraints depending on the quickest flow. This upper bound only depends on the worst spillback factor of the Nash flows over time of the given network. It therefore provides a way to quantify the impact of spillback to the quality of the dynamic equilibria. In addition, we show the surprising fact that the introduction of spillback behavior can actually speed up dynamic equilibria in some networks.
