Simple Causes of Complexity in Hedonic Games
Simple Causes of Complexity in Hedonic Games
复制标题
享乐游戏复杂性的简单原因
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Edith Elkind
中科院分区：
文献类型：
--
作者：
Dominik Peters;Edith Elkind
享乐游戏提供了一个自然的模型，联盟之间的自我利益的代理形成。在这种博弈中寻找稳定结果的相关问题已经得到了广泛的研究。在本文中，我们确定简单的条件表现力的享乐游戏是足够的问题，检查是否一个给定的游戏承认一个稳定的结果是计算困难的。有些令人惊讶的是，这些条件非常温和和直观。我们的结果适用于广泛的稳定性概念（核心稳定性，个人稳定性，纳什稳定性等）。以及许多已知的享乐游戏的形式（可加可分游戏、W偏好游戏、分数享乐游戏等），并统一和推广了这些形式主义的已知结果。他们也有更广泛的适用性：几类享乐游戏的计算复杂性还没有被探索在以前的工作中，我们表明，我们的框架立即意味着他们的硬度结果。
Hedonic games provide a natural model of coalition formation among self-interested agents. The associated problem of finding stable outcomes in such games has been extensively studied. In this paper, we identify simple conditions on expressivity of hedonic games that are sufficient for the problem of checking whether a given game admits a stable outcome to be computationally hard. Somewhat surprisingly, these conditions are very mild and intuitive. Our results apply to a wide range of stability concepts (core stability, individual stability, Nash stability, etc.) and to many known formalisms for hedonic games (additively separable games, games with W-preferences, fractional hedonic games, etc.), and unify and extend known results for these formalisms. They also have broader applicability: for several classes of hedonic games whose computational complexity has not been explored in prior work, we show that our framework immediately implies a number of hardness results for them.
联盟形成中的帕累托最优
DOI：
10.1016/j.geb.2013.08.006
发表时间：
2013
期刊：
Games Econ. Behav.
影响因子：
--
作者：
H. Aziz;F. Brandt;P. Harrenstein
通讯作者：
P. Harrenstein
分数享乐游戏
DOI：
10.1145/3327970
发表时间：
2019
期刊：
ACM Transactions on Economics and Computation (TEAC)
影响因子：
--
作者：
Brandl;Florian;Brandt;Harrenstein;Martin;Peters;Dominik
通讯作者：
Dominik