论文标题
无政府状态的拓扑价格是网络上聚类游戏的范围
Topological Price of Anarchy Bounds for Clustering Games on Networks
论文作者
论文摘要
我们考虑将玩家嵌入网络中的聚类游戏，并希望与邻居协调（或反协调）他们的策略。球员的目标是选择一种策略，鉴于邻居的策略，可以最大程度地提高其实用性。最近的研究表明，即使是这些游戏的非常基本的变体也表现出很大的无政府状态价格：集中式成果中产生的总实用程序与玩家自私地试图最大化其效用的均衡结果之间的效率很大。我们的主要目标是了解网络拓扑的结构属性如何影响这些游戏的效率低下。我们在不同类别的聚类游戏的无政府状态价格上得出了拓扑界限。这些拓扑界限比相应的无政府状态界价（最坏的）价格提供了对这些游戏效率低下的信息丰富的评估。作为我们的主要结果之一，我们在Erdős-rényi随机图上（网络中的每个可能的边缘都具有固定概率）的无政府状态价格（紧密）范围（紧密），这取决于图形密度，与已知的无政府状态界限的鲜明对比。
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ős-Rényi 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.
