Satisfaction-aware Task Assignment in Spatial Crowdsourcing

With the ubiquitous of GPS-equipped devices, spatial crowdsourcing (SC) technology has been widely utilized in our daily life. As a novel computing paradigm, it hires mobile users as workers who physically move to the location of the task and perform the task. Task assignment is a fundamental issue in SC. In real life, there are many complex tasks requir-ing different workers, among which the quality of worker cooperation and the price satis-faction of users should not be ignored. Hence, this paper examines a satisfaction-aware task assignment (SATA) problem with the goal of maximizing overall user satisfaction, where the user satisfaction integrates the satisfaction towards price and cooperation quality. The SATA problem has been proved to be NP-hard by reducing it from the k-set packing problem. In addition, two algorithms, namely, conflict-aware greedy (CAG) algorithm and game theoretic (GT) algorithm with an optimization strategy, are proposed for solving the SATA problem. The CAG algorithm can efficiently obtain a result with provable approxi-mate bound, while the GT algorithm is proven to be convergent which can find a Nash equilibrium. Extensive experiments have demonstrated the effectiveness and efficiency of our proposed approaches on both real and synthetic datasets.(c) 2022 Published by Elsevier Inc.

Automated summary

With the widespread use of GPS-equipped devices, spatial crowdsourcing (SC) technology has become popular in our daily lives. SC hires mobile users as workers who physically go to the task location and perform the task. This paper addresses the satisfaction-aware task assignment (SATA) problem in SC with the goal of maximizing overall user satisfaction, which combines satisfaction towards price and cooperation quality. The paper proposes the conflict-aware greedy (CAG) algorithm and game theoretic (GT) algorithm to solve the SATA problem, with the CAG algorithm providing an efficient result with a provable approximate bound and the GT algorithm finding a convergent Nash equilibrium. Extensive experiments demonstrate the effectiveness and efficiency of the proposed approaches on real and synthetic datasets.