Complexity of Hedonic Games with Dichotomous Preferences

Abstract

Hedonic games provide a model of coalition formation in which a set of agents is partitioned into coalitions and the agents have preferences over which set they belong to. Recently, Aziz et. al. (2014) have initiated the study of hedonic games with dichotomous preferences, where each agent either approves or disapproves of a given coalition. In this work, we study the computational complexity of questions related to finding optimal and stable partitions in dichotomous hedonic games under various ways of restricting and representing the collection of approved coalitions. Encouragingly, many of these problems turn out to be polynomial-time solvable. In particular, we show that an individually stable outcome always exists and can be found in polynomial time. We also provide efficient algorithms for cases in which agents approve only few coalitions, in which they only approve intervals, and in which they only approve sets of size 2 (the roommates case). These algorithms are complemented by NP-hardness results, especially for representations that are very expressive, such as in the case when agents' goals are given by propositional formulas.