Stable and Budget-Feasible Coalition Formation for Clustered Federated Learning: A Hedonic Potential-Game Approach

技術要約：クラスタリング型連合学習における安定かつ予算制約を満たす提携形成

問題提起
連合学習（FL）システムは、単一の「大連合（grand coalition）」がすべての参加者からなる場合にサブオプティマルなモデルしか得られないという、統計的異質性の問題に直面することが多い。クラスタリング型FLは、互換性のある参加者をグループ化することで統計的な側面に対処するが、経済的な側面については未だ十分に探索されていない。具体的には、以下の事項を同時に保証するフレームワークが欠如している。

1. 安定性（Stability）： 参加者が、割り当てられた提携から別の提携へ一方的に離脱したり（ナッシュ安定性）、あるいは移動先の提 사실 提携から拒絶されたりすることのない状態（個別安定性）。
2. 予算実現可能性（Budget Feasibility）： コーディネーター（調整主体）が、参加者への補償に必要な移転費用を、赤字を出すことなく賄えること。
3. 効率性（Efficiency）： 得られる安定な分割が、グローバルな社会的厚生（social welfare）の最適値に近似すること。

既存のアプローチは、安定性と予算制約を別々に扱ったり、余剰の超加法性（superadditivity）を仮定したりすることが多いが、これは不均一で非凸なFLの設定においては成立しない。

手法
本論文では、この問題を**移転可能な余剰を伴うヘドニック提携形成ゲーム（hedonic coalition-formation game）**としてモデル化する。

• システムモデル： 参加者 $N$ は提携へと分割される。各提携 $S$ は、重み付きのローカル目的関数を用いて、提盟固有のモデル $\theta_S$ を学習する。本モデルは、セーフ・アグリゲーション（安全な集計）ルールを用いることで、通信失敗（更新の脱落）に対処し、更新が届かない場合はモデルを変更しないように設計されている。
• 経済モデル：
  • 余剰（Surplus）： 総移転可能余剰 $W(S)$ は、期待学習利益 $B(S)$ からコーディネーターのコスト $C_0(S)$ および参加者のコスト $d_i(S)$ を差し引いたものと定義される。
  • 移転（Transfers）： コーディネーターは参加者に対して移転額 $t_i(S)$ を支払う。参加者の効用は $U_i(S) = t_i(S) - d_i(S)$ である。
  • 予算実現可能性： 配分ルールが「弱予算実現可能」であるとは、形成されたすべての提携において、コーディネーターが非負の余剰（$R_0(S) \ge 0$）を保持できることを指す。
• ヘドニック選好： 選好は、余剰を効用へと変換する配分ルールによって誘導される。本論文では、対称的なペアワイズ余剰配分に焦点を当てる。ここでは、ある参加者の提携内での効用は、その提携内の他の全メンバー $j \in S$ とのペアワイズ値 $v_{ij}$ の総和となる。
• ゲーム理論的分析：
  • 著者らは、対称的なペアワイズ配分が**厳密なポテンシャルゲーム（exact potential game）**を誘導することを証明している。ポテンシャル関数は、提携内のペアワイズ値の総和である。
  • この構造により、ナッシュ安定な分割の存在が保証され、厳密なベストレスポンス（より良い応答）の連鎖が有限ステップで終了することが保証される。
  • 個別安定性（流入希望者が受け入れられるためには、移動先のメンバーの同意が必要である状態）についても分析されており、ペアワイズ値が非負であれば、ナッシュ安定性は個別安定性を意味することが示されている。
• 厚生と効率性：
  • 社会的厚生は、参加者の効用（ポテンシャル関数に関連）と、コーディネーターが保持するスラック（余裕分）に分解される。
  • 本論文は、厳密な予算均衡（exact budget balance）（保持されるスラックがゼロの状態）が、余剰が正確にペアワイズ表現可能である場合にのみ、厚生最適となるナッシュ安定な分割をもたらすことを確立している。
  • 正確な表現可能性がない場合、予算実現可能性のみでは厚生の損失が無制限になる可能性がある。しかし、保持されるスラックが最適値に対して限定されている場合、乗法的効率性（Price of Stability）の保証が導出される。
  • グローバルなポテンシャル最大化は、**重み付き最大一致相関クラスタリング（weighted maximum-agreement correlation clustering）**と同等であることが示されている。本論文では、近似を行い、その後に厳密なベストレスポンスによる安定化を適用することで、近似保証を維持しながら安定な分割に到達するパイプラインを提案している。
