Fairness and Stability in Allocation-Induced Hedonic Games

Abstract

Understanding when fair allocation mechanisms lead to stable coalition structures is fundamental for designing robust multi-agent systems. We investigate the compatibility between stable allocations in transferable utility (TU) games and the stability of coalition structures in induced hedonic games, where agents' preferences over coalitions are derived from payoffs assigned by a fixed allocation rule applied to all subgames of the TU game. We analyze FX-FE strong Nash stability (SNS) in induced hedonic games, which captures a strong form of robustness under free-exit and free-entry conditions. We show that any efficient allocation rule ensuring core membership for the grand coalition induces a hedonic game that guarantees the existence of an FX-FE strong Nash stable partition. Examining the Shapley value, we further show that when it lies outside the core, the resulting hedonic game may or may not possess FX-FE strongly Nash stable partitions, highlighting a sensitive interaction between Shapley-based fairness and coalition-level stability. Our framework bridges SHAP methodology from explainable AI with hedonic coalition theory, providing theoretical foundations for understanding when fair allocation mechanisms shape coalition-level incentives in a way that ensures strategic stability in team formation and multi-agent systems.