Emergence of Cooperation in Multi-Agent Reinforcement Learning via Coalition Labeling and Structural Entropy

Multi-agent cooperation is essential for tasks that require collaboration to achieve optimal performance or cannot be completed by individual agents alone. These tasks often necessitate a divide-and-conquer strategy, where sub-goals are allocated to individual agents or groups. By integrating coalition formation concepts from cooperative game theory, we demonstrate the implicit learning of coalition formation and task assignments, resulting in emergent cooperative behavior. We propose a novel COaLition LABeling technique for Multi-Agent Reinforcement Learning (COLLAB-MARL) to encourage coalition formation and introduce a structural entropy measure to detect the emergence of coalitions and cooperative behavior. Compared to classical MARL methods, COLLAB-MARL is more effective, explainable, and easier to implement. Experiments on state-of-the-art cooperative MARL benchmarks show that our method’s mean return outperforms the strongest baselines by 8.4% on average. Additionally, visualization and structural entropy analysis reveal that COLLAB-MARL effectively learns meaningful cooperative behavior. The source code is available at https://github.com/SELGroup/ collab.