  Partitioning a large group of employees into teams can prove difficult
because unsatisfied employees may want to transfer to other teams. In this
case, the team (coalition) formation is unstable and incentivizes deviation
from the proposed structure. Such a coalition formation scenario can be modeled
in the framework of hedonic games and a significant amount of research has been
devoted to the study of stability in such games. Unfortunately, stable
coalition structures are not guaranteed to exist in general and their
practicality is further hindered by computational hardness barriers. We offer a
new perspective on this matter by studying a random model of hedonic games. For
three prominent stability concepts based on single-agent deviations, we provide
a high probability analysis of stability in the large agent limit.
  Our first main result is an efficient algorithm that outputs an individually
and contractually Nash-stable partition with high probability. Our second main
result is that the probability that a random game admits a Nash-stable
partition tends to zero. Our approach resolves the two major downsides
associated with individual stability and contractual Nash stability and reveals
agents acting single-handedly are usually to blame for instabilities.
