Computational Complexity in Additive Hedonic Games

Arbeitspapier

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.

Angaben zum Objekt

• Sprache: Englisch

Verweise und Beziehungen

• Erschienen in: Series: Munich Discussion Paper ; No. 2008-18

Klassifikation und Themen

• Klassifikation: Wirtschaft ; Computational Techniques; Simulation Modeling ; Game Theory and Bargaining Theory: General ; Cooperative Games
• Thema: additive preferences ; coalition formation ; computational complexity ; hedonic games ; NP-hard ; NP-complete ; Koalition ; Entscheidungstheorie ; Nash-Gleichgewicht ; Core ; Nichtlineare Optimierung ; Komplexe Systeme ; Theorie

Beteiligte, Orts- und Zeitangaben

• Ereignis: Geistige Schöpfung
• (wer): Sung, Shao-Chin ; Dimitrov, Dinko
• Ereignis: Veröffentlichung
• (wer): Ludwig-Maximilians-Universität München, Volkswirtschaftliche Fakultät
• (wo): München
• (wann): 2008

Weitere Informationen

• DOI: doi:10.5282/ubm/epub.6430
• Handle: http://hdl.handle.net/10419/104274
• URN: urn:nbn:de:bvb:19-epub-6430-0
• Letzte Aktualisierung: 10.03.2025, 11:41 MEZ