A COP Model for Graph-Constrained Coalition Formation (Extended Abstract)
Abstract
We focus on Graph-Constrained Coalition Formation (GCCF), a widely studied subproblem of coalition formation where the set of valid coalitions is constrained by a graph. We propose COP-GCCF, a novel approach that models GCCF as a COP. We then solve such COP with a highly-parallel GPU implementation of Bucket Elimination, which is able to exploit the high constraint tightness of COP-GCCF. Results on realistic graphs, i.e., a crawl of the Twitter social graph, show that our approach outperforms state of the art algorithms (i.e., DyCE and IDP G ) by at least one order of magnitude, both in terms of runtime and memory.
Cite
Text
Bistaffa and Farinelli. "A COP Model for Graph-Constrained Coalition Formation (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2018. doi:10.24963/IJCAI.2018/783Markdown
[Bistaffa and Farinelli. "A COP Model for Graph-Constrained Coalition Formation (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2018.](https://mlanthology.org/ijcai/2018/bistaffa2018ijcai-cop/) doi:10.24963/IJCAI.2018/783BibTeX
@inproceedings{bistaffa2018ijcai-cop,
title = {{A COP Model for Graph-Constrained Coalition Formation (Extended Abstract)}},
author = {Bistaffa, Filippo and Farinelli, Alessandro},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2018},
pages = {5553-5557},
doi = {10.24963/IJCAI.2018/783},
url = {https://mlanthology.org/ijcai/2018/bistaffa2018ijcai-cop/}
}