On the Price of Anarchy for Flows over Time

José Correa (), Andrés Cristi () and Tim Oosterwijk ()
Additional contact information
José Correa: Department of Industrial Engineering, Universidad de Chile, República 701, 8370439 Santiago, Chile
Andrés Cristi: Department of Industrial Engineering, Universidad de Chile, República 701, 8370439 Santiago, Chile
Tim Oosterwijk: Vrije Universiteit Amsterdam, De Boelelaan 1105, 1081 HV, Amsterdam, Netherlands

Mathematics of Operations Research, 2022, vol. 47, issue 2, 1394-1411

Abstract: Dynamic network flows, or network flows over time, constitute an important model for real-world situations in which steady states are unusual, such as urban traffic and the internet. These applications immediately raise the issue of analyzing dynamic network flows from a game-theoretic perspective. In this paper, we study dynamic equilibria in the deterministic fluid queuing model in single-source, single-sink networks—arguably the most basic model for flows over time. In the last decade, we have witnessed significant developments in the theoretical understanding of the model. However, several fundamental questions remain open. One of the most prominent ones concerns the price of anarchy, measured as the worst-case ratio between the minimum time required to route a given amount of flow from the source to the sink and the time a dynamic equilibrium takes to perform the same task. Our main result states that, if we could reduce the inflow of the network in a dynamic equilibrium, then the price of anarchy is bounded by a factor, parameterized by the longest path length that converges to e / ( e − 1 ) , and this is tight. This significantly extends a result by Bhaskar et al. (SODA 2011). Furthermore, our methods allow us to determine that the price of anarchy in parallel-link and parallel-path networks is exactly 4/3. Finally, we argue that, if a certain, very natural, monotonicity conjecture holds, the price of anarchy in the general case is exactly e / ( e − 1 ) .

Keywords: Primary: 91A25; 91A43; secondary: 91A10; 91A13; flows over time; price of anarchy; dynamic equilibrium (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1173 (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:47:y:2022:i:2:p:1394-1411

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