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.
| Dokumententyp: | Paper |
|---|---|
| Publikationsform: | Preprint |
| Keywords: | additive preferences; coalition formation; computational complexity; hedonic games; NP-hard; NP-complete |
| Fakultät: | Volkswirtschaft
Volkswirtschaft > Munich Discussion Papers in Economics Volkswirtschaft > Munich Discussion Papers in Economics > Mikroökonomik Volkswirtschaft > Munich Discussion Papers in Economics > Mathematische Methoden Volkswirtschaft > Munich Discussion Papers in Economics > Spieltheorie |
| Themengebiete: | 300 Sozialwissenschaften > 300 Sozialwissenschaft, Soziologie
300 Sozialwissenschaften > 330 Wirtschaft |
| JEL Classification: | C63, C70, C71 |
| URN: | urn:nbn:de:bvb:19-epub-6430-0 |
| Sprache: | Englisch |
| Dokumenten ID: | 6430 |
| Datum der Veröffentlichung auf Open Access LMU: | 10. Okt. 2008 16:09 |
| Letzte Änderungen: | 04. Nov. 2020 20:54 |
- Dokument bearbeiten
