Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search

1 Introduction

One of the main challenges in coalition formation is the coalition structure generation (CSG) problem: partitioning the agents into disjoint exhaustive coalitions so as to maximize social welfare. (A coalition structure is a partitioning of agents into coalitions.) This is a central problem in artificial intelligence and game theory that captures a number of important applications such as collaboration among trucking companies [Sandholm and Lesser, 1997], distributed sensor networks [Dang et al., 2006], etc.

Many algorithms have been developed for this problem. Dynamic programming algorithms [Yeh, 1986; Rahwan and Jennings, 2008; Michalak et al., 2016; Changder et al., 2019; Taguelmimt et al., 2022b] find an optimal solution if it is computationally feasible to run them to completion. Anytime algorithms [Sandholm et al., 1999; Dang and Jennings, 2004; Rahwan et al., 2009; Ueda et al., 2010; Taguelmimt et al., 2022a] provide intermediate solutions during the execution and allow premature termination. Heuristic algorithms [Sen and Dutta, 2000; Ueda et al., 2010; Krausburg et al., 2021; Taguelmimt et al., 2021] focus on speed and do not guarantee that an optimal solution is found.

Even though those algorithms perform well in practice in some cases, hybrid algorithms [Michalak et al., 2016; Changder et al., 2020; Changder et al., 2021; Taguelmimt et al., 2023; Taguelmimt et al., 2024] that combine dynamic programming with integer partition graph search have emerged as the dominant approach to find optimal solutions to this problem. The fastest exact algorithms to date are hybrid solutions called ODP-IP [Michalak et al., 2016], ODSS [Changder et al., 2020], and BOSS [Changder et al., 2021] that combine IDP [Rahwan and Jennings, 2008] and IP [Rahwan et al., 2009]. IDP is based on dynamic programming and computes the optimal solution for n agents by computing an optimal partition of all the coalitions C of size |C| ∈ {2, ..., 2n 3 , n}. In contrast, IP uses an integer representation of the search space and computes the optimal solution by traversing in a depth-first manner multiple search trees and uses branch-and-bound to speed up the search. However, the worst-case run time of the state-of-the-art hybrid algorithms is determined by their respective dynamic programming parts, which still need improvement. Also, the hybridization of IDP and IP in these algorithms relies heavily on the effectiveness of IP. Thus, the time required by the algorithms grows considerably when IP is not fast enough. Moreover, these algorithms exhibit very high run times for some distributions.

In light of this, and to enable faster generation of optimal coalition structures, we develop a new algorithm that combines three complementary techniques to guide the search. The advantage of these techniques is threefold. The first technique, Complementarity-Based Dynamic Programming (CDP), enables SMART to have the best worst-case time performance of all algorithms to date. GRadual seArch with Dynamic Programming (GRAD) enables it to find the optimal solution quickly by exploring a minimum number of solution subspaces which shortens the run time. Distributed Integer Partition Search (DIPS) further accelerates the search by exploring the subspaces that are most likely to contain the optimal solution. In short, our main contributions are:

• We develop a novel algorithm for optimal CSG that combines three new techniques, resulting in a significant performance improvement. Two of these techniques use offline phases to optimize the search. Moreover, we introduce a new complementarity principle in dynamic programming, where the optimal solution is found by combining the evaluation results of two distinct sets of coalitions. We also propose another principle of gradual search in dynamic programming, where percentages of solution subspaces are searched separately. These principles bring a new way of approaching the problem and a new level of precision to the field.
• We devise the fastest dynamic programming algorithm to date, which bounds the run time, and we propose a new way to speed the search for optimal solutions, while exploring only a part of the search space.
• We show that our algorithm outperforms existing algorithms when generating optimal solutions. We show that it is i) orders of magnitude faster in producing optimal solutions, and ii) more stable in the run time when varying the distributions and the numbers of agents.

2 Preliminaries

The input to a CSG problem is a set of agents A and a characteristic function v. We say that a CSG problem A = {a1, a2, ..., an} is of size n. A coalition C in A is any nonempty subset of A. The size of C is |C|, which is the number of agents it contains. A size set is a set of coalition sizes. In a CSG problem, a characteristic function v assigns a real value to each coalition C. A coalition structure CS is a partition of the set of agents A into disjoint coalitions. Given a set of non-empty coalitions {C1, C2, ..., Ck}, CS = {C1, C2, ..., Ck}, where k = |CS|, ⋃kj=1 Ci = A and for all i, j ∈ {1, 2, ..., k} where i ̸= j, Ci ∩ Cj = ∅. Π(A) denotes the set of all coalition structures. The value of a coalition structure CS is V (CS) = ∑C∈CS v(C). The optimal solution of the CSG problem is the most valuable coalition structure CS ∗ ∈ Π(A), that is, CS ∗ = argmaxCS∈Π(A)V (CS).

