Monte-Carlo Tree Search for Scalable Coalition Formation

1 Introduction

Coalition formation is an important research topic in multiagent systems where a group of agents come together to form coalitions in the performance of a specific task [Shehory and Kraus, 1998] or or provisioning of a service such as social ride-sharing [Bistaffa et al., 2017]. One of the key challenges that arise in this formation process is that of Coalition Structure Generation (CSG), which involves partitioning the set of agents into exhaustive and disjoint coalitions, called a coalition structure, so as to maximise the social welfare. Unfortunately, finding the optimal coalition structure is difficult and has been proved to be NP-complete [Sandholm et al., 1999].

To date, a number of approaches have been proposed to solve CSG problems either optimally or approximately. Given that the solution space is exponential with the number of agents, optimal methods [Yeh, 1986; Rahwan et al., 2009] are usually not scalable and can only handle problems with small number of agents (e.g., <40 [Rahwan et al., 2015]). This limits its applicability to real-world problems requiring many agents. On the other hand, approximate techniques [Di Mauro et al., 2010; Farinelli et al., 2013] can return a solution quickly but usually provide no guarantees on solution quality. This makes them unsatisfactory for some serious applications (e.g., disaster response). To amend this, approaches [Service and Adams, 2011; Farinelli et al., 2017] were proposed to offer bounds for the solution quality. However, they require the utility to have certain special structures that may not be realistic for some applications.

Against this background, we propose CSG-UCT - a scalable and anytime approach for coalition formation in multiagent systems. Notably, it is scalable and can solve large CSG problems with hundreds of agents, which is computationally intractable for existing optimal methods. Furthermore, it is anytime and can return the current best solution if time is limited, or converge to the optimal solution if time is sufficient. Specifically, we borrow ideas from the research on Monte-Carlo Tree Search (MCTS), which has been successful in solving large games (e.g., AlphaGo [Silver et al., 2016]), to find the best solution in the large coalition structure graph [Sandholm et al., 1999]. In more detail, we develop a variation of the UCT algorithm [Kocsis and Szepesv´ari, 2006] for CSG, which selects the most promising moves towards the optima using the UCB1 heuristic [Auer et al., 2002], and expands the search tree based on random sampling of the solution space. To the best of our knowledge, this is the first work to solve CSG problems using the MCTS techniques.

In this paper, we advance the state-of-the-art with the following contributions: 1) In Section 3, we propose a novel method to search the coalition structure graph using the MCTS framework. 2) In Section 4, we prove the proposed algorithm is complete and anytime, and discuss its connections with other methods and some implementation tricks. 3) In Section 5, we empirically evaluate the proposed approach on six common benchmark problems and a disaster response domain, and confirm that it indeed converges to the optimal solution given sufficient number of iterations and outperforms the leading approximate methods for large problems. All together, we contribute with the first MCTS-based method for CSG, which is promising to improve the applicability of coalition formation techniques in real-world applications.

2 Background

2.1 Coalition Structure Generation

Given a set of n agents denoted by A = {a1, a2, · · · , an}, a coalition C is defined as a non-empty subset of A, i.e., C ̸= ∅ and C ⊆ A. For any coalition C, the characteristic function v(C) ∈ ℜ specifies a value that represents a cost or profit for that coalition. A coalition structure CS = {C1, C2, · · · , Ck} is a collection of k coalitions, such that ⋃i∈1..k Ci = A and Ci ∩Cj = ∅ for any i, j ∈ 1..k and i ̸= j, i.e., each agent is selected at least in and only in one coalition. The value of a coalition structure CS is the sum of the coalition values in the structure, i.e., v(CS) = ∑C∈CS v(C). For example, given a set of four agents A = {a1, a2, a3, a4}, C = {a2, a3} is a coalition of A and a possible coalition structure over A is CS = {{a1}, {a2, a3}, {a4}}, with the value computed as: v(CS) = v({a1}) + v({a2, a3}) + v({a4}).

