Title | A COP Model for Graph-Constrained Coalition Formation (Extended Abstract) |
Publication Type | Conference Paper |
Year of Publication | 2018 |
Authors | Bistaffa F, Farinelli A |
Conference Name | International Joint Conference on Artificial Intelligence (IJCAI-ECAI 2018) |
Publisher | AAAI Press |
Pagination | 5553-5557 |
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. |
URL | https://www.ijcai.org/proceedings/2018/783 |
DOI | 10.24963/ijcai.2018/783 |