Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games

被引：0
作者：
Anja Rey
Jörg Rothe
Hilmar Schadrack
Lena Schend
机构：
[1] Heinrich-Heine-Universität Düsseldorf,Institut für Informatik
来源：
Annals of Mathematics and Artificial Intelligence | 2016年 / 77卷
关键词：
Game Theory; Hedonic games; Strict core stability; Wonderful stability; 68Q15; 68Q17; 91A12;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：317 / 333
页数：16
相关论文
共 70 条
[1]  
Aziz H(2013)Computing desirable partitions in additively separable hedonic games Artif. Intell. 195 316-334
[2]  
Brandt F(2013)The complexity of computing minimal unidirectional covering sets Theory of Computing Systems 53 467-502
[3]  
Seedig H(1991)Bounded queries to SAT and the boolean hierarchy Theor. Comput. Sci. 84 199-223
[4]  
Baumeister D(1988)The boolean hierarchy I: Structural properties SIAM J. Comput. 17 1232-1252
[5]  
Brandt F(1989)The boolean hierarchy II: Applications SIAM J. Comput. 18 95-111
[6]  
Fischer F(1995)On computing boolean connectives of characteristic functions Mathematical Systems Theory 28 173-198
[7]  
Hoffmann J(2006)Simple priorities and core stability in hedonic games Soc. Choice Welf. 26 421-433
[8]  
Rothe J(1989)The strong exponential hierarchy collapses J. Comput. Syst. Sci. 39 299-322
[9]  
Beigel R(1998)Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP Inf. Process. Lett. 65 151-156
[10]  
Cai J(1997)Exact analysis of Dodgson elections: Lewis Carroll’s 1876 voting system is complete for parallel access to NP J. ACM 44 806-825
1234567