Research On Fair Task Assignment Algorithm In Spatial Crowdsourcing

Task assignment is a crucial problem in spatial crowdsourcing,aiming to find the optimal solution to assign tasks to proper workers.Most related works focus on optimiz-ing task assignment from the platform perspective,maximizing the platform revenue or service rate,while ignoring the interests of workers and requesters.As the idea of social justice becomes more and more popular,both academia and industry are increasingly interested in fair task assignment.Ensuring the fairness in spatial crowdsourcing could coordinate the interests of the three stakeholders:the platform can achieve sustainable development and attract more new users without losing old ones;requesters feel re-spected and receive better quality services;and workers are guaranteed the earning they deserve,while stimulating healthy competition and improving efficiency.Recently,various models have verified that considering fairness affects the effectiveness and ef-ficiency of the platform,yet existing related work in spatial crowdsourcing is dedicated to improving the designed fairness and lacks further optimization of the loss of platform benefits.Based on this,this thesis investigates fair task assignment algorithms in two classical spatial crowdsourcing application scenarios,which are ridesharing platform and food delivery service platform.The details are the following three aspects.（1）We explore the fairness on the passenger side of ridesharing platform that has not been extensively studied.We formally define the multi-objective optimization prob-lem FORM finding the optimal one among all feasible fair matchings,and prove that FORM is an NP-hard problem.This thesis proposes two approximate algorithms for FORM,namely WPS and MCS.They can find the approximate optimal fair matching in polynomial time instead of randomly generating a fair solution,and maximize the passenger’s cost savings for participating in ridesharing while ensuring fairness without additional losses to the platform.In addition,this thesis proves that the approximate ratio of WPS is₇⁴,and also designs the GFRM method for solving the situation where previous work fails to find a fair solution.Finally,we extend our solution framework to the scenario of multi-person ridesharing.（2）We investigate and implement the first fair task assignment method LFD which considers the regional activity of workers in food delivery platform.LFD consists of three sub-modules:a clustering module TSC,a cross-zone worker scheduling module CWS,and an intra-zone fair task assignment module IFA.TSC clusters stores into zones based on historical order data at different time periods.CWS instructs workers within a zone with imbalanced supply and demand to move to a specific zone to achieve supply and demand balance;IFA is responsible for fair matching of workers and tasks within each zone meeting the conditions.（3）We conduct experiments on two real datasets that are widely used in ridesharing and food delivery platforms.The experimental results show that our proposed WPS and MCS methods help passengers save more travel costs without additional loss to the platform while ensuring fairness compared to the baseline methods.For food delivery platform,compared with the state-of-the-art fair task assignment method Fair Foody,our LFD method not only ensures similar fairness,but also takes about 3 miniutes less to deliver an order on average than Fair Foody for the same workload.