Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes

Basic Information

• Paper ID: 2510.12641
• Title: Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes
• Authors: Martin Bullinger (University of Bristol), Adam Dunajski (University of Edinburgh), Edith Elkind (Northwestern University), Matan Gilboa (University of Oxford)
• Classification: cs.GT (Game Theory), cs.DS (Data Structures and Algorithms)
• Publication Date: October 14, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.12641

Abstract

This paper investigates stability problems in Additively Separable Hedonic Games (ASHGs) under fixed coalition size constraints. The authors examine four classical stability concepts based on single-agent deviations: Nash stability, individual stability, contractual Nash stability, and contractual individual stability. For each stability concept, two variants are considered: one requiring that coalitions abandoned by deviating agents maintain valid sizes, and another without this constraint. The paper provides a complete characterization of the existence of stable outcomes under given size parameters and fully characterizes the computational complexity of relevant existence problems when only upper bounds are imposed.

Research Background and Motivation

Importance of the Problem

Coalition formation is a core problem in multi-agent systems with widespread applications in:

• Group division in student projects
• Seat allocation in departmental offices
• Group organization in outdoor activities
• Seating arrangements at conference dinners

These practical scenarios share a common characteristic: coalition sizes must satisfy upper and lower bound constraints, while partition schemes must remain stable against agent deviations.

Limitations of Existing Research

1. Insufficient consideration of lower bounds: Prior work primarily focused on upper bounds with limited treatment of lower bounds
2. Incomplete stability concepts: Lack of systematic analysis of different stability concepts under constraints
3. Unclear computational complexity: Computational complexity of various stability concepts under constraints remains incompletely characterized

Research Motivation

This paper aims to fill these research gaps by providing a complete theoretical framework for hedonic game stability under coalition size constraints.

Core Contributions

1. Complete existence characterization: Provides complete characterization of existence for all considered stability concepts under given size parameters
2. Complete computational complexity analysis: Fully characterizes computational complexity of all stability concepts when only upper bounds are imposed (λ=1)
3. Polynomial-time algorithms:
   • Polynomial-time algorithm for contractual individual stability (CIS)
   • Polynomial-time algorithm for contractual Nash stability (CNS) when upper bound is 2
   • Polynomial-time algorithm for CIS* when lower bound is at least 2
4. NP-completeness results: Proves NP-completeness of stability determination problems in multiple cases
5. Algorithm correction: Corrects errors in the algorithm by Aziz et al. (2013)

Methodology Details

Task Definition

Input:

• Agent set N
• Additively separable utility functions v = (va)a∈N, where va: N{a} → ℝ
• Coalition size constraints λ ≤ μ (λ as lower bound, μ as upper bound)

Output:

• (λ,μ)-partition: Coalition partition satisfying size constraints
• Stability determination: Whether the partition satisfies a specific stability concept

Constraints:

• Each coalition C satisfies λ ≤ |C| ≤ μ
• Deviations must be (λ,μ)-permissible or (λ,μ)-feasible

Stability Concepts Framework

Basic Definitions

For agent a's utility in coalition C: $u_a(C) = \sum_{b \in C\setminus\{a\}} v_a(b)$

Four Standard Stability Concepts

1. Nash Stability (NS): No agent can improve utility through deviation
2. Individual Stability (IS): Nash deviation + target coalition members consent
3. Contractual Nash Stability (CNS): Nash deviation + original coalition members consent
4. Contractual Individual Stability (CIS): Simultaneously satisfies IS and CNS conditions

Feasibility Variants

Each standard concept has a corresponding feasibility variant (marked with *), requiring that the original coalition remains within size constraints after deviation.

Key Algorithms

Algorithm 1: CIS Algorithm (Corrected Version)

Input: ASHG (N,v), parameter μ
Output: (1,μ)-partition

1. Initialize: i←0, A←N
2. while A ≠ ∅:
3.   Select agent a ∈ A
4.   Compute utility of creating new coalition h
5.   for k ∈ [i]:  // Consider joining existing coalitions
6.     Compute utility of joining coalition k as h'
7.     if h < h': Update optimal choice
8.   Create/join coalition based on optimal choice
9.   Update available agent set A

Algorithm 3: CIS* Algorithm (Non-zero Valuations)

For lower bound λ≥2, employs a two-phase approach:

1. Phase I: Form optimal minimum-size coalitions for each leader
2. Phase II: Fill remaining agents in reverse order

Experimental Setup

Theoretical Analysis Framework

The paper primarily conducts theoretical analysis including:

