Optimal Partitions in Additively Separable Hedonic Games

Aziz, Haris; Brandt, Felix; Seedig, Hans Georg

doi:10.5591/978-1-57735-516-8/IJCAI11-019

Optimal Partitions in Additively Separable Hedonic Games

Haris Aziz, Felix Brandt, Hans Georg Seedig

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 43-47.

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.

Haris Aziz, Felix Brandt, and Hans Georg Seedig. 2011. Optimal Partitions in Additively Separable Hedonic Games. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 43–47. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-019

@inproceedings{ijcai2011p19,
  title     = {Optimal Partitions in Additively Separable Hedonic Games},
  author    = {Aziz, Haris and Brandt, Felix and Seedig, Hans Georg},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {43--47},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-019},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-019},
}

TY  - CPAPER
TI  - Optimal Partitions in Additively Separable Hedonic Games
AU  - Aziz, Haris
AU  - Brandt, Felix
AU  - Seedig, Hans Georg
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 43
EP  - 47
DO  - 10.5591/978-1-57735-516-8/IJCAI11-019
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-019
ER  -