A COP Model for Graph-Constrained Coalition Formation
Abstract

 
 
 We consider Graph-Constrained Coalition Formation (GCCF), a widely studied subproblem of coalition formation in which the set of valid coalitions is restricted by a graph. We propose COP-GCCF, a novel approach that models GCCF as a COP, and we solve such COP with a highly-parallel approach based on Bucket Elimination executed on the GPU, which is able to exploit the high constraint tightness of COP-GCCF. Results show that our approach outperforms state of the art algorithms (i.e., DyCE and IDPG) by at least one order of magnitude on realistic graphs, i.e., a crawl of the Twitter social graph, both in terms of runtime and memory.
 
 
Cite
Text
Bistaffa and Farinelli. "A COP Model for Graph-Constrained Coalition Formation." Journal of Artificial Intelligence Research, 2018. doi:10.1613/JAIR.1.11205Markdown
[Bistaffa and Farinelli. "A COP Model for Graph-Constrained Coalition Formation." Journal of Artificial Intelligence Research, 2018.](https://mlanthology.org/jair/2018/bistaffa2018jair-cop/) doi:10.1613/JAIR.1.11205BibTeX
@article{bistaffa2018jair-cop,
title = {{A COP Model for Graph-Constrained Coalition Formation}},
author = {Bistaffa, Filippo and Farinelli, Alessandro},
journal = {Journal of Artificial Intelligence Research},
year = {2018},
pages = {133-153},
doi = {10.1613/JAIR.1.11205},
volume = {62},
url = {https://mlanthology.org/jair/2018/bistaffa2018jair-cop/}
}