The integer partition graph [Rahwan et al., 2007] (see Figure 1) divides the search space into subspaces that are represented by integer partitions of n. Given n agents, each integer partition of n is represented by a node, where the nodes are divided into levels. Each level l ∈ {1, 2, .., n} contains nodes representing integer partitions of n that contain l parts. For instance, level 3 contains nodes where integer partitions of n have 3 parts. Two adjacent nodes are connected if the integer partition in level l can be reached from the one in level l-1 by splitting only an integer. Each integer partition P represents a set of coalition structures in which the sizes of the coalitions match the parts of P. For example, the node [1,1,2] represents all coalition structures that contain two coalitions of size 1 and one coalition of size 2. Figure 1 shows a fouragent example of the integer partition graph.

For the remainder of this paper, we use the terms solution subspace and node interchangeably.

3 SMART: ANovel CSGAlgorithm

The SMART algorithm is based on three techniques (CDP, GRAD and DIPS) that combine dynamic programming with integer partition graph search. SMART introduces new ways of searching the integer partition graph of solutions.

3.1 Complementarity-Based Dynamic Programming (CDP)

CDP is an algorithm that determines the optimal coalition structure. To compute the optimal structure, CDP evaluates different sets of coalitions through two processes (Figure 2), and computes the best partition of each coalition, meaning the best way to split it into potentially multiple subcoalitions. The highest valued coalition structure returned by these processes is an optimal solution. To determine the coalitions to evaluate (that is, for which to compute the best partitions) and ensure that the optimal solution is found, the CDP algorithm uses an offline phase of preprocessing. This phase defines the best pair of coalition size sets to evaluate, such that when combined, the entire solution space is searched. This means that by evaluating these specific sets of coalitions, the CDP algorithm can guarantee that it has considered every possible grouping of agents.

CDP's Offline Phase

The offline phase is one of the key components of the CDP algorithm, which is responsible for determining the coalitions to evaluate in the two processes of the algorithm. This is done by considering the coalition sizes, as illustrated on the integer partition graph (Figure 1). To understand how this works, let us consider an example of four agents. Dividing a coalition of size 2 into two coalitions of size 1, when searching for the solutions, corresponds to an upward movement in the integer partition graph from the node [2, 2] to the node [1, 1, 2] (2=1+1). By choosing to split in this graph a subset of integers starting from the bottom node, that is, by considering the edges that result from splitting a subset of sizes, a subset of nodes in the integer partition graph becomes reachable from the bottom node, which means that the nodes are connected to the bottom node through a series of edges. Thus, to search a certain number of subspaces, several sets of coalition sizes could be considered, with a different run time for each set. For example, by splitting only the sizes 2 and 4 starting from the bottom node, that is, by deciding to evaluate all the coalitions of sizes 2 and 4 and not those of size 3, all the nodes in the integer partition graph are reachable from the bottom node through a series of edges that result from splitting the coalition sizes 2 and 4. Hence, the set of sizes {2, 4} generates 100% of subspaces, as does the set {2, 3, 4}, but with a lower run time. Hence, some sets of sizes may be more beneficial than others. To find the best size set pair, we propose the Size Sets Definition (SSD) algorithm. The SSD algorithm starts by estimating the time required to evaluate the coalitions of each size from 2 to n. This time corresponds to the evaluation time of all the different ways of splitting the coalitions of each size. The estimated time of a splitting is the computational cost associated with this hardware operation, which is a fixed value like any other operation, such as an addition or a subtraction. Then, SSD computes the best pair of coalition size sets that searches all the subspaces with minimum run time.

Then, SSD goes through each possible pair of coalition size sets, and for each pair, it constructs two integer partition graphs by only dividing the integers that belong to each set of sizes (Figure 2). The edges that result from dividing the sizes of the set connect a number of nodes to the bottom node. For a particular pair of sets, in case the generated nodes of the second set of sizes cover all the missed nodes of the first set, meaning that all the solution subspaces are obtained by the first or second set, the SSD algorithm tests whether the pair minimizes the run time. If so, this pair becomes the best pair. The run time of a set of sizes is the sum of the evaluation times of the coalitions of the size set. Given this, the run time of a pair of size sets is the highest run time of the size sets that comprise it.

