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

Computational Complexity in Additive Hedonic Games


Autori: Dinko Dimitrov, Shao-Chin Sung
Serie: Climate Change and Sustainable Development
Editor: Carlo Carraro
Tipo: Journal
Parole chiave: Additive Preferences,Coalition Formation,Computational Complexity,Hedonic Games,NP-hard,NP-complete
Numero JEL: C63,C70,C71,D02,D70,D71
JEL: European Journal of Operational Research
Pagine: Vol. 203, No. 3, pp. 635-639
Data: 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
Scarica il file PDF

FEEM Newsletter

Iscriviti per rimanere aggiornato.

I Suoi dati saranno trattati dalla Fondazione Eni Enrico Mattei. – Titolare del trattamento – per ricevere via posta elettronica la newsletter della Fondazione. Il conferimento dell’indirizzo e-mail è necessario alla fornitura del servizio. La invitiamo a consultare la Privacy Policy per ottenere maggiori informazioni a tutela dei Suoi diritti.

Questo Sito utilizza cookie tecnici e analytics, nonché consente l’invio di cookie di profilazione di terze parti.
Chiudendo questo banner o comunque proseguendo la navigazione sul Sito manifesti il tuo consenso all’uso dei cookie. Per ulteriori informazioni e per esprimere scelte selettive in ordine all’uso dei cookie vedi la   Cookie PolicyOk