Abstract
Coalition Structure Generation (CSG) is a critical challenge in multi-agent systems, focused on partitioning agents into non-overlapping groups to maximize collective utility. As the number of agents increases, the search space grows exponentially, creating a computational bottleneck that has historically limited exact solvers to approximately 27 agents. This paper presents FACS (Fast Code-based Algorithm for Coalition Structure Generation), a novel heuristic approach that utilizes a vector-based representation of the search space. By shifting from set-theoretic operations to efficient vector permutations, FACS achieves near-optimal solutions (99% quality) for up to 30 agents in under 10 milliseconds. Our evaluation shows that FACS outperforms existing state-of-the-art algorithms, such as ODP-IP and CSG-UCT, by several orders of magnitude in terms of speed while maintaining high solution quality.
Introduction
In the field of multi-agent systems, the ability of autonomous agents to cooperate effectively is paramount. Coalition Structure Generation (CSG) involves finding the optimal way to partition a set of $n$ agents into disjoint coalitions such that the sum of the values of these coalitions is maximized. This problem is central to applications ranging from distributed sensor networks to collaborative task execution in robotics.
The primary difficulty in solving CSG lies in the sheer size of the search space, which is defined by the Bell number $B_n$. For $n=27$, the number of possible coalition structures exceeds $10^{20}$, making exhaustive search impossible. While exact algorithms like ODP-IP provide guarantees of optimality, they struggle to scale beyond this "wall" of 27 agents. Heuristic methods offer a path forward for larger systems, but many existing approaches either sacrifice too much solution quality or fail to provide the low-latency performance required for real-time applications.
Methodology: Code-based Representation
The core innovation of FACS is its departure from traditional set-based representations. Instead of treating coalition structures as sets of sets, FACS represents them as vectors of indices.
Vector Coding
For a set of $n$ agents, a coalition structure is encoded as a vector $V = [c_1, c_2, ..., c_n]$, where $c_i$ is the index of the coalition to which agent $i$ belongs. This representation allows the algorithm to utilize fast numerical operations and systematic permutations to explore the search space.
Two-Phase Search Strategy
FACS operates in two distinct phases to navigate the search space efficiently:
- Phase 1 (Initialization): The algorithm leverages the Integer Partition (IP) graph to identify promising coalition sizes. For example, for 4 agents, the partitions include [4], [1,3], [2,2], [1,1,2], and [1,1,1,1]. By focusing on these partitions, FACS generates high-quality "seed" vectors.
- Phase 2 (Permutation): Starting from the seeds, the algorithm systematically permutes the codes within the vectors. By swapping agent assignments, it explores neighboring structures in the search space far more rapidly than set-based methods.
Experimental Evaluation
To assess the performance of FACS, the authors conducted experiments using three standard value distributions:
- Normal Distribution: Coalition values follow a bell curve, simulating scenarios where most groupings have average utility.
- Uniform Distribution: Values are spread evenly, testing the algorithm's robustness across diverse utility landscapes.
- Agent-based Normal: Values depend on the specific identities of the agents in a coalition, reflecting real-world scenarios where individual synergies matter.
Results and Discussion
The empirical results highlight the dramatic efficiency gains provided by the code-based approach.
Computational Speedup
As shown in the performance plots, FACS consistently requires significantly less time than both ODP-IP and CSG-UCT. In a test case with 25 agents under a Normal distribution, FACS was found to be 75.9 times faster than ODP-IP. While ODP-IP's execution time grows steeply as it approaches the 27-agent limit, FACS maintains a much flatter growth curve.
Scalability and Quality
FACS successfully scales to 30 agents, a threshold where exact algorithms become impractical. More importantly, it achieves this scale without a significant loss in quality. For 30 agents, FACS reaches 99% solution quality within approximately 10 milliseconds.
When compared to CSG-UCT, a popular Monte-Carlo Tree Search heuristic, FACS demonstrates superior performance in both speed and the ability to reach high-quality solutions quickly. The comparative data illustrates that for any given time budget, FACS consistently finds higher-quality coalition structures than CSG-UCT.
Conclusion
FACS represents a significant step forward in solving the Coalition Structure Generation problem for large-scale multi-agent systems. By rethinking the fundamental representation of the search space, the authors have developed an algorithm that is not only orders of magnitude faster than current state-of-the-art methods but also capable of handling larger agent populations with high precision. Future work could involve extending FACS to dynamic environments where coalition values change over time, or developing theoretical bounds to complement the strong empirical evidence presented here.
Summary updated