On the price of anarchy of highly congested nonatomic network games

Riccardo Colini-Baldeschi; Roberto Cominetti; Marco Scarsini

doi:10.1007/978-3-662-53354-3_10

On the price of anarchy of highly congested nonatomic network games

Riccardo Colini-Baldeschi, Roberto Cominetti, Marco Scarsini

Faculty of Engineering and Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

11 Scopus citations

Abstract

We consider nonatomic network games with one source and one destination. We examine the asymptotic behavior of the price of anarchy as the inflow increases. In accordance with some empirical observations, we show that, under suitable conditions, the price of anarchy is asymptotic to one. We show with some counterexamples that this is not always the case. The counterexamples occur in simple parallel graphs.

Original language	English
Title of host publication	Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings
Editors	Martin Gairing, Rahul Savani
Publisher	Springer Verlag
Pages	117-128
Number of pages	12
ISBN (Print)	9783662533536
DOIs	https://doi.org/10.1007/978-3-662-53354-3_10
State	Published - 2016
Event	9th International Symposium on Algorithmic Game Theory, SAGT 2016 - Liverpool, United Kingdom Duration: 19 Sep 2016 → 21 Sep 2016

Publication series

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

Conference

Conference	9th International Symposium on Algorithmic Game Theory, SAGT 2016
Country/Territory	United Kingdom
City	Liverpool
Period	19/09/16 → 21/09/16

Access to Document

10.1007/978-3-662-53354-3_10

Cite this

Colini-Baldeschi, R., Cominetti, R., & Scarsini, M. (2016). On the price of anarchy of highly congested nonatomic network games. In M. Gairing, & R. Savani (Eds.), Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings (pp. 117-128). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9928 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-662-53354-3_10

Colini-Baldeschi, Riccardo ; Cominetti, Roberto ; Scarsini, Marco. / On the price of anarchy of highly congested nonatomic network games. Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings. editor / Martin Gairing ; Rahul Savani. Springer Verlag, 2016. pp. 117-128 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9340ce0368894c0582e29af521a83923,

title = "On the price of anarchy of highly congested nonatomic network games",

abstract = "We consider nonatomic network games with one source and one destination. We examine the asymptotic behavior of the price of anarchy as the inflow increases. In accordance with some empirical observations, we show that, under suitable conditions, the price of anarchy is asymptotic to one. We show with some counterexamples that this is not always the case. The counterexamples occur in simple parallel graphs.",

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

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2016.; 9th International Symposium on Algorithmic Game Theory, SAGT 2016 ; Conference date: 19-09-2016 Through 21-09-2016",

year = "2016",

doi = "10.1007/978-3-662-53354-3_10",

language = "English",

isbn = "9783662533536",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "117--128",

editor = "Martin Gairing and Rahul Savani",

booktitle = "Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings",

}

Colini-Baldeschi, R, Cominetti, R & Scarsini, M 2016, On the price of anarchy of highly congested nonatomic network games. in M Gairing & R Savani (eds), Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9928 LNCS, Springer Verlag, pp. 117-128, 9th International Symposium on Algorithmic Game Theory, SAGT 2016, Liverpool, United Kingdom, 19/09/16. https://doi.org/10.1007/978-3-662-53354-3_10

On the price of anarchy of highly congested nonatomic network games. / Colini-Baldeschi, Riccardo; Cominetti, Roberto; Scarsini, Marco.
Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings. ed. / Martin Gairing; Rahul Savani. Springer Verlag, 2016. p. 117-128 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9928 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On the price of anarchy of highly congested nonatomic network games

AU - Colini-Baldeschi, Riccardo

AU - Cominetti, Roberto

AU - Scarsini, Marco

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2016.

PY - 2016

Y1 - 2016

N2 - We consider nonatomic network games with one source and one destination. We examine the asymptotic behavior of the price of anarchy as the inflow increases. In accordance with some empirical observations, we show that, under suitable conditions, the price of anarchy is asymptotic to one. We show with some counterexamples that this is not always the case. The counterexamples occur in simple parallel graphs.

AB - We consider nonatomic network games with one source and one destination. We examine the asymptotic behavior of the price of anarchy as the inflow increases. In accordance with some empirical observations, we show that, under suitable conditions, the price of anarchy is asymptotic to one. We show with some counterexamples that this is not always the case. The counterexamples occur in simple parallel graphs.

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

U2 - 10.1007/978-3-662-53354-3_10

DO - 10.1007/978-3-662-53354-3_10

M3 - Conference contribution

AN - SCOPUS:84987968044

SN - 9783662533536

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 117

EP - 128

BT - Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings

A2 - Gairing, Martin

A2 - Savani, Rahul

PB - Springer Verlag

T2 - 9th International Symposium on Algorithmic Game Theory, SAGT 2016

Y2 - 19 September 2016 through 21 September 2016

ER -

Colini-Baldeschi R, Cominetti R, Scarsini M. On the price of anarchy of highly congested nonatomic network games. In Gairing M, Savani R, editors, Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings. Springer Verlag. 2016. p. 117-128. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-53354-3_10

On the price of anarchy of highly congested nonatomic network games

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this