On non-trivial Nash stable partitions in additive hedonic games with symmetric 0/1-utilities

We consider the problem of computing non-trivial Nash equilibria in additive hedonic games with symmetric 0/1-utilities. Such a game can be represented by an undirected unweighted graph G(V,E)G(V,E) where a non-trivial Nash equilibrium corresponds to a partition of V into at least two sets such that each node has at least as many neighbours in its own set compared to any other set in the partition. We show that computing such an equilibrium is NP-complete. On the other hand, we show that such an equilibrium is computable in polynomial time if (1) G is triangle free, (2) G contains no 4-cycles sharing and edge, and (3) G is not a star. If G   is not a star with girth at least 5 we show how to compute a non-trivial equilibrium in O(n)O(n)-time.

► We study the computational complexity of additive hedonic games with symmetric 0/1 utilities.
► Sufficient conditions for the existence of non-trivial Nash stable partitions computable in polynomial time are presented.
► Computing non-trivial Nash stable partitions is shown to be NP-hard in such games.