The Price of Anarchy for Instantaneous Dynamic Equilibria

• 成果类型: Article
• 署名作者: Graf, Lukas; Harks, Tobias
• 署名单位: University of Passau
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1336
• 发表日期: 2023
• 页码: 2167-2195
• 关键词: differential-equation formulation; vickreys bottleneck model; traffic assignment; FLOWS; time

摘要

We consider flows over time within the deterministic queueing model of Vickrey 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 has been studied since the eighties, the worst-case efficiency of the solution concept with respect to the travel time is not well understood. We study the price of anarchy for this model under the makespan and total travel time objective and show the first known upper bound for both measures of order O(U center dot T) for single-sink instances, where U denotes the total inflow volume and T denotes the sum of edge travel times. We complement this upper bound with a family of quite complex instances proving a lower bound of order ohm(U center dot log T).