Onn Shechory and Sarit Kraus, Bar Ilan University, Israel
Goal-satisfaction in multi-agent environments via coalition formation may be beneficial in cases where agents cannot perform goals by themselves or they do so inefficiently. Agent coalition formation typically requires that each agent must be a member of only one coalition. This may lead to a waste of resources and capabilities. Therefore, we present algorithms that lead agents to the formation of overlapping coalitions, where each coalition is assigned a goal. The algorithms we present are appropriate for agents working as a distributed problem solving system in nonsuper-additive environments. They are any-time distributed algorithms with a low computational complexity and low ratio-bound.