Computing Stable Outcomes in Hedonic Games
Computing Stable Outcomes in Hedonic Games
复制标题
计算享乐游戏中的稳定结果
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Rahul Savani
中科院分区：
文献类型：
--
作者：
Martin Gairing;Rahul Savani
我们研究了在对称可加可分享乐博弈中寻找稳定结果的计算复杂性。这些联盟形成游戏由无向边加权图指定：节点是玩家，游戏的结果是将节点划分为联盟，并且节点的效用是同一联盟中的事件边权重的总和。我们考虑几个自然的稳定性要求在经济学文献中定义。对于所有这些问题，一个稳定的结果的存在是由一个潜在的功能参数保证，所以当地的改善将收敛到一个稳定的结果，所有这些问题都在PLS。不同的稳定性要求对应于不同的局部搜索邻域。对于不同的邻域结构，我们的研究结果包括积极的结果，在多项式时间算法的形式，寻找稳定的结果，和消极的（PLS-完整性）的结果。
We study the computational complexity of finding stable outcomes in symmetric additively-separable hedonic games. These coalition formation 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 natural stability requirements defined in the economics literature. For all of them the existence of a stable outcome is guaranteed by a potential function argument, so local improvements will converge to a stable outcome and all these problems are in PLS. The different stability requirements correspond to different local search neighbourhoods. For different neighbourhood structures, our findings comprise positive results in the form of polynomial-time algorithms for finding stable outcomes, and negative (PLS-completeness) results.