A COP Model For Graph-Constrained Coalition Formation

Filippo Bistaffa, Alessandro FarinelliJAIR 2018 · DOI · OpenReview

TL;DR

This paper introduces COP-GCCF, a novel approach that frames the Graph-Constrained Coalition Formation (GCCF) problem as a Constraint Optimization Problem (COP). By leveraging a GPU-accelerated Bucket Elimination algorithm, COP-GCCF significantly outperforms existing state-of-the-art methods in both speed and memory efficiency, particularly on sparse graph structures.

What Problem Does This Paper Address?

Coalition Formation (CF) is a fundamental concept in multi-agent systems, enabling agents to collaborate to achieve common goals. A key challenge within CF is Coalition Structure Generation (CSG), which involves partitioning agents into disjoint coalitions to maximize collective value. The paper focuses on Graph-Constrained Coalition Formation (GCCF), a variant where coalition feasibility is dictated by a graph representing relationships or constraints between agents (e.g., friends must form coalitions together). Existing GCCF algorithms often struggle with scalability, requiring exponential memory or making restrictive assumptions about the characteristic function (which defines coalition values). This paper aims to address these limitations by proposing a new COP-based model for GCCF that is more efficient and less restrictive.

Methods

The core contribution is the COP-GCCF model, which reformulates GCCF as a Constraint Optimization Problem (COP). This involves:

  • COP Formulation: Representing feasible coalitions as binary variables. The problem is then to find an assignment of these variables that satisfies constraints (ensuring a valid partition) and maximizes the total value of selected coalitions.
  • Graph-Based Constraints: Crucially, the model exploits the structure of the input graph to create a hierarchy of agents (using a pseudotree) and define constraints. This hierarchy helps manage the complexity by introducing "required variables" – if a coalition is formed, it implies the formation of sub-coalitions.
  • Incomplete Tables: The constraints are represented using incomplete tables, meaning only valid assignments are stored, significantly reducing memory usage compared to traditional methods that store all possible (including infeasible) assignments.
  • GPU-Accelerated Bucket Elimination: The authors employ a GPU implementation of the Bucket Elimination (BE) algorithm (specifically, CUBE) to solve the COP. BE is a dynamic programming approach well-suited for problems with high constraint tightness, and its GPU implementation allows for massive parallelism.

Datasets

The paper evaluates COP-GCCF on:

  • Synthetic Graphs: Scale-free networks generated using the Barabási-Albert model with varying edge densities (m=1 and m=2).
  • Realistic Graphs: Subgraphs from a large crawl of the Twitter social graph.

No new benchmarks were introduced; instead, existing graph topologies were used to test the algorithms.

Key Insights and Ideas

  • Bridging GCCF and COPs: The paper establishes a novel and significant link between GCCF and COPs, opening up new avenues for research using COP solvers for coalition formation problems.
  • Exploiting Graph Structure: The key to COP-GCCF's efficiency lies in its clever use of the graph structure to define constraints, particularly through the pseudotree and the concept of "required variables." This allows for a more compact representation than methods that ignore graph topology.
  • Incomplete Tables are Crucial: The success of the approach hinges on the ability of the solver to handle incomplete constraint tables. This feature is vital for managing memory, especially as the number of agents grows.
  • GPU Parallelism is Key: The choice of a GPU-accelerated BE solver is critical for achieving the reported performance gains, highlighting the power of parallel computing for complex combinatorial problems.

Key Results

  • Performance Outperformance: COP-GCCF significantly outperforms state-of-the-art GCCF algorithms (DyCE) and a GPU implementation of a related problem (IDPG) by at least one order of magnitude in terms of runtime and memory on realistic datasets (Twitter subgraphs).
  • Speedup on Sparse Graphs: On sparse scale-free networks (m=1), COP-GCCF is up to 4 orders of magnitude faster than counterparts.
  • Memory Efficiency: COP-GCCF's memory consumption is orders of magnitude lower than DyCE and IDPG, especially on sparse graphs. For example, it's 2 orders of magnitude lower on scale-free networks with m=1 and 1 order of magnitude lower on Twitter subgraphs.
  • Density Impact: On denser graphs (scale-free networks with m=2), COP-GCCF's performance advantage diminishes, and it can even require more memory than DyCE/IDPG, demonstrating the impact of graph density on the problem's complexity.

Limitations and Future Work

  • Density Sensitivity: The paper notes that COP-GCCF's advantage is most pronounced on sparse graphs. On denser graphs, the performance gains are reduced.
  • Future Work: The authors suggest applying the COP-GCCF model to realistic scenarios like Collective Energy Purchasing and Social Ridesharing, indicating a desire to explore its practical applicability in domain-specific settings.

Summary updated

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.
BibTeX
@article{bistaffa2018cop,
  author = {Filippo Bistaffa and Alessandro Farinelli},
  title = {{A COP Model For Graph-Constrained Coalition Formation}},
  journal = {J. Artif. Intell. Res.},
  year = {2018},
  doi = {10.1613/jair.1.11205},
}
Figure