Aarhus University Seal / Aarhus Universitets segl

Nash Stability in Additively Separable Hedonic Games and Community Structures

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

  • Datalogisk Institut
  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.

OriginalsprogEngelsk
TidsskriftTheory of Computing Systems
Vol/bind45
Nummer4
Sider (fra-til)917-925
Antal sider9
ISSN1432-4350
DOI
StatusUdgivet - 2009

Se relationer på Aarhus Universitet Citationsformater

ID: 16095577