Computational complexity in additive hedonic games

Dinko Dimitrov ; Shao-Chin Sung

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. -- Additive Preferences ; Coalition Formation ; Computational Complexity ; Hedonic Games ; NP-hard ; NP-complete

MoreLess

Year of publication:	2008
Authors:	Dimitrov, Dinko ; Sung, Shao Chin
Publisher:	Milano : Fondazione Eni Enrico Mattei
Subject:	Core \| Koalition \| Coalition \| Nash-Gleichgewicht \| Nash equilibrium \| Komplexe Systeme \| Complex systems \| Entscheidungstheorie \| Decision theory \| Nichtlineare Optimierung \| Nonlinear programming

Extent:	Online-Ressource (PDF-Datei: 32 S., 276,42 KB) graph. Darst.
Series:	Working paper. - Milan : [Verlag nicht ermittelbar], ZDB-ID 2217241-5. - Vol. 98.2008
Type of publication:	Book / Working Paper
Type of publication (narrower categories):	Arbeitspapier ; Working Paper ; Graue Literatur ; Non-commercial literature
Language:	English
Notes:	Systemvoraussetzungen: Acrobat Reader
Other identifiers:	hdl:10419/53192 [Handle]
Classification:	C63 - Computational Techniques ; C70 - Game Theory and Bargaining Theory. General ; C71 - Cooperative Games ; D02 - Institutions: Design, Formation, and Operations ; D70 - Analysis of Collective Decision-Making. General ; D71 - Social Choice; Clubs; Committees; Associations
Source:	ECONIS - Online Catalogue of the ZBW

Persistent link: https://ebvufind01.dmz1.zbw.eu/10008799165