VCG-based Truthful Mechanisms for Social Task Allocation

Abstract

In many applications of the task allocation problem such as peer-topeer and grid computing, and virtual organizations, the (social or business) relations between the participating agents play an important role, and thus they should be taken into account. Furthermore, in such applications, agents providing the resources usually act self-interested. This paper therefore studies the problem of finding truthful mechanisms for these kinds of social task allocation problems. In this paper we give on the one hand an optimal mechanism and model the problem as an integer linear program (ILP), and on the other hand a polynomialtime approximation by splitting the problem into smaller sub-problems, each of which is solved optimally. We show that both mechanisms are truthful. The optimal mechanism may take exponential time for some instances, and in theory, the quality of the approximation is not guaranteed. However, we show experimentally that for problem instances where the social network has the smallworld property, the quality of the results for the approximation is quite good, due to the fact that the division into subproblems uses the locality of tasks in the social network.