NP-completeness in Hedonic Games

This work is an attempt to show a small part of the complexity prob- lems encountered in the design of algorithms for characterizing some of the stable sets in hedonic games. Departing from the PARTITION problem, we show that these sets (the core, the Nash stable set and the individu- ally stable set) have corresponding NP-complete decision problems and, hence, only exponential (slow) algorithms are known for solving them.