Approximate Coalition Structure Generation

Travis C. Service, Julie A. AdamsAAAI 2010 · DOI

Abstract

Finding the optimal way to group agents into coalitions is a computationally intensive problem, traditionally requiring $O(3^n)$ time. This paper introduces a novel approximation algorithm for Coalition Structure Generation (CSG) that delivers high-quality solutions significantly faster than previous methods. It is the first to provide a constant-factor guarantee ($1/8$) within the theoretical minimum time complexity of $O(2^n)$. Empirical evaluations show the algorithm often reaches near-optimal or 100% optimal solutions in a fraction of the time required by standard dynamic programming.

Introduction

In multi-agent systems, Coalition Structure Generation (CSG) is the task of partitioning agents into disjoint groups to maximize total social welfare. This problem is central to cooperative game theory, specifically Characteristic Function Games (CFGs). However, the state-space explosion—where the number of possible partitions grows exponentially with the number of agents—makes finding the optimal structure a major bottleneck.

While "anytime" algorithms can provide quick estimates, providing a guaranteed quality bound (e.g., a solution at least 50% as good as the optimal) previously required either massive computation or bounds that degraded as the number of agents increased. This research bridges that gap by establishing algorithms with strong, constant-factor guarantees and significantly lower worst-case runtimes.

Methods

The authors' approach is based on extracting high-quality approximate solutions from partially completed dynamic programming (DP) tables. The technique involves four key steps:

  1. Transformation: The original utility function is transformed into a "superadditive" version, where merging coalitions never decreases total value.
  2. Partial DP: Instead of a full $O(3^n)$ search, a restricted DP (Algorithm 1) is run, considering only coalitions up to a specific size threshold.
  3. Extraction: Specialized search algorithms (Algorithms 2 and 3) identify the best one or two coalitions from the partial data.
  4. Theoretical Bound: The authors prove that in sufficiently superadditive games, the optimal solution consists of only a small, constant number of coalitions. This allows the algorithm to ignore the vast majority of the search space while maintaining mathematical guarantees.

Key Results

The algorithm was evaluated against synthetic distributions (Normal and Modified Uniform) commonly used in CSG research. The results demonstrate that the algorithm's actual performance far exceeds its theoretical worst-case guarantees.

Empirical performance and runtime comparison across different approximation ratios and distributions.

As shown in the table above, the "2/3" version of the algorithm achieved 100% optimality in Normal distribution tests and 99.5% in Modified Uniform tests. Notably, while standard optimal DP took over 10 hours for 25 agents, the 2/3 approximation finished in approximately 30 minutes. The algorithm also outperformed the previous state-of-the-art (Service and Adams' Algorithm) in both speed and solution quality at comparable ratios.

Complexity Breakthroughs

  • 2/3 approximation: Achieved in $O(\sqrt{n}2.83^n)$ time.
  • 1/2 approximation: Achieved in $O(\sqrt{n}2.59^n)$ time.
  • 1/8 approximation: Achieved in $O(2^n)$ time, hitting the theoretical floor for any algorithm providing a quality guarantee.

Conclusion

This work provides a significant advancement in CSG by offering the first constant-factor guarantee at the $O(2^n)$ complexity level. By leveraging superadditivity and partial DP, the authors have created a tool that is both theoretically robust and practically efficient. Future research will focus on reducing the computational overhead of the extraction phase to further enhance the algorithm's utility in real-time "anytime" applications.

Summary updated

BibTeX
@inproceedings{service2010approximate,
  author = {Travis C. Service and Julie A. Adams},
  title = {{Approximate Coalition Structure Generation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7636},
}
Figure