www.coalitiontheory.net
Published on www.coalitiontheory.net (http://coalitiontheory.net)

Home > Computational Complexity in Additive Hedonic Games

Computational Complexity in Additive Hedonic Games

Working paper
Author/s: 
Shao-Chin Sung and Dinko Dimitrov
Issue number: 
2008.098
Publisher: 
FEEM
Year: 
2008
PDF [1]
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.
Tags: 
Cooperative Game Theory [2]

Source URL:http://coalitiontheory.net/content/computational-complexity-additive-hedonic-games

Links
[1] http://www.feem.it/userfiles/attach/Publication/NDL2008/NDL2008-098.pdf [2] http://coalitiontheory.net/research-areas/cooperative-game-theory