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

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