Budget-aware online task assignment in spatial crowdsourcing

摘要

The prevalence of mobile internet techniques stimulates the emergence of various spatial crowdsourcing applications. Certain of the applications serve for the requesters, budget providers, who submit a batch of tasks and a fixed budget to platform with the desire to search suitable workers to complete the tasks in maximum quantity. Platform lays stress on optimizing assignment strategies on seeking less budget-consumed worker-task pairs to meet the requesters' demands. Existing research on the task assignment with budget constraints mostly focuses on static offline scenarios, where the spatiotemporal information of all workers and tasks is known in advance. However, workers usually appear dynamically on real spatial crowdsourcing platforms, where existing solutions can hardly handle it. In this paper, we formally define a novel problem called B udget-aware O nline task A ssignment(BOA) in spatial crowdsourcing applications. BOA aims to maximize the number of assigned worker-task pairs under budget constraints where workers appear dynamically on platforms. To address the BOA problem, we first propose an efficient threshold-based greedy algorithm called Greedy-RT which utilizes a random generated threshold to prune the pairs with large travel cost. Greedy-RT performs well in the adversarial model when compared with simple greedy algorithm, but it is unstable in the random model for its random generated threshold may produce poor quality in matching size. We then propose a revised algorithm called Greedy-OT which could learn near optimal threshold from historical data, and consequently improves matching size significantly in both models. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real and synthetic datasets.