FEEM working papers "Note di lavoro" series
2008 .098

Computational Complexity in Additive Hedonic Games


Authors: Dinko Dimitrov, Shao-Chin Sung
Series: Climate Change and Sustainable Development
Editor: Carlo Carraro
Type: Journal
Keywords: Additive Preferences,Coalition Formation,Computational Complexity,Hedonic Games,NP-hard,NP-complete
JEL n.: C63,C70,C71,D02,D70,D71
JEL: European Journal of Operational Research
Pages: Vol. 203, No. 3, pp. 635-639
Date: 06/2010

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.

Download file
Download PDF file

FEEM Update

Subscribe to stay connected.

Your personal data will be processed by Fondazione Eni Enrico Mattei. – data Controller – with the aim of emailing the FEEM newsletter. The use of Your email address is necessary for the implementation of the newsletter service. You are invited to read the Privacy Policy in order to obtain additional information about the protection of Your rights.

This Website uses technical cookies and cookie analytics, as well as “third party” profiling cookies.
If you close this banner or you decide to continue navigating on this Website, you express consent to the use of cookies. If you need additional information or you wish to express selective choices on the use of cookies, please refer to the   Cookie PolicyI agree