Coalition Structure Generation in Multi-Agent Systems with Positive and Negative Externalities

1 Introduction

One of the important issues in multi-agent system research is to generate a coalition structure , i.e. an exhaustive and disjoint division of the set of agents, such that the outcome of the entire system is maximised. Usually, this coalition structure generation (CSG) problem is dealt with in Characteristic Function Games (CFGs), where the value of a coalition is not affected by the way non-members are partitioned (see, e.g., [Shehory and Kraus, 1998; Sandholm et al., 1999; Dang and Jennings, 2004; Rahwan and Jennings, 2008; Rahwan et al., 2009]). However, even under this strict assumption, the CSG problem has been shown to be NP-complete [Sandholm et al., 1999]. Given this, a number of approaches have been proposed to help circumvent this complexity, including the use of anytime algorithms. Specifically, such an algorithm generates an initial solution that is guaranteed to be within a certain bound from the optimum, and then improves the quality of its solution as it searches more of the search space, and establishes progressively better bounds until an optimal solution is found. Although these algorithms might, in the worst case, end up searching the entire space (i.e. they run inO(nn )), the anytime property has a number of advantages. First, an outcome is delivered relatively quickly and, second, the algorithm is more robust against failure due to premature termination. All anytime CSG algorithms take advantage of the property of CFGs that the value of a particular coalition is always the same in every possible coalition structure. Although this assumption is valid in many environments, there exist a number of cases in which the performance of one coalition may be directly influenced by the cooperative arrangements of the other agents in the system. For instance, in resource allocation problems, a coalition that increases resource consumption in one part of the system can be detrimental to the agents' effectiveness in another part. In such cases, CFGs are not appropriate and much more general Partition Function Games (PFGs) have to be applied. In PFGs a coalition's value may depend on the formation of another coalition in a system. More formally, given two coalition structures: CS and CS′ such that C1, C2, C3 ∈ CS and C1, (C2 ∪ C3) ∈ CS′ , the value of C1 may be different in CS than in CS′ due to the merge of C2 with C3. Such an effect is usually referred to as an externality induced upon C1 by the merge of C2 and C3 and the formation of coalition C2 ∪ C3. In this context, only one CSG algorithm has been proposed [Michalak et al., 2008], which deals with two classes of PFGs, denoted PF + sub and PF - sup . Specifically, in PF + sub a merger of any two coalitions decreases their joint value (or keeps it constant), and increases the values of other coalitions in the structure (or keeps them constant). In other words, the coalition values are weakly sub-additivite 1 and the externalities are positive (or equal to zero). Conversely, PF - sup is the class in which the values are weakly super-additive, and the externalities are negative (or equal to zero).

Both PF + sub and PF - sup are very popular in economics and other social sciences where interdependencies between coalitions constitute, in many cases, the core of the analysed problem. Examples include Research & Development coalitions among pharmaceutical companies or various forms of international (macroeconomic/environmental) policy coordination. When two companies decide to jointly develop a new drug, their market share is likely to increase, whereas the market position of other companies is likely to decrease. Conversely, countries which decide to join international agreements and limit their emissions may hamper their economic growth (sub-additivity property) but, at the same time, they may have a positive influence on the rest of the world. Clearly, modeling the above phenomena with CFGs would be inappropriate and PFGs should be applied instead. Examples of systems with externalities can also be found in multi-agent system contexts. As more commercial activity moves to the Internet, we can expect online economies and societies to become increasingly sophisticated, as is happening, for instance, with real time electronic purchase of wholesale telecommunications bandwidth or computer processor resources. In such contexts, ad hoc coalition formation will need to allow for coalition externalities in as broad a sense as possible. In fact, even PF + sub and PF - sup classes are too strict to model a number of environments. For instance, a merger of a coalition in a multi-agent system may be profitable when coalitions are relatively small. However, if the size and extent of a created group results in communication problem, the cost of cooperation may exceed profits. 2 In other words, such systems are likely to meet neither super- nor sub-additivity properties.

