NP-completeness in Hedonic Games

Printer-friendly version
Working paper
Coralio Ballester
Universitat Autònoma de Barcelona
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.
Developed by Paolo Gittoi