Minimum Search to Establish Worst-Case Guarantees in Coalition Structure Generation

1 Introduction

An important feature of many multi-agent systems is the ability of agents to form coalitions in order to coordinate their actions and increase individual and collective performance. Coalition formation has been studied in many settings, including e-commerce ([Tsvetovat et al., 2000]), distributed vehicle routing ([Sandholm and Lesser, 1997]) or multi-sensor networks ([Dang et al., 2006]).

One of the key challenges in coalition formation is Coalition Structure Generation (CSG) - the problem of finding a coalition structure, i.e. an exhaustive and disjoint division of agents into coalitions, such that the performance of the entire system is optimised. In this context, it is usually assumed that the value of a coalition does not depend on the actions of nonmembers. Such settings are known as characteristic function games (CFGs). Many (but clearly not all) real-world multiagent problems happen to be CFGs [Sandholm et al., 1999; Sandholm and Lesser, 1997].

Finding the optimal coalition structure in a CFG setting is a challenging combinatorial problem as the number of possible solutions grows in O(nn ) for n agents. Various search techniques have been proposed to tackle this problem, including dynamic programming, linear programming, breadth-first search, depth-first search, and other heuristic and stochastic methods (see, e.g., [Shehory and Kraus, 1998; Sandholm et al., 1999; Sen and Dutta, 2000; Dang and Jennings, 2004; Rahwan et al., 2009b]). In this context, an important line of research is the development of anytime CSG algorithms. In particular, an algorithm is "anytime" if it can return a solution at any point of time during its execution, and the quality of its solution improves monotonically until termination. This is particularly desirable in the multi-agent system context since the agents might not always have sufficient time to run the algorithm to completion, especially when the search space of the problem at hand is of exponential size as in the CSG case. Moreover, being anytime makes the algorithm more robust against failure; if the execution is stopped before the algorithm would have normally terminated, then it would still provide the agents with a solution that is better than the initial solution, or any other intermediate one.

Thus, a fundamental open question in this line of research is the following [Sandholm et al., 1999]: If the space of possible solutions is too large to allow exhaustive search, then:

Can we search through only a subset of this space, and be guaranteed to find a solution that is within a desirable bound β from optimum? If so, what is the minimum such subset?

To date, the above question has only been partially answered by Sandholm et al. in their seminal work on anytime coalition structure generation [Sandholm et al., 1999]. More specifically, they only answered this question for two particular values of β: n and ⌈n/2⌉ (see the related-work section for more details). This question, however, remained open for other values of β.

Against this background, we provide in this paper the complete answer to the above question. That is, we identify the minimum subset of coalition structures that must be searched to establish any desirable bound β.

The paper is organized as follows. In the next section we formalize the coalition structure generation problem. We then present our main results in Section 3. In Section 4, we present a brief overview of the related work. Finally, in Section 5, we discuss new challenges that stem from our work.

2 Preliminaries

In this section we formally introduce the basic notation used throughout the paper. Let A = {a1, a2, · · · , an} be the set of agents and C the set of all coalitions. More formally, C = {C : C ⊆ A,C ̸= ∅}. A coalition structure CS = {C1, C2, · · · , C|CS|} is a partition of A, i.e., it satisfies the following conditions: (a) ∀i ∈ {1, · · · , |CS|},Ci ̸= ∅; (b) ∪|CS| i=1 Ci = A; and (c) ∀i, j ∈ {1, · · · , |CS|} : i ̸= j, Ci ∩ Cj = ∅. We will denote the set of all coalition structures as Πn.

A characteristic function assigns a real value v(C ) ∈ R to every coalition C ∈ C which reflects its performance. The value of any coalition structure CS ∈ Πn is the sum of the values of the coalitions in it, and is denoted as V (CS). Formally, ∀CS ∈ Πn, V (CS) = ∑C∈CS v(C ). The CSG problem is, then, to find an optimal coalition structure CS ∗ ∈ Πn, defined as:

Throughout the paper, we assume that the following holds:

