Multi-Stage Complex Task Assignment in Spatial Crowdsourcing

Abstract With the widespread application of smart devices, spatial crowdsourcing (SC) has been extensively integrated into daily life. Task assignment is a crucial issue in SC and has attracted much attention. Most prior studies on task assignment ignore the importance of dependency among tasks, resulting in some ineffective matching pairs and wasting workers’ time. To this end, we formulate a new problem in SC, abbreviated as multi-stage complex task assignment (MSCTA), which aims to assign workers to multi-stage complex tasks to maximize the total profit. Compared with existing studies, MSCTA can obtain more effective assignments by considering the dependency constraints among tasks. We prove that the MSCTA problem is NP-hard and propose a greedy algorithm and a game algorithm. Specifically, both algorithms iteratively utilize a filtering module to obtain a set of executable tasks (ET) for assignment. The greedy algorithm can quickly assign the most profitable workers to the subtasks in each round of ET, and obtain a provable approximate result. The game algorithm is proved to be convergent and can win a Nash equilibrium when processing the subtasks in each round of ET. Extensive experimental results demonstrate the efficiency of our algorithm.