On a Simple Hedonic Game with Graph-Restricted Communication

Abstract

We study a hedonic game for which feasible coalitions are prescribed by a graph representing the agents’ social relations. A group of agents can form a feasible coalition if and only if their corresponding vertices can be spanned with a star. This requirement guarantees that agents are connected, close to each other, and one central agent can coordinate the actions of the group. In our game, everyone strives to join the largest feasible coalition. We study the existence and computational complexity of both Nash stable and core stable partitions. Then, we provide tight or asymptotically tight bounds on their efficiency, measured in terms of the price of anarchy and the price of stability, under two natural social functions, namely, the number of agents who are not in a singleton coalition, and the number of coalitions. We also derive refined bounds for games in which the social graph is claw-free. Finally, we investigate the complexity of computing socially optimal partitions, as well as extreme Nash stable ones.