Abstract
Coalition Structure Generation (CSG) is a critical problem in multi-agent systems, involving the partitioning of agents into disjoint groups to maximize total system value. While exact algorithms exist, they often suffer from redundant calculations during search space exploration. This paper introduces BOSS (Bi-directional, Overlapping minimization, and Subspace Shrinking), a novel algorithm that partitions the search space into disjoint sets and employs a bi-directional search strategy. By running two complementary algorithms from opposite ends of the search space, BOSS achieves up to a 33.63% speedup over state-of-the-art methods like ODP-IP and ODSS.
Introduction
In cooperative game theory and artificial intelligence, the challenge of partitioning a set of agents into exhaustive and disjoint coalitions is known as the Coalition Structure Generation (CSG) problem. As the number of agents increases, the number of possible partitions grows exponentially, making the search for an optimal structure computationally intensive. While existing hybrid algorithms have improved efficiency, they often perform overlapping operations. The BOSS algorithm addresses these bottlenecks by ensuring minimal redundancy through a mathematically grounded division of the search space.
Methodology: Bi-directional Search and Space Division
The core innovation of BOSS lies in its management of two established search techniques: Improved Dynamic Programming (IDP) and Integer Partition (IP). The algorithm operates through four primary stages:
- Search Space Division: The entire search space is divided into $2n/3$ disjoint sets ($D_i$) based on the mathematical properties of integer partitions. This ensures that every possible coalition structure belongs to exactly one subspace.
- Bi-directional Execution: BOSS executes IDP and IP simultaneously from opposite ends of the subspace spectrum. IDP begins searching from $D_1$ (increasing order), while IP starts from the highest $D_i$ (decreasing order).
- Minimal Overlapping: Because the subspaces are disjoint, the two algorithms can work toward a central "meeting point" without duplicating effort.
- Termination: The search concludes as soon as one algorithm completes its assigned range or the two meet, guaranteeing an optimal solution with minimal wasted computation.
Experimental Evaluation
The performance of BOSS was evaluated using 27 agents across eight standard benchmark value distributions, including SVA-$\beta$ (Modified Schematic Value), Agent-Based Uniform (ABU), Agent-Based Normal (ABN), and Modified Uniform (MU). These distributions simulate various environments where coalition values follow distinct statistical patterns.
Key Results
Experimental results demonstrate that BOSS consistently outperforms state-of-the-art algorithms ODP-IP and ODSS, particularly in complex distributions. For the SVA-$\beta$ distribution, BOSS achieved a time saving of 3,392 seconds (nearly an hour) compared to the next fastest algorithm.
Statistical analysis using ANOVA confirmed that these speedups are significant for the most challenging distributions (ABU, ABN, SVA-$\beta$, and MU), with $p$-values well below the 0.05 threshold. However, on simpler distributions like Beta and Weibull, BOSS performed identically to existing methods, indicating that the overhead of bi-directional management is most beneficial when the search space is highly complex.
Discussion and Future Work
BOSS successfully exploits the natural strengths of IDP and IP by assigning them to handle smaller and larger coalition structures, respectively. While the algorithm shows significant gains for up to 27 agents, future research is needed to determine how the coordination overhead scales for systems involving hundreds or thousands of agents. Additionally, the bi-directional techniques introduced here could potentially be adapted for "anytime" algorithms, which prioritize finding high-quality solutions quickly over finding the absolute optimum.
Summary updated