Coalition Structure Generation (CSG) is the problem of finding a coalition structure CS∗ over A whose value is maximal, i.e., CS∗ = argmaxCS∈ΠA v(CS) where ΠA denotes the set of all possible coalition structures over A. Here, we assume that v(C) ≥ 0 for any C ⊆ A. Generally, the CSG problem implies searching ΠA in order to find one whose value is maximal. Several CSG approaches are based on the observation that the set ΠA has some structure, which can be exploited to speed up the search process. A commonly used representation for ΠA is the coalition structure graph [Sandholm et al., 1999], i.e., a undirected graph, where:

• A node represents a coalition structure and is categorized into levels, ΠA1 ,ΠA2 , · · · ,ΠAn , where level ΠAi contains the nodes that represent all coalition structures with exactly i coalitions.
• An edge connects two coalition structures if and only if: they belong to two consecutive levels ΠAi and ΠAi-1 and the coalition structure in ΠAi can be obtained from the one in ΠAi-1 by splitting one coalition into two.

2.2 Monte-Carlo Tree Search

Monte-Carlo tree search (MCTS) is a method for finding optimal decisions in a given domain by taking random samples in the decision space and building a search tree in an incremental and asymmetric manner. It has been proved to be useful in domains that can be represented as trees of sequential decisions, particularly games (e.g., Go [Silver et al., 2016]) and planning problems (e.g., MDPs).

The basic MCTS process is conceptually very simple. To incrementally build a search tree, at each iteration, it starts from the root and consists of the following four steps: 1) Selection: it selects successive child nodes down to a leaf node, 2) Expansion: it expands the tree by adding a new child node, 3) Simulation: it runs several simulations from that node, 4) Backpropagation: it uses the result of the simulations to update information in the nodes on the path from the leaf to the root. This process repeats until some termination condition meets. One of the essential step is how to select a child node so that the tree expands towards the most promising subspace.

UCT [Kocsis and Szepesv´ari, 2006] is a MCTS-based algorithm that has achieved remarkable success in solving large MDPs. Specifically, it treats the node selection as a multiarmed bandit problem and applies the UCB1 heuristic [Auer et al., 2002], where the node value is augmented by an exploration bonus that is highest for rarely tried children. More techniques on MCTS and its variances can be found in the recent survey [Browne et al., 2012].

3 ApplyingMCTS to CSG

We propose the CSG-UCT approach by applying the MCTS method to search the optimal coalition structure in the CS graph. Specifically, we start the search from the top level of the CS graph down to the bottom level and expand the search tree based on random sampling of the solution space.

Similar to the aforementioned CS graph, we define the search tree built by our algorithm as follow:

• Each tree node is associated with a coalition structure CS ∈ ΠA and the root node of the tree is with the singleton coalition structure, i.e., {{a1}, {a2}, · · · , {an}}.
• Each tree branch is linked with a pair-wise join operation, where the child linked by that branch is generated by joining two coalitions of the CS in its parent node, e.g., {{a1, a2}, {a3}, {a4}} is the child of node {{a1}, {a2}, {a3}, {a4}} by joining {a1}, {a2}.

Clearly, the maximal depth of the search tree is n, the size of CS in depth k of the tree is k, and each path from the root to the leaf will end with the grand coalition. In the rest of this paper, we will interchangeably use a coalition structure CS to refer the tree node associated with CS.

Starting from the tree with only the root node, we incrementally build the search tree iteration by iteration. A partial search tree represents the solution space that has been sampled (i.e., searched). Following the standard procedure of MCTS, we describe one iteration of our algorithm, given the current (partial) search tree, with the following four steps:

3.1 Selection

The selection step is for each tree node to select a branch in order to form a path from the root to a leaf. This is a critical step for MCTS because it implies which region of the solution space should be searched at the current iteration. We borrow ideas from the UCT algorithm and view the node selection as a Multi-Armed Bandit (MAB) problem. Specifically, we use the UCB1 heuristic [Auer et al., 2002], which is a simple yet attractive method to solve MAB.

Let V (CS) = maxCS′∈Tree(CS) v(CS′ ) be the maximal value of the coalition structures in the subtree Tree(CS) rooted by CS. This value is known only when the subtree is complete. Let Tree(CS) be the partial subtree built the search process and ¯ V (CS) = maxCS′∈Tree(CS) v(CS′ ) be the current maximal value. Let N(CS) be the frequency count of the node being visited during the search process. The UCB1 heuristic for node selection can be written as:

