Computational Complexity in Additive Hedonic Games

Shao-Chin Sung and Dinko Dimitrov

Discussion Papers in Economics from University of Munich, Department of Economics

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 (search for similar items in EconPapers)
Date: 2008-10-07
New Economics Papers: this item is included in nep-gth
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://epub.ub.uni-muenchen.de/6430/1/Complexity.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:lmu:muenec:6430

Access Statistics for this paper

More papers in Discussion Papers in Economics from University of Munich, Department of Economics Ludwigstr. 28, 80539 Munich, Germany. Contact information at EDIRC.
Bibliographic data for series maintained by Tamilla Benkelberg ().