BRIDGE: Bi-level Reinforcement Learning for Dynamic Group Structure in Coalition Formation Games

Coalition Formation Games investigate how a group of autonomous agents voluntarily organize into subgroups (i.e., coalitions) to achieve common goals or maximize collective utility. This field has been a subject of long-standing research within game theory and related disciplines. The core challenge in these games lies in efficiently exploring the exponentially large space of possible coalition structures to identify the optimal partition. While existing approaches to solve coalition formation games either provide exact solutions with limited scalability or approximate solutions without quality guarantees, we propose a novel scalable and sample-efficient approximation method based on deep reinforcement learning. Specifically, we model the coalition formation game as a finite Markov Decision Process (MDP) and utilize deep neural networks to approximate the optimal value functions within both the full and abstracted coalition structure spaces, thereby indirectly deriving optimal coalition structures. Furthermore, our method can be leveraged for bi-level optimization problems where coalition values are determined by the policies of individual agents at a lower decision-making level. This way, our approach can facilitate dynamic, adaptive adjustments to coalition value assessments as they evolve over time. Empirical results demonstrate our algorithm's effectiveness in approximating optimal coalition structures in both normal-form and mixed-motive Markov games.