Topological price of anarchy bounds for clustering games on networks

DOI10.1007/978-3-030-35389-6_18MaRDI QIDQ777968zbMATH OpenOpenAlexFDO

Authors Pieter Kleer, Guido Schäfer

Publication date 30 June 2020

Full work available at URL https://arxiv.org/abs/2011.09717, https://ir.cwi.nl/pub/29214

zbMATH Keywords

coordination gamesprice of anarchyrandom graphsNash equilibrium existenceclustering games

Mathematics Subject Classification ID

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

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.

Recommendations

• A unified framework for strong price of anarchy in clustering games
• A clustering coefficient network formation game
• Local and global price of anarchy of graphical games
• On the price of stability of social distance games
• The Price of Anarchy in Network Creation Games Is (Mostly) Constant

Cites work

• A unified framework for strong price of anarchy in clustering games
• Anti-coordination games and stable graph colorings
• Braess's Paradox in large random graphs
• Coordination games on graphs
• Designing network protocols for good equilibria
• Efficient equilibria in polymatrix coordination games
• Generalized graph \(k\)-coloring games
• Hedonic Coalitions: Optimality and Stability
• How bad is selfish routing?
• Introduction to Random Graphs
• Nash equilibria in random games
• Nash stable outcomes in fractional hedonic games: existence, efficiency and computation
• Performance of global load balancing by local adjustment
• Potential games are \textit{necessary} to ensure pure Nash equilibria in cost sharing games
• Random Graphs
• The densest subgraph problem in sparse random graphs
• The max \(k\)-cut game and its strong equilibria
• Worst-case equilibria

Cited in

(3)

• A unified framework for strong price of anarchy in clustering games
• Signed network formation games and clustering balance
• A clustering coefficient network formation game

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)