1 Recall that weak sub-additivity refers to the case where, given any two coalitions C1,C2, and given any coalition structure CS ⊇ {C1,C2}, we have: V (CS) ≤ V (CS′ ), where CS′ = (CS\{C1, C2}) ∪ {C1 ∪C2}. On the other hand, weak super-additivity refers to the case where V (CS) ≥ V (CS′ ).

Against this background, in this paper, we deal with two significantly broader classes of PFGs created from PF + sub and PF - sup by removing the assumption of super- and subadditivity. For these two classes, denoted PF + and PF -, we develop a number of techniques to solve the CSG problem in an anytime fashion. In particular:

• The first challenge related to PF + and PF - is caused by the fact that, in the presence of externalities, a coalition's value may differ from one structure to another. However, we show how to compute upper and lower bounds on the values of all feasible coalitions in the system (Section 3);
• We identify the minimum set of coalition structures that needs to be searched in order to establish a worst-case guarantee on solution quality (Section 4);
• We develop a novel algorithm for improving the worstcase guarantee with further search (Section 5);
• We develop a preprocessing algorithm that prunes parts of the search space (Section 6.1); and
• We propose a revised version of the state-of-the-art anytime CSG algorithm [Rahwan et al., 2009], called IP+/-, that can be applied in our PF +/PF - setting (Section 6.2).

Since there are no previous algorithms that improve worstcase guarantees in PF +/PF -, we benchmark our algorithm against the state-of-the-art CFG algorithms that were developed for this purpose. Note that CFGs are a special case of PF +/PF - and, therefore, the bounds provided by our algorithm hold even in a CFG setting. Surprisingly, we find that our algorithm outperforms the other algorithms by orders of magnitude. This is despite the fact that the other algorithms take advantage of the special properties of CFGs, while ours does not. Moreover, unlike Michalak et al. [2008] who could not test their algorithm for more than 10 agents (because of the inefficient way by which they generate random instances of their problem), we develop an efficient function for generating random instances of PF +/PF -, which enables us to test our IP+/- algorithm for up to 20 agents (Section 7.2).

2 Such a situation occurs, for instance, when the number of users of a local network increases over its optimal capacity.

2 Basic Definitions

Given a coalition C and a coalition structure CS, we denote by v(C,CS) ≥ 0 the value of C in CS, and denote by V (CS) = ∑C∈CS v(C, CS) the value of CS. Moreover, given the set of n agents, A = {a1, a2, ..., an}, and a coalition C, we denote by C the agents in A that do not belong to C (i.e. C = A\C).

We define a partition of C as a set containing disjoint coalitions of which the union equals C. The value of a partition is defined as the sum of the values of all the coalitions in that partition. We denote by V (P, CS) the value of partition P in CS (i.e. V (P, CS) = ∑p∈P V (p, CS)), and denote by PC the set of all the possible partitions of C. 3

We denote by Is : s ∈ N the set of possible integer partitions of s, 4 and denote by SI : I ∈ In the sub-space containing all the coalition structures within which the coalition sizes match the parts of the integer partition (e.g. given 4 agents, S[1,1,2] contains every coalition structure in which two coalitions are of size 1, and one coalition is of size 2). Moreover, we denote by G(Is) the integer partition graph 5 of s. Finally, given a set (or a multiset) Π, we denote by |Π| the cardinality of Π.

3 Computing Upper and Lower Bounds

In this section, we show how to compute upper and lower bounds on the value of any partition or coalition. This is important since these bounds are going to be used in every step of the CSG process.

Theorem 1 Consider a PF - (PF +) setting. Given a coalition C ⊆ A, a partition P ∈ PC, and a coalition structure CS ⊇ P , the following holds, where C = {a1, ..., a|C| }:

Proof. To simplify notation, let CS′ = {C} ∪ P and let CS′′ = {{a1}, ..., {a|C| }} ∪ P . Also, without loss of generality, assume that CS ̸= CS′ and CS ̸= CS′′ . Then, given a PF - (PF +) setting, we first need to prove that:

Beginning with CS, one could reach CS′ by performing multiple steps, each involving the merging of two coalitions into one. After each step, the coalitions in P remain unchanged and, due to negative (positive) externalities, their values can only decrease (increase). As a result, the inequality in (1) holds. Similarly, beginning with CS′′ , it can be proved that the following holds: V (P, CS) ≤ (≥) V (P, CS′′ ).

