Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/104274 
Erscheinungsjahr: 
2008
Schriftenreihe/Nr.: 
Munich Discussion Paper No. 2008-18
Verlag: 
Ludwig-Maximilians-Universität München, Volkswirtschaftliche Fakultät, München
Zusammenfassung: 
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.
Schlagwörter: 
additive preferences
coalition formation
computational complexity
hedonic games
NP-hard
NP-complete
JEL: 
C63
C70
C71
Persistent Identifier der Erstveröffentlichung: 
Dokumentart: 
Working Paper

Datei(en):
Datei
Größe
352.32 kB





Publikationen in EconStor sind urheberrechtlich geschützt.