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

制約付き連立規模を有する加法分離享楽ゲームにおける単一偏離安定性

基本情報

論文ID: 2510.12641
タイトル: Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes
著者: Martin Bullinger (ブリストル大学)、Adam Dunajski (エディンバラ大学)、Edith Elkind (ノースウェスタン大学)、Matan Gilboa (オックスフォード大学)
分類: cs.GT (ゲーム理論)、cs.DS (データ構造とアルゴリズム)
発表日: 2025年10月14日 (arXiv プレプリント)
論文リンク: https://arxiv.org/abs/2510.12641

要旨

本論文は、連立規模が固定された境界によって制約されている場合の、加法分離享楽ゲーム(Additively Separable Hedonic Games, ASHGs)における安定性問題を研究している。著者らは、単一エージェント偏離に基づく4つの古典的安定性概念を検討している：ナッシュ安定性(Nash stability)、個別安定性(individual stability)、契約ナッシュ安定性(contractual Nash stability)、および契約個別安定性(contractual individual stability)。各安定性概念について、著者らは2つの変種を考察している：1つは偏離者が残す連立が有効な規模を保つことを要求し、もう1つはこの制約を持たない。本論文は、与えられた規模パラメータの下での安定結果の存在性に関する完全な図景を提供し、上界制約のみがある場合に関連する存在性問題の計算複雑性を完全に特徴付けている。

研究背景と動機

問題の重要性

連立形成は多エージェントシステムにおける中核的な問題であり、以下の広範な応用がある：

学生グループプロジェクトにおけるグループ分け
部門オフィスの座席配置
屋外活動におけるグループ編成
会議ディナーの座席配置

これらの実際のシナリオはすべて共通の特性を持つ：連立規模は上下限制約を満たす必要があり、同時に分割スキームはエージェントの偏離行動に対して安定している必要がある。

既存研究の限界

下限制約の考慮不足：先行研究は主に上限制約に焦点を当てており、下限制約の研究が不十分である
安定性概念の不完全性：制約条件下での異なる安定性概念の体系的分析が欠けている
計算複雑性の不明確性：制約条件下での各種安定性概念の計算複雑性が完全には特徴付けられていない

研究の動機

本論文は、これらの研究ギャップを埋めることを目的とし、連立規模制約下での享楽ゲーム安定性の完全な理論的枠組みを提供する。

核心的貢献

完全な存在性の特徴付け：すべての検討された安定性概念について、与えられた規模パラメータの下での存在性の完全な図景を提供
計算複雑性の完全分析：上限制約のみがある場合(λ=1)、すべての安定性概念の計算複雑性を完全に特徴付け
多項式時間アルゴリズム：
- 契約個別安定性(CIS)のための多項式時間アルゴリズム
- 上限が2の場合の契約ナッシュ安定性(CNS)のための多項式時間アルゴリズム
- 下限が少なくとも2の場合のCIS*のための多項式時間アルゴリズム
NP完全性結果：複数の場合における安定性判定問題のNP完全性を証明
アルゴリズムの修正：Azizら(2013)のアルゴリズムの誤りを発見し修正

方法論の詳細

タスク定義

入力：

エージェント集合N
加法分離効用関数v = (va)a∈N、ここでva: N{a} → ℝ
連立規模制約λ ≤ μ(λは下限、μは上限)

出力：

(λ,μ)-分割：規模制約を満たす連立分割
安定性判定：その分割が特定の安定性概念を満たすかどうか

制約条件：

各連立Cは λ ≤ |C| ≤ μ を満たす
偏離は(λ,μ)-許可可能または(λ,μ)-実行可能である必要がある

安定性概念の枠組み

基本定義

連立Cにおけるエージェントaの効用： $u_a(C) = \sum_{b \in C\setminus\{a\}} v_a(b)$

4つの標準安定性概念

ナッシュ安定性(NS)：エージェントが偏離によって自身の効用を改善できない
個別安定性(IS)：ナッシュ偏離 + 目標連立メンバーの同意
契約ナッシュ安定性(CNS)：ナッシュ偏離 + 元の連立メンバーの同意
契約個別安定性(CIS)：IS と CNS の両方の条件を満たす

実行可能性変種

各標準概念には対応する実行可能性変種(記号*で表記)があり、偏離後の元の連立が規模制約を満たすことを要求する。

主要アルゴリズム

アルゴリズム1: CISアルゴリズム(修正版)

入力: ASHG (N,v)、パラメータμ
出力: (1,μ)-分割

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を更新

