The asymptotic price of anarchy for k-uniform congestion games

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

*Corresponding author for this work

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

4 Citations (Scopus)
131 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 languageEnglish
Title of host publicationApproximation and Online Algorithms
Subtitle of host publication15th International Workshop, WAOA 2017, Revised Selected Papers
EditorsRoberto Solis-Oba
PublisherSpringer
Pages317-328
Number of pages12
Volume10787 LNCS
ISBN (Electronic)978-3-319-89441-6
ISBN (Print)9783319894409
DOIs
Publication statusPublished - 2018
Event15th Workshop on Approximation and Online Algorithms, WAOA 2017 - Vienna, Austria
Duration: 7 Sep 20178 Sep 2017
Conference number: 15

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10787 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference15th Workshop on Approximation and Online Algorithms, WAOA 2017
Abbreviated titleWAOA 2017
CountryAustria
CityVienna
Period7/09/178/09/17

Keywords

  • Asymptotic price of anarchy
  • Congestion games
  • Uniform matroid

Fingerprint Dive into the research topics of 'The asymptotic price of anarchy for k-uniform congestion games'. Together they form a unique fingerprint.

Cite this