Multi-stage complex task assignment in spatial crowdsourcing

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 prov-able 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 experimen-tal results demonstrate the efficiency of our algorithm. (c) 2021 Elsevier Inc. All rights reserved.

Automated summary

This paper focuses on the task assignment problem in spatial crowdsourcing and proposes the multi-stage complex task assignment problem. Unlike previous studies, this problem considers the dependency among tasks and presents greedy and game algorithms to solve it. Experimental results show the efficiency of the proposed algorithms.