Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Topological Price of Anarchy Bounds for Clustering Games on Networks


Kleer,  Pieter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 346KB

Supplementary Material (public)
There is no public supplementary material available

Kleer, P., & Schäfer, G. (2020). Topological Price of Anarchy Bounds for Clustering Games on Networks. doi:10.1007/978-3-030-35389-6_18.

Cite as: https://hdl.handle.net/21.11116/0000-0007-915F-B
We consider clustering games in which the players are embedded in a network
and want to coordinate (or anti-coordinate) their strategy with their
neighbors. The goal of a player is to choose a strategy that maximizes her
utility given the strategies of her neighbors. Recent studies show that even
very basic variants of these games exhibit a large Price of Anarchy: A large
inefficiency between the total utility generated in centralized outcomes and
equilibrium outcomes in which players selfishly try to maximize their utility.
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\'enyi random graphs (where every possible edge
in the network is present with a fixed probability), which, depending on the
graph density, stand in stark contrast to the known Price of Anarchy bounds.