Lemma 1 ([13]). Given two coalition structures A, B ∈ M(N), with A 6= B**, then**
A can be transformed into B by doing at most n − 1 **applications of the SPLIT or** the MERGE rules.

Lemma 2 ([13]). Given two coalition structures A, B ∈ M(N), with A 6= B**, then**
A can be transformed into B by doing at most n−1 **applications of the SHIFT rule.**
Now we can define the coalition structure problem as follows.

Definition 3 (Coalition structure generation problem). **Given a set of agents** A,
the coalition structure generation **problem is to maximize the social welfare of the** agents by finding a coalition structure C
∗ **= arg max**C∈M(A) v(C).

Formally, a CSG problem may be formulated as a set partitioning problems
(SPP). Let I = {1, . . . , m} be a set of objects, and let {P1, . . . , Pn} **be a collection**
of subsets of I**, with a cost** cj ∈ R
+ associated with each subset Pj **. Given a** n × m binary matrix A = {aij}, where aij = 1 if i inPj and aij = 0 otherwise, let Jb **be a**
solution of SPP represented as the n-dimensional vector ~x = hxi, . . . , xni **of binary**
decision variables. An integer programming formulation of the set partitioning problem is

$$z(x)=\operatorname*{max}\sum_{j=1}^{n}c_{j}x_{j}$$
subject to $\sum_{j=1}^{n}a_{ij}x_{j}=1,i=1\ldots m$.  
Given n **agents, the size of the input to a CSG algorithm is exponential, since**
it contains the values v(·) associated to each of the (2n − **1) possible coalitions.**
Furthermore, the number of coalition structures grows as the number of agents increases and corresponds to Pn i=1 Z(n, i), where Z(n, i**), also known as the Stirling**
number of the second kind, is the number of coalition structures with i **coalitions,** and may be computed using the following recurrence: Z(n, i) = iZ(n−1, i)+Z(n− 1, i − 1), where Z(n, n) = Z(n, **1) = 1. As proved in [25], the number of coalition**
structures is O(n n**) and** ω(n n/2**), and hence an exhaustive enumeration becomes**
prohibitive.

In this paper we focus on games that are neither superadditive nor **subadditive**
for which the problem of coalition structure generation is computationally complex. Indeed, for superadditive games where v(S ∪ T ) ≥ v(S) + v(T **) (meaning any two** disjoint coalitions are better off by merging together), and for subadditive games where v(S ∪ T ) < v(S) + v(T ) for all disjoint coalitions S, T ⊆ A**, the problem of** coalition structure generation is trivial. In particular, in superadditive games, the agents are better off forming the grand coalition where all agents operate together (C
∗ = {A}**), while in subadditive games, the agents are better off by operating**
alone (C
∗ = {{a1}, {a2}**, . . . ,** {an}}).

Instances of the CSG problem have been defined using the following distributions, as proposed in [16, 22], for the values of the characteristic function v:
- Uniform (U): v(C) ∼ U(a, b) where a = 0 and b **= 1;** - Uniform Scaled (US): v(C) ∼ |C| · U(a, b) where a = 0 and b **= 1;**
- Normal (N): v(C) ∼ N(µ, σ2) where µ = 1 and σ = 0.1; - Normal Scaled (NS): v(C) ∼ |C| · N(µ, σ2) where µ = 1 and σ = 0.1; - Normally Distributed (ND): v(C) ∼ N(µ, σ2) where µ = |C| and σ =
p|C|.