Monte-Carlo Tree Search for Scalable Coalition Formation

Monte-Carlo Tree Search for Scalable Coalition Formation

Feng Wu, Sarvapali D. Ramchurn

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 407-413. https://doi.org/10.24963/ijcai.2020/57

We propose a novel algorithm based on Monte-Carlo tree search for the problem of coalition structure generation (CSG). Specifically, we find the optimal solution by sampling the coalition structure graph and incrementally expanding a search tree, which represents the partial space that has been searched. We prove that our algorithm is complete and converges to the optimal given sufficient number of iterations. Moreover, it is anytime and can scale to large CSG problems with many agents. Experimental results on six common CSG benchmark problems and a disaster response domain confirm the advantages of our approach comparing to the state-of-the-art methods.
Keywords:
Agent-based and Multi-agent Systems: Cooperative Games
Agent-based and Multi-agent Systems: Coordination and Cooperation