研究线上群体分组的稳定性,用距离衡量成员间契合度。
Metric Hedonic Games on the Line
- 基于成员价值差异定义成本,建模相似性分组行为
- 无论何种规则,稳定分组结构始终存在
- 适用于运动员、选民等按特质分群的场景
霍德尼克博弈是研究策略性代理人结盟形成的经典模型,每个代理对可能加入的联盟具有特定效用。为避免需定义指数级联盟效用的困难,已有多种简洁表示方法被提出,如Monaco等人[JAAMAS 2020]提出的修正分数型霍德尼克博弈。本文提出一种新型简洁变体:每位代理具有固定类型值,其在某联盟中的成本取决于自身值与联盟内其他成员值的差异。该模型可刻画运动员按能力水平组队或选民沿政治光谱划分等自然情形。我们研究了基于距离阈值、最大值差或平均值差定义成本的不同设定,分析稳定联盟结构的存在性、性质及其质量(以纳什均衡价格和稳定价格衡量)。同时考察了限制联盟数量的影响。尽管设置简单(线性度量空间),仍揭示出丰富的模型行为,部分结果反直觉。通过同时考虑交换稳定性和跳跃稳定性,我们进一步探讨了固定联盟数量与大小的影响。总体发现:稳定联盟结构始终存在,但其性质和质量差异显著。
原文摘要 · Abstract (English)
Hedonic games are fundamental models for investigating the formation of coalitions among a set of strategic agents, where every agent has a certain utility for every possible coalition of agents it can be part of. To avoid the intractability of defining exponentially many utilities for all possible coalitions, many variants with succinct representations of the agents' utility functions have been devised and analyzed, e.g., modified fractional hedonic games by Monaco et al. [JAAMAS 2020]. We extend this by studying a novel succinct variant that is related to modified fractional hedonic games. In our model, each agent has a fixed type-value and an agent's cost for some given coalition is based on the differences between its value and those of the other members of its coalition. This allows to model natural situations like athletes forming training groups with similar performance levels or voters that partition themselves along a political spectrum. In particular, we investigate natural variants where an agent's cost is defined by distance thresholds, or by the maximum or average value difference to the other agents in its coalition. For these settings, we study the existence of stable coalition structures, their properties, and their quality in terms of the price of anarchy and the price of stability. Further, we investigate the impact of limiting the maximum number of coalitions. Despite the simple setting with metric distances on a line, we uncover a rich landscape of models, partially with counter-intuitive behavior. Also, our focus on both swap stability and jump stability allows us to study the influence of fixing the number and the size of the coalitions. Overall, we find that stable coalition structures always exist but that their properties and quality can vary widely.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。