3 Note that if C = A, then any partition of C would be a coalition structure, and PA would be the set of all possible coalition structures.

4 Recall that an integer partition of s is a multiset of positive integers (called parts) that add up to exactly s. For presentation clarity, we use square brackets throughout this paper (instead of curly ones) to represent integer partitions.

5 For more details on this graph, see [Rahwan and Jennings, 2008].

□

As opposed to Michalak et al. [2008] who bound the value of any given coalition C, Theorem 1 bounds the value of any given partition of C. Specifically, for every partition P ∈ PC, the upper and lower bounds can be computed in a PF - (PF +) setting as follows, where C = {a1, ..., a|C| }:

Note that, by assuming that P = {C}, it is possible, using the above equations, to compute an upper bound UBC and a lower bound LBC on the value of any coalition C. Moreover, given an integer partition I ∈ Is : s ≤ n, if we denote by SI the set of partitions within which the coalition sizes match the parts in I, then we can compute upper and lower bounds (denoted UBI and LBI respectively) on the values of the partitions in SI : 6

4 Establishing aWorst-Case Bound β

Having computed upper and lower bounds for coalition values, we now show how these can be used to identify the minimum search required to establish a worst-case ratio bound β from the optimum. In order to do so, we will use the following theorem:

Theorem 2 Let X be a set of elements, and let Ys be a set containing subsets of X such that: ∀y ∈ Ys, |y| ≤ s. Moreover, for all x ∈ X, y ∈ Ys, let us define v(x, y) ≥ 0 as the value of x in y, and let us define V (y) = ∑x∈y v(x, y) as the value of y. Then, for any Y ′ s ⊆ Ys, if:

then the following holds:

In other words, if every element in x appears with its maximum value in one, or more, of the subsets in Y ′ s , then the best subset in Y ′ s is within a ratio bound β = s from the best subset in Ys.

Proof. Let y∗ , y∗∗ be the best subset in Ys, Y ′ s respectively, i.e. y∗ = argmaxy∈Ys V (y) and y∗∗ = arg maxy∈Y ′ s V (y). Then, assuming that (2) holds, we need to prove the following:

6 Note that SI : I ∈ In refers to the set of coalition structures that match I, while SI : I ∈ Is : s ≤ n refers to the set of partitions that match I.

To this end, let x∗ be defined as: x∗ = arg maxx∈y∗ v(x, y∗ ). Since y∗ contains at most s elements, then the following holds:

Moreover, from (2), we know that there exist y′ ∈ Y ′ s such that x∗ ∈ y′ and:

Since the value of y′ is the sum of the values of the coalitions in y′ , and since x∗ ∈ y′ , then:

Finally, from the definition of y∗∗ , we know that:

From (3), (4), (5) and (6), we find that:

Having proved Theorem 2, we now show how it can be used while proving the main theorem for establishing a ratio bound β:

Theorem 3 To establish a bound β on the value of a coalition structure given a PF + setting, every sub-space SI : I ∈ In : |I| ≤ 2 must be searched. With this search, the number of coalition structures searched is 2n-1 , and the bound β = n. On the other hand, given a PF - setting, every sub-space SI : I ∈ {[n], [n - 1, 1], [n - 2, 1, 1], · · · , [1, 1, · · · , 1]} must be searched. With this search, the number of coalition structures searched is 2n - n + 1, and β = ⌈ n2 ⌉

Proof. To establish a bound, the maximum possible value of each coalition C has to be observed (in some coalition structure). Given a PF + setting, the only coalition structure in which C is guaranteed to have its maximum value is {C,A\C}. Based on this, the sub-spaces SI : I ∈ In : |I| ≤ 2 must be searched, and these contain 2n-1 coalition structures.

To prove that β = n, we use Theorem 2, and that is by considering X to be the set of coalitions, Yn to be the set of coalition structures 7 , and Y ′n to be the union of the sub-spaces SI : I ∈ In : |I| ≤ 2. In more detail, since every element in X appears with its maximum value in one, or more, of the coalition structures in Y ′ s , then the best coalition structure in Y ′ s is within a ratio bound β = n from the best coalition structure in Yn (see Theorem 2).

