TY - GEN
T1 - Optimal partitions in additively separable hedonic games
AU - Aziz, Haris
AU - Brandt, Felix
AU - Seedig, Hans Georg
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=80055097082&partnerID=8YFLogxK
U2 - 10.5591/978-1-57735-516-8/IJCAI11-019
DO - 10.5591/978-1-57735-516-8/IJCAI11-019
M3 - Conference contribution
AN - SCOPUS:80055097082
SN - 9781577355120
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 43
EP - 48
BT - IJCAI 2011 - 22nd International Joint Conference on Artificial Intelligence
T2 - 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011
Y2 - 16 July 2011 through 22 July 2011
ER -