Computing stable outcomes in hedonic games with voting-based deviations
Computing stable outcomes in hedonic games with voting-based deviations
复制标题
使用基于投票的偏差计算享乐游戏中的稳定结果
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Rahul Savani
中科院分区：
文献类型：
--
作者：
Martin Gairing;Rahul Savani
本文研究了一类联盟形成对策——享乐对策中寻找稳定结果的计算复杂度。我们将注意力限制在一类保证具有稳定结果的非平凡对策子集上，即对称可加可分享乐对策集。这些博弈由无向边加权图指定：节点是玩家，博弈的结果是将节点划分成联盟，节点的效用是同一联盟中事件边权重的总和。我们考虑文献中定义的几个稳定性要求。这是基于限制可行的玩家偏差，例如，通过给予现有联盟成员否决权。我们通过考虑联盟成员的更一般形式的偏好聚合来扩展这些限制。特别是，我们考虑投票方案来决定联盟成员是否允许玩家进入或离开他们的联盟。对于我们所考虑的所有稳定性要求，一个稳定结果的存在是由一个势函数参数保证的，并且局部改进将收敛到一个稳定结果。根据计算这些稳定结果的可追溯性，我们提供了这些游戏的几乎完整的特征。我们的发现包括多项式时间算法形式的积极结果和消极（pls -完备性）结果。负面结果延伸到更普遍的享乐游戏。
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 a nontrivial subclass of such games, which are guaranteed to possess stable outcomes, i.e., the set of symmetric additively-separable hedonic games. These games are specified by an undirected edge-weighted graph: 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 if 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 (PLS-completeness) results. The negative results extend to more general hedonic games.