Nash Stability in Additively Separable Hedonic Games and Community Structures

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

    Abstract

      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

    Fingeraftryk

    Dyk ned i forskningsemnerne om 'Nash Stability in Additively Separable Hedonic Games and Community Structures'. Sammen danner de et unikt fingeraftryk.

    Citationsformater