Szczegóły publikacji
Opis bibliograficzny
Individual rationality in constrained hedonic games: additively separable and fractional preferences / Foivos Fioravantes, Harmender Gahlawat, Nikolaos Melissinos, Šimon SCHIERREICH // W: AAMAS'2026 [Dokument elektroniczny] : proceedings of the 25th international conference on Autonomous Agents and Multiagent Systems : Paphos, Cyprus, May 25–29, 2026. — Wersja do Windows. — Dane tekstowe. — [USA] : International Foundation for Autonomous Agents and Multiagent Systems, cop. 2026. — e-ISBN: 979-8-4007-2317-9. — S. 2848–2857. — Wymagania systemowe: Adobe Reader. — Bibliogr. s. 2856–2857, Abstr. — Publikacja dostępna online od: 2026-05-24. — Š. Schierreich - dod. afiliacja: Czech Technical University in Prague, Czech Republic
Autorzy (4)
- Fioravantes Foivos
- Gahlawat Harmender
- Melissinos Nikolaos
- AGHSchierreich Šimon
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 168863 |
|---|---|
| Data dodania do BaDAP | 2026-08-28 |
| Tekst źródłowy | URL |
| DOI | 10.65109/ICRJ7770 |
| Rok publikacji | 2026 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Creative Commons | |
| Konferencja | International Joint Conference on Autonomous Agents and Multiagent Systems 2026 |
Abstract
Hedonic games are an archetypal problem in coalition formation, where a set of selfish agents want to partition themselves into stable coalitions. In this work, we focus on two natural constraints on the possible outcomes. First, we require that exactly k coalitions are created. Then, loosely following the model of Bilò et al. (AAAI 2022), we assume that each of the k coalitions is additionally associated with a lower and upper bound on its size. The notion of stability that we study is that of individual rationality (IR), which requires that no agent strictly prefers to be alone compared to being in his or her coalition. Although IR is trivially satisfiable even in the most general models of hedonic games, the complexity picture of deciding whether an IR allocation exists, considering the above constraints, is unexpectedly rich. We reveal that tractable fragments of this computational problem require surprisingly nontrivial arguments, even if we restrict ourselves to additively separable and fractional hedonic games. Our tractability results, achieved by exploiting the structure of the underlying preference graph, are also complemented by their intractability counterparts, painting a fairly complete picture of the tractability landscape of this problem.
