Individual Rationality in Constrained Hedonic Games: Friends, Enemies, and Neutrals
2026-08-14 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors explore how groups form when players see others as friends, enemies, or neutrals, focusing on two ways preferences can be shaped: friend-oriented and enemy-oriented. They want group divisions that make everyone happier than being alone (individually rational) and have exactly k groups within certain size limits. They find that deciding if such groupings exist is easy in some enemy-focused cases but much harder when preferences focus on friends, especially depending on symmetry of relationships and strictness of size rules. Their work fully maps out when these problems are easy or hard based on the structure of friendships and enmities.
coalition formationadditively separable preferencesfriend-oriented preferencesenemy-oriented preferencesindividually rational (IR)hedonic gamesgraph coloringsymmetrycomputational complexityparameterized complexity
Authors
Šimon Schierrreich, Ildikó Schlotter
Abstract
We study constrained coalition formation in games induced by friends, enemies, and neutrals, under the two standard refinements of additively separable preferences: friend-oriented and enemy-oriented. We ask for partitions that are individually rational (IR), while additionally requiring exactly $k$ non-empty coalitions, each satisfying a prescribed lower and upper bound on its size. Although IR alone is trivial to satisfy for any hedonic game, the size constraints make it computationally intractable to decide whether a feasible partition exists. The two models tell strikingly different stories. Under enemy-oriented preferences, the problem collapses to size-constrained graph coloring, and its complexity follows accordingly. Under friend-oriented preferences, however, the picture is far more intricate, and is governed by the enmity structure rather than the friendships. The complexity is further shaped by two factors: how strict the imposed size requirements are, and whether relationships are symmetric or asymmetric, with several cases turning out tractable in the symmetric setting but intractable once asymmetry is allowed. Charting this boundary in terms of both classical and parameterized complexity, we provide a complete understanding of which properties of the friend/enemy structure are responsible for hardness.