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

D.A. Dimitrov, S.C. Sung

Research output: Working paperDiscussion paperOther research output

482 Downloads (Pure)


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
Publication statusPublished - 2004

Publication series

NameCentER Discussion Paper


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


Dive into the research topics of 'Enemies and Friends in Hedonic Games: Individual Deviations, Stability and Manipulation'. Together they form a unique fingerprint.

Cite this