Research On Worker Recruitment And Task Assignment Mechanisms In Spatial Crowdsourcing Systems

In recent years,portable smart terminal devices,represented by smart phones,which have more and more powerful communication,storage,sensing and wireless communication capabilities,have been widely popularized.Against this background,a new crowdsourcing mode,called spatial crowdsourcing,which gathers the users of smart terminal devices to conduct tasks with spatial characteristics,is generally causing widespread concern in academia and industry.A typical spatial crowdsourcing system is mainly composed of a platform residing on the cloud and a set of spatial crowdsourc-ing users.The spatial crowdsourcing users including task initiators and mobile workers who carry smart terminal devices.The platform receives spatial tasks from task ini-tiators,and then outsources these tasks to mobile workers.Later,the workers need to move to the specific locations of these tasks and perform them by using their terminal devices.Lastly,the platform receives the results of tasks executed by workers and feeds back to task initiators.Because the spatial crowdsourcing system makes full use of the intelligence of crowds to deal with complex and large-scale spatial tasks,and is accom-panied by many advantages such as high flexibility,low cost and universality,it has a wide application prospect.Currently,a large number of applications based on spatial crowdsourcing have been applied to the realistic life.Generally speaking,spatial crowdsourcing mainly includes several procedures,such as worker recruitment,task assignment,task execution and result delivery.Among them,who to recruit and how to assign tasks are the cornerstones of an effective spa-tial crowdsourcing system.Consequently,this dissertation focuses on the issues related to task assignment and worker recruitment.Firstly,we concern how to make stable task assignment for spatial crowdsourcing users who possess preferences.Normally,the utility of a spatial crowdsourcing system is quantified by the assignment outcomes produced by some task assignment algorithm.There are various quantitative indicators in existing research works.Based on these indicators,the ultimate objective of design-ing a task assignment algorithm is mostly defined as the optimization of system utility.However,in the actual scenarios,spatial crowdsourcing users may have their own re-quirements and preferences,and they are unwilling to sacrifice personal convenience for system utility,thus giving rise to the spatial crowdsourcing task assignment problem with preferences.To solve this problem,we introduce the stable matching theory,and define pairwise stable matching and coalitionally stable matching based on the different preference lists determined by workers and task initiators.Since prove the existence of the coalitionally stable matching in spatial crowdsourcing task assignment with bud-get constraint and output one are both NP-hard problems,we propose a approximately coalitionally stable task assignment mechanism.In this mechanism,based on the pref-erence list of each worker,we constantly optimize and update the matching result of the proposed task by solving the 0-1 knapsack problem.Through rigorous theoretical analyses,we prove that the designed mechanism can always produce a pairwise stable matching,and the matching is a coalitionally 2-stable matching.Finally,we verify the excellent performance of this mechanism through a large number of simulations.Secondly,task initiators always wish that the platform can recruit mobile work-ers with high qualities to perform tasks.Whereas in practical scenarios,on one hand,the platform and task initiators cannot obtain the workers' qualities of completing tasks in advance.On the other hand,these quality values usually involve workers' private information.Therefore,it is necessary to conduct in-depth research on such a privacy-preserving unknown worker recruitment problem.In order to address this problem,we formalize the unknown worker recruitment as a Differentially Private Multi-Armed Bandit(DP-MAB)model by seeing each worker as an arm of DP-MAB and seeing the task completion quality contributed by each worker as the reward of pulling an arm.Then,recruiting workers is equivalent to designing a bandit policy for DP-MAB.In the MAB-based unknown worker recruitment process,the platform will.face a dilemma of deciding whether to recruit the worker who may be the best in future or recruit the worker who is the best currently.To solve this dilemma,we extend the ?-First bandit policy and the UCB(Upper Confidence Bound)bandit policy in MAB,and respec-tively propose two budget-feasible differentially private unknown worker recruitment mechanisms.Whereafter,we prove the proposed mechanisms are both?-differentially private through rigorous theoretical analyses,and we have also derived an tight asymp-totic upper bound of regret for the mechanisms.Finally,extensive simulations based on real-trace and synthetic datasets have verified the superior performances of the proposed mechanisms.Lastly,we focus on the order assignment problem in a specific spatial crowdsourc-ing system,i.e.,the mobile taxi-hailing system.In the mobile taxi-hailing system,pas-sengers generate taxi-hailing orders and send them to the platform via their terminal de-vices installed with mobile taxi-hailing system software,while taxi drivers also receive orders through their terminal devices installed with such software.Through mobile taxi-hailing systems,passengers' trips and drivers' service efficiency both have been improved significantly.Existing mobile taxi-hailing order assignment mechanisms fall short in flexibility and personalized pricing,resulting in unsatisfactory service expe-riences with regard to taxi drivers.In order to enable drivers to flexibly compete for their preferred taxi-hailing orders with personalized pricing,we design a competitive order assignment framework for the mobile taxi-hailing system.Under this framework,we design an automatic valuation component for each driver,which embed an MAB-based automatic valuation algorithm.This algorithm can generate different valuation schemes for different taxi-hailing orders.While conducting the order assignment pro-cess on the platform side,in order to handle the competitive relationship among taxi drivers and the strategic behaviors of drivers(that is,reporting untruthful valuations to the platform so as to improve their payoffs),we adopt the auction theory and propose a reverse-auction-based order assignment mechanism.The mechanism includes a win-ning driver selection algorithm which is designed on the basis of the weighted bipartite graph matching problem,and a payment computation algorithm which is designed ac-cording to Myerson's theorem.In the end,we conduct detail theoretical analyses on the automatic valuation algorithm and the reverse-auction-based order assignment mecha-nism respectively,including the online performances,time complexity,truthfulness and individual rationality.A large number of theoretical analyses and simulations based on real-world datasets have demonstrated and verified the efficiency of the proposed algo-rithm and mechanism.In conclusion,based on worker recruitment and task assignment in spatial crowd-sourcing,our dissertation conducts in-depth research on the above mentioned three problems,and the proposed solutions have achieved superior performances from both theoretical and experimental perspectives,providing valuable reference for the practi-cal application of the spatial crowdsourcing system.In future work,we can study the problem with regard to task execution and result delivery of spatial crowdsourcing,so as to further perfect the theoretical significance of the spatial crowdsourcing system and improve its overall performance in practical scenarios.