Introduction
In the study of multi-agent systems, hedonic games provide a robust framework for modeling how agents form coalitions based on individual preferences. Traditionally, these models assume "free movement," where agents can join any group that accepts them. However, many real-world scenarios—such as seating assignments at a dinner party or the formation of fixed-capacity project teams—impose rigid constraints on group sizes. This paper introduces a framework for hedonic games with fixed-size coalitions, addressing the "musical chairs" problem where movement is only possible if another agent vacates their spot.
Stability and Swap Dynamics
Because agents cannot simply join a full group, the standard notion of Nash stability is replaced by swap stability. An outcome is considered stable if no two agents can improve their utility by switching places. The authors focus on additively separable hedonic games (ASHGs) with symmetric preferences, where an agent's utility is the sum of their affinity scores for other members in their coalition.
They define three distinct levels of stability:
- Swap Stability under Transferable Utilities (SSTU): A swap occurs if the combined utility of the two agents increases.
- Swap Stability (SS): A swap occurs if at least one agent improves their utility and the other is not made worse off.
- Strict Swap Stability (SSS): A swap occurs only if both agents strictly improve their utility.
Key Theoretical Insights
The research yields several fundamental results regarding the existence and quality of stable states:
- Guaranteed Existence: Using potential function arguments, the authors prove that a swap-stable assignment is always guaranteed to exist for all three stability notions. In symmetric ASHGs, total social welfare acts as a potential function; since every beneficial swap increases total welfare and the number of arrangements is finite, the process must terminate in a stable state.
- Optimality and Stability: A significant finding is that the social optimum—the arrangement maximizing total happiness—is always stable under all three definitions. Consequently, the Price of Stability is 1.
- The Cost of Selfishness: While the best outcome is stable, agents may converge to sub-optimal stable states. For "simple" games (binary preferences), the Price of Anarchy (PoA)—the ratio between the optimal welfare and the worst stable welfare—is exactly $2k - 1$, where $k$ is the number of groups. However, if the social graph contains isolated nodes, the PoA can become unbounded.
Computational Complexity
While stable states always exist, finding them can be computationally demanding. The authors demonstrate that finding a stable assignment is PLS-complete, suggesting that reaching stability through local swaps may take exponential time in the worst case. Furthermore, finding the absolute social optimum is NP-hard. To address this, the paper provides an $O(k^2)$-approximation algorithm for general weighted games and tighter approximations for simple games with large group capacities.
Conclusion and Future Directions
This work establishes a rigorous foundation for hedonic games under capacity constraints. While the assumption of symmetric preferences ensures stability, the authors note that directed (asymmetric) preferences can lead to instability. Future research may explore egalitarian social welfare objectives, multi-agent rotations (swaps involving more than two agents), and the application of these constraints to fractional hedonic games, where agents prioritize average group happiness over aggregate utility.
Summary updated