Topological price of anarchy bounds for clustering games on networks

DOI10.1007/978-3-030-35389-6_18zbMATH Open1435.91037arXiv2011.09717OpenAlexW3104308279MaRDI QIDQ777968FDOQ777968

Guido Schäfer, Pieter Kleer

Publication date: 30 June 2020

Abstract: 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 ErdH{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.

Full work available at URL: https://arxiv.org/abs/2011.09717

zbMATH Keywords

coordination gamesprice of anarchyrandom graphsNash equilibrium existenceclustering games

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Games involving graphs (91A43)

Cites Work

• Random Graphs
• Title not available (Why is that?)
• How bad is selfish routing?
• The densest subgraph problem in sparse random graphs
• Performance of global load balancing by local adjustment
• Designing Network Protocols for Good Equilibria
• Introduction to Random Graphs
• Hedonic Coalitions: Optimality and Stability
• Nash equilibria in random games
• Generalized graph \(k\)-coloring games
• Braess's Paradox in large random graphs
• Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games
• Coordination games on graphs
• Anti-coordination Games and Stable Graph Colorings
• Efficient Equilibria in Polymatrix Coordination Games
• The Max k-Cut Game and Its Strong Equilibria
• A Unified Framework for Strong Price of Anarchy in Clustering Games
• Nash Stable Outcomes in Fractional Hedonic Games: Existence, Efficiency and Computation

Cited In (1)

• Signed network formation games and clustering balance

This page was built for publication: Topological price of anarchy bounds for clustering games on networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q777968)