Algorithm 1 shows how SSD computes the best pair of coalition size sets. The sets of sizes are represented in binary format, with numbers of n - 2 bits that represent sizes between 2 and n - 1. The coalitions of size 1 and n are not evaluated because the size 1 coalitions are never split and the coalition of size n is always split. For example with five agents, the sets of sizes are {2, 3} and {2, 4}, are represented by the binary numbers 0112 and 1012, respectively.

These steps are all executed offline, meaning that we run the SSD algorithm only once for each problem size n (not once for each problem instance) to set up CDP. For example with ten agents, the best pair of coalition size sets that SSD returns is BS1 = {2, 4, 6, 10} and BS2 = {2, 8, 10}, which together search all the subspaces.

Algorithm 1: Size Sets Definition (SSD) Algorithm

Input: A problem size n, the required time to evaluate the coalitions of each size.

Output: The best pair BS1, BS2 of coalition size sets to search the entire solution subspaces. BS1 and BS2 are in binary format.

• 1 BS1 ← 2n-2 - 1 ▷ Initially, the best sizes include all the coalition sizes, i.e. {2, .., n - 1}
• 2 BS2 ← 2n-2 -1
• 3 x ←GeneratedSubspaces(2n-2 -1) ▷ GeneratedSubspaces(2n-2 - 1) returns the set of subspaces for a problem of n agents
• 4 t∗1 ←SetTime(2n-2 -1) ▷ SetTime returns the run time for a set of sizes. The best time for searching the subspaces is initialized to the run time of considering all the sizes
• 5 t∗2 ←SetTime(2n-2 -1)
• 6 for i = 1 to 2n-2 -1 do ▷ i corresponds to a set of coalition sizes represented in binary format

7

8

9

• 10 if t1 < t∗1 or t1 < t∗2 then ▷ the set i has a chance to improve the result

11

12

13

14

15

16

17

y ← GeneratedSubspaces(i)

v ← x \ y ▷ v contains the missed nodes when

considering the set i

t1 ← SetT ime(i)

for j = i + 1 to 2n-2 - 1 do

y ← GeneratedSubspaces(j)

if v ⊆ z then ▷ the set j generates all the

missed nodes of the set i

t2 ← SetT ime(j)

if t1 < t∗1 and t2 ≤ t∗2 or t2 < t∗2 and

t1 ≤ t∗1 then ▷ the pair of sets {i, j}

improves the result

BS1 ← y, BS2 ← z

t∗1 ← t1, t∗2 ← t2

• 18 Add n to BS1 and BS2 ▷ n is always considered. 19 Return BS1, BS2

CDP's Online Phase

The CDP algorithm uses these sets to compute the optimal coalition structure each time a problem instance is to be solved. CDP starts, in a first step, by constructing two tables, the partition table Pt that stores the optimal partition of each coalition C in Pt(C) and the value table Vt that stores the optimal value of each coalition C in Vt(C). Pt(C) and Vt(C) are computed for each coalition C by evaluating all possible ways of splitting C into two coalitions and checking whether it is beneficial to split it or not. For example, for a coalition of size 4, we evaluate its splitting into a coalition of size 1 and a coalition of size 3 (4=1+3) and into two coalitions of size 2 (4=2+2). This evaluation is done by the two CDP processes, which each consider the coalitions whose sizes belong to the sets returned by SSD. In each process, CDP starts evaluating the smallest coalitions first, as the result of this evaluation is used for evaluating larger coalitions (see Algorithms 2 and 3). In a second step, each process of CDP computes the best

Algorithm 2: The CDP algorithm

Input: Set of all possible coalitions and the value n. Sets of coalition sizes BS1 and BS2 to

• Vt(C) of each coalition C. A number of agents consider by CDP. Output: An optimal coalition structure CS ∗ and its value. ▷ Begin parallel ▷ CDP runs in parallel given BS1 1 CS ∗1 , V ∗ 1 ←Computing Optimal CS(Vt, n, BS1) ▷ CDP runs in parallel given BS2 2 CS ∗2 , V ∗ 2 ←Computing Optimal CS(Vt, n, BS2) ▷ End parallel 3 if V ∗ 1 > V ∗ 2 then 4 V ∗ ←V ∗ 1 , CS ∗ ← CS ∗1 5 else 6 V ∗ ←V ∗ 2 , CS ∗ ← CS ∗2 7 Return CS ∗ , V ∗

