2025-11-23T02:22:15.133554

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

Bullinger, Dunajski, Elkind et al.
We study stability in additively separable hedonic games when coalition sizes have to respect fixed size bounds. We consider four classic notions of stability based on single-agent deviations, namely, Nash stability, individual stability, contractual Nash stability, and contractual individual stability. For each stability notion, we consider two variants: in one, the coalition left behind by a deviator must still be of a valid size, and in the other there is no such constraint. We provide a full picture of the existence of stable outcomes with respect to given size parameters. Additionally, when there are only upper bounds, we fully characterize the computational complexity of the associated existence problem. In particular, we obtain polynomial-time algorithms for contractual individual stability and contractual Nash stability, where the latter requires an upper bound of 2. We obtain further results for Nash stability and contractual individual stability, when the lower bound is at least 2.
academic

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

基本信息

  • 论文ID: 2510.12641
  • 标题: Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes
  • 作者: Martin Bullinger (University of Bristol), Adam Dunajski (University of Edinburgh), Edith Elkind (Northwestern University), Matan Gilboa (University of Oxford)
  • 分类: cs.GT (Game Theory), cs.DS (Data Structures and Algorithms)
  • 发表时间: 2025年10月14日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.12641

摘要

本文研究了在联盟规模受到固定边界约束的情况下，可加分离享乐博弈(Additively Separable Hedonic Games, ASHGs)中的稳定性问题。作者考虑了四种基于单智能体偏离的经典稳定性概念：纳什稳定性(Nash stability)、个体稳定性(individual stability)、合约纳什稳定性(contractual Nash stability)和合约个体稳定性(contractual individual stability)。对于每种稳定性概念，作者考虑了两种变体：一种要求偏离者留下的联盟仍须保持有效规模，另一种则无此约束。论文提供了关于给定规模参数下稳定结果存在性的完整图景，并在仅有上界约束时完全刻画了相关存在性问题的计算复杂性。

研究背景与动机

问题的重要性

联盟形成是多智能体系统中的核心问题，广泛应用于：

  • 学生分组项目中的小组划分
  • 部门办公室的座位分配
  • 户外活动中的小组组织
  • 会议晚宴的座位安排

这些实际场景都存在共同特征：联盟规模需要满足上下界约束，同时分割方案需要对智能体的偏离行为保持稳定。

现有研究的局限性

  1. 缺乏下界约束考虑：先前工作主要关注上界约束，对下界约束研究不足
  2. 稳定性概念不完整：缺乏对不同稳定性概念在约束条件下的系统性分析
  3. 计算复杂性未明确：在约束条件下各种稳定性概念的计算复杂性尚未完全刻画

研究动机

本文旨在填补这些研究空白，提供在联盟规模约束下享乐博弈稳定性的完整理论框架。

核心贡献

  1. 完整的存在性刻画：为所有考虑的稳定性概念提供了在给定规模参数下的存在性完整图景
  2. 计算复杂性的完整分析：在仅有上界约束(λ=1)时，完全刻画了所有稳定性概念的计算复杂性
  3. 多项式时间算法：
    • 为合约个体稳定性(CIS)提供了多项式时间算法
    • 为上界为2时的合约纳什稳定性(CNS)提供了多项式时间算法
    • 为下界至少为2时的CIS*提供了多项式时间算法
  4. NP完全性结果：证明了多种情况下稳定性判定问题的NP完全性
  5. 算法修正：修正了Aziz等人(2013)算法中的错误

方法详解

任务定义

输入：

  • 智能体集合N
  • 可加分离效用函数v = (va)a∈N，其中va: N{a} → ℝ
  • 联盟规模约束λ ≤ μ（λ为下界，μ为上界）

输出：

  • (λ,μ)-partition：满足规模约束的联盟划分
  • 稳定性判定：该划分是否满足特定稳定性概念

约束条件：

  • 每个联盟C满足λ ≤ |C| ≤ μ
  • 偏离必须是(λ,μ)-permissible或(λ,μ)-feasible

稳定性概念框架

基础定义

对于智能体a在联盟C中的效用： ua(C)=∑b∈C∖{a}va(b)u_a(C) = \sum_{b \in C\setminus\{a\}} v_a(b)

四种标准稳定性概念

  1. 纳什稳定性(NS)：无智能体能通过偏离改善自身效用
  2. 个体稳定性(IS)：纳什偏离 + 目标联盟成员同意
  3. 合约纳什稳定性(CNS)：纳什偏离 + 原联盟成员同意
  4. 合约个体稳定性(CIS)：同时满足IS和CNS条件

可行性变体

每种标准概念都有对应的可行性变体（标记为*），要求偏离后原联盟仍满足规模约束。

关键算法

Algorithm 1: CIS算法（修正版）

输入: ASHG (N,v), 参数μ
输出: (1,μ)-partition

