Incentivizing Cooperation between Heterogeneous Agents in Dynamic Task Allocation

Market Clearing is an economic concept that features attractive properties when used for resource and task allocation, e.g., Pareto optimality and Envy Freeness. Recently, an algorithm based on Market Clearing, F M C_T A, has been shown to be most effective for realistic dynamic multi agent task allocation, outperforming general optimization methods, e.g., Simulated annealing, and dedicated algorithms, specifically designed for task allocation. That been said, F M C_T A was applied to a homogeneous team of agents and used linear personal utility functions for representing agents' preferences. These properties limited the settings on which the algorithm could be applied. In this paper we advance the research on task allocation methods based on market clearing by enhancing the F M C_T A algorithm such that it: 1) can use concave personal utility functions as its input and 2) can apply to applications which require the collaboration of heterogeneous agents, i.e. agents with different capabilities. We demonstrate that the use of concave functions indeed encourages collaboration among agents. Our results on both homogeneous and heterogeneous scenarios indicate that the use of personal utility functions with small concavity is enough to achieve the desired incentivized cooperation result, and on the other hand, in contrast to functions with increased concavity, does not cause a severe delay in the execution of tasks.