Hedonic Games With Friends, Enemies, and Neutrals: Resolving Open Questions and Fine-Grained Complexity

Abstract

We investigate verification and existence problems for prominent stability concepts in hedonic games with friends, enemies, and optionally with neutrals [8, 15]. We resolve several (long-standing) open questions [4, 15, 19, 22] and show that for friend-oriented preferences, under the friends and enemies model, it is coNP-complete to verify whether a given agent partition is (strictly) core stable, while under the friends, enemies, and neutrals model, it is NP-complete to determine whether an individual stable partition exists. We further look into natural restricted cases from the literature, such as when the friends and enemies relationships are symmetric, when the initial coalitions have bounded size, when the vertex degree in the friendship graph (resp. the union of friendship and enemy graph) is bounded, or when such graph is acyclic or close to being acyclic. We obtain a complete (parameterized) complexity picture regarding these cases.