Before we start with descriptions of algorithms developed for given problem, we first define few important terms.
Usual situation is following: We have given set of n agents A={A1, A2, ... ,An}. Each agent Ai has a vector of real non-negative capabilities. Each capability is a property of an agent that quantifies its ability to perform a specific action. We assume, that there is a set of independent tasks T={t1, ... ,tm}.
We assume that coalition can work on single task at a time, and that each agent is not a member of more than one coalition. A coalition C has a vector of capabilities(sum of vectors of capabilities). Coalition C can perform task t only if the vector of capabilities necessary for its fulfilment Bt satisfies. For each coalition C a value V can be calculated. V is a joint utility that the members of C can reach by cooperating via coalitional activity for satisfying a specific task.
Many algorithms used for coalition formation works well in super-additive environments. A super-additive environment is such that the set of all possible coalitions C satisfies the following rule: .