Monte-Carlo Tree Search for Graph Coalition Structure Generation

The techniques used in tree search have been proved to be effective in solving coalition structure generation (CSG). Inspired by this, we propose an algorithm to solve the problem of CSG on graphs, where the goal is to divide the graph into connected subgraphs and find the optimal partition. Specifically, we develop a new search algorithm for the problem of graph coalition structure generation (GCSG), which draws on the monte-carlo tree search (MCTS) to sample and expand the GCSG search space generated by edge contraction and 2-color graph to obtain the optimal solution. The algorithm is complete and anytime. The experimental results are compared with the latest methods, and show that this method is better than other. The proposed algorithm can be applied to the study of large-scale agent GCSG problems.