Computational Complexity in Additive Hedonic Games

Shao Chin Sung and Dinko Dimitrov

No 46655, Coalition Theory Network Working Papers from Fondazione Eni Enrico Mattei (FEEM)

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.

Keywords: Research; Methods/; Statistical; Methods (search for similar items in EconPapers)
Pages: 36
Date: 2008-12
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://ageconsearch.umn.edu/record/46655/files/98-08.pdf (application/pdf)

Related works:
Journal Article: Computational complexity in additive hedonic games (2010)
Working Paper: Computational Complexity in Additive Hedonic Games (2008)
Working Paper: Computational Complexity in Additive Hedonic Games (2008)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ags:feemct:46655

DOI: 10.22004/ag.econ.46655

Access Statistics for this paper

More papers in Coalition Theory Network Working Papers from Fondazione Eni Enrico Mattei (FEEM) Contact information at EDIRC.
Bibliographic data for series maintained by AgEcon Search ().