where c is a constant parameter. Given this, we can select the child node that maximizes the UCB1 heuristic as: CS∗ = argmaxCS′∈Child(CS) UCB1(CS′ ), where Child(CS) denotes all possible children of node CS.

Intuitively, if N(CS′ ) is equal for all children, the UCB1 will select the child with the maximal ¯ V (CS′ ) because the remaining term is equal for all of them. However, if some child is much less frequently visited than others, the term

√log N(CS)/N(CS′ ) will become significant and bias the selection towards it. For example, if N(CS) = 100,N(CS′ ) = 1,N(CS′′ ) = 99, √log 100/1 ≈ 1.4 > √log 100/99 ≈ 0.14. Therefore, the UCB1 may select CS′ instead of CS′′ though ¯ V (CS′′ ) is slightly larger (e.g., less than 1.0). In a word, the UCB1 has the good property of balancing the well-known exploration and exploitation tradeoff [Auer et al., 2002].

3.2 Expansion

When a child CS∗ ∈ Child(CS) chosen by the node selection procedure is currently not in the tree, the search tree is then expanded by adding a new leaf node CS∗ as a child of CS to the tree.

3.3 Simulation

When a new leaf node CS∗ is added to the tree, some default policy is used to estimate ¯ V (CS∗ ). In this work, we perform a rollout search by successively joining two coalitions. For example, a rollout trace starting from the singleton coalition structure {{a1}, {a2}, {a3}, {a4}} is:

Apparently, this process ends with the grand coalition when no join of two coalitions is possible. Then, the value of CS∗ is initialized by ¯ V (CS∗ ) ← maxCS′∈Trace(CS∗ ) v(CS′ ), where Trace(CS∗ ) is a set of coalition structures encountered during the rollout search starting from CS∗ .

Now, the remaining problem is how to select the two coalitions C1,C2 to be joined in a coalition structure CS. Here, we use a simple myopic heuristic as follow:

where CS′ = CS + {C ′1 ∪ C ′2 } - {C ′1 } - {C ′2 } is the coalition structure after joining two coalitions C ′1 and C ′2 in CS. Intuitively, we join two coalitions in CS when it results in the maximal improvement in the coalition structure value.

3.4 Backpropagation

After the value ¯ V (CS∗ ) of the newly added node CS∗ is initialized, the values of all its ancestors in the tree are updated by backpropagting the value ¯ V (CS∗ ) from the leaf node CS∗ to the root. Specifically, for every level-l node CSl in the propagation path of the tree, its value is updated by ¯ V (CSl) = max{¯ V (CSl), ¯ V (CSl+1)}, where CSl+1 is the child of CSl in the path.

To put the above four steps together, we have one iteration of the overall CSG-UCT algorithm. Starting from the singleton coalition structure, the iteration continues until it runs out of time or all nodes have be added to the tree, which implies the complete solution space ΠA has been searched. In the later case, the algorithm returns the optimal solution while in the former case it returns the currently best solution.

An example of the partial search tree built by CSG-UCT is shown in Figure 1. An iteration on the tree starts from the root node {{a1}, {a2}, {a3}, {a4}}. In the selection step, the UCB1 heuristic first selects tree node {{a1}, {a2}, {a3, a4}}

and then recursively selects {{a1, a2}, {a3, a4}}. Since this (red) node is not currently in the tree, the tree is expanded by adding it as a leaf of the tree in the expansion step. Then in the simulation step, the value of the newly added node {{a1, a2}, {a3, a4}} is initialized by a rollout search ending with the grand coalition {{a1, a2, a3, a4}}. Finally in the backpropagation step, the value of the newly added node is propagated back to the root to update the value of the currently best solution along the path. The search tree grows iteration by iteration until all CS ∈ ΠA are added in the tree.

4 Analysis and Discussion

Theorem 1. The CSG-UCT algorithm is complete given a sufficient amount of time.

