EconStor >
Fondazione Eni Enrico Mattei (FEEM), Mailand >
FEEM Working Papers, Fondazione Eni Enrico Mattei  >

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10419/53192
  
Title:Computational complexity in additive hedonic games PDF Logo
Authors:Dimitrov, Dinko
Sung, Shao-chin
Issue Date:2008
Series/Report no.:Nota di lavoro // Fondazione Eni Enrico Mattei: Sustainable development 98.2008
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.
Subjects:Additive Preferences
Coalition Formation
Computational Complexity
Hedonic Games
NP-hard
NP-complete
JEL:C63
C70
C71
D02
D70
D71
Document Type:Working Paper
Appears in Collections:FEEM Working Papers, Fondazione Eni Enrico Mattei

Files in This Item:
File Description SizeFormat
644374551.pdf276.42 kBAdobe PDF
No. of Downloads: Counter Stats
Download bibliographical data as: BibTeX
Share on:http://hdl.handle.net/10419/53192

Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.