Price of Anarchy for Graphic Matroid Congestion Games

Wouter Fokkema; Ruben Hoeksma; Marc Uetz

doi:10.1007/978-3-031-71033-9_21

Price of Anarchy for Graphic Matroid Congestion Games

Wouter Fokkema, Ruben Hoeksma, Marc Uetz^*

^*Corresponding author for this work

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

Abstract

This paper analyzes the quality of pure-strategy Nash equilibria for symmetric Rosenthal congestion games with linear cost functions. For this class of games, the price of anarchy is known to be (5N-2)/(2N+1), where N is the number of players. It has been open if restricting the strategy spaces of players to be bases of a matroid suffices to obtain stronger price of anarchy bounds. This paper answers this open question negatively. We consider graphic matroids, where each of the N players chooses a minimum cost spanning tree in a graph with linear cost functions on its edges. We provide constructions of graphs for N=2,3,4 and for unbounded N, where the price of anarchy attains the known upper bounds (5N-2)/(2N+1) and 5/2, respectively. These constructions translate the tightness of algebraic constraints into combinatorial conditions which are necessary for tight lower bound instances. The main technical contribution lies in showing the existence of recursively defined graphs which fulfill these combinatorial conditions, and which are based on solutions of a bilinear Diophantine equation.

Original language	English
Title of host publication	Algorithmic Game Theory - 17th International Symposium, SAGT 2024, Proceedings
Editors	Guido Schäfer, Carmine Ventre
Publisher	Springer
Pages	371-388
Number of pages	18
ISBN (Print)	9783031710322
DOIs	https://doi.org/10.1007/978-3-031-71033-9_21
Publication status	Published - Sept 2024
Event	17th International Symposium on Algorithmic Game Theory, SAGT 2024 - Amsterdam, Netherlands Duration: 3 Sept 2024 → 6 Sept 2024 Conference number: 17

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	15156 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	17th International Symposium on Algorithmic Game Theory, SAGT 2024
Abbreviated title	SAGT 2024
Country/Territory	Netherlands
City	Amsterdam
Period	3/09/24 → 6/09/24

Keywords

2024 OA procedure
Matroid
Minimum Spanning Tree
MST
POA
Price of Anarchy
Congestion Game

Access to Document

10.1007/978-3-031-71033-9_21

Cite this

Fokkema, W., Hoeksma, R., & Uetz, M. (2024). Price of Anarchy for Graphic Matroid Congestion Games. In G. Schäfer, & C. Ventre (Eds.), Algorithmic Game Theory - 17th International Symposium, SAGT 2024, Proceedings (pp. 371-388). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 15156 LNCS). Springer. https://doi.org/10.1007/978-3-031-71033-9_21

Fokkema, Wouter ; Hoeksma, Ruben ; Uetz, Marc. / Price of Anarchy for Graphic Matroid Congestion Games. Algorithmic Game Theory - 17th International Symposium, SAGT 2024, Proceedings. editor / Guido Schäfer ; Carmine Ventre. Springer, 2024. pp. 371-388 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{095d831fd9b44080a6f3a8a730ae54a6,

title = "Price of Anarchy for Graphic Matroid Congestion Games",

abstract = "This paper analyzes the quality of pure-strategy Nash equilibria for symmetric Rosenthal congestion games with linear cost functions. For this class of games, the price of anarchy is known to be (5N-2)/(2N+1), where N is the number of players. It has been open if restricting the strategy spaces of players to be bases of a matroid suffices to obtain stronger price of anarchy bounds. This paper answers this open question negatively. We consider graphic matroids, where each of the N players chooses a minimum cost spanning tree in a graph with linear cost functions on its edges. We provide constructions of graphs for N=2,3,4 and for unbounded N, where the price of anarchy attains the known upper bounds (5N-2)/(2N+1) and 5/2, respectively. These constructions translate the tightness of algebraic constraints into combinatorial conditions which are necessary for tight lower bound instances. The main technical contribution lies in showing the existence of recursively defined graphs which fulfill these combinatorial conditions, and which are based on solutions of a bilinear Diophantine equation.",

keywords = "2024 OA procedure, Matroid, Minimum Spanning Tree, MST, POA, Price of Anarchy, Congestion Game",

author = "Wouter Fokkema and Ruben Hoeksma and Marc Uetz",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.; 17th International Symposium on Algorithmic Game Theory, SAGT 2024, SAGT 2024 ; Conference date: 03-09-2024 Through 06-09-2024",

year = "2024",

month = sep,

doi = "10.1007/978-3-031-71033-9_21",

language = "English",

isbn = "9783031710322",

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

publisher = "Springer",

pages = "371--388",

editor = "Guido Sch{\"a}fer and Carmine Ventre",

booktitle = "Algorithmic Game Theory - 17th International Symposium, SAGT 2024, Proceedings",

address = "Germany",

}

