  Coalition formation is concerned with the question of how to partition a set
of agents into disjoint coalitions according to their preferences. Deviating
from most of the previous work, we consider an online variant of the problem,
where agents arrive in sequence and whenever an agent arrives, they have to be
assigned to a coalition immediately and irrevocably. The scarce existing
literature on online coalition formation has focused on the objective of
maximizing social welfare, a demanding requirement, even in the offline
setting. Instead, we seek to achieve stable coalition structures in an online
setting, and focus on stability concepts based on deviations by single agents.
We present a comprehensive picture in additively separable hedonic games,
leading to dichotomies, where positive results are obtained by deterministic
algorithms and negative results even hold for randomized algorithms.