In the appendix we demonstrate that the above assumption results in no loss of generality as far as the solution to the CSG problem is concerned. Laso in the appendix we summarise the main notations used throughout the paper.

3 Answering the Open Question

This section presents our main theorems. In particular, the first four of them are concerned with a generalized case, where two arbitrary sets of coalition structures Π′ , Π′′ ⊆ Πn are given, and the aim is to establish a bound β on the best solution in Π′ with respect to the best one in Π′′ . These four theorems lay the foundation to our final theorem, corollary of which constitutes the solution to the open question posed in the introduction.

In what follows we will need the following additional notation. For any coalition structure CS ∈ Πn, let P(CS) be the set of possible partitions of CS. That is,

For instance, given CS = {{a1}, {a2, a3}, {a4}}, the set P(CS) consists of the possible partitions of CS, which are: {{{a1}}, {{a2, a3}}, {{a4}}}, {{{a1}, {a2, a3}}, {{a4}}}, {{{a1}}, {{a2, a3}, {a4}}}, {{{a1}, {a4}}, {{a2, a3}}}, and {{{a1}, {a2, a3}, {a4}}}.

Moreover, for any set of coalition structures Π′ ⊆ Πn, let δ(Π′ ) be the set that consists of every non-empty subset of every coalition structure in Π′ . That is:

For example, given the following set of coalition structures: Π′ = {{{a1, a2}, {a3}}, {{a1}, {a2, a3}}}, the set δ(Π′ ) consists of all non-empty subsets of the two coalition structures in Π′ . In other words, it consists of following six subsets: {{a1, a2}}, {{a3}}, {{a1, a2},{a3}}, {{a1}}, {{a2, a3}}, and {{a1}, {a2, a3}}.

We start with proving the following:

Theorem 1 For any two sets of coalition structures Π′ , Π′′ ⊆ Πn, if:

then the following holds:

In other words, if the subsets in δ(Π′ ) can partition every coalition structure in Π′′ , then the best coalition structure in Π′ is within a bound from the best one in Π′′ . To compute this bound, we first compute for every coalition structure CS ∈ Π′′ the size of the smallest subset of δ(Π′ ) that partitions CS. The bound is then equal to the largest such size.

Proof. Assuming that condition (3) holds, let CS ∗ be the best coalition structure in Π′′ , and P ∗ = {P ∗ 1 , · · · , P ∗ |P ∗ | } be the smallest subset of δ(Π′ ) that partitions CS ∗ , i.e.,

Now, since P ∗ is a partition of CS ∗ , then we can write V (CS ∗ ) as follows:

This, in turn, implies that:

Furthermore, from (6), we know that:

From (7) and (8), we find that:

Moreover, since P ∗ ⊆ δ(Π′ ), then ∀P ∗ i ∈ P ∗ ∃CS ∈ Π′ : P ∗ i ⊆ CS. This implies that:

From (9) and (10), we find that there exists CS ∈ Π′ :

This, as well as (5), imply that (4) holds.

□

Secondly, we prove that the bound obtained in Theorem 1 cannot be improved upon.

Theorem 2 The bound in Theorem 1 is tight.

Proof. Given two sets of coalition structures Π′ , Π′′ ⊆ Πn such that condition (3) holds, we will construct a worst case where:

First, let us define ˜ CS and ˜ P = { ˜ P1, . . . , ˜ P | ˜ P|} as follows:

Based on this, we need to construct a worst case where:

Since ˜ P is a partition of ˜ CS, then we can write V ( ˜ CS) as follows:

Now assume that the following holds:

˜

In other words, assume that every Pi contains exactly one coalition, and let us denote this coalition as ˜ Ci. Also assume that:

Finally, assume that:˜

From equations (12), (13) and (14), we find that:

Now since ˜ P is the smallest partition of ˜ CS in δ(Π′ ), then this implies that:

From (13) and (16), we find that:

From (15) and (17), we find that (11) holds.

□

Thirdly, we prove that the condition in Theorem 1 is necessary to obtain a finite bound.

