On the Price of Anarchy for flows over time

J. Correa, A. Cristi, T. Oosterwijk

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

© 2019 Association for Computing Machinery.Dynamic network flows, or network flows over time, constitute an important model for real-world situations where 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 exactly e/(e - 1) ≈ 1.582. This significantly extends a result by Bhaskar, Fleischer, and Anshelevich (SODA 2011). Furthermore, our methods allow to determine that the Price of Anarchy in parallel-link 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).
Original languageEnglish
Title of host publicationACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages559-577
ISBN (Electronic)9781450367929
DOIs
Publication statusPublished - 17 Jun 2019
Externally publishedYes
Event20th ACM Conference on Economics and Computation, EC 2019 - Phoenix, United States
Duration: 24 Jun 201928 Jun 2019

Conference

Conference20th ACM Conference on Economics and Computation, EC 2019
Country/TerritoryUnited States
CityPhoenix
Period24/06/1928/06/19

Funding

The authors would like to thank Dario Frascaria, Marcus Kaiser, Neil Olver, Leon Sering and Laura Vargas Koch for fruitful discussions. This work was partially supported by CONICYT under Grants PCI PII 20150140 and CONICYTPFCHA/ Doctorado Nacional/2018-21180347.

FundersFunder number
Comisión Nacional de Investigación Científica y TecnológicaPCI PII 20150140

    Fingerprint

    Dive into the research topics of 'On the Price of Anarchy for flows over time'. Together they form a unique fingerprint.

    Cite this