On the other hand, given a PF - setting, the only coalition structure in which C is guaranteed to have its maximum value is: {C, {a1}, ..., {a|C| }}, where {a1} ∪ ... ∪ {a|C| } = C. Based on this, SI :∈ {[n], [n - 1, 1], [n - 2, 1, 1], ..., [1, 1, ..., 1]} must be searched. With this search, the number of searched coalition structures would be 2n n+1 since every possible coalition appears in a unique coalition structure, except for the singleton ones (which all appear in a single coalition structure).

7 This is possible since every coalition structure is a subset of X containing at most n of the elements (i.e. coalitions) in X.

As in the PF + case, we use Theorem 2 to prove that β = ⌈ n2 ⌉. Here, however:

• We consider X to contain all the possible coalitions, as well as the possible partitions that contain singletons. For example, given 3 agents, X contains all the possible coalitions of size 3, as well as {{a1}, {a2}}, {{a1}, {a3}}, {{a2}, {a3}} and {{a1}, {a2}, {a3}}. Note that the maximum possible value of each one of these partitions has been observed in S[1,··· ,1] (see Theorem 1).
• We consider the singletons in every coalition structure to be grouped together (e.g. {{a1}, {a2}, {a3, a4}, {a5, a6}} becomes {{{a1}, {a2}}, {a3, a4}, {a5, a6}}). Based on this, we can consider Y⌈n/2⌉ to be the set of coalition structures (because any coalition structure now contains at most ⌈n/2⌉ elements fromX).

The above three points imply that the best coalition structure in Y ′ ⌈n/2⌉ is within a ratio bound β = ⌈n/2⌉ from the best coalition structure in Y⌈n/2⌉, and that is because every possible element in X appears with its maximum value in Y ′ ⌈n/2⌉ .□

Note that, in CFGs, it is sufficient to search levels 1 and 2 of the coalition structure graph in order to bound β [Sandholm et al., 1999]. However, it is also possible to bound β by searching any other set of coalition structures as long as every coalition appears at least once in this set. On the other hand, given a PF - setting, it is necessary to search SI : I ∈ {[n], [n - 1, 1], [n - 2, 1, 1], · · · , [1, 1, · · · , 1]} and, given a PF + setting, it is necessary to search SI : I ∈ In : |I| ≤ 2 (see Theorem 3).

5 Improving theWorst-Case Bound β

In this section, we present a novel anytime algorithm that reduces the ratio bound β with further search. This algorithm is based on the following observation (which is a direct result of Theorem 2): If we consider X to be the set of all possible coalitions, and Yn to be the set of all possible coalition structures, and if Y ′n ⊆ Yn is a set of coalition structures in which the maximum value of every element in X appears at least once, then by searching through Y ′n , we end up with a solution that is within a ratio bound β = n from the optimal coalition structure.

Based on the above observation, the ratio bound β can be reduced by using the following two main steps:

1. Add certain partitions to X and, in every coalition structure, group the coalitions that match any of those partitions. This is done such that the maximum number of elements from X that can appear in a single coalition structure drops to m < n. Given 3 agents, for example, the possible structures are: {{a1, a2, a3}},
2. {{a1}, {a2, a3}}, {{a2}, {a1, a3}}, {{a3}, {a1, a2}} and {{a1}, {a2}, {a3}}. Now, suppose that X contains every possible coalition. Then, if we add the partition {{a1}, {a2}} to X, and we group the coalitions that match this partition (i.e. {{a1}, {a2}, {a3}} becomes {{{a1}, {a2}}, {a3}}), then the maximum number of elements from X that can appear in a single coalition structure drops from 3 to 2.
3. For every partition P that was added to X, examine the coalition structure in which P appears with its maximum value. More specifically, given a PF - setting, examine the coalition structure CS = {{a1}, · · · , {a|C| }} ∪ P and, given a PF + setting, examine CS = {C} ∪ P (see Theorem 1). In so doing, we would have searched through a set of coalition structures in which the maximum value of every element in X appears at least once. This, in turn, reduces the ratio bound to m (see Theorem 2).

