Coalition-based Task Assignment in Spatial Crowdsourcing

Abstract

With the fast-paced development of mobile networks and the widespread usage of mobile devices, Spatial Crowdsourcing (SC), which refers to assigning location-based tasks to moving workers, has drawn increasing attention in recent years. One of the critical issues in SC is task assignment that allocates tasks to appropriate workers. In this paper, we propose a novel SC problem, namely Coalition-based Task Assignment (CTA), where the spatial tasks (e.g., house removals, furniture installation) may require more than one workers (forming a coalition) to cooperate in order to maximize the overall rewards of workers. To tackle the CTA problem, we design both greedy method and equilibrium-based method. In particular, the greedy method aims to form a set of worker coalitions greedily to perform the tasks, in which we introduce an acceptance possibility to find the high-value task assignments. In the equilibrium-based algorithm, workers form coalitions in sequence and update their strategy (i.e., selecting a best-response task) at their turn, in order to maximize their own utility (i.e., reward of the coalition they stay in) until Nash equilibrium is reached. Since the equilibrium point obtained by the best-response approach is not unique and optimal in terms of total rewards, we further propose a simulated annealing scheme to find a better Nash equilibrium. The extensive experiments demonstrate the efficiency and effectiveness of the proposed methods on both real and synthetic datasets.