C^2: Truthful Incentive Mechanism for Multiple Cooperative Tasks in Mobile Cloud

In the practical crowd sourcing systems, there exist many cooperative tasks, each of which requires a group of users to perform together, such as finding the shortest multi-hop path or obtaining the media resources from a set of hosts. In this paper, we tackle the problem of how to truthfully and fairly schedule or allocate sufficient users who join mobile crowd sourcingapplications with their smartphones. Moreover, the cooperation among users is taken into account. Thus, we present a novel Cooperative Crowd sourcing (C2) auction mechanism for crowd sourcing multiple cooperative tasks. C2 contains two parts: user selection and payment computation. In the first part,we first prove that users selection with the minimum social cost is NP hard problem and design a greedy algorithm to achieve near-optimal solution in polynomial time. The other part is that the server determines the payments of selected users to avoid the bidder’s cheating behavior through a pricing algorithm that if and only if users honestly bid their cost, they can obtain the maximum utility. Both theoretical analysis and extensive simulations demonstrate that C2 auction achieves not only truthfulness, individual rationality and high computational efficiency, but also low over payment ratio.