
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.
Item Type: | Paper |
---|---|
Form of publication: | Preprint |
Keywords: | additive preferences; coalition formation; computational complexity; hedonic games; NP-hard; NP-complete |
Faculties: | Economics Economics > Munich Discussion Papers in Economics Economics > Munich Discussion Papers in Economics > Micro-Economics Economics > Munich Discussion Papers in Economics > Mathematical Methods Economics > Munich Discussion Papers in Economics > Game Theory |
Subjects: | 300 Social sciences > 300 Social sciences, sociology and anthropology 300 Social sciences > 330 Economics |
JEL Classification: | C63, C70, C71 |
URN: | urn:nbn:de:bvb:19-epub-6430-0 |
Language: | English |
Item ID: | 6430 |
Date Deposited: | 10. Oct 2008, 16:09 |
Last Modified: | 04. Nov 2020, 20:54 |