Abstract:
We study hedonic coalition formation problems with friend-oriented preferences; that is, each agent has preferences over her coalitions based on a partition of the set of agents, except herself, into "friends'' and "enemies'' such that (E) adding an enemy makes her strictly worse off and (F) adding a friend together with a set of enemies makes her strictly better off. Friend-oriented preferences induce a so-called friend-oriented preference 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 friend-oriented preference 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.