Error message

Deprecated function: Array and string offset access syntax with curly braces is deprecated in include_once() (line 20 of /mnt/web104/a0/07/510451407/htdocs/includes/

NP-completeness in Hedonic Games

Printer-friendly version
Working paper
Coralio Ballester
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.
Developed by Paolo Gittoi