Introduction
In multi-agent systems, agents often need to form groups, or coalitions, to accomplish tasks more efficiently. The Coalition Structure Generation (CSG) problem asks: How do we partition a set of agents into disjoint coalitions such that the sum of their values is maximized? This is a computationally "hard" problem (NP-complete) with a search space that grows exponentially with the number of agents.
Historically, researchers used two main approaches:
- Dynamic Programming (IDP): Predictable and fast for small sets of agents, but it isn't "anytime"---you get no answer until the very end.
- Tree-Search (IP): An anytime algorithm that uses branch-and-bound techniques. Its performance is highly sensitive to the specific values of the coalitions.
A previous hybrid, IDP-IP, tried to combine them by running IDP as a "preprocessing" step and then switching to IP. However, it required a manual tuning parameter ($m$) to decide when to switch.
As shown in Figure 4, if the wrong $m$ is chosen, the algorithm's performance can vary by orders of magnitude. Furthermore, the anytime property was lost during the IDP phase.
The IDP-IP* Algorithm
The authors propose IDP-IP*, a state-of-the-art hybrid algorithm that makes the two components work together interactively rather than sequentially. This eliminates the need for manual parameter tuning and preserves the "anytime" property.
Key Innovations
- Interactive Pruning: As IDP calculates optimal partitions for small subsets, it stores them in a table. IP uses this table to prune its search tree. If IP realizes IDP has already found a better partition for a subset of agents, it can skip that branch.
- Dynamic Search Ordering: IP is modified to prioritize subspaces that IDP would take the longest to reach, ensuring the two algorithms complement each other without redundant work.
- Parameter-Free Design: IDP-IP* automatically balances the workload based on the problem instance, removing the need for users to guess an optimal switch point.
Experimental Evaluation
The algorithm was evaluated using several synthetic coalition value distributions:
- Standard: Uniform, Normal, and NDCS (Normally Distributed Coalition Structures).
- Modified: "Modified Uniform" and "Modified Normal," which add random "shocks" to coalition values.
- Agent-based: Coalition values are derived from the individual "power" values of members, mimicking realistic scenarios.
Key Results
IDP-IP* demonstrates significant speedups and robustness across all tested distributions.
As illustrated in Figure 3, IDP-IP consistently outperforms the previous IDP-IP (even when optimally tuned) and the anytime IDP version by Service and Adams (2011). Notably, in "Modified" distributions where IDP-IP often struggled, IDP-IP maintained high efficiency. The authors successfully scaled the algorithm to 25 agents, managing a search space of over $4 \times 10^{12}$ possible structures.
Conclusion
IDP-IP* represents a major step forward in solving the CSG problem. By interleaving dynamic programming with tree search, it provides a robust, parameter-free, and anytime solution that scales significantly better than previous methods. Future work includes formalizing the worst-case complexity and integrating further anytime guarantees.
Summary updated