The necessity of forming coalitions in multi-agent system (MAS) arises in situations, when there is no agent, which can fulfil given task. In this situation we need to form group of agents to fulfil given task. This group is called coalition of agents. It may also be useful to assign group of agents to the task when the group's performance is more efficient than the performance of the single agent. The usual situation is following: We have given set of tasks for given multi-agent system. Our goal is to find the set of groups (coalitions) of agents, that fulfils all tasks so that the performance of MAS is maximal possible. Previously mentioned set of groups is called coalition structure. Of course the question how to define performance of the system arises there. The performance can be defined in many ways and in next sections we will show how this definition can impact complexity of the solution of given problem.
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: .
This algorithm was introduced by Onn Shehory and Sarit Kraus. This algorithm works in not necessarily super-additive environments.1 In the following subsection we first describe the environment for this algorithm by mathematical means and then the algorithm itself. Sequentially we will discuss the limitations of described algorithm.
I didn't find the perfect description of enviroments, in which this algorithm will work. But It seems to, that this algorithm is mostly used for super-additive enviroments.