Computing Desirable Partitions in Coalition Formation Games

Coalition formation games aim at predicting the cooperative behavior of agents when forming alliances. Agents entertain preferences over coalition structures, and the goal is to find a coalition structure that is good for both individual agents and the society as an entity. We measure the quality of partitions in terms of Pareto optimality and popularity. We give both efficient algorithms and hardness results for computing partitions that satisfy these properties for various classes of coalition formation games, including roommate games, flatmate games, and cardinal hedonic games.