A significant amount of research on coalition formation in the framework of hedonic games is devoted to a variety of stability concepts.
A frequent concern is that stable coalition structures are not guaranteed to exist, and a long stream of literature proves computational hardness results for stability in hedonic games.
However, many of these hardness constructions rely on complex No-instances, which seem just to be corner cases.
We perform an average-case analysis and investigate stability in random games.
Our main result is that the probability that an individually stable partition exists tends to~$1$ if the number of agents tends to infinity for random additively separable hedonic games.
Our proof relies on probabilistic combinatorics and gives rise to an efficient algorithm computing individually stable partitions in random games.
This is joint work with Sonja Kraiczy.