Figure 1 plots the coalition structures' values according to the previous five distributions of the characteristic function for 10 agents. Each graph plots on the x-axis the value of the coalition structures whose cardinality is represented by a point on the y-axis. As we can see, it seems to be easy to find optimal solutions in the case of normal and uniform distributions, while it becomes more complicated for the case of scaled distributions. For the normal distribution, the optimal solution belongs to the less populated region corresponding **to CSs with**
none or ten coalitions. The same scenario arises for the uniform distribution, even if here the region containing the optimal solution is more populated than in the previous case. The CFGs with scaled distributions are very hard to solve since the optimal solution may belong to very populated regions. More formally, given n agents, let c be the random variable of the value of a CS with k **coalitions**
ci. For each distribution the expected value of the c **variable may be computed**
as follows: EU (c) = Pk i E(ci) = k/2 (maximum when k = n**, many coalitions);**
EUS (c) = Pk i |ci|/**2 (maximum with few coalitions where it is more probable to**
assign a high value to each one); EN (c) = Pk i 1 = k **(maximum when** k = n);
ENS(c) = Pk i |Ci| (maximum with few coalitions); END(c) = Pk i |Ci| **(maximum**
with few coalitions).

## 4. Related Work

Previous works on CSG can be broadly divided into two main categories: exact algorithms that return an optimal solution, and approximate algorithms that find an approximate solution with limited resources.

A deterministic algorithm must systematically explore the search space of candidate solutions. One of the first algorithms returning an optimal solution is the dynamic programming algorithm (DP) proposed in [29] for the set partitioning problem.This algorithm is polynomial in the size of the input (2n − **1) and it runs** in O(3n**) time, which is significantly less than an exhaustive enumeration (**O(n n)).

However, DP is not an anytime algorithm, and has a large memory requirement.

Indeed, for each coalition C it computes the tables t1(C) and t2(C**). It computes all** the possible splits of the coalition C and assigns to t1(C**) the best split and to** t2(C)
its value. In [21] the authors proposed an improved version of the DP algorithm (IDP) performing fewer operations and requiring less memory than **DP. IDP, as** shown by the authors, is considered one of the fastest available exact algorithm in the literature computing an optimal solution.

Given a coalition C, |C| = n, the number of splitting of C **into two coalitions** C1 and C2, with |C1| = s1 and |C2| = s2 **is computed as follows**

$$S(s_{1},s_{2})={\left\{\begin{array}{l l}{\mathbf{C}(s_{1}+s_{2},s_{2})/2}&{{\mathrm{if~}}s_{1}=s_{2}}\\ {\mathbf{C}(s_{1}+s_{2},s_{2})}&{{\mathrm{~otherwise~}}}\end{array}\right.}$$

where C(n, k) = n k is the binomial coefficient, i.e. the number of k**-combinations**
from a set with n **elements. Now, the total number of splittings computed by DP** is

$$\mathbf{S}_{D P}=\sum_{s=1}^{n}\mathbf{C}(n,s)\sum_{k=\lceil s/2\rceil}^{s-1}S(s-k,k)$$
