Efficiency of equilibria in uniform matroid congestion games

Jasper de Jong; Max Klimm; Marc Jochen Uetz

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

Efficiency of equilibria in uniform matroid congestion games

Jasper de Jong, Max Klimm, Marc Jochen Uetz

Discrete Mathematics and Mathematical Programming

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

12 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 language	Undefined
Title of host publication	Proceedings of the 9th International Symposium on Algorithmic Game Theory (SAGT 2016)
Editors	Martin Gairing, Rahul Savani
Place of Publication	Heidelberg
Publisher	Springer
Pages	105-116
Number of pages	12
ISBN (Print)	978-3-662-53353-6
DOIs	https://doi.org/10.1007/978-3-662-53354-3_9
Publication status	Published - 1 Sept 2016
Event	10th International Symposium on Algorithmic Game Theory: SAGT 2017 - L'Aquila, Italy Duration: 12 Sept 2017 → 14 Sept 2017 Conference number: 10 http://cs.gssi.infn.it/sagt2017/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	9928
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th International Symposium on Algorithmic Game Theory
Country/Territory	Italy
City	L'Aquila
Period	12/09/17 → 14/09/17
Internet address	http://cs.gssi.infn.it/sagt2017/

Keywords

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

Access to Document

10.1007/978-3-662-53354-3_9

Cite this

@inproceedings{37da3723f98d49e3ae3137c069d02734,

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, Price of Anarchy, EWI-27473, IR-102393, Matroid strategy spaces, Atomic congestion games, METIS-319498, Affine cost functions",

author = "{de Jong}, Jasper and Max Klimm and Uetz, {Marc Jochen}",

note = "10.1007/978-3-662-53354-3_9 ; 10th International Symposium on Algorithmic Game Theory ; Conference date: 12-09-2017 Through 14-09-2017",

year = "2016",

month = sep,

day = "1",

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

language = "Undefined",

isbn = "978-3-662-53353-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "105--116",

editor = "Martin Gairing and Rahul Savani",

booktitle = "Proceedings of the 9th International Symposium on Algorithmic Game Theory (SAGT 2016)",

address = "Germany",

url = "http://cs.gssi.infn.it/sagt2017/",

}

de Jong, J, Klimm, M & Uetz, MJ 2016, Efficiency of equilibria in uniform matroid congestion games. in M Gairing & R Savani (eds), Proceedings of the 9th International Symposium on Algorithmic Game Theory (SAGT 2016). Lecture Notes in Computer Science, vol. 9928, Springer, Heidelberg, pp. 105-116, 10th International Symposium on Algorithmic Game Theory, L'Aquila, Italy, 12/09/17. https://doi.org/10.1007/978-3-662-53354-3_9

Efficiency of equilibria in uniform matroid congestion games. / de Jong, Jasper; Klimm, Max; Uetz, Marc Jochen.
Proceedings of the 9th International Symposium on Algorithmic Game Theory (SAGT 2016). ed. / Martin Gairing; Rahul Savani. Heidelberg: Springer, 2016. p. 105-116 (Lecture Notes in Computer Science; Vol. 9928).

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

TY - GEN

T1 - Efficiency of equilibria in uniform matroid congestion games

AU - de Jong, Jasper

AU - Klimm, Max

AU - Uetz, Marc Jochen

N1 - Conference code: 10

PY - 2016/9/1

Y1 - 2016/9/1

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 - Price of Anarchy

KW - EWI-27473

KW - IR-102393

KW - Matroid strategy spaces

KW - Atomic congestion games

KW - METIS-319498

KW - Affine cost functions

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

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

M3 - Conference contribution

SN - 978-3-662-53353-6

T3 - Lecture Notes in Computer Science

SP - 105

EP - 116

BT - Proceedings of the 9th International Symposium on Algorithmic Game Theory (SAGT 2016)

A2 - Gairing, Martin

A2 - Savani, Rahul

PB - Springer

CY - Heidelberg

T2 - 10th International Symposium on Algorithmic Game Theory

Y2 - 12 September 2017 through 14 September 2017

ER -