Coalition Formation

We define a coalition formation problem as:
- S: coalition, a subset of A agents.
- V_S: the value of coalition S to its members.
- CS: a coalition structure. The set of all coalitions such that all agents belong to one.
If the costs are supperadditive (V_S+T >= V_S + V_T) then the grand coalition is the best deal.
Otherwise, finding the optimal CS is very hard.

If we explore the lowest two levels of the graph we can be sure that the best coalition is no more than |A| times better than the one we found. Notice that we have examined every possible S, so the best will have to be <= S'|A|, where S' is the best one we have found so far.
Unfortunately, there are 2^{|A| - 1} in just those two levels.
Coalition formation and task allocation are just instances of a more general multiagent search problem.