Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918160542728192 |
|---|---|
| author | Bullinger, Martin Dunajski, Adam Elkind, Edith Gilboa, Matan |
| author_facet | Bullinger, Martin Dunajski, Adam Elkind, Edith Gilboa, Matan |
| contents | We study stability in additively separable hedonic games when coalition sizes have to respect fixed size bounds. We consider four classic notions of stability based on single-agent deviations, namely, Nash stability, individual stability, contractual Nash stability, and contractual individual stability. For each stability notion, we consider two variants: in one, the coalition left behind by a deviator must still be of a valid size, and in the other there is no such constraint. We provide a full picture of the existence of stable outcomes with respect to given size parameters. Additionally, when there are only upper bounds, we fully characterize the computational complexity of the associated existence problem. In particular, we obtain polynomial-time algorithms for contractual individual stability and contractual Nash stability, where the latter requires an upper bound of 2. We obtain further results for Nash stability and contractual individual stability, when the lower bound is at least 2. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_12641 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes Bullinger, Martin Dunajski, Adam Elkind, Edith Gilboa, Matan Computer Science and Game Theory Data Structures and Algorithms We study stability in additively separable hedonic games when coalition sizes have to respect fixed size bounds. We consider four classic notions of stability based on single-agent deviations, namely, Nash stability, individual stability, contractual Nash stability, and contractual individual stability. For each stability notion, we consider two variants: in one, the coalition left behind by a deviator must still be of a valid size, and in the other there is no such constraint. We provide a full picture of the existence of stable outcomes with respect to given size parameters. Additionally, when there are only upper bounds, we fully characterize the computational complexity of the associated existence problem. In particular, we obtain polynomial-time algorithms for contractual individual stability and contractual Nash stability, where the latter requires an upper bound of 2. We obtain further results for Nash stability and contractual individual stability, when the lower bound is at least 2. |
| title | Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.12641 |