Split-Merge Dynamics for Shapley-Fair Coalition Formation

Researchers Quanyan Zhu and Zhengye Han have published a novel paper, 'Split-Merge Dynamics for Shapley-Fair Coalition Formation,' introducing a control-theoretic framework that models how groups of agents dynamically form teams. The core innovation is a mechanism where two distinct economic forces—individual fairness and collective efficiency—drive the system. The framework uses specific triggers: a coalition splits when a member's Shapley value becomes negative (indicating they are responsible for inefficiency), and coalitions merge only when doing so creates a strict surplus, a condition known as superadditivity. This creates a self-correcting system that continuously rebalances fairness and performance.

The authors provide rigorous mathematical proof that this dynamic process converges in finite time to a stable state they term a Shapley-Fair and Merge-Stable (SFMS) partition. They achieve this by constructing a vector Lyapunov function, a tool from control theory, to track the system's aggregate fairness deficits and total surplus, applying a discrete-time LaSalle invariance principle. This convergence guarantee is a significant theoretical advance over static equilibrium models. The paper includes a numerical case study on a 10-player game, demonstrating the algorithm's practical ability to resolve fairness tensions and reach optimal, stable configurations autonomously.

This work moves beyond traditional static game theory to provide a foundational model for endogenous, real-time coalition formation. It has direct applications for designing multi-agent AI systems where autonomous entities (like robots, software agents, or data contributors in federated learning) must collaborate. The framework ensures that as these systems evolve, teams are not only efficient but also fair to individual participants, preventing exploitation and promoting stable, long-term cooperation in complex, dynamic environments.