---
title: "Optimal Partitions in Additively Separable Hedonic Games"
authors:
  - "Haris Aziz"
  - "Felix Brandt"
  - "Hans Georg Seedig"
doi: "10.5591/978-1-57735-516-8/IJCAI11-019"
url: "https://ijcai.org/proceedings/2011/19"
pdf: "https://ijcai.org/proceedings/2011/0019.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "43-47"
track: ""
keywords:
---

# Optimal Partitions in Additively Separable Hedonic Games

Haris Aziz, Felix Brandt, Hans Georg Seedig

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 43-47. DOI: [10.5591/978-1-57735-516-8/IJCAI11-019](https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-019)

## 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 Σ2p-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.