Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games

• 成果类型: Article
• 署名作者: Gairing, Martin; Savani, Rahul
• 署名单位: University of Liverpool
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2018.0960
• 发表日期: 2019
• 页码: 1101-1121
• 关键词: coalition-formation games; core stability; LOCAL SEARCH; optimality

摘要

We study the computational complexity of finding stable outcomes in hedonic games, which are a class of coalition formation games. We restrict our attention to symmetric additively separable hedonic games, which are a nontrivial subclass of such games that are guaranteed to possess stable outcomes. These games are specified by undirected edge-weighted graphs: nodes are players, an outcome of the game is a partition of the nodes into coalitions, and the utility of a node is the sum of incident edge weights in the same coalition. We consider several stability requirements defined in the literature. These are based on restricting feasible player deviations, for example, by giving existing coalition members veto power. We extend these restrictions by considering more general forms of preference aggregation for coalition members. In particular, we consider voting schemes to decide whether coalition members will allow a player to enter or leave their coalition. For all of the stability requirements we consider, the existence of a stable outcome is guaranteed by a potential function argument, and local improvements will converge to a stable outcome. We provide an almost complete characterization of these games in terms of the tractability of computing such stable outcomes. Our findings comprise positive results in the form of polynomial-time algorithms and negative results in the form of proofs of polynomial local search (PLS)-hardness. The negative results extend to more general hedonic games.