1. Existence proofs: Constructive proofs and counterexamples
2. Complexity analysis: Reduction proofs and algorithm design
3. Algorithm correctness: Formal verification

Complexity Analysis Methods

• NP-completeness proofs: Reductions from 3-SAT, X3C, and other classical problems
• Polynomial algorithms: Constructive algorithm design
• Lower bound analysis: Proving non-existence through counterexamples

Experimental Results

Existence Results

Key Findings:

• Symmetric valuations guarantee existence of the strongest feasible stability concept (NS*)
• Even for simple symmetric valuations, standard stability concepts may not exist
• CIS* always exists when feasible partitions exist

Computational Complexity Results (λ=1)

Specific Algorithm Complexity:

• CIS: Polynomial algorithm with O(n³) time complexity
• CNS (μ=2): Polynomial algorithm with O(n²) time complexity
• NS/IS: NP-completeness proven through reduction from minimum bottleneck matching problem

Results for Lower Bound λ≥2

Related Work

Foundations of Hedonic Games

• Drèze & Greenberg (1980): Introduction of hedonic game concepts
• Bogomolnaia & Jackson (2002): Establishment of additively separable hedonic games

Development of Stability Concepts

• Sung & Dimitrov (2010): Complexity of single-agent deviation stability
• Aziz et al. (2013): Polynomial algorithm for CIS (error discovered and corrected in this paper)

Constrained Coalition Research

• Levinger et al. (2024): Group stability under upper bound constraints
• Fioravantes et al. (2025): Parameterized complexity analysis

Conclusions and Discussion

Main Conclusions

1. Existence dichotomy: Fundamental differences between feasible and standard stability concepts in terms of existence
2. Complexity hierarchy: Clear complexity hierarchy ranging from polynomial-solvable CIS to NP-complete NS
3. Impact of constraints: Lower bound constraints significantly affect stability existence and computability

Limitations

1. Open problems: Complexity of NS when λ=2, μ=3 remains undetermined
2. Practical applications: Bridging theoretical results with practical application scenarios requires further research
3. Algorithm efficiency: Constant factors in certain polynomial algorithms may be large

Future Directions

1. Other game types: Extension to fractional hedonic games and other models
2. Approximation algorithms: Design approximation algorithms for NP-hard cases
3. Online algorithms: Consider coalition formation in dynamic environments

In-Depth Evaluation

Strengths

1. Theoretical completeness: Provides systematic theoretical framework for stability in constrained coalition hedonic games
2. Technical innovation:
   • Clever reduction constructions (e.g., X3C to CNS reduction)
   • Innovative algorithm design (two-phase CIS* algorithm)
   • Error correction (correction of Aziz et al. algorithm)
3. Result depth: Provides not only existence but also constructive algorithms
4. Clear presentation: Well-defined concepts and complete proof structure

Weaknesses

1. Lack of experimental validation: Pure theoretical work without verification on actual data
2. Limited practical guidance: Guidance for practical application scenarios requires further development
3. Lengthy proofs: Some NP-completeness proofs are complex with room for improved readability

Impact

1. Academic value: Provides important theoretical foundation for constrained coalition game theory
2. Practical value: Provides algorithmic tools for practical coalition formation problems
3. Reproducibility: Clear algorithm descriptions facilitate implementation and verification

Applicable Scenarios

1. Education: Student grouping, course scheduling
2. Organizational management: Team formation, resource allocation
3. Social choice: Voting coalitions, interest group formation
4. Computer science: Node clustering in distributed systems

References

1. Bogomolnaia, A., & Jackson, M. O. (2002). The stability of hedonic coalition structures. Games and Economic Behavior, 38(2), 201-230.
2. Aziz, H., Brandt, F., & Seedig, H. G. (2013). Computing desirable partitions in additively separable hedonic games. Artificial Intelligence, 195, 316-334.
3. Sung, S. C., & Dimitrov, D. (2010). Computational complexity in additive hedonic games. European Journal of Operational Research, 203(3), 635-639.
4. Levinger, C., Hazon, N., Simola, S., & Azaria, A. (2024). Coalition formation with bounded coalition size. In Proceedings of AAMAS 2024.

Overall Assessment: This is a high-quality theoretical computer science paper that makes important contributions to constrained coalition game theory. The theoretical depth and technical innovation are both outstanding, providing a solid foundation for subsequent research in this field. While lacking experimental validation, this limitation is understandable given its theoretical nature. This work has significant academic value for game theory, algorithm design, and multi-agent systems.