TL;DR
This paper introduces a new way to model how groups of people form coalitions (hedonic games) by allowing agents to have nuanced preferences: they can categorize others as friends, enemies, or neutral, and rank them within those categories. This richer model allows for more realistic preference elicitation and leads to new insights into coalition stability, with a focus on computational complexity.
What Problem Does This Paper Address?
Traditional hedonic games often simplify agent preferences, either by assuming everyone is a friend or by using very basic preference structures. This can be unrealistic when modeling real-world scenarios where agents have complex relationships with each other – some they want to work with, some they want to avoid, and some they are indifferent about. The authors address the challenge of creating a more expressive yet still computationally tractable model for these games. They aim to capture these nuanced preferences and then analyze how different "stability" concepts (like whether agents would want to leave their current coalition) behave in this new framework, particularly focusing on the computational difficulty of determining these stable outcomes.
Methods
The core of the paper is the introduction of the FEN-hedonic game model. This model allows each agent to:
- Partition other agents into three groups: Friends, Enemies, and Neutrals.
- Rank friends and enemies separately: This provides a fine-grained preference within the friend and enemy categories.
- Specify thresholds: Agents can indicate which coalitions are better than being alone, worse, or indifferent.
This "weak ranking with double threshold" is then used to derive preferences over coalitions via a polarized responsive extension principle. This principle generalizes existing methods by considering the impact of adding/removing friends and enemies. The paper then analyzes various stability concepts (like Nash stability, individual rationality, core stability, popularity) within this FEN-hedonic game framework, focusing on the computational complexity of "possible" (there exists an extension where it's stable) and "necessary" (it's stable for all extensions) versions of these concepts.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Richer Preference Representation: The FEN model offers a more expressive way to capture real-world agent relationships in hedonic games, moving beyond simple "all friends" or "all enemies" scenarios.
- Bridging Expressivity and Tractability: The polarized responsive extension provides a principled way to lift player preferences to coalition preferences, striking a balance between how much agents need to specify and how complex the resulting model is.
- Nuanced Stability Analysis: By considering "possible" and "necessary" stability, the paper accounts for the inherent uncertainty arising from incomplete preference extensions, offering a more robust analysis of coalition structures.
- Complexity Landscape: The paper systematically maps out the computational complexity of various stability concepts in this new framework, revealing which problems are tractable (polynomial time) and which are computationally hard (NP-complete, coNP-complete).
Key Results
The paper provides a comprehensive analysis of stability concepts in FEN-hedonic games. Key results include:
- Polynomial-time algorithms for verifying Nash stability, individual stability, and contractually individual stability (both possible and necessary versions).
- coNP-completeness results for Pareto optimality verification (both possible and necessary) and for popularity and strict popularity verification (both possible and necessary).
- NP-completeness results for the existence of Nash stable, individual stable, and contractually individual stable coalition structures.
- coNP-hardness results for the existence of strictly popular coalition structures.
- Characterizations for various stability notions in terms of agent preferences and coalition structures.
Limitations and Future Work
The authors acknowledge that while their FEN model is more expressive, there are still open problems regarding complexity. They suggest future work could involve:
- Exploring other solution concepts and completing the complexity analysis for all entries in their summary table.
- Applying meta-results from existing literature to further understand NP-hardness.
- Introducing "partition correspondences" to identify "good" coalition structures, potentially using a central authority.
- Investigating altruistic hedonic games where players care about their friends' preferences, using the polarized responsive extension.
- Extending the model to handle more general preference structures and scenarios like fair division and multiwinner elections.
Summary updated