A COP Model For Graph-Constrained Coalition Formation

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...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of artificial intelligence research 2018-01, Vol.62, p.133-153
Main Authors: Bistaffa, Filippo, Farinelli, Alessandro
Format: Article
Language:English
Subjects:
Algorithms
Artificial intelligence
Constraints
Tightness
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1076-9757
1076-9757
1943-5037
DOI:10.1613/jair.1.11205