An Imperfect Algorithm for Coalition Structure Generation

Narayan Changder, Samir Aknine, Animesh DuttaAAAI 2019 · DOI

Abstract

Coalition Structure Generation (CSG) is a fundamental problem in multi-agent systems, involving the partitioning of agents into disjoint groups to maximize total utility. While exact solvers like ODP-IP provide optimal solutions, their $O(3^n)$ complexity makes them prohibitive for large agent sets. This paper introduces Imperfect Dynamic Programming (ImDP), a novel algorithm that reduces complexity to $O(n 2^n)$ by utilizing a partial enumeration strategy. ImDP achieves up to a 91% speedup over state-of-the-art exact solvers while maintaining solution quality consistently above 99% of the optimal value.

Introduction

In multi-agent systems, agents often need to form coalitions to perform tasks efficiently. The goal of CSG is to find a partition—a coalition structure—that maximizes the sum of the values of each coalition. The primary challenge is the search space, which grows exponentially according to Bell numbers. Current exact algorithms are limited by their $O(3^n)$ complexity. ImDP addresses this by asking whether a "good enough" solution can be found significantly faster by skipping less likely optimal partitions.

The ImDP Algorithm

ImDP is an "imperfect" dynamic programming approach that maintains a partition table ($P_t$) and a value table ($V_t$). Instead of an exhaustive search of all possible splits, it employs two specific merge functions to populate these tables.

Merge Functions

The efficiency of ImDP stems from its targeted search strategy:

  1. Merge1: This function evaluates coalitions by selecting a single agent and checking splits against the remaining subset. This captures structures where a single agent joins an existing group. Illustration of Merge1 operations where a single agent $a_s$ is merged with subsets $u_1$ or $u_2$. Source, p. 2
  2. Merge2: This function combines two disjoint coalitions, typically of sizes roughly equal to $n/2$. This allows the algorithm to find optimal structures composed of larger, balanced sub-coalitions. Illustration of Merge2 operations combining disjoint coalitions $x_i$ and $y_j$. Source, p. 2
Illustration of Merge1 operations where a single agent $a_s$ is merged with subsets $u_1$ or $u_2$.
Illustration of Merge2 operations combining disjoint coalitions $x_i$ and $y_j$.

By limiting the search to these patterns, the complexity is reduced to $O(n 2^n)$. While this means the algorithm might miss the absolute optimum if it lies outside these patterns, the statistical likelihood of such a failure is low in practical scenarios.

Experimental Evaluation

The authors evaluated ImDP against the ODP-IP benchmark using synthetic datasets with various reward distributions (e.g., Uniform, Normal, Chi-square, Geometric, Raleigh, Laplace). Tests were conducted with up to 27 agents.

Key Results

  • Computational Efficiency: For 27 agents under a uniform distribution, ImDP completed in 4.9 minutes compared to 54 minutes for ODP-IP—a 91% reduction in execution time.
  • Solution Accuracy: The failure rate (missing the absolute optimum) was remarkably low, such as 1.7% for Geometric distributions and 3.34% for Laplace.
  • Optimality Ratio: Even when the absolute optimum was missed, the solutions found were typically above 99% of the optimal value, demonstrating graceful degradation.

Discussion and Limitations

The primary trade-off in ImDP is its "imperfection." There exist contrived reward functions where the optimal split is specifically hidden from the Merge1 and Merge2 patterns. However, for most standard distributions used in CSG research, the algorithm provides near-optimal results with a fraction of the computational cost.

Future work includes using ImDP results as high-quality initial seeds for meta-heuristic algorithms and adapting these merge strategies for even larger agent populations where $2^n$ scaling becomes the next bottleneck.

Summary updated

BibTeX
@inproceedings{changder2019imperfect,
  author = {Narayan Changder and Samir Aknine and Animesh Dutta},
  title = {{An Imperfect Algorithm for Coalition Structure Generation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33019923},
}
Figure