Algorithms for Coalition Formation in Multi-agent Systems

Software agents situated in the same environment typically need to interact with one another in order to fulfill their objectives or improve their performance. Coalition formation is a fundamental form of interaction that has proven to be useful in a number of scenarios, including:

sensor networks
e-commerce
distributed vehicle routing


Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the potential coalitions to form in order to achieve some goal. This usually requires calculating a value for every coalition, known as the coalition value, which indicates how beneficial that coalition would be if it was formed. Once these values are calculated, the agents need to find a combination of coalitions of which the sum of values is maximized, and in which every agent belongs to exactly one coalition.



Finding an optimal, or near-optimal, solution to this coalition structure generation problem is extremely challenging due to the large number of possible solutions. To date, many algorithms have been proposed to solve this problem using different techniques - ranging from dynamic programming, to integer programming, to stochastic search - all of which suffer from major limitations relating to execution time, solution quality, and memory requirements.

Against this background, this thesis presents a novel algorithm for distributing the coalition-value calculations among the agents. The algorithm is decentralized, requires no communication between the agents, has minimal memory requirements, and can reflect variations in the computational speeds of the agents. We also develop an anytime algorithm for coalition structure generation. By using a novel representation of the search space, and applying branch-and-bound techniques, the algorithm is shown to significantly outperform other existing ones in the literature.