Theorem 3 For any two sets of coalition structures Π′ , Π′′ ⊆ Πn, condition (3) must hold in order to establish a finite bound on maxCS∈Π′′ V (CS )/ maxCS∈Π′ V (CS ).

Proof. Assume that condition (3) does not hold. In other words, assume that:

This implies that:

Now, from the definition of δ(Π′ ) in (2), we know that:

From (18) and (19), we find that:

In other words, there exists a coalition that does not appear in any of the coalitions in Π′ , but appears in at least one of the coalition structures in Π′′ . Now since this coalition could be arbitrarily better than every other coalition in C, then the coalition structures containing it could be arbitrarily better than those not containing it. □

While the above theorem is concerned with the necessary condition to establish a finite bound β, the following theorem is concerned with the necessary condition to establish a particular bound β = b, where 1 ≤ b ≤ n.

Theorem 4 For any set of coalition structures Π′′ ⊆ Πn, and for any b : 1 ≤ b ≤ n, in order to search a subset Π′ ⊆ Π′′ and be guaranteed to find a coalition structure of which the value is within a bound β ≤ b from maxCS∈Π′′ V (CS), it is necessary that Π′ satisfies the following condition:

Proof. Assuming that Π′ does not satisfy condition (21), we will prove that it is not possible to find a coalition structure in Π′ of which the value is within a bound β ≤ b frommaxCS∈Π′′ V (CS). In other words, we will prove that:

From Theorem 3, we know that Π′ must satisfy condition (3) in order to establish a finite bound on maxCS∈Π′ V (CS ). This, in turn, implies that the inequality in (4) holds (see Theorem 1). Finally, from Theorem 2, we know that it is possible to have a case where:

Based on this, as well as the fact that Π′ does not satisfy condition (21), we find that the inequality in (22) holds.

□

For any b : 1 ≤ b ≤ n, let Πbn ⊆ Πn be the minimum set guaranteed to contain a coalition structure of which the value is within a bound β ≤ b from the optimal one, i.e.:

Moreover, let In be the set of integer partitions of n and, for any integer partition I = {i1, · · · , i|I|} ∈ In, let SI ⊆ Πn be defined as follows:

In other words, SI contains every coalition structure containing coalitions of which the sizes match the integers in I. For instance, given n = 4, we have:

Now, our final theorem is as follows:

Theorem 5 For any b : 1 ≤ b ≤ n, there exists I ′n ⊆ In such that:

Proof. In order to prove Theorem 5, it is sufficient to prove that, for any I ∈ In, and for any two coalition structures CS ′ , CS ′′ ∈ SI , we will show that:

Now, for any coalition structure CS ∈ Πn, let us define Πn(CS) as follows:

Based on this, we have:

To this end, note that, for any subset ˜Π ⊆ Πn, there are exactly two properties based on which it is determined whether ˜Π = Πbn :

1. The number of coalition structures in ˜Π, i.e., | ˜Π|.
2. The ability of the elements in δ( ˜Π) to partition the coalition structures in Π\ ˜Π. This is measured as the maximum of the sizes of the smallest partitions of the coalition structures in Π\ ˜Π, where the parts of the partitions are elements of δ( ˜Π).

Now since both CS ′ and CS ′′ belong to the same subset SI , then, by only changing the indices of the agents, it is possible to transform CS ′ into CS ′′ . For example, given CS ′ = {{a1}, {a2}, {a3, a4}}, CS ′′ = {{a2}, {a4}, {a1, a3}}, it is possible to transformCS ′ into CS ′′ by only changing the indices of the agents such that a1, a2, a3 and a4 become a2, a4, a1 and a3 respectively, and that is because CS ′ and CS ′′ belong to the same subset S{1,1,2}. In a similar way (i.e., by only changing the indices of the agents) it is possible to transform any subset Π′ ∈ Πn(CS ′ ) into exactly one subset Π′′ ∈ Πn(CS ′′ ). What is particularly important is the fact that the above two properties are exactly the same for Π′ and Π′′ since the transformation only involved changing the agents' indices, and these do not have any effect on the above two properties. As a result, if Πbn ̸= Π′ , then Πbn ̸= Π′′ . This means:

