Facilitating multi-agent coalition formation in self-interested environments

This paper considers the problem of facilitating coalition formation in self-interested multi-agent environments. To successfully form a coalition, agents must collectively agree on the monetary amount to charge for completion of a task as well as the distribution of subtasks within the coalition. The problem is accentuated as different subtasks have various degrees of difficulty and the agents do not possess perfect information. That is, an agent is uncertain of the true monetary requirement of other agents for completing subtasks. These complexities, coupled with the self-interested nature of agents, can inhibit or even prevent the formation of coalitions in such a real-world setting. As a solution we present an auction-based protocol called ACCORD. ACCORD facilitates coalition formation by promoting the adoption of cooperative behaviour amongst agents as a means of overcoming the complexities outlined above. Through extensive empirical analysis we analyse two variations of the ACCORD protocol and demonstrate that cooperative and fair behaviour is dominant and any agents deviating from this behaviour suffer a degradation in performance.