VCG-based Truthful Mechanisms for Social Task Allocation

VCG-based Truthful Mechanisms for Social Task Allocation

Zhang, Y.
De Weerdt, M.M.

Electrical Engineering, Mathematics and Computer Science

Software Computer Technology

2007-12-13

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.

http://resolver.tudelft.nl/uuid:4d38cd4e-1bc7-4c2c-899e-ffe45cc3aa79

EUMAS 2007: Proceedings of the 5th European Workshop on Multi-Agent Systems, Hammamet, Tunesia, 13-14 December 2007

Institutional Repository

conference paper

(c) 2007 The Author(s)