Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games
Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games
复制标题
面向敌人的享乐博弈中存在极稳定分区和严格核心稳定联盟结构的复杂性
DOI：
10.1007/s10472-015-9461-y
复制
发表时间：
2015
影响因子：
1.2
通讯作者：
Lena Schend
中科院分区：
文献类型：
--
作者：
Anja Rey;J. Rothe;Hilmar Schadrack;Lena Schend
我们研究了存在的稳定分区（WSPE和WSPV）的存在的计算复杂性和验证问题以及在面向敌方的享乐游戏中严格核心稳定联盟结构（SCSC）的存在问题。在本说明中，我们表明WSPV是NP完整的，WSPE和SCSC均为DP-HARD，其中DP是布尔层次结构的第二级，我们讨论了一种根据其复杂性来对后两个问题进行分类的方法。
We study the computational complexity of the existence and the verification problem for wonderfully stable partitions (WSPE and WSPV) and of the existence problem for strictly core stable coalition structures (SCSCS) in enemy-oriented hedonic games. In this note, we show that WSPV is NP-complete and both WSPE and SCSCS are DP-hard, where DP is the second level of the boolean hierarchy, and we discuss an approach for classifying the latter two problems in terms of their complexity.
影响因子：
0.5
作者：
D. Baumeister;F. Brandt;F. Fischer;J. Hoffmann;J. Rothe
通讯作者：
J. Rothe