1. 初始化: i←0, A←N
2. while A ≠ ∅:
3.   选择智能体a ∈ A
4.   计算创建新联盟的效用h
5.   for k ∈ [i]:  // 考虑加入现有联盟
6.     计算加入联盟k的效用h'
7.     if h < h': 更新最优选择
8.   根据最优选择创建/加入联盟
9.   更新可用智能体集合A

Algorithm 3: CIS*算法（非零估值）

针对下界λ≥2的情况，通过两阶段方法：

  1. 阶段I：为每个领导者形成最优的最小规模联盟
  2. 阶段II：按逆序填充剩余智能体

实验设置

理论分析框架

本文主要进行理论分析，包括：

  1. 存在性证明：构造性证明和反例
  2. 复杂性分析：归约证明和算法设计
  3. 算法正确性：形式化验证

复杂性分析方法

  • NP完全性证明：从3-SAT、X3C等经典问题归约
  • 多项式算法：构造性算法设计
  • 下界分析：通过反例证明不存在性

实验结果

存在性结果

稳定性概念对称估值一般估值简单对称估值
NS*✓存在?不确定✓存在
IS*, CNS*✓存在✗不存在✓存在
CIS*✓存在✓存在✓存在
NS, IS, CNS, CIS✗不存在✗不存在✗不存在

关键发现：

  • 对称估值保证最强可行稳定性概念(NS*)的存在
  • 即使对简单对称估值，标准稳定性概念可能不存在
  • CIS*在任何情况下都存在（当可行划分存在时）

计算复杂性结果（λ=1）

稳定性概念μ=2μ≥3
CISPP
CNSPNP-complete
NS, ISNP-completeNP-complete

具体算法复杂性：

  • CIS: O(n³)时间复杂性的多项式算法
  • CNS (μ=2): O(n²)时间复杂性的多项式算法
  • NS/IS: 通过从最小极大匹配问题归约证明NP完全性

下界λ≥2的结果

条件结果
μ≥4, λ<μNS为NP-complete
非零估值CIS*为P
非负估值CIS*为P

相关工作

享乐博弈基础

  • Drèze & Greenberg (1980): 享乐博弈概念的提出
  • Bogomolnaia & Jackson (2002): 可加分离享乐博弈的确立

稳定性概念发展

  • Sung & Dimitrov (2010): 单智能体偏离稳定性的复杂性
  • Aziz et al. (2013): CIS的多项式算法（本文发现并修正了其错误）

约束联盟研究

  • Levinger et al. (2024): 上界约束下的群体稳定性
  • Fioravantes et al. (2025): 参数化复杂性分析

结论与讨论

主要结论

  1. 存在性二分性：可行稳定性概念与标准稳定性概念在存在性上存在根本差异
  2. 复杂性阶梯：从CIS的多项式可解到NS的NP完全性，呈现清晰的复杂性层次
  3. 约束的影响：下界约束显著影响稳定性的存在性和可计算性

局限性

  1. 开放问题：λ=2, μ=3时NS的复杂性仍未确定
  2. 实际应用：理论结果与实际应用场景的桥接需要进一步研究
  3. 算法效率：某些多项式算法的常数因子可能较大

未来方向

  1. 其他博弈类型：扩展到分数享乐博弈等其他模型
  2. 近似算法：为NP困难情况设计近似算法
  3. 在线算法：考虑动态环境下的联盟形成

深度评价

优点

  1. 理论完整性：提供了约束联盟享乐博弈稳定性的系统性理论框架
  2. 技术创新：
    • 巧妙的归约构造（如X3C到CNS的归约）
    • 创新的算法设计（两阶段CIS*算法）
    • 错误修正（Aziz等人算法的修正）
  3. 结果深度：不仅给出存在性，还提供了构造性算法
  4. 写作清晰：概念定义清楚，证明结构完整

不足

  1. 实验验证缺失：纯理论工作，缺乏实际数据上的验证
  2. 应用指导有限：对实际应用场景的指导意义需要进一步挖掘
  3. 某些证明冗长：部分NP完全性证明较为复杂，可读性有待提高

影响力

  1. 学术价值：为约束联盟博弈理论提供了重要理论基础
  2. 实用价值：为实际的联盟形成问题提供了算法工具
  3. 可复现性：算法描述清晰，易于实现和验证

适用场景

  1. 教育领域：学生分组、课程安排
  2. 组织管理：团队组建、资源分配
  3. 社会选择：投票联盟、利益集团形成
  4. 计算机科学：分布式系统中的节点聚类

参考文献

  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.

总体评价：这是一篇高质量的理论计算机科学论文，在约束联盟博弈理论方面做出了重要贡献。论文的理论深度和技术创新都很突出，为该领域的后续研究奠定了坚实基础。虽然缺乏实验验证，但考虑到其理论性质，这种局限是可以理解的。该工作对博弈论、算法设计和多智能体系统等领域都具有重要的学术价值。