论文标题
瞬时动态平衡的无政府状态价格
The Price of Anarchy for Instantaneous Dynamic Equilibria
论文作者
论文摘要
我们考虑在确定性排队模型中随着时间的流动，并研究瞬时动态平衡（IDE）的解决方案概念，其中流粒子在每个决策点选择当前最短路径。这种路径的长度是通过物理旅行时间加上排队时间来衡量的。尽管自八十年代以来就对IDE进行了研究，但解决方案概念的效率尚未得到充分理解。我们研究了该模型的无政府状态价格，并显示了单链实例的订单上限$ \ MATHCAL {O}（U \CDOTτ）$，其中$ U $表示总的流入量和$τ$ Edge Travel Times的总和。我们与相当复杂的实例的家族进行补充，证明了$ω（u \ cdot \logτ）$的下限。
We consider flows over time within the deterministic queueing model and study the solution concept of instantaneous dynamic equilibrium (IDE) in which flow particles select at every decision point a currently shortest path. The length of such a path is measured by the physical travel time plus the time spent in queues. Although IDE have been studied since the eighties, the efficiency of the solution concept is not well understood. We study the price of anarchy for this model and show an upper bound of order $\mathcal{O}(U\cdot τ)$ for single-sink instances, where $U$ denotes the total inflow volume and $τ$ the sum of edge travel times. We complement this upper bound with a family of quite complex instances proving a lower bound of order $Ω(U\cdot\logτ)$.
