Separable Hedonic Games and Contractually Stabilities

We are concerned with the problem of constructing stable partitions for hedonic games with respect from contractually stability concepts, including contractually individual (CI), contractually core (CC), contractually strict core (CSC). In general, every instance of hedonic games has at least one stable partition when one of the contractually stability concepts is under consideration. For additive instances, it is known that a CI stable partition can be constructed in quadratic time in term of the number of players. In this paper, we consider a wider domain, namely separable instances. A instance of hedonic games is separable when any player classifies any other players as friends, enemies or others and the classification characterize her or his preference. However, it is not clear whether such a stable partition can be constructed efficiently with the characteristic of separable instance. We propose two quadratic time algorithms which respectively construct a CI stable partition and a CC stable partition for every separable instance. Moreover, we show that CSC stable partition can be obtained by one of the proposed algorithms when a subdomain of separable instance is under consideration.