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

技术摘要：面向聚类联邦学习的稳定且预算可行的联盟形成机制

问题陈述
联邦学习（FL）系统经常受到统计异质性的影响，即单一的“大联盟”（所有参与者组成的联盟）会导致次优的模型。虽然聚类联邦学习通过将兼容的参与者分组来解决统计层面的问题，但经济层面的问题仍未得到充分探索。具体而言，目前缺乏能够同时确保以下三点的框架：

1. 稳定性（Stability）： 参与者没有动力单方面离开其分配的联盟去加入另一个联盟（纳什稳定性），或者不被目标联盟拒绝（个体稳定性）。
2. 预算可行性（Budget Feasibility）： 协调实体能够为补偿参与者所需的转移支付提供资金，而不产生赤字。
3. 效率（Efficiency）： 生成的稳定划分能够逼近全局社会福利最优值。

现有方法通常将稳定性与预算约束分开处理，或者假设剩余价值具有超加性（superadditivity），但在异质性、非凸性的联邦学习场景中，这一假设并不成立。

方法论
本文将该问题建模为一个具有可转移剩余价值的享誉型联盟形成博弈（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$），则称该分配规则是弱预算可行的。
• 享誉型偏好（Hedonic Preferences）： 偏好通过一种将剩余价值转化为效用的分配规则来诱导。本文重点研究对称成对剩余分配（symmetric pairwise surplus allocations），其中参与者在联盟中的效用是与其成员 $j \in S$ 的所有成对价值 $v_{ij}$ 之和。
• 博弈论分析：
  • 作者证明了对称成对分配会诱导出一种精确势能博弈（exact potential game）。其势函数是联盟内成对价值的总和。
  • 这种结构保证了**纳什稳定划分（Nash-stable partition）**的存在性，并确保任何严格的更好响应（better-response）移动序列都会在有限步内终止。
  • 个体稳定性（Individual Stability）（即目标成员必须同意新成员加入）也被进行了分析，结果表明如果成对价值为非负，则纳什稳定性蕴含个体稳定性。
• 福利与效率：
  • 社会福利被分解为参与者效用（与势函数相关）和协调者保留的松弛量（slack）。
  • 本文确立了精确预算平衡（零保留松弛量）仅在剩余价值恰好可由成对关系表示时，才会产生福利最优的纳什稳定划分。
  • 在仅考虑预算可行性的情况下，若剩余价值无法精确表示，福利损失可能是无界的。然而，如果保留的松弛量相对于最优值是有界的，则可以推导出乘法效率保证（稳定性价格，Price of Stability）。
  • 全局势能最大化被证明等价于加权最大一致性相关聚类（weighted maximum-agreement correlation clustering）。本文提出了一个流程：先进行近似聚类，然后应用严格的更好响应稳定化过程，以达到稳定划分并保持近似保证。
• 验证： 本文提供了一个多项式时间或acles（oracle）验证方法，用于在保留松弛量为子模（submodular）时验证预算可行性。

核心贡献

1. 建模： 引入了一种联盟特定的联邦学习模型，该模型可以处理通信不成功的轮次而不会导致未定义的聚合，并且不假设超加性。
2. 经济分离： 明确区分了学习收益、成本、转移支付和协调者保留的剩余，并推导了预算可行性和个体理性性的条件。
3. 稳定性保证： 证明了对称成对分配会创建精确势能博弈，从而保证了纳什稳定划分和个体稳定划分的存在性以及有限收敛性。
4. 效率界限： 表征了协调者保留的松弛量与福利效率之间的关系。本文证明了精确平衡仅在特定类别的剩余价值上产生最优稳定性，而有界的相对松弛量则提供了紧致的乘法效率界限。
5. 计算复杂度： 将全局势能最大化与相关聚类（NP-hard）联系起来，并推导了“近似加稳定化”流程的端到端福利保证。
6. 验证： 表明如果保留的松弛量是子模的，则指数级的预算约束可以在多项式时间或acles下完成验证。
7. 实证验证： 在 $n=4$ 个参与者的 CIFAR-10 数据集上进行了预注册研究。

实验结果
该研究在五个具有异质分布的 CIFAR-10 数据种子集上评估了该机制：

• 福利最优性： 在“良性”校准下，去中心化机制在所有五个种子集上都达到了认证的估计表福利最优值。其实测稳定性价格（Price of Stability）恰好为 1。
• 稳定性对比基准： 相比之下，“等额剩余分配”基准在五个种子集中的三个中未能产生纳什稳定结果（纳什稳定集为空，且动态过程出现循环）。
• 收敛性： 从各种初始化开始，去中心化的更好响应过程收敛迅速（平均 1.53 次移动）。
• 敏感性： 在“精简”（成本敏感）校准下，稳定性成本增加（稳定性价格高达 1.29），且最优划分对估计误差变得敏感，这突显了预算紧凑性与稳定性之间的权衡。
• 估计： 成对验证增益（PVG）估计器提供的成对符号比梯度对齐（gradient alignment）更可靠，后者容易出现假阳性。

意义与主张
本文声称将学习价值、货币转移、稳定性与经济效率联系起来，且并未将局部均衡、全局最优性与计算可处理性混为一谈。

• 理论层面： 它纠正了初步工作的局限性，即正确地将纳什均衡解释为局部势能最优，并且没有假设超加性。它确立了稳定性与效率是两个通过协调者保留的松弛量相联系的独立概念。
• 实践层面： 所提出的机制为异质联邦学习参与者的组织提供了一种可证明稳定且预算可行的方案。实证结果表明，虽然简单的剩余分配规则可能会导致无法稳定，但所提出的成对势能方法保证了收敛到一个可以与福利最优值重合的稳定状态。
• 局限性： 作者指出，目前的模型假设协调者已知或能估计成本与收益（属于激励分配而非真实机制设计）。由于需要进行精确枚举和认证，实证验证受限于 $n=4$ 个参与者，且结果针对实验特定的估计值表。

研究结论认为，虽然精确预算平衡通常不能保证福利最优，但所提出的框架为聚类联邦学习中稳定且预算可行的联盟形成提供了坚实的理论基础和实用的机制。