Computational Complexity in Additive Hedonic Games

descriptionPublicationkeyboard_double_arrow_right Article , Research , Other literature type , Preprint 01 Jan 2008 Germany English Publisher:Elsevier BVJournal:SSRN Electronic Journal (eissn: 1556-5068,

Copyright policy )

Authors: Dinko Dimitrov; Shao-Chin Sung;

doi: 10.2139/ssrn.1318329 , 10.1016/j.ejor.2009.09.004 , 10.5282/ubm/epub.6430

handle: 10419/53192 , 10419/104274

Computational Complexity in Additive Hedonic Games

- Summary
- Subjects
- Metrics

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.

Country

Germany

Related Organizations

Keywords

Computational Complexity, 330, hedonic games, Decision theory for games, Additive Preferences, NP-hard, Komplexe Systeme, C71, D70, D71, Cooperative games, additive preferences, C70, Applications of game theory, Entscheidungstheorie, Abstract computational complexity for mathematical programming problems, NP-complete, Hedonic Games, computational complexity, ddc:330, Nash-Gleichgewicht, Koalition, 300, Coalition Formation, C63, additive preferences; coalition formation; computational complexity; hedonic games; NP-hard; NP-complete, coalition formation, D02, Core, Nichtlineare Optimierung, Theorie, Additive Preferences, Coalition Formation, Computational Complexity, Hedonic Games, NP-hard, NP-complete, jel: jel:C63, jel: jel:D02, jel: jel:C70, jel: jel:D70, jel: jel:C71, jel: jel:D71

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	37
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average