Coalition structure generation in task-based settings

The coalition formation process, in which a number of independent, autonomous agents come together to act as a collective, is an important form of interaction in multi-agent systems. However, one of the main problems that hinders the wide spread adoption of coalition formation technologies is the computational complexity of coalition structure generation. That is, once a group of agents has been identified, how can it be partitioned in order to maximise the social payoff To date, most work on this problem has concentrated on simple characteristic function games. However, this lacks the notion of tasks which makes it more difficult to apply it in many applications. Against this background, this paper studies coalition structure generation in a general task-based setting. Specifically, we show that this problem is NP-hard and that the minimum number of coalition structures that need to be searched through in order to establish a solution within a bound from the optimal is exponential to the number of agents. We then go onto develop an anytime algorithm that can establish a solution within a bound from the optimal with a minimal search and can reduce the bound further if time permits.