Enemies and Friends in Hedonic Games: Individual Deviations, Stability and Manipulation

D.A. Dimitrov, S.C. Sung

Research output: Working paperDiscussion paperOther research output

259 Downloads (Pure)

Abstract

We consider hedonic games with separable preferences, and explore the existence of stable coalition structures if only individual deviations are allowed.For two natural subdomains of separable preferences, namely preference domains based on (1) aversion to enemies and (2) appreciation of friends, we show that an individually stable coalition structure always exist, and a Nash stable coalition structure exists when mutuality is imposed.Moreover, we show that on the domain of separable preferences a contractual individually stable coalition structure can be obtained in polynomial time.Finally, we prove that, on each of the two subdomains, the corresponding algorithm that we use for finding Nash stable and individually stable coalition structures turns out to be strategy-proof.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages23
Volume2004-111
Publication statusPublished - 2004

Publication series

NameCentER Discussion Paper
Volume2004-111

Fingerprint

Deviation
Hedonic games
Coalition structure
Manipulation
Separable preferences
Mutuality
Strategy-proof
Polynomials

Keywords

  • additive separability
  • coalition formation
  • hedonic games
  • stability
  • strategy-proofness

Cite this

Dimitrov, D. A., & Sung, S. C. (2004). Enemies and Friends in Hedonic Games: Individual Deviations, Stability and Manipulation. (CentER Discussion Paper; Vol. 2004-111). Tilburg: Operations research.
Dimitrov, D.A. ; Sung, S.C. / Enemies and Friends in Hedonic Games : Individual Deviations, Stability and Manipulation. Tilburg : Operations research, 2004. (CentER Discussion Paper).
@techreport{c66aeb6aa6014927888fddc89eed26e6,
title = "Enemies and Friends in Hedonic Games: Individual Deviations, Stability and Manipulation",
abstract = "We consider hedonic games with separable preferences, and explore the existence of stable coalition structures if only individual deviations are allowed.For two natural subdomains of separable preferences, namely preference domains based on (1) aversion to enemies and (2) appreciation of friends, we show that an individually stable coalition structure always exist, and a Nash stable coalition structure exists when mutuality is imposed.Moreover, we show that on the domain of separable preferences a contractual individually stable coalition structure can be obtained in polynomial time.Finally, we prove that, on each of the two subdomains, the corresponding algorithm that we use for finding Nash stable and individually stable coalition structures turns out to be strategy-proof.",
keywords = "additive separability, coalition formation, hedonic games, stability, strategy-proofness",
author = "D.A. Dimitrov and S.C. Sung",
note = "Pagination: 23",
year = "2004",
language = "English",
volume = "2004-111",
series = "CentER Discussion Paper",
publisher = "Operations research",
type = "WorkingPaper",
institution = "Operations research",

}

Dimitrov, DA & Sung, SC 2004 'Enemies and Friends in Hedonic Games: Individual Deviations, Stability and Manipulation' CentER Discussion Paper, vol. 2004-111, Operations research, Tilburg.

Enemies and Friends in Hedonic Games : Individual Deviations, Stability and Manipulation. / Dimitrov, D.A.; Sung, S.C.

Tilburg : Operations research, 2004. (CentER Discussion Paper; Vol. 2004-111).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - Enemies and Friends in Hedonic Games

T2 - Individual Deviations, Stability and Manipulation

AU - Dimitrov, D.A.

AU - Sung, S.C.

N1 - Pagination: 23

PY - 2004

Y1 - 2004

N2 - We consider hedonic games with separable preferences, and explore the existence of stable coalition structures if only individual deviations are allowed.For two natural subdomains of separable preferences, namely preference domains based on (1) aversion to enemies and (2) appreciation of friends, we show that an individually stable coalition structure always exist, and a Nash stable coalition structure exists when mutuality is imposed.Moreover, we show that on the domain of separable preferences a contractual individually stable coalition structure can be obtained in polynomial time.Finally, we prove that, on each of the two subdomains, the corresponding algorithm that we use for finding Nash stable and individually stable coalition structures turns out to be strategy-proof.

AB - We consider hedonic games with separable preferences, and explore the existence of stable coalition structures if only individual deviations are allowed.For two natural subdomains of separable preferences, namely preference domains based on (1) aversion to enemies and (2) appreciation of friends, we show that an individually stable coalition structure always exist, and a Nash stable coalition structure exists when mutuality is imposed.Moreover, we show that on the domain of separable preferences a contractual individually stable coalition structure can be obtained in polynomial time.Finally, we prove that, on each of the two subdomains, the corresponding algorithm that we use for finding Nash stable and individually stable coalition structures turns out to be strategy-proof.

KW - additive separability

KW - coalition formation

KW - hedonic games

KW - stability

KW - strategy-proofness

M3 - Discussion paper

VL - 2004-111

T3 - CentER Discussion Paper

BT - Enemies and Friends in Hedonic Games

PB - Operations research

CY - Tilburg

ER -

Dimitrov DA, Sung SC. Enemies and Friends in Hedonic Games: Individual Deviations, Stability and Manipulation. Tilburg: Operations research. 2004. (CentER Discussion Paper).