Proof (Sketch). Given a sufficient amount of time, CSG-UCT terminates when all nodes have be added to the tree. Assuming there exists a coalition structure CS′ that cannot be selected by its parent CS in the tree. Therefore, CS′ cannot be added to the tree by the iteration of CSG-UCT. This is contradicted with the fact that every arm in the MAB will eventually be pulled using the UCB1 heuristic [Auer et al., 2002]. By induction, we conclude that all possible coalition structures in ΠA will eventually be added to the tree if time is sufficient. Thus, the CSG-UCT algorithm is complete.

Theorem2. The CSG-UCT algorithm is anytime and always returns the currently best solution.

Proof (Sketch). Note that the value of every searched node is propagated back to the root node at the end of each iteration. Therefore, the root node always maintains the value of the currently best solution. When the algorithm stops, it can return the currently best solution from the root node. After an iteration, ∀CS : ¯ V t (CS) ≤ ¯ V t+1 (CS) ≤ V (CS) holds. With more iterations, more nodes will be searched and added to the tree. As a result, the solution is constantly improved. Thus, the CSG-UCT algorithm is anytime.

Relation with the DP method. The DP for CSG [Yeh, 1986] can be viewed as evaluating every movement upward in the coalition structure graph by splitting one coalition into two. It then stores the best movements in a table and finally moves upwards in the graph, starting from the bottom node, as long as it is beneficial to do so. In CSG-UCT, we perform best-first search downward in the coalition structure graph, starting from the top node, by joining two coalitions into one. We store the best movements in a tree structure and speed up the search by combining several heuristics. Similar to DP, CSG-UCT is also complete. In practice, it is often more efficient than DP due to the use of the heuristics.

Relation with the C-Link method. The C-Link [Farinelli et al., 2017] starts from the top node of the coalition structure graph, iteratively computes the most suitable pair of coalitions, and move downward in the graph if joining a coalition pair has benefit to do so. In contrast to CSG-UCT, C-Link is memory-less and only keeps the currently best solution. It can be viewed as a local search method and can easily get stuck in local optimal. In fact, we also use similar local search technique in the simulation phase and improve it using a tree structure to memorize the intermediate results.

Implementation. There are several techniques that can make CSG-UCT more memory-efficient. Firstly, the tree nodes representing the same coalition structure can share a single node in the memory. By doing so, the search tree has at most the number of nodes as the coalition structure graph. Secondly, if a subtree rooted with some coalition structure is complete (i.e., with all branches ending with the leaf node of the grand coalition), it can be removed from the search tree in order to save some memory. There are also many wellestablished techniques for MCTS [Browne et al., 2012] that can be applied to speed up the search process of CSG-UCT, such as parallel MCTS, MCTS on GPUs, etc.

5 Empirical Evaluation

We evaluated the performance of our algorithm on several CSG problems including the six benchmark problems commonly used in the literature and a disaster response domain that motivates our approach. We compared our algorithm with GRASP [Di Mauro et al., 2010] and C-Link [Farinelli et al., 2013], which are currently the leading approximate methods for the CSG problem. All the algorithms are implemented in Java and executed on a Intel(R) Core(TM) i7 CPU, 2.50GHz, with 8GB of memory.

In the experiments, we recorded the following two indicative measures of the solution quality. Firstly, we computed the Optimal Ratio = v(CS)/v(CS∗ ) between the value of the computed solution CS and the optimal solution CS∗ . This measure shows how far the value of the computed solution is from the optimal. Here, optimal solutions are computed using the integer programming formulation solved by CPLEX. We limit the computation of the optimal solutions up to 20 agents because this is the maximum number of agents that can be handled on our machine using CPLEX. Secondly, we recorded the Baseline Gain = v(CS)-∑i∈A v({i}) between the computed solution CS and the singleton coalition structure when the optimal solution is unavailable as the number of agents are too large to be solved by CPLEX. This measure shows how valuable it is to form the computed coalition structure as opposed to the singletons (i.e., the baseline).

5.1 Common Benchmark Problems

Note that the common practice in evaluating CSG algorithms is to choose some standard instances of the problem and compare the various algorithms that exist without giving them a priori knowledge of the type of utilities they are presented with. Although our algorithm can solve CSG problems with any types of utilities, we benchmark with six types of utilities with the following commonly used distributions:

