We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The Price of Anarchy for Instantaneous Dynamic Equilibria.
- Authors
Graf, Lukas; Harks, Tobias
- Abstract
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 · τ) for single-sink instances, where U denotes the total inflow volume and τ 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 Ω (U · log τ). Funding: The research of the authors was funded by the Deutsche Forschungsgemeinschaft [Grants HA 8041/1-1 and HA 8041/4-1].
- Subjects
DEUTSCHE Forschungsgemeinschaft; TRAVEL time (Traffic engineering); PRICES; ANARCHISM; GRANULAR flow; TRAFFIC assignment; CAPITAL movements
- Publication
Mathematics of Operations Research, 2023, Vol 48, Issue 4, p2167
- ISSN
0364-765X
- Publication type
Article
- DOI
10.1287/moor.2022.1336