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

Standard

Nash Stability in Additively Separable Hedonic Games and Community Structures. / Olsen, Martin.

I: Theory of Computing Systems, Bind 45, Nr. 4, 2009, s. 917-925.

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

Harvard

APA

CBE

MLA

Vancouver

Author

Olsen, Martin. / Nash Stability in Additively Separable Hedonic Games and Community Structures. I: Theory of Computing Systems. 2009 ; Bind 45, Nr. 4. s. 917-925.

Bibtex

@article{7b225df0363511debd59000ea68e967b,
title = "Nash Stability in Additively Separable Hedonic Games and Community Structures",
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.",
author = "Martin Olsen",
year = "2009",
doi = "10.1007/s00224-009-9176-8",
language = "English",
volume = "45",
pages = "917--925",
journal = "Theory of Computing Systems",
issn = "1432-4350",
publisher = "Springer New York LLC",
number = "4",

}

RIS

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

VL - 45

SP - 917

EP - 925

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 4

ER -