Finding Nash Stable Coalitions under Membership Rights in Boolean Hedonic Games

Boolean hedonic games are a class of cooperative games involving multiple agents in which agents aim to form coalitions based on individual agents’ preferences. In this work, we provide complexity results and exact algorithms for the task of forming Nash stable coalitions under different membership rights in the dichotomous setting where agents specify preferences for which coalitions they are happy/unhappy to join. The membership rights specify veto rights for coalitions, allowing a coalition to forbid an individual agent from moving (exiting the current coalition or entering another coalition) even if the agent themself would become more happy to move. We establish that various problem variants and their refinements in this setting are often situated on the second level of the polynomial hierarchy, complete for Σp2. Building on the complexity results, we develop Boolean satisfiability (SAT) based counterexample-guided abstraction refinement algorithms for the Σp2 problem variants and empirically evaluate a first-of-kind implementation of the approaches.