Computational Complexity in Additive Hedonic Games

Sung, Shao-Chin and Dimitrov, Dinko (7. October 2008): Computational Complexity in Additive Hedonic Games. Discussion Papers in Economics 2008-18

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.

• Item Type: Paper
• Form of publication: Preprint
• Keywords: additive preferences; coalition formation; computational complexity; hedonic games; NP-hard; NP-complete
• Faculties: Economics; Economics > Munich Discussion Papers in Economics; Economics > Munich Discussion Papers in Economics > Micro-Economics; Economics > Munich Discussion Papers in Economics > Mathematical Methods; Economics > Munich Discussion Papers in Economics > Game Theory
• Subjects: 300 Social sciences > 300 Social sciences, sociology and anthropology; 300 Social sciences > 330 Economics
• JEL Classification: C63, C70, C71
• Language: English