Nash Stability in Additively Separable Hedonic Games and Community Structures

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Department of Computer Science
  We prove that the problem of deciding whether a Nash stable
  partition exists in an Additively Separable Hedonic Game is
  NP-complete. We also show that the problem of deciding whether a
  non trivial Nash stable partition exists in an
  Additively Separable Hedonic Game with
  non-negative and symmetric
  preferences is NP-complete. We motivate our study of the
  computational complexity by linking Nash stable partitions in
  Additively Separable Hedonic Games to community structures in
  networks. Our results formally justify that computing community
  structures in general is hard.

Original languageEnglish
JournalTheory of Computing Systems
Volume45
Issue4
Pages (from-to)917-925
Number of pages9
ISSN1432-4350
DOIs
Publication statusPublished - 2009

See relations at Aarhus University Citationformats

ID: 16095577