Optimal Partitions in Additively Separable Hedonic Games
| Autor: | Aziz, Haris, Brandt, Felix, Seedig, Hans Georg |
|---|---|
| Rok vydání: | 2010 |
| Předmět: | |
| Zdroj: | Artificial Intelligence 195, 2013 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.artint.2012.09.006 |
| Popis: | 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. Comment: 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 |
| Databáze: | arXiv |
| Externí odkaz: |
|