Fokkema, W, Hoeksma, R & Uetz, M 2024, Price of Anarchy for Graphic Matroid Congestion Games. in G Schäfer & C Ventre (eds), Algorithmic Game Theory - 17th International Symposium, SAGT 2024, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 15156 LNCS, Springer, pp. 371-388, 17th International Symposium on Algorithmic Game Theory, SAGT 2024, Amsterdam, Netherlands, 3/09/24. https://doi.org/10.1007/978-3-031-71033-9_21

Price of Anarchy for Graphic Matroid Congestion Games. / Fokkema, Wouter; Hoeksma, Ruben ; Uetz, Marc.
Algorithmic Game Theory - 17th International Symposium, SAGT 2024, Proceedings. ed. / Guido Schäfer; Carmine Ventre. Springer, 2024. p. 371-388 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 15156 LNCS).

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

TY - GEN

T1 - Price of Anarchy for Graphic Matroid Congestion Games

AU - Fokkema, Wouter

AU - Hoeksma, Ruben

AU - Uetz, Marc

N1 - Conference code: 17

PY - 2024/9

Y1 - 2024/9

N2 - This paper analyzes the quality of pure-strategy Nash equilibria for symmetric Rosenthal congestion games with linear cost functions. For this class of games, the price of anarchy is known to be (5N-2)/(2N+1), where N is the number of players. It has been open if restricting the strategy spaces of players to be bases of a matroid suffices to obtain stronger price of anarchy bounds. This paper answers this open question negatively. We consider graphic matroids, where each of the N players chooses a minimum cost spanning tree in a graph with linear cost functions on its edges. We provide constructions of graphs for N=2,3,4 and for unbounded N, where the price of anarchy attains the known upper bounds (5N-2)/(2N+1) and 5/2, respectively. These constructions translate the tightness of algebraic constraints into combinatorial conditions which are necessary for tight lower bound instances. The main technical contribution lies in showing the existence of recursively defined graphs which fulfill these combinatorial conditions, and which are based on solutions of a bilinear Diophantine equation.

AB - This paper analyzes the quality of pure-strategy Nash equilibria for symmetric Rosenthal congestion games with linear cost functions. For this class of games, the price of anarchy is known to be (5N-2)/(2N+1), where N is the number of players. It has been open if restricting the strategy spaces of players to be bases of a matroid suffices to obtain stronger price of anarchy bounds. This paper answers this open question negatively. We consider graphic matroids, where each of the N players chooses a minimum cost spanning tree in a graph with linear cost functions on its edges. We provide constructions of graphs for N=2,3,4 and for unbounded N, where the price of anarchy attains the known upper bounds (5N-2)/(2N+1) and 5/2, respectively. These constructions translate the tightness of algebraic constraints into combinatorial conditions which are necessary for tight lower bound instances. The main technical contribution lies in showing the existence of recursively defined graphs which fulfill these combinatorial conditions, and which are based on solutions of a bilinear Diophantine equation.

KW - 2024 OA procedure

KW - Matroid

KW - Minimum Spanning Tree

KW - MST

KW - POA

KW - Price of Anarchy

KW - Congestion Game

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

U2 - 10.1007/978-3-031-71033-9_21

DO - 10.1007/978-3-031-71033-9_21

M3 - Conference contribution

AN - SCOPUS:85204399765

SN - 9783031710322

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

SP - 371

EP - 388

BT - Algorithmic Game Theory - 17th International Symposium, SAGT 2024, Proceedings

A2 - Schäfer, Guido

A2 - Ventre, Carmine

PB - Springer

T2 - 17th International Symposium on Algorithmic Game Theory, SAGT 2024

Y2 - 3 September 2024 through 6 September 2024

ER -

Fokkema W, Hoeksma R , Uetz M. Price of Anarchy for Graphic Matroid Congestion Games. In Schäfer G, Ventre C, editors, Algorithmic Game Theory - 17th International Symposium, SAGT 2024, Proceedings. Springer. 2024. p. 371-388. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-71033-9_21