Incentive Mechanisms for Large-scale Crowdsourcing Task Diffusion based on Social Influence

Crowdsourcing has become an effective tool to utilize human intelligence to perform tasks that are challenging for machines. Many incentive mechanisms for crowdsourcing systems have been proposed. However, most of existing mechanisms assume that there are enough participants to perform the crowdsourcing tasks. This assumption may not be true in large-scale crowdsourcing scenarios. To address this issue, we diffuse the crowdsourcing tasks via the social network. We study two task diffusion models, and formulate the problem of minimizing the total cost such that all tasks can be completed in expectation for each model. The topology based influence estimation and history based influence estimation based on the limited knowledge of social network are presented in this paper. Further, we present the global influence estimation method to measure the influence over the whole community with the full knowledge of social network. We design two sealed reverse auction based truthful incentive mechanisms, MTD-L and MTD-IC, for both diffusion models. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the proposed mechanisms achieve computational efficiency, individual rationality, truthfulness, and guaranteed approximation. Moreover, the global influence estimation based mechanisms always output the least social cost and overpayment ratio, and the history influence estimation based mechanisms show significant superiority in terms of task completion rate.