The asymptotic behavior of the price of anarchy

Riccardo Colini-Baldeschi, Roberto Cominetti, Panayotis Mertikopoulos, Marco Scarsini

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

9 Scopus citations

Abstract

This paper examines the behavior of the price of anarchy as a function of the traffic inflow in nonatomic congestion games with multiple origin-destination (O/D) pairs. Empirical studies in real-world networks show that the price of anarchy is close to 1 in both light and heavy traffic, thus raising the question: can these observations be justified theoretically? We first show that this is not always the case: the price of anarchy may remain bounded away from 1 for all values of the traffic inflow, even in simple three-link networks with a single O/D pair and smooth, convex costs. On the other hand, for a large class of cost functions (including all polynomials), the price of anarchy does converge to 1 in both heavy and light traffic conditions, and irrespective of the network topology and the number of O/D pairs in the network.

Original languageEnglish
Title of host publicationWeb and Internet Economics - 13th International Conference, WINE 2017, Proceedings
EditorsNikhil R. Devanur, Pinyan Lu
PublisherSpringer Verlag
Pages133-145
Number of pages13
ISBN (Print)9783319719238
DOIs
StatePublished - 2017
Event13th International Conference on Web and Internet Economics, WINE 2017 - Bangalore, India
Duration: 17 Dec 201720 Dec 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10660 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Conference on Web and Internet Economics, WINE 2017
Country/TerritoryIndia
CityBangalore
Period17/12/1720/12/17

Fingerprint

Dive into the research topics of 'The asymptotic behavior of the price of anarchy'. Together they form a unique fingerprint.

Cite this