Efficiency of equilibria in uniform matroid congestion games

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

Abstract

Network routing games, and more generally congestion games play a central role in algorithmic game theory, comparable to the role of the traveling salesman problem in combinatorial optimization. It is known that the price of anarchy is independent of the network topology for non-atomic congestion games. In other words, it is independent of the structure of the strategy spaces of the players, and for affine cost functions it equals 4/3. In this paper, we show that the dependence of the price of anarchy on the network topology is considerably more intricate for atomic congestion games. More specifically, we consider congestion games with affine cost functions where the strategy spaces of players are symmetric and equal to the set of bases of a k-uniform matroid. In this setting, we show that the price of anarchy is strictly larger than the price of anarchy for singleton strategy spaces where the latter is 4/3. As our main result we show that the price of anarchy can be bounded from above by 28/13. This constitutes a substantial improvement over the price of anarchy bound 5/2, which is known to be tight for arbitrary network routing games with affine cost functions.
Original languageUndefined
Title of host publicationProceedings of the 9th International Symposium on Algorithmic Game Theory (SAGT 2016)
EditorsMartin Gairing, Rahul Savani
Place of PublicationHeidelberg
PublisherSpringer
Pages105-116
Number of pages12
ISBN (Print)978-3-662-53353-6
DOIs
Publication statusPublished - 1 Sep 2016
Event10th International Symposium on Algorithmic Game Theory: SAGT 2017 - L'Aquila, Italy
Duration: 12 Sep 201714 Sep 2017
Conference number: 10
http://cs.gssi.infn.it/sagt2017/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume9928
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Symposium on Algorithmic Game Theory
CountryItaly
CityL'Aquila
Period12/09/1714/09/17
Internet address

Keywords

  • MSC-90C27
  • Price of Anarchy
  • EWI-27473
  • IR-102393
  • Matroid strategy spaces
  • Atomic congestion games
  • METIS-319498
  • Affine cost functions

Cite this