Coalition Formation Strategies for Self-Interested Agents in Task Oriented Domains

This article addresses the problem of coalition formation. Our work specially focuses on task oriented domains, where self-interested agents want to perform bundles of tasks. Depending on its resources, an agent may not be able to perform a bundle of tasks alone. Then the agent needs to find partners, interested in the same bundle, and agree to put their resources in common, in order to perform the bundle all together. We present in this paper, different behavior algorithms for the agents. We propose a coalition construction algorithm based on: (1) a bundle selection algorithm, which allows an agent to select a bundle of tasks to propose and (2) a solicited agents selection algorithm, which allows an agent to select a group of agents to perform this bundle. We provide two different solicited agents selection algorithms designed for structured-preference context, based on the use of the information gathered in the previous interactions with other agents: (1) the similarity-based selection algorithm and (2) the occurrence of tasks-based selection algorithm. Both allow the agents to select partners, which are more likely interested in the bundles. These algorithms are detailed and exemplified. We have implemented and tested them, and we provide the results of their evaluation.

I. Introduction

This paper focuses on autonomous and self-interested agents motivated by performing bundles of tasks among a whole set of performable tasks. Each agent has its own preference order over bundles of tasks, but an agent is often not able to achieve its most preferred bundles by itself (for instance, because of lack of resources or lack of expertise). Putting their resources together, a group of agents will be able to perform a bundle, which none agent of the group can perform by itself. In this context, a coalition is a group of agents formed in order to perform a bundle of tasks. In such a context, autonomous agents have to find partners with which they will share the achievement of the bundles they want to perform, i.e. bundles which have high ranks in their preference orders. To do so, an agent has to construct and to send coalition formation proposals to other agents and when it receives a proposal of coalition formation, it has to decide whether it wants to join the coalition or not. We propose in this paper some behavior strategies for agents. Assuming that preferences of agents are structured, we propose strategies which use the information gathered in previous interactions the agent had with other agents, in order to construct coalitions, which are worth to be proposed.