Pareto-Optimality in Cardinal Hedonic Games

Pareto-optimality and individual rationality are among the most natural requirements in coalition formation. We study classes of hedonic games with cardinal utilities that can be succinctly represented by means of complete weighted graphs, namely additively separable (ASHG), fractional (FHG), and modified fractional (MFHG) hedonic games. Each of these can model different aspects of dividing a society into groups. For all classes of games, we give algorithms that find Pareto-optimal partitions under some natural restrictions. While the output is also individually rational for modified fractional hedonic games, combining both notions is NP-hard for symmetric ASHGs and FHGs. In addition, we prove that welfare-optimal and Pareto-optimal partitions coincide for simple, symmetric MFHGs, solving an open problem from Elkind et al. [9]. For general MFHGs, our algorithm returns a 2-approximation to welfare. Interestingly, welfare-optimal partitions in MFHGs only require coalitions of at most three agents.