Core stability and strategy-proofness in hedonic coalition formation problems with friend-oriented preferences

We study hedonic coalition formation problems with friend-oriented preferences; that is, each agent has preferences over his coalitions based on a partition of the set of agents, except himself, into "friends" and "enemies" such that (E) adding an enemy makes him strictly worse off and (F) adding a friend together with a set of enemies makes him strictly better off. Friend-oriented preferences induce a so-called friendship graph where vertices are agents and directed edges point to friends. We show that the partition associated with the strongly connected components (SCC) of the friendship graph is in the strict core. We then prove that the SCC mechanism, which assigns the SCC partition to each hedonic coalition formation problem with friend-oriented preferences, satisfies a strong group incentive compatibility property: group strategy-proofness. Our main result is that on any "rich" subdomain of friend-oriented preferences, the SCC mechanism is the only mechanism that satisfies core stability and strategy-proofness.