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

被引：7

作者：

Rey, Anja ^{[1
]}

Rothe, Joerg ^{[1
]}

Schadrack, Hilmar ^{[1
]}

Schend, Lena ^{[1
]}

机构：

[1] Univ Dusseldorf, Inst Informat, D-40225 Dusseldorf, Germany

来源：

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE | 2016年 / 77卷 / 3-4期

关键词：

Game Theory; Hedonic games; Strict core stability; Wonderful stability; BOOLEAN HIERARCHY; PARALLEL ACCESS; STABILITY;

D O I：

10.1007/s10472-015-9461-y

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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

页数：17

共 37 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2]

[Anonymous], 2011, SYNTHESIS LECT ARTIF

[3] Computing desirable partitions in additively separable hedonic games [J].

Aziz, Hans ;

Brandt, Felix ;

Seedig, Hans Georg .

ARTIFICIAL INTELLIGENCE, 2013, 195 :316-334

[4] The Complexity of Computing Minimal Unidirectional Covering Sets [J].

Baumeister, Dorothea ;

Brandt, Felix ;

Fischer, Felix ;

Hoffmann, Jan ;

Rothe, Joerg .

THEORY OF COMPUTING SYSTEMS, 2013, 53 (03) :467-502

[5]

Beigel R., 1989, Proceedings. Structure in Complexity Theory Fourth Annual Conference (Cat. No.89CH2745-8), P225, DOI 10.1109/SCT.1989.41828

[6] BOUNDED QUERIES TO SAT AND THE BOOLEAN HIERARCHY [J].

BEIGEL, R .

THEORETICAL COMPUTER SCIENCE, 1991, 84 (02) :199-223

[7]

Brams S., 2002, HDB SOCIAL CHOICE WE, V1, P173, DOI DOI 10.1016/S1574-0110(02)80008-X

[8]

Brandt F., 2013, MULTIAGENT SYSTEMS, P213

[9] THE BOOLEAN HIERARCHY .1. STRUCTURAL-PROPERTIES [J].

CAI, JY ;

GUNDERMANN, T ;

HARTMANIS, J ;

HEMACHANDRA, LA ;

SEWELSON, V ;

WAGNER, K ;

WECHSUNG, G .

SIAM JOURNAL ON COMPUTING, 1988, 17 (06) :1232-1252

[10] THE BOOLEAN HIERARCHY .2. APPLICATIONS [J].