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.
Cite
Text
Aziz et al. "Optimal Partitions in Additively Separable Hedonic Games." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-019Markdown
[Aziz et al. "Optimal Partitions in Additively Separable Hedonic Games." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/aziz2011ijcai-optimal/) doi:10.5591/978-1-57735-516-8/IJCAI11-019BibTeX
@inproceedings{aziz2011ijcai-optimal,
title = {{Optimal Partitions in Additively Separable Hedonic Games}},
author = {Aziz, Haris and Brandt, Felix and Seedig, Hans Georg},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2011},
pages = {43-48},
doi = {10.5591/978-1-57735-516-8/IJCAI11-019},
url = {https://mlanthology.org/ijcai/2011/aziz2011ijcai-optimal/}
}