Download the Paper (PDF format) - January 16, 2009 Tell a colleague about it. Printing Tips: Select 'print as image' in the Acrobat print dialog if you have trouble printing.

ABSTRACT:
We investigate the computational complexity of several decision problems in hedonic coalition formation games and demonstrate that attaining stability in such games remains NP-hard even when they are additive. Precisely, we prove that when either core stability or strict core stability is under consideration, the existence problem of a stable coalition structure is NP-hard in the strong sense. Furthermore, the corresponding decision problems with respect to the existence of a Nash stable coalition structure and of an individually stable coalition structure turn out to be NP-complete in the strong sense.

SUGGESTED CITATION:
Dinko Dimitrov and Shao-Chin Sung, "Computational Complexity in Additive Hedonic Games" (January 16, 2009). Fondazione Eni Enrico Mattei Working Papers. Working Paper 257.
http://www.bepress.com/feem/paper257