6 Searching the Sub-Spaces

We now present two algorithms for searching the sub-spaces. The first is a preprocessing algorithm that prunes some of the sub-spaces by comparing their upper and lower bounds (Section 6.1), while the second is a revised version of Rahwan et al.'s [2009] IP algorithm, which we call IP+/-, that uses the preprocessing algorithm, and solves the CSG problem in PF +/PF - settings (Section 6.2).

6.1 Preprocessing

Before detailing the preprocessing algorithm, we first discuss its underlying theoretical background. In particular, the main theoretical results upon which we build are as follows:

Lemma 1 Given the integer partition graph of s (i.e. G(Is)), let G(Is)s′ denote the part of G(Is) in which every node (i.e. integer partition) contains at least s′ integers that are equal to 1 (where s′ < s). Then, if we remove those s′ parts from every node in G(Is)s′ , then G(Is)s′ becomes identical to G(Is-s′ ).

An example is shown in Figure 1. What is interesting is that, by removing [1, 1] from every node in G(I6)2 for example, then we will not only get all the integer partitions in I4, but these integer partitions will also be ordered and connected in exactly the same way as they are in G(I4). This particular observation will be used in our preprocessing algorithm as we will see later in this section. Now, we give the main theorem:

Theorem 4 Consider a PF - (PF +) setting. Then, given a coalition C ⊆ A and a partition P ∈ PC, any coalition structure containing P can be pruned from the search space if there exists another partition P ′ ∈ PC such that:

Proof. Given a PF - (PF +) setting, and given two partitions P, P ′ ∈ PC such that: ∀p′ ∈ P ′ , ∃p ∈ P : p′ ⊆ (⊇) p and UBP ≤ LBP ′ , we will prove that, for any coalition structure CS ⊇ P, there exists another coalition structure CS′ such that V (CS) ≤ V (CS′ ).

Since P is a partition of C, then CS\P must be a partition of C. In particular, let P = CS\P, then of course, CS = P ∪ P. Now, by replacing P with P ′ , we end up with a different coalition structure, denoted CS′ , such that: CS′ = P ′ ∪P. In this case, we have:

Since we have: ∀p′ ∈ P ′ , ∃p ∈ P : p′ ⊆ (⊇) p, then every coalition in P ′ (P) is a subset of some coalition in P (P ′ ). Based on this, as well as the fact that P and P ′ are partitions of the same coalition, we find that P (P ′ ) can be reached from P ′ (P) by performing multiple steps, each involving the merging of two coalitions from P ′ (P). This, in turn, implies that CS (CS′ ) can be reached fromCS′ (CS) by performing merging steps that do not involve any of the coalitions in P. As a result, and due to negative (positive) externalities, we have:

On the other hand, since UBP ≤ LBP ′ , then we have:

From (7), (8) and (9), we find that V (CS) ≤ V (CS′ ). This, in turn, implies that CS can be pruned from the search space.

□

From Theorem 4, we can see that the following lemma holds:

Lemma 2 Consider a PF - (PF +) setting. Then, given an integer partition I ∈ Is : s ≤ n, any sub-space represented by an integer partition G ∈ In : I ⊆ G can be pruned from the search space if there exists another integer partition I ′ ∈ Is such that:

The condition ∀i ∈ I (I ′ ), ∃J ⊆ I ′ (I) : ∑j∈J = i in Lemma 2 implies that the number of parts in I is smaller (greater) than the number of parts in I ′ , and that I and I ′ are connected in the integer partition graph of s via a series of nodes belonging to consequent levels of the graph. In this case, we use the notation: I → I ′ (I ′ → I). In Figure 1, for example, we have: [1, 5] → [1, 1, 1, 1, 2].

We can now show how both Lemma 1 and Lemma 2 are used in our preprocessing algorithm to prune sub-spaces (see Algorithm 1). In short, the algorithm tries to find the integer partitions in I2 that can be pruned using Lemma 2, and then moves to I3, and then I4, and so on until it reaches In. The way it moves from Is-1 to Is is done using the observation from Lemma 1. More specifically, the algorithm adds [1] to every integer partition in Is-1, and then combines the resulting integer partitions with those in Is that do not contain any 1. To generate the integer partitions of s that do not contain any 1, we use getIntParts(s, 2). This function is implemented using the parta algorithm [Riha and James, 1974], which is the state-of-the-art for generating doubly-restricted 8 integer partitions.

