Computational Complexity in Additive Hedonic Games

Dinko Dimitrov and Shao-Chin Sung
Additional contact information
Shao-Chin Sung: Aoyama Gakuin University

No 2008.98, Working Papers from Fondazione Eni Enrico Mattei

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: Additive Preferences; Coalition Formation; Computational Complexity; Hedonic Games; NP-hard; NP-complete (search for similar items in EconPapers)
JEL-codes: C63 C70 C71 D02 D70 D71 (search for similar items in EconPapers)
Date: 2008-12
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://feem-media.s3.eu-central-1.amazonaws.com/w ... oads/NDL2008-098.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:fem:femwpa:2008.98

Access Statistics for this paper

More papers in Working Papers from Fondazione Eni Enrico Mattei Contact information at EDIRC.
Bibliographic data for series maintained by Alberto Prina Cerai ( this e-mail address is bad, please contact ).