coalition structure, among the searched subspaces, by computing the best partition of the grand coalition A. Hence, the optimal solution that CDP finds is the highest-valued coalition structure produced by these processes (Figure 2).

Theorem 1 establishes that when considering any pair of coalition size sets, the presence of a path between each node and the bottom node in one of the two integer partition graphs associated with the respective size sets guarantees finding an optimal coalition structure.

Theorem 1. When considering any pair of coalition size sets to evaluate, if there is a path between each node and the bottom node of one of the two integer partition graphs generated by the two size sets, CDP will fully search the solution subspaces. Thus it finds an optimal coalition structure.

Proof. The splitting operations of CDP are represented with edges in the integer partition graph (Figure 2). An edge that connects two adjacent nodes, and results from splitting an integer x into two, represents the evaluation of all coalitions of size x by CDP. If there is a path between the bottom node of the integer partition graph and a node N, then all the coalitions that need to be split to find the best solution in N are evaluated. As all the nodes are at least connected to one of the bottom nodes of the two integer partition graphs generated by the pair of size sets, CDP fully searches each subspace.

Algorithms 2 and 3 detail the pseudocode of CDP. CDP runs in parallel on the two coalition size sets obtained from the offline phase. In Algorithm 3, CDP computes the optimal coalition structure that belongs to the subspaces searched considering each set. Then, the optimal solution is the highest valued solution of the two (see lines 3-7 of Algorithm 2).

3.2 Gradual Search with Dynamic Programming (GRAD)

The GRAD algorithm uses multiple parallel processes to search for the optimal solution, each with a set of coalition sizes as input with which it explores a certain percentage of the search space. These percentages that we detail in Section 6 are hyperparameters that can be adjusted to fine-tune the algorithm.

GRAD's Offline Phase

GRAD also uses an offline phase to compute, for each considered percentage ω, the best coalition size set that allows one to search this percentage of subspaces with the shortest run time. To find these sets, we introduce the Size Optimization for diFferent percenTages (SOFT) algorithm. For each size set S, SOFT constructs the corresponding integer partition graph GS by only dividing the integers that belong to the set S. GS is thus partial, as shown in the example of Figure 2. If this number of generated nodes in GS is at least an ω fraction of the total number of subspaces and S minimizes the run time, then S becomes the best set. Algorithm 4 shows how SOFT computes the best coalition size sets. For example with n = 10 agents and ω = 90%, the best coalition size set that SOFT returns is {2, 4, 6, 10}; it searches 92.86% of subspaces (Figure 2.a).

GRAD's Online Phase

Once these size sets are computed by the SOFT algorithm, each process of GRAD is tuned with the corresponding size set. To solve the problems, GRAD builds a partial integer partition graph with all subspaces and no edges and launches each process with its size set and this partial graph as input (Algorithm 5). Each process of GRAD evaluates all the coalitions whose sizes belong to the best size set obtained from the offline phase and computes their best partitions. The GRAD process evaluates all possible ways of splitting each coalition of the selected sizes into two coalitions and tests whether it is beneficial to split or not. The coalitions are evaluated starting with the smallest ones (Figure 2.a). The result of this evaluation is stored in the partition table Pt and the value table Vt. Once all the coalitions have been evaluated, the GRAD process returns the best coalition structure among the searched subspaces. This is determined by computing the best partition of the grand coalition A using the partition and value tables generated during the evaluation process.

When the optimal solution is in the subspaces explored by a process of GRAD that searches a specific percentage of subspaces ω < 100%, the process finds it with the shortest run time and enables the other GRAD processes to instantly prune certain subspaces without exploring them. To prune the subspaces, we introduce the upper bound UB(N) of a subspace N , which is the highest value a coalition structure of this subspace can possibly reach. UB(N) = ∑i∈Integers(N) Maxi, where Maxi is the maximum value a coalition of size i can take and Integers(N) is the set of integers that form the corresponding integer partition of the subspace N. For instance, for N = [1, 4, 5], Integers(N) = {1, 4, 5} and UB(N) = ∑i∈{1,4,5} Maxi =Max1 +Max4 +Max5. By comparing the upper bounds of the subspaces, the GRAD processes identify those that have no chance of improving the solution quality and prune the corresponding nodes that do not have a better upper bound than the last best solution found (Line 10 in Algorithm 6). Moreover, after evaluating all the coalitions of size x, a GRAD process updates the integer partition graph by adding the edges that result from splitting x into two integers (Line 8 in Algorithm 6). For example in Figure 2.b, after evaluating all the coalitions of size 8, all the green edges are added to the graph. Hence, a number of nodes become reachable from the bottom node through a series of edges, and the corresponding subspaces are fully searched. Thus, the GRAD process prunes them (Line 9 in Algorithm 6). The subspace pruning, using the upper bounds and the connection to the bottom node, are repeated each time a process of GRAD finishes evaluating the coalitions of each size. Hence, as the size x increases, more subspaces are pruned from the graph. Thus, when all subspaces are pruned, GRAD finishes and returns the optimal solution.

