Causes of Stability in Dynamic Coalition Formation

We study the formation of stable outcomes via simple dynamics in cardinal hedonic games, where the valuations of agents change over time depending on the history of the coalition formation process. Specifically, we analyze situations where members of a coalition decrease their valuation for a leaving agent ( resentment ) or increase their valuation for a joining agent ( appreciation ). We show a series of convergence results for dynamics for resentful or appreciative agents that do not hold for classic dynamics. In particular, resentment turns out to be a strong stability-driving force. We complement our theoretical analysis with simulations that shed some light on the average running time of the dynamics and on the structure of the produced outcomes. From an algorithmic perspective, we obtain general hardness results for determining the fastest convergence time, results that also carry over to classic dynamics under static valuation functions. Finally, we explore a related model for preference updates where resentment is expressed by the deviator. We find a more nuanced picture but still a broad possibility of convergence.