Monte-Carlo Tree Search for Scalable Coalition Formation

Feng Wu; Sarvapali D. Ramchurn

IJCAI 2020poster0 citations

Monte-Carlo Tree Search for Scalable Coalition Formation

Abstract

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.

Agent-based and Multi-agent Systems: Cooperative GamesAgent-based and Multi-agent Systems: Coordination and Cooperation

BibTeX

@inproceedings{ijcai2020p57,
  title     = {Monte-Carlo Tree Search for Scalable Coalition Formation},
  author    = {Wu, Feng and Ramchurn, Sarvapali D.},
  booktitle = {Proceedings of the Twenty-Ninth International Joint Conference on
               Artificial Intelligence, {IJCAI-20}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Christian Bessiere},
  pages     = {407--413},
  year      = {2020},
  month     = {7},
  note      = {Main track},
  doi       = {10.24963/ijcai.2020/57},
  url       = {https://doi.org/10.24963/ijcai.2020/57},
}