NP-completeness in Hedonic Games

In this paper, we show that there are natural limitations in attaining stability in cooperative environments. These limitations are related to the fact that the time required to obtain a stable partition of the players can grow exponentially, even under very simple assumptions on the preferences over partners. These difficulties arise even when players assess potential coalitions based solely on their size. For this purpose, we demonstrate that the core, the Nash stable set and the individually stable set have corresponding NP-complete decision problems for a variety of situations and, hence, that only exponential-time (slow) algorithms are known for solving them.