From (25) and (26), we find that (24) holds.

□

Having introduced the above five theorems, for any integer partition I ∈ In, let us define P(I ) to be the set of possible partitions of I. That is,

For instance, given n = 4, the set P({1, 1, 2}) consists of the following four partitions: {{1}, {1}, {2}}, {{1, 1}, {2}}, {{1, 2}, {1}}, and {{1, 1, 2}}.

Moreover, for any set of integer partitions I ′n ⊆ In, let δ(I ′n ) be the set that consists of every non-empty subset of every integer partition in I ′n . That is:

For example, given I ′4 = {{1, 1, 2}, {1, 3}}, the set δ(I ′n ) consists of the following seven subsets: {{1}}, {{2}}, {{3}}, {{1, 1}}, {{1, 2}}, {{1, 3}}, {{1, 1, 2}}. Finally, let In(b) be defined as follows:

That is, In(b) consists of integer partitions such that, if we take every subset of every individual integer partition in In(b) - i.e., if we take every subset in ∪I∈In(b)δ(I ) - then these subsets are sufficient to partition every integer partition in In into at most b parts.

Now, we obtain from Theorems 1-5 the following corollary:

Corollary 1 For any b : 1 ≤ b ≤ n, it holds that:

Equation (29) provides the complete answer to the open question, i.e., it identifies Πbn - the minimum subset of the coalition structure space that is guaranteed to contain at least one coalition structure of which the value is within a bound β = b from the value of the optimal coalition structure, where 1 ≤ b ≤ n. 1

4 RelatedWork

In this section, we discuss the relevant anytime approaches to the CSG problem. 2 In particular, these can be divided into two categories:

1. The first tries to improve the quality of the solution as quickly as possible using various search techniques. Arguably, the state-of-the-art algorithm in this category is the IP algorithm by Rahwan et al. [Rahwan et al., 2009b]. While this algorithm does generate an initial bound of ⌈n/2⌉ on its solution quality, the process of improving upon this bound depends entirely on the values of the characteristic function. Thus, in a general case, there are no guarantees on how this bound will drop over time, if it drops at all.
2. In the second category, the search process consists of a number of steps such that, at each step, a particular subset of the search spaces is searched. This is designed such that, after completing particular steps, the bound is guaranteed to drop to a certain value.

Since our approach belongs to the latter category, we will discuss the algorithms that belong to it in more detail. In particular, the first such study is due to Sandholm et al. [Sandholm et al., 1999], who showed that the minimum subset of coalition structures that has to be searched in order to establish any theoretical worst-case bound contains 2n-1 coalition structures, which are those containing less than three coalitions. In this case, β = n. Interestingly, they also showed that, by searching one more coalition structure, which is the one containing n coalitions, the bound drops to ⌈n/2⌉. After that, to drop the bound below ⌈n/2⌉, the authors proposed to search the remaining coalition structures as follows. They first search the subset containing all the coalition structures that are made of exactly n1 coalitions, then the subset containing all those that are made of n - 2 coalitions, and so on and so forth.

An alternative sequence to drop the bound below ⌈n/2⌉ was proposed by Dang and Jennings [Dang and Jennings, 2004]. In more detail, they search through the subsets containing coalition structures that have at least one coalition of which the size is not less than ⌈n(d1)/d⌉, where d is first equal to ⌊(n + 1)/4⌋, and then equal to ⌊(n + 1)/4⌋ - 1, and so on until d = 2. It was shown that the bound drops for every d.

More recently, Rahwan et al. [Rahwan et al., 2009a] analysed the issue of establishing worst-case bounds in partition function games (PFGs) - a more general type of games where a coalition can have different values in different coalition structures due to externalities (i.e., influences caused by the formation of other coalitions). More specifically, Rahwan et al. proposed two sequences to establish progressively better bounds in PFG+ and PFG- - two special cases of PFGs where all externalities are weakly positive and weakly negative respectively. Although these sequences are designed to suit specific requirements of either PFG+ or PFG-, in principle, they can also be used in CFGs as CFG ⊂ PFG+ and CFG ⊂ P FG-.

