CoalFormer: Learning Emergent Coalition Structures via Differentiable Prototype Clustering for Multi-Agent Coordination

Effective multi-agent coordination often requires forming coalitions, subgroups that cooperate internally while acting independently from others. However, existing multi-agent reinforcement learning (MARL) methods lack mechanisms to discover and exploit such structures explicitly. We propose CoalFormer, a value decomposition framework that learns coalition structures via differentiable prototype clustering. Unlike prior methods requiring combinatorial optimization or fixed groupings, CoalFormer jointly learns coalition prototypes, soft agent assignments, and coalition-aware value factorization through end-to-end gradient descent. We prove CoalFormer satisfies the Individual-Global-Max (IGM) principle and converges under two-phase regularization that prevents coalition collapse. Experiments on heterogeneous multi-agent tasks show CoalFormer achieves superior performance over standard value decomposition baselines while discovering interpretable role-based coalitions without supervision. Ablations confirm prototype separation regularization is critical, and analysis reveals coalition formation provides the largest gains when task heterogeneity exceeds baseline coordination capacity.