Stability in FEN-Hedonic Games for Single-Player Deviations

Hedonic games model how players form coalitions based on their preferences about the coalitions they can join. Lang et al. [17] introduced FEN-hedonic games where each player partitions the other players into friends, enemies, and neutral players and ranks her friends and enemies. They then use bipolar responsive extensions to derive preferences over coalitions, and since such preferences can be incomplete, they consider possible and necessary stability for various stability notions and study the related verification and existence problems in terms of computational complexity. However, in their complexity analysis they left a number of cases open. We settle several of these open problems for stability concepts based on single-player deviations: We show that possible verification can be solved in polynomial time for Nash stability, individual stability, and contractually individual stability. Yet, necessary existence is an NP-complete problem for individual stability while possible existence is easy for contractually individual stability.