• Uniform, as studied in [Larson and Sandholm, 2000]: v(C) ∼ U(a, b) where a = 0 and b = |C|.
• Normal, as studied in [Rahwan et al., 2007]: v(C) ∼ N(µ, σ2 ) where µ = 10 × |C| and σ = 0.1.
• Modified Uniform, as studied in [Service and Adams, 2010]: v(C) ∼ U(0, 10 × |C|), and v(C) is increased by a random number r ∼ U(0, 50) with probability 0.2.
• Modified Normal, as studied in [Rahwan et al., 2012]: v(C) ∼ N(10 × |C|, 0.12 ), and the team value v(C) is increased by a random number r ∼ U(0, 50) with probability 0.2.
• NDCS, as studied in [Rahwan et al., 2009]: v(C) ∼ ×N(µ, σ2 ) where µ = |C| and σ = √|C|.
• Agent-based, as studied in [Rahwan et al., 2012]: v(C) = ∑i∈C pCi where pCi ∼ U(0, 2pi) and pi ∼ U(0, 10) is a random power for agent i.

Figures 2(a-f) summarize our experimental results on the common benchmark problems with the utilities using the distributions described above. We tested CSG-UCT with different size of iterations (i.e., K = 102 and K = 105 ). As we can see from the figures, CSG-UCT outperforms both GRASP and C-Link with better solution quality in all the tested instances. In particular, with more iterations (e.g., K = 105 ), CSG-UCT can find the near-optimal solutions for all the tested problems. This set of experiments shows the advantage of CSG-UCT comparing to the state-of-the-art approximate methods. As we can see, C-Link already performed quite well with the optimal ration of about 0.9 in all the six benchmark problems. Our algorithm can still make significant improvement comparing with C-Link. This confirms the effectiveness of our algorithm.

Table 1 illustrates the maximal number of iterations required for CSG-UCT to find the optimal solution on the NDCS benchmark problems with different numbers of agents. As shown in the table, CSG-UCT is very efficient and only requires few iterations (mostly less than 20) to find the optimal solution for the tested problem instance. It is worth noting that the number of searched coalition structures is usually much smaller than the overall solution space.

As aforementioned, CSG-UCT is anytime that can stop at anytime and return the currently best solution, and continue to improve the solution until it converges to the optimal if more time is available. To demonstrate this property, we conduct experiments on the NDCS benchmark problem with 25

(g) Disaster Response (Optimal Ration and Baseline Gain)

(h) Anytime (Iterations vs. Optimal Ration and Runtime)

Figure 2: Experimental Results on Six Common Benchmark Problems and the Disaster Response Domain

agents. Specifically, we vary the number of iterations used in CSG-UCT and observe how it affects the solution quality and runtime of the algorithm. As we can see from Figure 2(h), the solution quality constantly improves when the number of iterations increases. As expected, the runtime increases linearly when the number of iterations grows. In practice, we can repeatedly run the sampling steps until it runs out of time and return the currently best solution. This is appealing in domains where time and resources are limited.

5.2 Case Study: Disaster Response

Our work is motivated by a disaster scenario [Ramchurn et al., 2015; Ramchurn et al., 2016], in which a satellite, powered by radioactive fuel, has crashed in a sub-urban area. Debris is strewn around a large area, damaging buildings and causing accidents and injuring civilians. Moreover, radioactive particles discharged from the debris are gradually spreading over the area, threatening to contaminate food reserves and people. Hence, emergency services are deployed to evacuate the casualties and key assets before they are engulfed by the radioactive cloud. As in the scenario [Ramchurn et al., 2016], the mission of emergency responders is to evacuate 4 types of targets as: victim, animal, fuel, or other resource, which require a combination of 4 roles played by the responders as: medic, fire-fighter, soldier, or transporter. Before being despatched, hundreds of human responders must coordinate together and form teams quickly in a way that the overall performance is maximized.