6.2 The IP+/- algorithm

In this section, we briefly describe the original IP algorithm, and then show how it can be revised for the PF +/PF - case.

IP: Let Maxs and Avgs be the maximum and average value of the coalitions of size s respectively. Then, for all I ∈ In, the IP algorithm computes upper and lower bounds on the value of the best coalition structure in SI as follows: UBI = ∑s∈I Maxs, LBI = ∑s∈I Avgs. 9 These bounds are then used to identify any sub-spaces that have no potential of containing a solution better than the current best one (in which case they are pruned from the search space). As for the remaining sub-spaces, IP searches them one at a time, unless a value is found that is higher than the upper bound of another sub-space, in which case, that sub-space no longer needs to be searched. The order in which the algorithm searches through these sub-spaces is based on their upper bounds (i.e. it starts with the one with the highest upper bound, and then the second-highest and so on). Searching a sub-space SI : I = [i1, i2, ..., i|I|] is carried out using depthfirst search combined with branch-and-bound. Basically, for every coalition of size i1, denoted C1, the algorithm finds the coalitions of size i2 that do not overlap with C1, and for every such coalition, denoted C2, the algorithm finds the coalitions of size i3 that do not overlap with C1 and C2, and so on. This is repeated until we reach the coalitions of size i|I| that do not overlap with C1,C2, ...,C|I|-1. For every such coalition, denoted C|I|, we would have a coalition structure CS = {C1, ...,C|I|} ∈ SI. This process is repeated in such a way that is guaranteed to go through every coalition structure in SI exactly once. To speed up the search, IP applies a branch-and-bound technique as follows. If we denote by CS∗∗ the best coalition structure bound so far, then, before the algorithm goes through the coalitions of size ix that do not overlap with C1, ...,Cx-1, it checks whether the following holds: 10

8 Unlike restricted integer partitions, where the parts are only bounded by a maximum value, doubly-restricted integer partitions consist of parts that are also bounded by a minimum value. getIntParts(s, 2) sets the minimum value to 2 so that the resulting integer partitions do not contain any 1.

9 Interestingly enough, Rahwan et al. [2009] proved that this lower bound is actually the average value of all the solutions in SI .

If the above holds, then there is no need to go through any of the coalitions of size ix that do not overlap with C1, ..., Cx-1. This is because any coalition structure containing C1, ...,Cx-1 cannot possibly be better than CS∗∗ . This simple branch-and-bound technique has proved to be very effective in CFGs (see [Rahwan et al., 2009]).

IP+/-: The main difference in our PF -/PF + setting (compared to a CFG setting) is that, instead of having one value for every coalition C, we now have a maximum value UBC and a minimum value LBC (see Section 3 for more details). Based on this, IP+/- differs from IP in the following ways:

• It uses the preprocessing algorithm from Section 6.1.
• It computes Maxs and Avgs as follows: ∀s ≤ n,Maxs = maxC⊆A:|C|=s UBC and Avgs = avgC⊆A:|C|=sLBC .
• The order in which it searches through sub-spaces is based on our anytime algorithm for reducing the ratio bound β (i.e., it always searches the sub-spaces that are necessary to drop the current ratio bound).
• While searching a sub-space SI : I = [i1, i2, ..., i|I|], and before going through the coalitions of size ix that do not overlap with C1, ...,Cx-1, the algorithm checks whether the following holds, where UB{C1,...,Cx-1} is computed as in Section 3:

7 Performance Evaluation

In this section, we evaluate our anytime algorithm for improving the ratio bound, as well as our IP+/- algorithm.

10 Here, v(C) is used (instead of v(C, CS)) to refer to the value of C in CS. This is because IP deals with CFGs where every coalition has one value, regardless of the coalition structure to which it belongs.

7.1 Evaluating the Anytime Ratio Bound Algorithm