アルゴリズム3: CIS*アルゴリズム(非ゼロ評価)

下限λ≥2の場合、2段階方法を通じて：

段階I：各リーダーのための最適な最小規模連立を形成
段階II：逆順で残りのエージェントを充填

実験設定

理論分析枠組み

本論文は主に理論分析を実施し、以下を含む：

存在性証明：構成的証明と反例
複雑性分析：帰約証明とアルゴリズム設計
アルゴリズムの正確性：形式的検証

複雑性分析方法

NP完全性証明：3-SAT、X3Cなどの古典的問題からの帰約
多項式アルゴリズム：構成的アルゴリズム設計
下限分析：反例による非存在性の証明

実験結果

存在性結果

安定性概念	対称評価	一般評価	単純対称評価
NS*	✓存在	?不確定	✓存在
IS, CNS	✓存在	✗不存在	✓存在
CIS*	✓存在	✓存在	✓存在
NS, IS, CNS, CIS	✗不存在	✗不存在	✗不存在

主要な発見：

対称評価は最強の実行可能安定性概念(NS*)の存在を保証する
単純対称評価でさえ、標準安定性概念は存在しない可能性がある
CIS*はあらゆる状況で存在する(実行可能な分割が存在する場合)

計算複雑性結果(λ=1)

安定性概念	μ=2	μ≥3
CIS	P	P
CNS	P	NP-完全
NS, IS	NP-完全	NP-完全

具体的なアルゴリズム複雑性：

CIS: O(n³)時間複雑性の多項式アルゴリズム
CNS (μ=2): O(n²)時間複雑性の多項式アルゴリズム
NS/IS: 最小最大マッチング問題からの帰約によるNP完全性の証明

下限λ≥2の結果

条件	結果
μ≥4, λ<μ	NSはNP-完全
非ゼロ評価	CIS*はP
非負評価	CIS*はP

結論と考察

主要な結論

存在性の二分性：実行可能安定性概念と標準安定性概念は存在性において根本的な違いがある
複雑性の階層：CISの多項式可解性からNSのNP完全性まで、明確な複雑性の階層を示す
制約の影響：下限制約は安定性の存在性と計算可能性に大きな影響を与える

限界

未解決問題：λ=2, μ=3の場合のNSの複雑性は依然として未確定
実用的応用：理論結果と実際の応用シナリオとの橋渡けにはさらなる研究が必要
アルゴリズム効率：いくつかの多項式アルゴリズムの定数因子は大きい可能性がある

今後の方向性

他のゲームタイプ：分数享楽ゲームなど他のモデルへの拡張
近似アルゴリズム：NP困難な場合のための近似アルゴリズムの設計
オンラインアルゴリズム：動的環境での連立形成の検討

深い評価

利点

理論的完全性：制約付き連立享楽ゲーム安定性の体系的理論枠組みを提供
技術的革新：
- 巧妙な帰約構成(X3CからCNSへの帰約など)
- 革新的なアルゴリズム設計(2段階CIS*アルゴリズム)
- 誤り修正(Azizらのアルゴリズムの修正)
結果の深さ：存在性だけでなく、構成的アルゴリズムも提供
記述の明確性：概念定義が明確で、証明構造が完全

不足

実験検証の欠如：純粋な理論的研究であり、実際のデータでの検証が欠けている
応用指導の限定：実際の応用シナリオへの指導意義をさらに掘り下げる必要がある
証明の冗長性：いくつかのNP完全性証明は複雑で、可読性の改善が必要

影響力

学術的価値：制約付き連立ゲーム理論に重要な理論的基礎を提供
実用的価値：実際の連立形成問題にアルゴリズムツールを提供
再現可能性：アルゴリズム記述が明確で、実装と検証が容易

適用シナリオ

教育分野：学生グループ分け、コース編成
組織管理：チーム編成、リソース配分
社会選択：投票連立、利益集団形成
コンピュータサイエンス：分散システムのノードクラスタリング

参考文献

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

総合評価：これは理論計算機科学における高品質な論文であり、制約付き連立ゲーム理論の分野で重要な貢献をしている。論文の理論的深さと技術的革新は顕著であり、この分野の後続研究のための堅固な基礎を確立している。実験検証は欠けているが、その理論的性質を考慮すると、この限界は理解できるものである。本研究はゲーム理論、アルゴリズム設計、および多エージェントシステムなどの分野に対して重要な学術的価値を持つ。