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) 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 0 (n)-time. (C) 2012 Elsevier B.V. All rights reserved.
nash stable partitions additive hedonic games graph algorithms computational complexity