Figure 2 shows on a log scale the ratio bound β as a function of the number of searched coalition structures, and that is for 24 agents. As can be seen, given a PF + setting, our algorithm is significantly faster than the existing CFG algorithms. For example, the number of coalition structures required by our algorithm to establish a ratio bound β = 3 is only 0.00003% of that required by Sandholm et al. [1999], and only 0.9% of that required by Dang and Jennings [2004]. On the other hand, given a PF - setting, the algorithm requires searching more coalition structures (compared to other algorithms) in order to establish its first ratio bound (see Theorem 3). However, once it establishes its first bound, which requires searching less than 4×10-11 of the space, it becomes significantly faster than the other algorithms. For example, the number of coalition structures to establish a ratio bound β = 3 is only 0.00002% and 0.5% compared to Sandholm et al.'s and Dang and Jennings's, respectively.

7.2 Evaluating IP+/-

In order to evaluate our IP+/- algorithm, we need to be able to efficiently generate random instances of PF +/PF -. To this end, let us assume, without loss of generality, that the agents in every coalition are ordered ascendingly, and that the coalitions in any partition are also ordered ascendingly based on the smallest 11 agent in each coalition. Now, let l(ai,C) denote the location of agent ai in C (e.g., l(a6, {a2, a5, a6, a9}) = 3), and let l(ai, P) denote the location of the coalition in P that contains ai (e.g., l(a6, {{a1, a7}, {a3, a5, a6}, {a4, a9}}) = 2). With these definitions in place, we now show how to generate the coalition values such that the PF - (PF +) condition is met. At first, for every coalition C, we generate the following non-negative random values: vC and eC and eC,1, eC,2, · · · , eC,|C| such that ∑|C| j=1 eC,j = eC. After that, for any coalition structure CS ∋ C, we set the value of C as follows:

11 For any two agents ai, aj ∈ A, we say that ai is smaller than aj if i < j.

In more detail, vC represents the value of coalition C in the absence of any externalities, while the remainder of the left hand side of (10) represents the externality induced upon C in CS. Note that this externality is always smaller than, or equal to, eC. This comes from the fact that: ∀ai ∈ C : l(ai, CS\{C}) ≥ 1, which implies that:

Theorem 5 By setting the value of each coalition as per equation (10), we end up with a PF - (PF +) setting. 12

Next, we analyze the memory required to store the input. As opposed to [Michalak et al., 2008], where a value must be stored for every pair (C, CS) : C ∈ CS, using equation (10) only requires storing vc and eC,1, eC,2, · · · , eC,|C| for every coalition C. Thus, given n agents, the total number of values to be stored is computed as follows, where n! is the factorial of n:

This is significantly smaller, compared to the number of values stored by Michalak et al. (e.g. 0.000000007% given 25 agents).

In our experiments, vC is generated using a normal distribution, while eC is generated using a uniform distribution as follows: e ∼ U(a, b), where a = 0 and b = vC.

Given 20 agents, Figure 3 shows on a log scale how the quality of our solution improves over the running time. 13 As can be seen, the solution quality grows very rapidly (e.g. it reaches 94% within only one second). Moreover, an optimal solution is reached within only 5% of the total running time, while the rest of the time is spent trying to verify that the found solution is indeed optimal.

8 Conclusions

The coalition structure generation problem is usually studied in the context of characteristic function games where no externalities are allowed. However, in many cases externalities do exist and need to be accounted for. In this paper, we presented a number of important results for such partition function games: we showed how to bound coalition values in games with positive or negative externalities, identified the minimum amount of search required to establish a worst-case bound from the optimal solution, developed a novel algorithm for improving that bound with further search, and showed that it outperforms existing approaches by orders of magnitude. By so doing, we have laid the foundation for further work on this important setting. In particular, we are keen to develop an efficient approach to systems that posses mixed characteristics and cannot be neatly categorized to only one class.

12 The proof of Theorem 5 is omitted from the paper due to space limitations.

13 The PC on which we ran our experiments had 4 processors (each is an Intel(R) Xeon(R) CPU @ 2.66 GHz), with 3GB of RAM.