3.3 Distributed Integer Partition Graph Search (DIPS)

DIPS searches the solution subspaces using the integer partition graph. First, DIPS computes the upper bounds of the subspaces and searches them based on their upper bounds. Then, whenever a CDP or GRAD process finishes, while there are still unexplored nodes, DIPS uses that process for a different problem space to parallelize its search. The new process uses the same search technique in DIPS. Thus, the subspaces of

Algorithm 4: The SOFT Algorithm

• Input: A CSG problem size n, the required times to evaluate the coalitions of sizes 2 to n-1 for splitting, and the percentage ω of solution subspaces.

Output: The best set of coalition sizes BS to search at least the percentage ω of the solution subspaces. BS is in binary format.

• 1 BS ← 2n-2 - 1 ▷ Initially, the best set includes all the coalition sizes, i.e. {2, .., n - 1}. 2n-2 - 1 is the binary representation of this set.
• 2 x ←NumberOfSubspaces(2n-2 -1) ▷ The functionNumberOfSubspaces returns the number of subspaces for a CSG problem with n agents
• 3 t∗ ←SetTime(2n-2 -1) ▷ SetTime returns the run time for a set of sizes. t∗ is initialized to the run time when considering all the coalition sizes, which is the worst time
• 4 for i = 1 to 2n-2 -1 do ▷ i corresponds to a set of coalition sizes represented in binary format
• 5 y ← NumberOfSubspaces(i) ▷ y represents the number of generated subspaces in i
• 6 if y ≥ x × ω and SetT ime(i) < t∗ then ▷ the set i generates at least the needed percentage of subspaces
• 7 BS ← i
• 8 t∗ ← SetT ime(i)
• 9 Add n to BS ▷ n is always considered. 10 Return BS

Algorithm 5: The GRAD algorithm

Input: Set of all possible coalitions and the value Vt(C) and Pt(C) of each coalition C. A number of agents n. Sets of coalition sizes BSi to consider by GRAD.

Output: An optimal coalition structure CS ∗ and its value.

• 1 for i = 1 to |BS| do ▷ |BS| is the number of considered percentages.
• 2 Generate a partial integer partition graph IG with all subspaces and with no edges
• ▷ Begin parallel
• ▷ GRAD process runs in parallel given BSi
• 3 CS ∗ , V ∗ ←Search Process(Pt, Vt, n, BSi, IG) ▷ End parallel
• 4 Return CS ∗ , V ∗

solutions will gradually be distributed between several processes as they are released by CDP or GRAD, which share the subspaces, their upper bounds, and their sorting. This way, each subspace is searched by only one process.

DIPS progressively prunes the subspaces that do not have a better upper bound than the last best solution found. To search a subspace of solutions, a DIPS process constructs several search trees to explore the coalition structures. The

Algorithm 6: Search Process

Input: The partition and value tables Pt and Vt. A number of agents n. Set of coalition sizes BS to consider by the process. A partial integer partition graph.

Output: An optimal coalition structure CS∗ and its value.

1 for s ∈ BS do

2

3

4

5

6

foreach C ⊆ A, where |C| = s do

foreach C1, C2 ⊆ C, where C1 ∪ C2 = C and

C1 ∩ C2 = ∅ do

if Vt(C1) + Vt(C2) > Vt(C) then

Vt(C) ← Vt(C1) + Vt(C2)

Pt(C) ← {C1, C2}

7 Compute the best solution, CS ∗ , V ∗ , from Pt and Vt 8 Add to the integer partition graph the edges that result from splitting the size s

9 Prune the subspaces connected to the bottom node ▷ these subspaces are already explored

10 Prune the subspaces that do not have a better upper bound than the last best solution found

11

• 12

if all the subspaces are pruned then Return CS ∗ , V ∗