Generally, given a team of responders C, there are many ways to estimate its team performance and define the utility v(C) required by team formation algorithms. As a case study, we consider a simple model as follows. Each responder i has been assigned a value cri ∼ U(0, 10) to indicate her capability to play the role r based on her training, past experience, body condition, etc. For each target k, the upper bound of the team performance is defined as: ¯ pCk = ∑r∈Θk ∑i∈C cri , where Θk is the set of roles required by the target. Then, the utility for the team is denoted as: v(C) = ∑4k=1 pCk , where pCk ∼ U(0, ¯ pCk ) is the estimate of the performance of team T on target k subject to uncertainty. Note that this is just a specification for the team utility. In practice, we can use any utility function designed by the domain experts.

Figure 2(g) reports the experimental results on the disaster response domain. As we can see from the figure, CSG-UCT outperforms both GRASP and C-Link to achieve more gains comparing to the baseline performance if no team is formed. Notice that this domain with hundreds of responders is intractable for existing optimal algorithms. Thus, we must use approximate techniques to solve such CSG problems. However, existing approximate methods such as GRASP and CLink are not anytime and have no guarantee on solution quality. Therefore, their performance cannot be improved even more time and resources are available.

6 RelatedWork

Optimal approaches for solving CSG are mostly based on Dynamic Programming (DP). The first DP algorithm [Yeh, 1986] works by iteratively determining, for every coalition, whether it is beneficial to split it into two coalitions and storing the best split. The DP algorithm computes an optimal coalition structure in O(3n ) time and may take hours to handle 30 agents on a modern desktop computer [Rahwan et al., 2015]. Improvements such as ODP and IDP were made by avoiding some operations of DP. Following early efforts [Sandholm et al., 1999; Dang and Jennings, 2004] on identifying the worst-case guarantees if only subspace is searched, an anytime algorithm, named IP [Rahwan et al., 2009], was proposed based on the integer partition-based representation. To further boost the performance, approaches such as IDP-IP and ODP-IP [Michalak et al., 2016] were proposed to combine techniques of DP and IP. These algorithms only take seconds to handle 30 agents but is unlikely to solve problems of 40 agents or more on a modern desktop computer [Rahwan et al., 2015]. Generally, optimal algorithms are not scalable to large problems with more than 40 agents.

A number of heuristics have been developed to solve large CSG problems approximately, ranging from greedy methods [Shehory and Kraus, 1998; Di Mauro et al., 2010] to genetic or local search algorithms [Sen and Dutta, 2000; Kein¨anen, 2009]. Among them, GRASP [Di Mauro et al., 2010] is a greedy method that, at each iteration, a coalition structure is constructed greedily and then a local search is used to improve the coalition structure by exploring its neighbours. C-Link [Farinelli et al., 2013] is another greedy based approach motivated by data clustering methods. It starts from the structure of all singleton coalitions and iteratively selects a pair of coalitions to be merged. The pair of coalitions are chosen based on the suitability function in a myopic manner, without taking into consideration the future consequences of this choice. Hence, it can be trapped in local maxima of the objective function. To date, both GRASP and C-Link are the leading approximate CSG algorithms with good empirical results. Although approximate methods return solutions relatively quickly, they do not provide any guarantees on solution quality. Some efforts have been made to bound the solution quality but they usually require the characteristic function (i.e., the utility function) to have some special structure (e.g., the m+ a functions as in [Farinelli et al., 2017]).

Recently, several approaches [Rahwan et al., 2011; Bistaffa et al., 2017] were proposed to exploit specific domain structures and improve the performance. Existing CSG algorithms can be speeded up using GPU [Pawłowski et al., 2014] or multi-core machines [Cruz et al., 2017]. However, scalability is still an issue. A comprehensive survey on the CSG algorithms can be found in [Rahwan et al., 2015].

7 Conclusions

This paper presented a scalable algorithm based on UCT for the CSG problem. Specifically, we proposed the CSG-UCT algorithm that builds a search tree by sampling the solution space of coalition structures. We show that CSG-UCT is complete and will eventually converge to the optimal given sufficient number of iterations. Moreover, it is anytime and can return the current best solution if time is limited. In the future, we plan to further improve the performance on very large CSG problems by exploiting the properties of coalition structures and test our method on real-world applications.

Acknowledgements

This work was supported in part by the National Key R&D Program of China (2017YFB1002204), the National Natural Science Foundation of China (U1613216, 61603368), and the Guangdong Province Science and Technology Plan (2017B010110011).