Preventing Under-Reporting in Social Task Allocation

Preventing Under-Reporting in Social Task Allocation

De Weerdt, M.M.
Zhang, Y.

Electrical Engineering, Mathematics and Computer Science

Software Computer Technology

2010-12-31

In games where agents are asked to declare their available resources, they can also strategize over this declaration. Surprisingly, not in all such games a VCG payment can be applied to construct a truthful mechanism using an optimal algorithm, though such payments can prevent under-reporting of resources. We show this for the problem of allocating tasks in a social network (STAP). Since STAP is NP-hard, we introduce an approximation algorithm as well. However for such an approximation, a VCG payment cannot prevent under-reporting anymore. Therefore we introduce an alternative payment function that motivates agents to fully declare their resources. We also demonstrate by experiments that the approximation algorithm works well in different types of social networks.

http://resolver.tudelft.nl/uuid:39fcae97-c6fb-4fbb-b06a-2dbb63f03a22

Springer

https://doi.org/doi:10.1007/978-3-642-15237-5_1

Lecture Notes in Business Information Processing, 44, 2010; authors version

Institutional Repository

book chapter

(c) 2010 Springer
The original publication is available at www.springerlink.com