nodes of these trees represent coalitions and each path from the root to a leaf represents a coalition structure. Moreover, DIPS applies a branch-and-bound technique to identify and avoid branches that have no chance of containing an optimal solution. An example of this step is given in Figure 3 in the appendix.

4 Hybridization: The SMART Algorithm

We combine CDP, GRAD, and DIPS to make the coalitionSize optiMization and subspAce ReconfiguraTion (SMART) algorithm. Initially, SMART sorts the subspaces by their upper bounds. The DIPS algorithm starts searching with the subspace that has the highest upper bound. Then, DIPS prunes out the subspaces that are either already searched by CDP or GRAD, or that do not have a better upper bound than the last best solution found. CDP and GRAD evaluate the coalitions of the computed sizes obtained from their respective offline phases and allow subspace pruning through intermediate solutions. Whenever a process in CDP or GRAD finishes evaluating the coalitions of any size, they prune out the subspaces that are connected to the bottom node of the integer partition graph through a series of edges because the optimal coalition structure among these subspaces is found by CDP or GRAD. Hence, DIPS does not need to search them. Figure 3 shows how DIPS distributes the search.

Algorithm 7 shows the pseudocode of SMART. We now introduce the following results.

Lemma 1. CDP is faster than or at least as fast as IDP.

Proof. Let SIDP be the set of sizes used by IDP [Rahwan and Jennings, 2008]. SIDP is hand tuned and is always equal to {2, 3, .., 2n 3 , n} for n agents. Let S1 and S2 be the sets of sizes used by CDP, which are tuned automatically by the SSD algorithm. S1 and S2 are configured to be the pair of sets with the shortest resulting run time. We now show that IDP can not have a better run time than CDP. Let time(Si) be the run time produced by the set i. Suppose now that there exists a number of agents for which SIDP is the best set of sizes to consider and that no pair of sets can produce a better run time. In this case, as the sets S1 and S2 find the shortest run time, they must coincide with SIDP , meaning that max(time(S1), time(S2)) = time(SIDP ). Hence, the SSD algorithm would find the sets S1 = SIDP and S2 is not necessary because SIDP is sufficient to search the entire solution space and the statement follows.

Lemma 1 shows a notable property of CDP, and hence of SMART. In particular, it enables us to prove the following theorem. To the best of our knowledge, ODPIP [Michalak et al., 2016], ODSS [Changder et al., 2020], and BOSS [Changder et al., 2021] are the fastest prior optimal algorithms for the CSG problem.

Theorem 2. In the worst case, SMART is faster than or at least as fast as ODP-IP, ODSS, and BOSS.

Proof. SMART uses the CDP algorithm, which relies on having the best pair of coalition size sets that enables fast search of optimal results. By Lemma 1, CDP is faster than IDP. Recall that the fastest exact algorithms are the hybrid solutions, ODP-IP, ODSS, and BOSS, that combine IDP and an integer partition-based algorithm. However, this combination is highly dependent on the efficiency of the integer partitionbased algorithm, which in the worst case requires searching all the coalition structures in O(nn ) time [Rahwan et al., 2009], which is infeasible in a reasonable time. Thus, in the worst case, the run time of such hybrid algorithms is determined by the dynamic programming approach. Hence, for hard problems, SMART represents the fastest solution as the dynamic programming algorithm used (CDP) is faster than IDP used by the other algorithms. Formally, let TSMART be the time complexity of SMART, where TSMART = min(O(nn ), time(GRAD), time(CDP)) ≤ time(CDP) and let TOther be the time complexity of the other algorithms, where TOther = min(O(nn ), time(IDP)) =

The result of this hybridization is threefold: (1) CDP is faster than the dynamic programming algorithm IDP (results reported in Section 6). This allows SMART to be faster in the worst case than the state-of-the-art algorithms ODPIP [Michalak et al., 2016] and BOSS [Changder et al., 2021] because the CDP part of SMART is faster than the IDP algorithm used by ODP-IP and BOSS, and the worst case time performance of these algorithms is determined by their dynamic programming parts; (2) GRAD gradually searches the best size sets for each percentage of solution subspaces. This allows SMART to reach the number of subspaces needed to guarantee finding an optimal solution with the best run time; (3) The integer partitions are distributed among several processes, enabling an efficient and faster search in the integer partition graph.

Algorithm 7: The SMART algorithm

