The formal study of coalition formation in multi-agent systems is typically realized using so-called hedonic games, which originate from economic theory. The main focus of this branch of research has been on the existence and the computational complexity of deciding the existence of coalition structures that satisfy various stability criteria. The actual process of forming coalitions based on individual behavior has only received increased attention very recently. In this talk, we present some of the pioneering work in this direction.

We study the convergence of simple dynamics based on single-agent deviations in hedonic games. We consider various strategies for proving convergence of the dynamics based on potential functions. In particular, we showcase methods for dealing with non-monotonic potential functions.

This is joint work with Felix Brandt, Leo Tappe, and Anaëlle Wilczynski