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.
Cite
Text
Wu and Ramchurn. "Monte-Carlo Tree Search for Scalable Coalition Formation." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/57Markdown
[Wu and Ramchurn. "Monte-Carlo Tree Search for Scalable Coalition Formation." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/wu2020ijcai-monte/) doi:10.24963/IJCAI.2020/57BibTeX
@inproceedings{wu2020ijcai-monte,
title = {{Monte-Carlo Tree Search for Scalable Coalition Formation}},
author = {Wu, Feng and Ramchurn, Sarvapali D.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2020},
pages = {407-413},
doi = {10.24963/IJCAI.2020/57},
url = {https://mlanthology.org/ijcai/2020/wu2020ijcai-monte/}
}