Optimal Partitions in Additively Separable Hedonic Games

Abstract

We conduct a computational analysis of fair and optimal partitions in additively separable hedonic games. We show that, for strict preferences, a Pareto optimal partition can be found in polynomial time while verifying whether a given partition is Pareto optimal is coNP-complete, even when preferences are symmetric and strict. Moreover, computing a partition with maximum egalitarian or utilitarian social welfare or one which is both Pareto optimal and individually rational is NP-hard. We also prove that checking whether there exists a partition which is both Pareto optimal and envy-free is ${\Sigma }_2^p$-complete. Even though an envy-free partition and a Nash stable partition are both guaranteed to exist for symmetric preferences, checking whether there exists a partition which is both envy-free and Nash stable is NP-complete.

11 pages; A preliminary version of this work was invited for presentation in the session `Cooperative Games and Combinatorial Optimization' at the 24th European Conference on Operational Research (EURO 2010) in Lisbon

References in corpus (1)

• An Anytime Algorithm for Optimal Coalition Structure Generation

Cited by in corpus (10)

• A Game-Theoretic Approach to Distributed Coalition Formation in Energy-Aware Cloud Federations (Extended Version)
• Hedonic Games with Graph-restricted Communication
• Peer Effects and Stability in Matching Markets
• Topological Distance Games
• Precise Complexity of the Core in Dichotomous and Additive Hedonic Games
• Computational Complexity of Hedonic Games on Sparse Graphs
• On Maximizing Egalitarian Value in K-coalitional Hedonic Games
• Optimal Partition of a Tree with Social Distance
• Testing Stability Properties in Graphical Hedonic Games
• Structural Stability of a Family of Group Formation Games