Efficiency of equilibria in uniform matroid congestion games

Research output: Book/ReportReportOther research output

6 Citations (Scopus)
84 Downloads (Pure)

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
Place of PublicationEnschede
PublisherCentre for Telematics and Information Technology (CTIT)
Number of pages16
Publication statusPublished - 22 Feb 2016

Publication series

NameCTIT Technical Report Series
PublisherUniversity of Twente, Centre for Telematics and Information Technology (CTIT)
No.TR-CTIT-16-04
ISSN (Print)1381-3625

Keywords

  • MSC-90C27
  • Matroid strategy spaces
  • IR-100255
  • Price of Anarchy
  • Affine cost functions
  • EWI-26855
  • METIS-316842
  • Atomic congestion games

Cite this

de Jong, J., Klimm, M., & Uetz, M. J. (2016). Efficiency of equilibria in uniform matroid congestion games. (CTIT Technical Report Series; No. TR-CTIT-16-04). Enschede: Centre for Telematics and Information Technology (CTIT).
de Jong, Jasper ; Klimm, Max ; Uetz, Marc Jochen. / Efficiency of equilibria in uniform matroid congestion games. Enschede : Centre for Telematics and Information Technology (CTIT), 2016. 16 p. (CTIT Technical Report Series; TR-CTIT-16-04).
@book{1ece4bbdde194389b0fa025328c7864d,
title = "Efficiency of equilibria in uniform matroid congestion games",
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.",
keywords = "MSC-90C27, Matroid strategy spaces, IR-100255, Price of Anarchy, Affine cost functions, EWI-26855, METIS-316842, Atomic congestion games",
author = "{de Jong}, Jasper and Max Klimm and Uetz, {Marc Jochen}",
note = "eemcs-eprint-26855",
year = "2016",
month = "2",
day = "22",
language = "Undefined",
series = "CTIT Technical Report Series",
publisher = "Centre for Telematics and Information Technology (CTIT)",
number = "TR-CTIT-16-04",
address = "Netherlands",

}

de Jong, J, Klimm, M & Uetz, MJ 2016, Efficiency of equilibria in uniform matroid congestion games. CTIT Technical Report Series, no. TR-CTIT-16-04, Centre for Telematics and Information Technology (CTIT), Enschede.

Efficiency of equilibria in uniform matroid congestion games. / de Jong, Jasper; Klimm, Max; Uetz, Marc Jochen.

Enschede : Centre for Telematics and Information Technology (CTIT), 2016. 16 p. (CTIT Technical Report Series; No. TR-CTIT-16-04).

Research output: Book/ReportReportOther research output

TY - BOOK

T1 - Efficiency of equilibria in uniform matroid congestion games

AU - de Jong, Jasper

AU - Klimm, Max

AU - Uetz, Marc Jochen

N1 - eemcs-eprint-26855

PY - 2016/2/22

Y1 - 2016/2/22

N2 - 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.

AB - 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.

KW - MSC-90C27

KW - Matroid strategy spaces

KW - IR-100255

KW - Price of Anarchy

KW - Affine cost functions

KW - EWI-26855

KW - METIS-316842

KW - Atomic congestion games

M3 - Report

T3 - CTIT Technical Report Series

BT - Efficiency of equilibria in uniform matroid congestion games

PB - Centre for Telematics and Information Technology (CTIT)

CY - Enschede

ER -

de Jong J, Klimm M, Uetz MJ. Efficiency of equilibria in uniform matroid congestion games. Enschede: Centre for Telematics and Information Technology (CTIT), 2016. 16 p. (CTIT Technical Report Series; TR-CTIT-16-04).