Split-Merge Dynamics for Shapley-Fair Coalition Formation
This addresses coalition formation for agents in dynamic environments, offering a novel dynamic approach to an often static problem.
The paper tackles the problem of dynamic coalition formation by proposing a split-and-merge framework that balances individual fairness and collective efficiency, proving convergence to Shapley-Fair and Merge-Stable partitions in finite time with numerical validation on a 10-player game.
Coalition formation is often modeled as a static equilibrium problem, neglecting the dynamic processes governing how agents self-organize. This paper proposes a dynamic split-and-merge framework that balances two conflicting economic forces: individual fairness and collective efficiency. We introduce a control-theoretic mechanism where topological operations are driven by distinct signals: splits are triggered by fairness violations (specifically, negative Shapley values representing "agent-responsible inefficiency"), while merges are driven by strict surplus improvements (superadditivity). We prove that these dynamics converge in finite time to a specific class of steady states termed Shapley-Fair and Merge-Stable (SFMS) partitions. Convergence is established via a vector Lyapunov function tracking aggregate fairness deficits and system surplus, leveraging a discrete-time LaSalle invariance principle. Numerical case studies on a 10-player game demonstrate the algorithm's ability to resolve fairness tensions and reach stable configurations, providing a rigorous foundation for endogenous coalition formation in dynamic environments.