1 Note that it is impossible to obtain a finite bound greater than n [Sandholm et al., 1999]. Moreover, the bound, by definition, cannot be smaller than 1.

2 For an overview of other approaches, see [Rahwan et al., 2009b]

Given 9 agents, we provide in Table 1 the numbers of coalition structures searched by each of the above algorithms to establish different bound β, and compare these to the optimal numbers obtained using equation (29). This shows that none of the sequences proposed in previous works is optimal. For example, to find a coalition structure that is guaranteed to be within a bound β = 3 from the optimum, the number of coalition structures that has to be searched by Rahwan et al.'s algorithm is 1132, and by Sandholm et al.'s is 755 and by Dang and Jennings's is 2393. However, following equation (29), we find that the minimum subset, which is:

contains only 671 coalition structures.

5 Discussion

By solving the open question that was posed in the introduction, we open a new one. In particular, the new question is related to the computational complexity of identifying the coalition structures that belong to Πbn given any value of n and b. As can be seen from equation (29), the challenge is as follows:

For any value of n and b, how to efficiently compute a subset I ′ of the integer partitions of n such that:

• by solely using every possible subset of every I ∈ I ′ , we can partition every integer partition of n into at most b parts? and
• if there are more than one such subset, how to efficiently compute the one for which the union of the corresponding subspaces of the integer partitions is of minimal size?

Note that the solution to the above question involves solving several Set Partitioning Problems (SPPs) which are each NP-hard [Garey and Johnson, 1990]. We envisage that this question will trigger significant interest in the research community. In this context, it should be observed that the minimum subsets have to be computed only once as they are independent of coalition values. Thus, once computed for a certain number of agents (e.g., n = 25), they can be stored and re-used whenever a problem is encountered that has that same number of agents.

Acknowledgments

Tomasz Michalak acknowledges support from the EPSRC under the project ALADDIN (Autonomous Learning Agents for Decentralised Data and Information Systems) project and is jointly funded by a BAE Systems and EPSRC strategic partnership.

A Summary of Notation

• β Bound from the optimum.
• A The set of agents.
• ai An agent in A.
• n The number of agents in A.
• C A coalition.
• C The set of all coalitions over A.
• CS A coalition structure.
• P(CS) The set of possible partitions of CS.
• CS ∗ An optimal coalition structure.
• Π A set of coalition structures.
• Πn The set of all coalition structures for n agents.
• Πbn A minimum set guaranteed to contain a coalition structure of which the value is within a bound β = b from the optimum.
• δ(Π) The set that consists of every non-empty subset of every coalition structure in Π.
• I An integer partition.
• In The set of integer partitions of n.
• SI The subspace of coalition structures in which the sizes of the coalitions match integers in I.
• P(I) The set of possible partitions of I.
• δ(In) The set that consists of every the non-empty subset of every integer partition in In.

B Note on the Assumption in (1)

We will show how any real-valued characteristic function bounded from below (i.e. without infinitely negative values of coalitions) can be transformed so as to meet the condition in (1). While such a transformation can be done by simply subtracting from every coalition's value the following amount: minCS∈Πn v(C ) (see, e.g., [Sandholm et al., 1999; Ohta et al., 2009]), we note that this may result in a significant change to the CSG problem. Specifically, the value of any coalition structure containing s coalitions would increase by s × abs(minCS∈Πn v(C )), where abs(·) denotes the absolute value. Since this increase differs from one coalition structure to another, the optimal solution to the CSG problem may change. To circumvent this problem, we propose to transform the characteristic function as follows:

By so doing, the value of every coalition structure increases by exactly the same amount, which is the absolute value of:

n × min(0, minC∈C v(C )). Thus, it will not change (an) optimal coalition structure(s). Nevertheless, it may affect the ratio between value of any suboptimal coalition structure and the optimal one(s). 3