Stability Under Valuation Updates in Coalition Formation

Frank, Fabian; Novaković, Matija; Romen, Rene

doi:10.24963/ijcai.2026/380

Stability Under Valuation Updates in Coalition Formation

Fabian Frank, Matija Novaković, Rene Romen

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 3418-3426.

https://doi.org/10.24963/ijcai.2026/380

Keywords

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

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.

Fabian Frank, Matija Novaković, and Rene Romen. 2026. Stability Under Valuation Updates in Coalition Formation. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 3418–3426. https://doi.org/10.24963/ijcai.2026/380

@inproceedings{ijcai2026p380,
  title     = {Stability Under Valuation Updates in Coalition Formation},
  author    = {Frank, Fabian and Novaković, Matija and Romen, Rene},
  booktitle = {Proceedings of the Thirty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-26}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Diego Calvanese},
  pages     = {3418--3426},
  year      = {2026},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2026/380},
  url       = {https://doi.org/10.24963/ijcai.2026/380},
}

TY  - CPAPER
TI  - Stability Under Valuation Updates in Coalition Formation
AU  - Frank, Fabian
AU  - Novaković, Matija
AU  - Romen, Rene
T2  - Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2026
SP  - 3418
EP  - 3426
DO  - 10.24963/ijcai.2026/380
UR  - https://doi.org/10.24963/ijcai.2026/380
ER  -