  In hedonic games, players form coalitions based on individual preferences
over the group of players they could belong to. Several concepts to describe
the stability of coalition structures in a game have been proposed and analysed
in the literature. However, prior research focuses on algorithms with time
complexity that is at least linear in the input size. In the light of very
large games that arise from, e.g., social networks and advertising, we initiate
the study of sublinear time property testing algorithms for existence and
verification problems under several notions of coalition stability in a model
of hedonic games represented by graphs with bounded degree. In graph property
testing, one shall decide whether a given input has a property (e.g., a game
admits a stable coalition structure) or is far from it, i.e., one has to modify
at least an $\epsilon$-fraction of the input (e.g., the game's preferences) to
make it have the property. In particular, we consider verification of
perfection, individual rationality, Nash stability, (contractual) individual
stability, and core stability. While there is always a Nash-stable coalition
structure (which also implies individually stable coalitions), we show that the
existence of a perfect coalition structure is not tautological but can be
tested. All our testers have one-sided error and time complexity that is
independent of the input size.
