Strategy Proof Mechanism for Complex Task Allocations in Prior Consent for Subtasks Completion Environment

In this paper we propose solution for complex tasks´ allocation problems that have predetermined and known overall payments for any given task and the agents capabilities are known. In previous work it has been proved that this problem in cooperative environments is NP-hard. Moreover, it has been proved in previous work that in case the agents give their prior consent to perform any subtask they are capable, no efficient, individually rational, and budget balanced mechanism exists. Against this background, here we analyse a more specific, but nevertheless important, settings, where the overall task payment ensures the coverage of the task payment for any possible agent´s cost that may exist in the market. For these settings we developed the modified VCG protocol which we proved to be strategy proof, individually rational, and strongly budget balanced. Moreover, the performance of the modified VCG is evaluated via extensive experiments that show that they outperform previous solutions in this area in terms of efficiency and stability.