@inproceedings{78ed56663aeb4839abb3d5cc7ddc838b,
title = "Topological price of anarchy bounds for clustering games on networks",
abstract = "We consider clustering games in which the players are embedded in a network and want to coordinate (or anti-coordinate) their choices with their neighbors. Recent studies show that even very basic variants of these games exhibit a large Price of Anarchy. Our main goal is to understand how structural properties of the network topology impact the inefficiency of these games. We derive topological bounds on the Price of Anarchy for different classes of clustering games. These topological bounds provide a more informative assessment of the inefficiency of these games than the corresponding (worst-case) Price of Anarchy bounds. As one of our main results, we derive (tight) bounds on the Price of Anarchy for clustering games on Erd{\H o}s-R{\'e}nyi random graphs, which, depending on the graph density, stand in stark contrast to the known Price of Anarchy bounds.",
keywords = "clustering games, coordination games, price of anarchy, random graphs, nash equilibrium existence",
author = "Pieter Kleer and Guido Sch{\"a}fer",
year = "2019",
month = dec,
doi = "10.1007/978-3-030-35389-6_18",
language = "English",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "241--255",
editor = "I. Caragiannis and V. Mirrokni and E. Nikolova",
booktitle = "Proceedings of the International Conference on Web and Internet Economics (WINE 2019)",
address = "Germany",
}