• 検証： 保持されるスラックが劣モジュラ（submodular）である場合、指数関数的に多い予算制約を多項式時間のオーラクル検証で検証できることを示している。

主な貢献

1. モデリング： 未定義の集計が発生しないように通信失敗を扱う、提携固有のFLモデルを導入し、超加法性を仮定しないモデルを提示した。
2. 経済的分離： 学習利益、コスト、移転、およびコーディネーターが保持する余剰を明示的に分離し、予算実現可能性と個別合理性の条件を導出した。
3. 安定性の保証： 対称的なペアワイズ配分が厳密なポテンシャルゲームを生成することを証明し、ナッシュ安定および個別安定な分割の存在と有限回での収束を保証した。
4. 効率性の境界： コーディネーターが保持するスラックと厚生効率の関係を特徴付けた。厳密な予算均衡は特定のクラスの余剰においてのみ最適安定性をもたらす一方で、相対的なスラックが限定されている場合には、タイトな乗法的効率性の境界が得られることを証明した。
5. 計算複雑性： グローバルなポテンシャル最大化を相関クラスタリング（NP困難）に関連付け、近似と安定化のパイプラインにおけるエンドツーエンドの厚生保証を導出した。
6. 検証： 保持されるスラックが劣モジュラである場合、指数関数的な数の予算制約を多項式時間のオーラクル時間で検証できることを示した。
7. 実証的検証： $n=4$ の参加者を対象としたCIFAR-10に関する事前登録済み研究を実施した。

実験結果
本研究では、不均一な分布を持つCIFAR-10の5つのシードを用いてメカニズムを評価した。

• 厚生の最適性： 「ベニグン（良心的）」なキャリブレーションにおいて、分散型メカニズムは、5つのシードすべてにおいて認定された推定テーブルに基づく厚生最適値に到達した。経験的なPrice of Stabilityは、正確に1であった。
• 安定性とベースラインの比較： 対照的に、「等価余剰分配（equal-surplus sharing）」ベースラインでは、5つのシードのうち3つでナッシュ安定な結果を得ることに失敗した（ナッシュ安定集合が空となり、ダイナミクスが循環した）。
• 収束性： 分散型のベストレスポンス・プロセスは、様々な初期化から迅速に収束した（平均1.53ステップ）。
• 感度分析： 「リーン（低コスト）」なキャリブレーションでは、安定化コストが増大し（Price of Stabilityが最大1.29）、最適な分割が推定誤差に対して敏感になった。これは、予算のタイトさと安定性の間のトレードオフを浮き彫りにしている。
• 推定： ペアワイズ検証利得（PVG）エスティメータは、勾配アライメントよりも信頼性の高いペアの符号を提供した。勾配アライメントは偽陽性が生じやすい傾向があった。

意義と主張
本論文は、局所平衡、グローバル最適性、および計算可能性を混同することなく、学習価値、金銭的移転、安定性、および経済的効率性を結びつけるものである。

• 理論面： ナッシュ平衡を局所的なポテンシャル最適として正しく解釈し、超加法性を仮定しないことで、先行研究の限界を修正した。また、安定性と効率性は、コーディネーターが保持するスラックによって結びつけられた別個の概念であることを確立した。
• 実践面： 提案されたメカニズムは、不均一なFL参加者を組織するための、証明可能なほど安定かつ予算実現可能な方法を提供する。実験結果は、単純な余剰分割ルールは安定化に失敗する場合がある一方で、提案されたペアワイズ・ポテンシャル・アプローチは、厚生最適値と一致し得る安定な状態への収束を保証することを示している。
• 限界： 著者らは、現在のモデルがコーディネーターがコストと利益を既知または推定していることを前提としている（インセンティブ割り当てであり、真実告知的なメカニメントデザインではない）ことを指摘している。また、厳密な列挙と認定を可能にするため、実証検証は $n=4$ の参加者に限定されており、結果は実験で使用された推定値テーブルに依存している。

結論として、厳密な予算均衡は一般に厚生の最適性を保証しないものの、提案されたフレームワークは、クラスタリング型連合学習における安定かつ予算実現可能な提携形成のための、強固な理論的基礎と実用的なメカニズムを提供するものである。