Stability in Random Hedonic Games

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 incentivises deviation from the proposed structure. Such a coalition formation scenario can be modelled 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 stable and contractually Nash-stable partition with high probability in the large agent limit. Our second main result is that the probability that a random game admits a Nash-stable partition tends to zero in the large agent limit. These results reveal that agents acting single-handedly are to blame for instabilities in coalition formation scenarios.

This work is a recent collaboration with Martin Bullinger.