Input: Set of all possible coalitions and the value v(C) of each coalition C for n agents. Sets of coalition sizes BS1, BS2 to consider by CDP and BSi to consider by GRAD.

Output: An optimal coalition structure CS∗ and its

value.

• 1 Generate a partial integer partition graph with all subspaces and with no edges
• 2 Sort the subspaces by their upper bounds
• ▷ Begin parallel ▷ CDP runs in parallel with DIPS and GRAD
• 3 CS ∗ , V ∗ ←CDP(v, n, BS1, BS2)
• 4 Return CS ∗ , V ∗
• ▷ GRAD runs in parallel with DIPS and CDP
• 5 CS ∗ , V ∗ ←GRAD(v, n, BSi)
• 6 Return CS ∗ , V ∗ ▷ DIPS runs in parallel with CDP and GRAD
• 7 foreach promising subspace PS do
• 8 DIPS searches the subspace PS
• 9 Return CS ∗ , V ∗
• ▷ End parallel

5 Analysis of SMART

In this section, we prove that the SMART algorithm is complete in Theorem 3. Then, we analyze the computational complexity of the algorithms in detail.

Theorem 3. The SMART algorithm always finds the optimal solution.

Proof. Each node in the integer partition graph is searched by SMART using the CDP, GRAD, and DIPS algorithms. A node represents a subspace, which contains a number of coalition structures that match the parts of the subspace. The SMART algorithm returns the final solution when all nodes have been searched or pruned. For a particular node that contains the optimal coalition structure, the only way for SMART

not to search it is for DIPS or GRAD to prune it without any of the three algorithms searching it. However, DIPS or GRAD will only prune nodes that have no chance of containing the optimal solution. Thus, such a node would never be pruned, and one of the three algorithms would always completely search the node that contains an optimal solution.

Time complexity of the SSD algorithm. For each problem size n, the SSD algorithm tests all possible pairs of coalition size sets. For each set of coalition sizes, SSD reconstructs the integer partition graph by dividing only the integers that belong to that set and tests whether it is beneficial to pair that set with another set or not. To test this for one set, CDP pairs it with all the other sets. The total number of sets that SSD evaluates is 2n-2 - 1. We denote by I(s) the number of integer splits performed for a set s and by p(n, s), the number of subspaces generated by the set s. The total number of operations performed by SSD for one set is T (n) = ∑2n-2-1 s=1 I(s) = ∑2n-2-1 s=1 ∑N I(N, s), where I(N, s) is the number of integer splits performed on node N. The number of splits into two for a certain integer i is i2 , the highest integer to split is n, and the highest possible number of integers in a single node is n, which is the number of integers of the node that represents the singleton coalition structure. Thus, I(N, s) ≤ n × n2 , and T (n) ≤ ∑2n-2-1 s=1 p(n, s) × n × n2 . However, the growth rate of the number of nodes in the integer partition graph, which is the same as the growth rate of integer partitions of n, is O( eπ√ 2n 3 n ) [Wilf, 2000]. Hence,

As a result, the total number of operations of SSD when testing one set is O(n2 × 2n × eπ√ 2n 3 n ). SSD tests 2n-2 - 1 different sets. Thus, the time complexity of SSD is O(22n × n2 × eπ√ 2n 3 n ).

Time complexity of the SMART algorithm. SMART combines three algorithms-CDP, GRAD, and DIPS, and runs them in parallel. The worst-case run time of dynamic programming on this problem is O(3n ) [Yeh, 1986]. CDP and GRAD are based on dynamic programming. They run in parallel on several sets of sizes and terminate when all sets are fully evaluated. Thus, the time complexity of both CDP and GRAD is O(3n ). The worst-case run time of DIPS, which, in the worst-case, requires us to search all coalition structures, is O(nn ). As a result, the time complexity of SMART is min(O(3n ), O(3n ), O(nn )) = O(3n ).

6 Empirical Evaluation

We now evaluate the effectiveness of SMART by comparing it to the prior state-of-the-art algorithms ODP-IP and BOSS. We implemented SMART in Java and for ODP-IP and BOSS, we used the codes provided by their authors for the comparisons. They are also written in Java. The algorithms were run on an Intel Xeon 2.30GHz E5-2650 CPU with

256GB of RAM. For GRAD, we considered values of ω ∈ {10%, 20%, 30%, 40%, 50%, 60%, 70%, 80%, 90%, 100%}. We also designed and tested a different version of ODP-IP, namely POI (Parallel ODP-IP), that we developed to integrate parallelism in the baseline version of ODP-IP in order to improve its performance. It uses the same number of processes as SMART (see the appendix for more details). This does not affect the theoretical guarantees but improves the practical performances of the algorithm.

