The asymptotic price of anarchy for k-uniform congestion games

Jasper de Jong; Walter Kern; Berend Steenhuisen; Marc Uetz

doi:10.1007/978-3-319-89441-6_23

The asymptotic price of anarchy for k-uniform congestion games

Jasper de Jong, Walter Kern, Berend Steenhuisen, Marc Uetz^*

^*Corresponding author for this work

Discrete Mathematics and Mathematical Programming

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

7 Citations (Scopus)

317 Downloads (Pure)

Abstract

We consider the atomic version of congestion games with affine cost functions, and analyze the quality of worst case Nash equilibria when the strategy spaces of the players are the set of bases of a k-uniform matroid. In this setting, for some parameter k, each player is to choose k out of a finite set of resources, and the cost of a player for choosing a resource depends affine linearly on the number of players choosing the same resource. Earlier work shows that the price of anarchy for this class of games is larger than 1.34 but at most 2.15. We determine a tight bound on the asymptotic price of anarchy equal to ≈1.35188. Here, asymptotic refers to the fact that the bound holds for all instances with sufficiently many players. In particular, the asymptotic price of anarchy is bounded away from 4/3. Our analysis also yields an upper bound on the price of anarchy <1.4131, for all instances.

Original language	English
Title of host publication	Approximation and Online Algorithms
Subtitle of host publication	15th International Workshop, WAOA 2017, Revised Selected Papers
Editors	Roberto Solis-Oba
Publisher	Springer
Pages	317-328
Number of pages	12
Volume	10787 LNCS
ISBN (Electronic)	978-3-319-89441-6
ISBN (Print)	9783319894409
DOIs	https://doi.org/10.1007/978-3-319-89441-6_23
Publication status	Published - 2018
Event	15th Workshop on Approximation and Online Algorithms, WAOA 2017 - Vienna, Austria Duration: 7 Sept 2017 → 8 Sept 2017 Conference number: 15

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10787 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	15th Workshop on Approximation and Online Algorithms, WAOA 2017
Abbreviated title	WAOA 2017
Country/Territory	Austria
City	Vienna
Period	7/09/17 → 8/09/17

Keywords

Asymptotic price of anarchy
Congestion games
Uniform matroid

Access to Document

10.1007/978-3-319-89441-6_23

JKSU2017_finalAccepted author version, 330 KB

Cite this

de Jong, J., Kern, W., Steenhuisen, B., & Uetz, M. (2018). The asymptotic price of anarchy for k-uniform congestion games. In R. Solis-Oba (Ed.), Approximation and Online Algorithms: 15th International Workshop, WAOA 2017, Revised Selected Papers (Vol. 10787 LNCS, pp. 317-328). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10787 LNCS). Springer. https://doi.org/10.1007/978-3-319-89441-6_23

de Jong, Jasper ; Kern, Walter ; Steenhuisen, Berend et al. / The asymptotic price of anarchy for k-uniform congestion games. Approximation and Online Algorithms: 15th International Workshop, WAOA 2017, Revised Selected Papers. editor / Roberto Solis-Oba. Vol. 10787 LNCS Springer, 2018. pp. 317-328 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f70129f6ab9f429a92f5d911fbade32a,

title = "The asymptotic price of anarchy for k-uniform congestion games",

abstract = "We consider the atomic version of congestion games with affine cost functions, and analyze the quality of worst case Nash equilibria when the strategy spaces of the players are the set of bases of a k-uniform matroid. In this setting, for some parameter k, each player is to choose k out of a finite set of resources, and the cost of a player for choosing a resource depends affine linearly on the number of players choosing the same resource. Earlier work shows that the price of anarchy for this class of games is larger than 1.34 but at most 2.15. We determine a tight bound on the asymptotic price of anarchy equal to ≈1.35188. Here, asymptotic refers to the fact that the bound holds for all instances with sufficiently many players. In particular, the asymptotic price of anarchy is bounded away from 4/3. Our analysis also yields an upper bound on the price of anarchy <1.4131, for all instances.",

keywords = "Asymptotic price of anarchy, Congestion games, Uniform matroid",

author = "{de Jong}, Jasper and Walter Kern and Berend Steenhuisen and Marc Uetz",

