Stability Under Valuation Updates in Coalition Formation

Fabian Frank; Matija Novaković; Rene Romen

IJCAI 20260 citations

Stability Under Valuation Updates in Coalition Formation

Fabian Frank, Matija Novaković, Rene Romen

Abstract

Coalition formation studies how to partition a set of agents into disjoint coalitions based on their preferences. In this paper, we consider the class of additively separable hedonic games and study the setting in which agents' valuations of each other evolve over time. Since rearranging coalitions can be costly, our goal is to find a stable partition close to the current one, where distance is measured by the number of agents that must change coalition. We study this problem for four stability notions based on single-agent deviations: Nash, individual, contractual Nash, and contractual individual stability. For all four, deciding whether a close stable partition exists is NP-complete, even under severe restrictions on the valuations and even when only a single valuation changes. On the positive side, we give polynomial-time algorithms for the two contractual notions under restricted symmetric valuations, and show that over long sequences of updates, these algorithms maintain stability with constant average reconfiguration cost.

Game Theory and Economic Paradigms: Cooperative gamesGame Theory and Economic Paradigms: Computational social choice

BibTeX

@inproceedings{ijcai2026_stabilityunderva,
  title = {Stability Under Valuation Updates in Coalition Formation},
  author = {Fabian Frank and Matija Novaković and Rene Romen},
  booktitle = {IJCAI 2026},
  year = {2026}
}