We conducted the experiments on common benchmark problems. We show results on nine value distributions. Results on other distributions are in the appendix. We compared the algorithms using the following value distributions: Modified Normal [Rahwan et al., 2012], Beta, Exponential, Gamma [Michalak et al., 2016], Normal [Rahwan et al., 2007], Uniform [Larson and Sandholm, 2000], Modified Uniform [Service and Adams, 2010], Zipf, SVA Beta and Weibull [Changder et al., 2020]. The experiments shown in the remainder of the paper are also representative of those in the appendix. For each distribution and number of agents, we ran each algorithm 50 times. Figure 4 reports the run times of SMART, BOSS, ODP-IP and POI. On all distributions, SMART was the fastest for all numbers of agents. For example, after 2 seconds, with the Normal distribution for 24 agents, SMART returns optimal solutions roughly 92% faster than BOSS, 91% faster than ODP-IP and 54% faster than POI, while outperforming them by multiple orders of magnitude as can be seen in Figure 4. The reason for this is twofold. First, when problems are hard to solve (see, for instance, the results for Exponential), the CDP part of SMART finishes before the other algorithms as it presents the best worst-case time performance. The second reason is that for problems where the search of a specific percentage of the solution subspaces is sufficient to find the optimal solution, the combination of GRAD and DIPS achieves the best run time. On one hand, GRAD searches that percentage of subspaces with the best run time. On the other hand, DIPS distributes the search to further accelerate it. Notice that the relative contribution of each technique depends on the specific problem instance. Generally, for easier-to-solve instances, DIPS and GRAD play a more significant role in finding the optimal solution, as they target specific subspaces with the upper bound for DIPS and percentages for GRAD. As the problem becomes more difficult, CDP becomes increasingly important for searching a larger portion of the solution space, as it aims to search the entire solution space. In the worst-case scenario, CDP is the fastest technique to search the entire solution space. Hence, all algorithms have a goal and help each other achieve it as explained in Section 4. Additional experimental insights are described in the appendix.

We also report the empirical performance of CDP, which, as discussed earlier in this paper, determines the worst-case run time of SMART. We compared CDP to the dynamic programming algorithm IDP [Rahwan and Jennings, 2008] used by prior hybrid algorithms, and to the fastest dynamic programming algorithm to date, ODP [Michalak et al., 2016]. Notice that ODP, which stands for Optimal DP, is optimal in the sense that it evaluates a minimum number of coalitions to find the optimal solution, not in the sense of run time, meaning that the number of evaluated coalitions is optimal. This does not mean that the resulting run time is optimal. We also compared CDP to a parallel version of IDP (P-IDP). P-IDP uses the same technique presented in [Cruz et al., 2017] and uses two processes to evaluate the coalitions. The evaluation of the coalitions of the same size can be distributed because the coalitions of the same size are independent of each other. Hence, for every coalition size s, each process of PIDP evaluates half of the coalitions of size s. Table 1 shows the results. The run time of these algorithms depends only on the number of agents. As can be seen, CDP outperforms IDP by at least 50%. Moreover, CDP is also faster than ODP and P-IDP (See the appendix for the time difference between CDP and P-IDP). This experimentally confirms that SMART offers the best worst-case run time. This superior speed appears to translate into the superior practical performance of the SMART algorithm as well. With the most difficult distributions, such as Gamma (see Figure 4), the SMART algorithm is significantly faster than the other algorithms.

7 Conclusion

In this paper, we developed an optimal algorithm, SMART, for the coalition structure generation problem. Our method contributes and combines a number of ideas and techniques. First, we introduced several results concerning the choice of coalitions to evaluate. We used those results to build offline phases to optimize the choice of coalitions to evaluate. Second, we developed three techniques that have different pros. Two of them use the results of the offline phases. The third one uses branch-and-bound and integer partition graph search to explore the solution space. Finally, we combined these techniques by showing how they can assist one another during the search process. Experiments showed that SMART is faster than the fastest prior algorithms on all of the instance distributions for all numbers of agents.

Acknowledgments

Tuomas Sandholm's research is supported by the Vannevar Bush Faculty Fellowship ONR N00014-23-1-2876, National Science Foundation grant RI-2312342, ARO award W911NF2210266, and NIH award A240108S001.