year = "2018",

doi = "10.1007/978-3-319-89441-6_23",

language = "English",

isbn = "9783319894409",

volume = "10787 LNCS",

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

publisher = "Springer",

pages = "317--328",

editor = "Roberto Solis-Oba",

booktitle = "Approximation and Online Algorithms",

address = "Germany",

note = "15th Workshop on Approximation and Online Algorithms, WAOA 2017, WAOA 2017 ; Conference date: 07-09-2017 Through 08-09-2017",

}

de Jong, J, Kern, W, Steenhuisen, B & Uetz, M 2018, The asymptotic price of anarchy for k-uniform congestion games. in R Solis-Oba (ed.), Approximation and Online Algorithms: 15th International Workshop, WAOA 2017, Revised Selected Papers. vol. 10787 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10787 LNCS, Springer, pp. 317-328, 15th Workshop on Approximation and Online Algorithms, WAOA 2017, Vienna, Austria, 7/09/17. https://doi.org/10.1007/978-3-319-89441-6_23

The asymptotic price of anarchy for k-uniform congestion games. / de Jong, Jasper; Kern, Walter; Steenhuisen, Berend et al.
Approximation and Online Algorithms: 15th International Workshop, WAOA 2017, Revised Selected Papers. ed. / Roberto Solis-Oba. Vol. 10787 LNCS Springer, 2018. p. 317-328 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10787 LNCS).

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

TY - GEN

T1 - The asymptotic price of anarchy for k-uniform congestion games

AU - de Jong, Jasper

AU - Kern, Walter

AU - Steenhuisen, Berend

AU - Uetz, Marc

N1 - Conference code: 15

PY - 2018

Y1 - 2018

N2 - We consider the atomic version of congestion games with affine cost functions, and analyze the quality of worst case Nash equilibria when the strategy spaces of the players are the set of bases of a k-uniform matroid. In this setting, for some parameter k, each player is to choose k out of a finite set of resources, and the cost of a player for choosing a resource depends affine linearly on the number of players choosing the same resource. Earlier work shows that the price of anarchy for this class of games is larger than 1.34 but at most 2.15. We determine a tight bound on the asymptotic price of anarchy equal to ≈1.35188. Here, asymptotic refers to the fact that the bound holds for all instances with sufficiently many players. In particular, the asymptotic price of anarchy is bounded away from 4/3. Our analysis also yields an upper bound on the price of anarchy <1.4131, for all instances.

AB - We consider the atomic version of congestion games with affine cost functions, and analyze the quality of worst case Nash equilibria when the strategy spaces of the players are the set of bases of a k-uniform matroid. In this setting, for some parameter k, each player is to choose k out of a finite set of resources, and the cost of a player for choosing a resource depends affine linearly on the number of players choosing the same resource. Earlier work shows that the price of anarchy for this class of games is larger than 1.34 but at most 2.15. We determine a tight bound on the asymptotic price of anarchy equal to ≈1.35188. Here, asymptotic refers to the fact that the bound holds for all instances with sufficiently many players. In particular, the asymptotic price of anarchy is bounded away from 4/3. Our analysis also yields an upper bound on the price of anarchy <1.4131, for all instances.

KW - Asymptotic price of anarchy

KW - Congestion games

KW - Uniform matroid

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

U2 - 10.1007/978-3-319-89441-6_23

DO - 10.1007/978-3-319-89441-6_23

M3 - Conference contribution

AN - SCOPUS:85045994491

SN - 9783319894409

VL - 10787 LNCS

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

SP - 317

EP - 328

BT - Approximation and Online Algorithms

A2 - Solis-Oba, Roberto

PB - Springer

T2 - 15th Workshop on Approximation and Online Algorithms, WAOA 2017

Y2 - 7 September 2017 through 8 September 2017

ER -

de Jong J, Kern W, Steenhuisen B, Uetz M. The asymptotic price of anarchy for k-uniform congestion games. In Solis-Oba R, editor, Approximation and Online Algorithms: 15th International Workshop, WAOA 2017, Revised Selected Papers. Vol. 10787 LNCS. Springer. 2018. p. 317-328. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-89441-6_23

The asymptotic price of anarchy for k-uniform congestion games

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this