Price of Anarchy for Highly Congested Routing Games in Parallel Networks

Riccardo Colini-Baldeschi; Roberto Cominetti; Marco Scarsini

doi:10.1007/s00224-017-9834-1

Price of Anarchy for Highly Congested Routing Games in Parallel Networks

Riccardo Colini-Baldeschi, Roberto Cominetti, Marco Scarsini

Faculty of Engineering and Science

Research output: Contribution to journal › Article › peer-review

13 Scopus citations

Abstract

We consider nonatomic routing games with one source and one destination connected by multiple parallel edges. We examine the asymptotic behavior of the price of anarchy as the inflow increases. In accordance with some empirical observations, we prove that under suitable conditions on the costs the price of anarchy is asymptotic to one. We show with some counterexamples that this is not always the case, and that these counterexamples already occur in simple networks with only 2 parallel links.

Original language	English
Pages (from-to)	90-113
Number of pages	24
Journal	Theory of Computing Systems
Volume	63
Issue number	1
DOIs	https://doi.org/10.1007/s00224-017-9834-1
State	Published - 15 Jan 2019

Keywords

High congestion
Nonatomic routing games
Parallel networks
Price of Anarchy
Regularly varying functions
Wardrop equilibrium

Access to Document

10.1007/s00224-017-9834-1

Cite this

@article{7ce63818517c4fa5a417fcbf4c8b87bf,

title = "Price of Anarchy for Highly Congested Routing Games in Parallel Networks",

abstract = "We consider nonatomic routing games with one source and one destination connected by multiple parallel edges. We examine the asymptotic behavior of the price of anarchy as the inflow increases. In accordance with some empirical observations, we prove that under suitable conditions on the costs the price of anarchy is asymptotic to one. We show with some counterexamples that this is not always the case, and that these counterexamples already occur in simple networks with only 2 parallel links.",

keywords = "High congestion, Nonatomic routing games, Parallel networks, Price of Anarchy, Regularly varying functions, Wardrop equilibrium",

author = "Riccardo Colini-Baldeschi and Roberto Cominetti and Marco Scarsini",

note = "Publisher Copyright: {\textcopyright} 2018, Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2019",

month = jan,

day = "15",

doi = "10.1007/s00224-017-9834-1",

language = "English",

volume = "63",

pages = "90--113",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Price of Anarchy for Highly Congested Routing Games in Parallel Networks

AU - Colini-Baldeschi, Riccardo

AU - Cominetti, Roberto

AU - Scarsini, Marco

PY - 2019/1/15

Y1 - 2019/1/15

N2 - We consider nonatomic routing games with one source and one destination connected by multiple parallel edges. We examine the asymptotic behavior of the price of anarchy as the inflow increases. In accordance with some empirical observations, we prove that under suitable conditions on the costs the price of anarchy is asymptotic to one. We show with some counterexamples that this is not always the case, and that these counterexamples already occur in simple networks with only 2 parallel links.

AB - We consider nonatomic routing games with one source and one destination connected by multiple parallel edges. We examine the asymptotic behavior of the price of anarchy as the inflow increases. In accordance with some empirical observations, we prove that under suitable conditions on the costs the price of anarchy is asymptotic to one. We show with some counterexamples that this is not always the case, and that these counterexamples already occur in simple networks with only 2 parallel links.

KW - High congestion

KW - Nonatomic routing games

KW - Parallel networks

KW - Price of Anarchy

KW - Regularly varying functions

KW - Wardrop equilibrium

UR - http://www.scopus.com/inward/record.url?scp=85039984458&partnerID=8YFLogxK

U2 - 10.1007/s00224-017-9834-1

DO - 10.1007/s00224-017-9834-1

M3 - Article

AN - SCOPUS:85039984458

SN - 1432-4350

VL - 63

SP - 90

EP - 113

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 1

ER -

Price of Anarchy for Highly Congested Routing Games in Parallel Networks

Abstract

Keywords

Access to Document

Fingerprint

Cite this