The Price of Anarchy for Instantaneous Dynamic Equilibria

Lukas Graf () and Tobias Harks ()
Additional contact information
Lukas Graf: Faculty of Computer Science and Mathematics, University of Passau, 94032 Passau, Germany
Tobias Harks: Faculty of Computer Science and Mathematics, University of Passau, 94032 Passau, Germany

Mathematics of Operations Research, 2023, vol. 48, issue 4, 2167-2195

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 τ ) .

Keywords: Primary: 05C21; 90B10; dynamic traffic assignment; Vickrey model; price of anarchy; flows over time; equilibria (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1336 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:4:p:2167-2195

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().