Cost Minimization and Social Fairness for Spatial Crowdsourcing Tasks
Résumé
Spatial crowdsourcing is an activity consisting in outsourcing spatial tasks to a community of online, yet on-ground and mobile, workers. A spatial task is characterized by the requirement that workers must move from their current location to a specified location to accomplish the task. We study the assignment of spatial tasks to workers. A sequence of sets of spatial tasks is assigned to workers as they arrive. We want to minimize the cost incurred by the movement of the workers to perform the tasks. In the meanwhile, we are seeking solutions that are socially fair. We discuss the competitiveness in terms of competitive ratio and social fairness of the Work Function Algorithm, the Greedy Algorithm, and the Randomized versions of the Greedy Algorithm to solve this problem. These online algorithms are memory-less and are either inefficient or unfair. In this paper, we devise two Distribution Aware Algorithms that utilize the distribution information of the tasks and that assign tasks to workers on the basis of the learned distribution. With realistic and synthetic datasets, we empirically and comparatively evaluate the performance of the three baseline and two Distribution Aware Algorithms.