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

• URL: http://arxiv.org/abs/2607.26788v1
• Date: Wed, 29 Jul 2026 11:29:45 GMT
• Title: Stable and Budget-Feasible Coalition Formation for Clustered Federated Learning: A Hedonic Potential-Game Approach
• Abstract summary: Clustered learning benefits from organizing heterogeneous participants into coalitions that train coalition-specific models.<n>We develop a transferable-surplus model separating learning benefit, system cost, participant cost, and monetary transfers.
• Score: 0.23689955632456086
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Clustered federated learning benefits from organizing heterogeneous participants into coalitions that train coalition-specific models, but such clustering is sustainable only if participants prefer their assigned coalition and the required transfers are affordable. We develop a transferable-surplus model separating learning benefit, system cost, participant cost, and monetary transfers; an allocation rule converts coalition surplus into hedonic preferences, and weak budget feasibility guarantees nonnegative retained coordinator surplus. For symmetric pairwise allocations the induced game is an exact potential game: a Nash-stable partition exists, every strict better-response process converges, and with destination consent accepted better responses reach an individually stable partition. We characterize feasibility of bounded pair incentives and verify the exponentially many budget constraints in polynomial oracle time when retained slack is submodular. Decomposing welfare into participant potential and retained slack yields additive and multiplicative price-of-stability guarantees, the latter asymptotically tight; exact balance gives welfare-optimal stability only on the pairwise-representable class, and budget feasibility alone permits unbounded welfare loss. Global potential maximization equals weighted maximum-agreement correlation clustering, and approximation followed by stabilization satisfies an end-to-end welfare bound governed by retained slack and negative-edge mass, attained by an explicit construction. In a preregistered five-seed CIFAR-10 study the mechanism reaches the certified estimated-table welfare optimum on every primary instance, equal-surplus sharing has no Nash-stable outcome on three, and pairwise validation gain gives far more reliable pair signs than gradient alignment.

Related papers

• Online Fair Division with Budget Constraints [20.176419497210585]
  We study an online variant of discrete fair division under generalized assignment budget constraints.<n>We first show that, without additional structure, no deterministic online algorithm can guarantee any fixed approximation to feasible envy-freeness.<n>We then identify bounded density spread as a structural condition that restores meaningful guarantees.
  arXiv  Detail & Related papers  (2026-07-25T17:53:10Z)
• TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning [52.67756371231985]
  Reinforcement learning with verifiable rewards (RLVR) is a promising approach for enhancing reasoning and agentic behavior in large language models.<n>We introduce Tree Rollout Allocation for Contrastive Exploration (TRACE), a unified rollout allocation framework.<n>Technically, TRACE allocates rollout budget to both prompt roots and intermediate prefixes that are most likely to yield mixed terminal rewards.
  arXiv  Detail & Related papers  (2026-06-09T17:16:03Z)
• Phi-Actor-Critic: Steering General-Sum Games to Pareto-Efficient Correlated Equilibria [3.061219970798378]
  Real-world multi-agent systems are often modeled as general-sum games where individual incentives conflict with collective welfare.<n>Standard deep multi-agent reinforcement learning (MARL) methods struggle with this problem.<n>We propose $$-Actor-Critic ($$-AC), a framework that leverages swap regret minimization to steer learning toward high-welfare correlated equilibria.
  arXiv  Detail & Related papers  (2026-06-09T16:40:26Z)
• Multimodal Learning on Low-Quality Data with Conformal Predictive Self-Calibration [72.0672328514289]
  Multimodal learning often grapples with the challenge of low-quality data.<n>We propose a unified framework, termed Conformal Predictive Self-Calibration.<n>Our framework consistently outperforms existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2026-05-05T14:48:52Z)
• Computing Equilibrium beyond Unilateral Deviation [27.786964046329455]
  We study an alternative solution concept that minimizes coalitional deviation incentives, rather than requiring them to vanish.<n> Specifically, we focus on minimizing the average gain of a deviating coalition, and extend the framework to weighted-average and maximum-within-coalition gains.<n>For the average-gain and maximum-gain objectives, we prove a lower bound on the complexity of computing such an equilibrium and present an algorithm that matches this bound.
  arXiv  Detail & Related papers  (2026-04-30T17:59:07Z)
• Fairness Aware Reward Optimization [78.85867531002346]
  We introduce Fairness Aware Reward Optimization (Faro), an in-processing framework that trains reward models under demographic parity, equalized odds, or counterfactual fairness constraints.<n>We provide the first theoretical analysis of reward-level fairness in LLM alignment.<n>Faro significantly reduces bias and harmful generations while maintaining or improving model quality.
  arXiv  Detail & Related papers  (2026-02-08T03:35:49Z)
• Toward a Sustainable Federated Learning Ecosystem: A Practical Least Core Mechanism for Payoff Allocation [71.86087908416255]
  We introduce a payoff allocation framework based on the least core (LC) concept.<n>Unlike traditional methods, the LC prioritizes the cohesion of the federation by minimizing the maximum dissatisfaction.<n>Case studies in federated intrusion detection demonstrate that our mechanism correctly identifies pivotal contributors and strategic alliances.
  arXiv  Detail & Related papers  (2026-02-03T11:10:50Z)
• Outcome-Grounded Advantage Reshaping for Fine-Grained Credit Assignment in Mathematical Reasoning [60.00161035836637]
  Group Relative Policy Optimization has emerged as a promising critic-free reinforcement learning paradigm for reasoning tasks.<n>We introduce Outcome-grounded Advantage Reshaping (OAR), a fine-grained credit assignment mechanism that redistributes advantages based on how much each token influences the model's final answer.<n>OAR-G achieves comparable gains with negligible computational overhead, both significantly outperforming a strong GRPO baseline.
  arXiv  Detail & Related papers  (2026-01-12T10:48:02Z)
• On Sybil Proofness in Competitive Combinatorial Exchanges [0.0]
  We study Sybil manipulation in BRACE, a competitive equilibrium mechanism for exchanges.<n>We show that the feasibility of BRACE fails in the event of an unbounded population of Sybils.
  arXiv  Detail & Related papers  (2025-12-11T01:53:04Z)
• Integrating upstream and downstream reciprocity stabilizes cooperator-defector coexistence in N-player giving games [1.1381558444077822]
  We show how pay-it-forward chains and reputation systems can jointly maintain social including cooperation despite cognitive limitations and group size challenges.<n>This framework demonstrates how pay-it-forward chains and reputation systems can jointly maintain social including cooperation despite cognitive limitations and group size challenges.
  arXiv  Detail & Related papers  (2025-09-05T01:49:26Z)
• Monotonic Improvement Guarantees under Non-stationarity for Decentralized PPO [66.5384483339413]
  We present a new monotonic improvement guarantee for optimizing decentralized policies in cooperative Multi-Agent Reinforcement Learning (MARL) We show that a trust region constraint can be effectively enforced in a principled way by bounding independent ratios based on the number of agents in training.
  arXiv  Detail & Related papers  (2022-01-31T20:39:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.