Introduction


Development of multi-agent systems, that rapidly increases in the past years, brings us many advantages of robust and well distributed systems, but also it opens up many new questions in designing and fine-tuning of multi-agent systems to obtain maximal performance.
One of problems that arose in last few years is the problem of finding of optimal coalition structures to fulfil given set of tasks passed to multi-agent system. This problem was solved by many means in Artificial Intelligence. There were also some experiments based on use of genetic algorithm.
In this work we focus on problem of finding of optimal coalition structures. The problem itself is described in section 2. There are described results of previous works on given theme in section three. In section four we focus on this problem by the point of view of Evolutionary Techniques.

Coalition formation in Multi-agent systems


Basic of the problem

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.

Basic definitions

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: .

Greedy distributed set partitioning algorithm

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.
Description of the environment
 
 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.