Nash Stability in Additively Separable Hedonic Games and Community Structures

TY - JOUR

T1 - Nash Stability in Additively Separable Hedonic Games and Community Structures

AU - Olsen, Martin

PY - 2009

Y1 - 2009

N2 -   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.

AB -   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.

U2 - 10.1007/s00224-009-9176-8

DO - 10.1007/s00224-009-9176-8

M3 - Journal article

SN - 1432-4350

VL - 45

SP - 917

EP - 925

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 4

ER -