| Sung, Shao-Chin and Dimitrov, Dinko (07. October 2008): Computational Complexity in Additive Hedonic Games. Discussion Papers in Economics 2008-18 |
![[img]](http://epub.ub.uni-muenchen.de/style/images/fileicons/application_pdf.png)
| PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Reader 187Kb |
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 (Discussion Paper) |
|---|---|
| Keywords: | additive preferences; coalition formation; computational complexity; hedonic games; NP-hard; NP-complete |
| Subjects: | Economics Economics > Discussion Papers in Economics Economics > Discussion Papers in Economics > Micro-Economics Economics > Discussion Papers in Economics > Mathematical Methods Economics > Discussion Papers in Economics > Game Theory |
| Dewey Classification: | 300 Social sciences 300 Social sciences > 330 Wirtschaft |
| Journal of Economic Literature classification: | C63, C70, C71 |
| URN: | urn:nbn:de:bvb:19-epub-6430-0 |
| Language: | English |
| ID Code: | 6430 |
| Deposited On: | 10. Oct 2008 18:09 |
| Last Modified: | 28. Jun 2010 15:04 |
