Stability Under Valuation Updates in Coalition Formation
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911465310519296 |
|---|---|
| author | Frank, Fabian Novaković, Matija Romen, René |
| author_facet | Frank, Fabian Novaković, Matija Romen, René |
| contents | Coalition formation studies how to partition a set of agents into disjoint coalitions under consideration of their preferences. We study the classical objective of stability in a variant of additively separable hedonic games where agents can change their valuations. Our objective is to find a stable partition after each change. To minimize the reconfiguration cost, we search for nearby stable coalition structures. Our focus is on stability concepts based on single-agent deviations. We present a detailed picture of the complexity of finding nearby stable coalition structures in additively separable hedonic games, for both symmetric and non-symmetric valuations. Our results show that the problem is NP-complete for Nash stability, individual stability, contractual Nash stability, and contractual individual stability. We complement these results by presenting polynomial-time algorithms for contractual Nash stability and contractual individual stability under restricted symmetric valuations. Finally, we show that these algorithms guarantee a bounded average distance over long sequences of updates. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_21041 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Stability Under Valuation Updates in Coalition Formation Frank, Fabian Novaković, Matija Romen, René Computer Science and Game Theory Multiagent Systems Coalition formation studies how to partition a set of agents into disjoint coalitions under consideration of their preferences. We study the classical objective of stability in a variant of additively separable hedonic games where agents can change their valuations. Our objective is to find a stable partition after each change. To minimize the reconfiguration cost, we search for nearby stable coalition structures. Our focus is on stability concepts based on single-agent deviations. We present a detailed picture of the complexity of finding nearby stable coalition structures in additively separable hedonic games, for both symmetric and non-symmetric valuations. Our results show that the problem is NP-complete for Nash stability, individual stability, contractual Nash stability, and contractual individual stability. We complement these results by presenting polynomial-time algorithms for contractual Nash stability and contractual individual stability under restricted symmetric valuations. Finally, we show that these algorithms guarantee a bounded average distance over long sequences of updates. |
| title | Stability Under Valuation Updates in Coalition Formation |
| topic | Computer Science and Game Theory Multiagent Systems |
| url | https://arxiv.org/abs/2602.21041 |