Logo Logo
Hilfe
Hilfe
Switch Language to English

Sung, Shao-Chin und Dimitrov, Dinko (7. Oktober 2008): Computational Complexity in Additive Hedonic Games. Münchener Wirtschaftswissenschaftliche Beiträge (VWL) 2008-18 [PDF, 191kB]

[thumbnail of Complexity.pdf]
Vorschau
Download (191kB)

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.

Dokument bearbeiten Dokument bearbeiten