2019-12-10
Topological Price of Anarchy bounds for clustering games on networks
Publication
Publication
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ős-Rényi random graphs, which, depending on the graph density, stand in stark contrast to the known Price of Anarchy bounds.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.1007/978-3-030-35389-6_18 | |
| Lecture Notes in Computer Science | |
| Conference on Web and Internet Economics | |
| Organisation | Networks and Optimization |
|
Kleer, P., & Schäfer, G. (2019). Topological Price of Anarchy bounds for clustering games on networks. In Proceedings of the International Conference on Web and Internet Economics (pp. 241–255). doi:10.1007/978-3-030-35389-6_18 |
|
