Profit-driven Task Assignment in Spatial Crowdsourcing

1 Introduction

Recent years have witnessed a revolution in Spatial Crowdsourcing (SC), where people with mobile sensing facilities can move as sensors and participate some location-based tasks instantaneously [Deng et al., 2015; Tong et al., 2016a; Tong et al., 2016b; Song et al., 2017; Li et al., 2015; Zhao et al., 2017; Tong et al., 2018a; Tong et al., 2017; Tong et al., 2018b]. A typical SC system consists of a platform, task requesters and mobile workers. The role of platform is to provide task assignment services to task requesters and encourage workers to contribute the system. Most existing research in SC focuses on task assignment with different optimization strategies [Cheng et al., 2015b;

∗ Jinfu Xia and Yan Zhao made equal contribution.

†Corresponding Author

Cheng et al., 2015a; Zhao et al., 2019a]. Although task assignment has been studied for many years to improve the performance of SC, problems have been long-standing remain, which include how to optimize the profit for SC platform.

A primary driving force of the SC platform is its inherent cost effectiveness. In other words, it is in the SC platform's interests to maximize the profit during task assignment. Although several SC applications have been proposed, most of them assume that the SC platform assigns tasks to mobile workers voluntarily without considering the profit of SC system [Jain et al., 2009; Cooper et al., 2011], which are often difficult to engineer non-monetary incentive schemes for tedious and repetitive work [Singer and Mittal, 2013] and unrealistic for commercial SC platform due to its profit-driven nature. Moreover, workers are not willing to perform the assigned tasks without actual payments or credits as they have various participation cost (e.g., mobile device battery energy cost for sensing and data processing). Several profit-based task assignment mechanisms have been developed in crowdsourcing system. For instance, considering the profit of platform, Yang et al. [Yang et al., 2012] design incentive mechanisms for mobile crowdsourcing systems based on two system models (i.e., platform-centric and user-centric model), but they mainly focus on improving the computational efficiency instead of improving the profit. [Shah-Mansouri and Wong, 2015] proposes a profit maximizing truthful auction mechanism, in which the platform acts as an auctioneer and workers act as sellers submitting their bids to the platform. However, when assigning tasks, the above researches fail to consider the spatio-temporal constraints, which play an essential role in SC. Meanwhile, they improve the total profit for the platform by designing different incentive mechanisms instead of paying attention to task assignment process.

Fig. 1 illustrates an example of profit-based task assignment problem with five workers (indicated as {w1,...,w5}) and three tasks (shown as {s1, s2, s3}). Each worker is associated with her current location and reachable distance range (marked as w.r). Each task, published and expired at different time instances, is labelled with its workload (s.wl) and reward information (i.e., penalty rate s.pr and maximum reward s.maxR). The problem is to assign tasks to the suitable workers so as to maximize the total platform profit. In SC, it is intuitive to assign the nearby tasks to workers without violating the spatio-temporal constraint, referred to as shortest distance priority algorithm. Therefore, we can obtain a task assignment, {< s1,w2 >,< s2,w1 >,< s3,w3 >} (shown in blue arrow lines in Fig. 1), with the platform profit of 5.7 (we assume the platform gets 80% of the reward as its profit). However, this assignment algorithm leaves w4 and w5 unassigned, which may contribute more profit for SC platform.

To address these challenges, we propose a profit-based task assignment framework that links the task assignment process with its economic performance in profit. We first formulate the Profit-driven Task Assignment (PTA) problem and show it is NP-hard. Then we establish a reward pricing model with the task's temporal constraints, wherein the total reward is directly associated with the payment of task requesters and the processing time of the task. When it comes to task assignment, we introduce an exact tree-decomposition-based algorithm that finds the optimal assignment result in terms of the total platform profit. For the sake of efficiency, we propose a Greedy Task Assignment (GTA) algorithm that tries to give priority to the tasks with the highest possible reward per unit of work and assign the closest worker to this task until it is finished before its expected completion time. Meanwhile, GTA with two Random Tuning Optimization strategies (GTA-RTO) are developed to prune the non-promising worker-task assignment pairs. The red arrow lines in Fig. 1 depict the task assignment by our GTA-RTO algorithm that generates the profit of 8.72.

Our primary contributions can be summarized as follows:

1. We formulate a PTA problem in SC. To the best of our knowledge, this is the first work that aims to maximize the profit for SC platform during task assignment process.
2. We develop a reward pricing model by considering both task's expected completion time and task's expiration time.
3. We develop both optimal and greedy task assignment algorithms to address the proposed problem.
4. Extensive experiments are conducted to verify the effectiveness and efficiency of the proposed methods.

2 Problem Statement

We define a set of preliminaries and formulate our PTA problem.

Definition 1 (Spatial Task) A spatial task, denoted by s = < s.l, s.p, s.e, s.d, s.wl, s.maxR, s.pr >, is a task to be performed at location s.l, published at time s.p, expected to be finished at time s.e and will expire at deadline s.d. Each task is also labelled with a required workload s.wl to finish task s by a normal worker (we simply use the time required to finish a task to denote s.wl). s.maxR is the maximum reward the task requester can provide and s.pr is a penalty rate, which establishes a correlation between completion time and reward.

Definition 2 (Worker) A worker, denoted by w = < w.l, w.r >, is a person who is able to perform tasks only if she is paid. A worker is associated with her current location w.l and her reachable circular range with w.l as the center and w.r as the radius, in which w can accept assignment of tasks.

Definition 3 (AvailableWorker Set) Given a task s to be assigned and a set of workers in the vicinity of s, the available worker set for task s, denoted as AWS(s), should satisfy the following two conditions: ∀w ∈ AWS(s),

1) tnow + t(w.l, s.l) < s.d, and

2) d(w.l, s.l) ≤ w.r, and

3) ∑w∈AWS(s) w.wl(s) = s.wl,

where tnow is current time, t(a, b) is travel time from location a to b, d(a, b) is travel distance from location a to b, and w.wl(s)(> 0) is the workload assigned to w to finish s.

Definition 4 (Platform Profit) Given a task s to be assigned and an available worker set AWS(s) for s, the profit of SC platform can be computed as PAWS(s) = αRAWS(s), where PAWS(s) and RAWS(s) (0 ≤ RAWS(s) ≤ s.maxR) are the profit of SC platform to finish s and the reward of s (i.e., the payment the task requirer provides) respectively when assigning task s to workers in AWS(s), and α (0 < α < 1) is a parameter controlling the earnings that SC platform obtains from the task reward. The reward of s, RAWS(s), will be elaborated in Section 3.

Note that we simply assume the profit of an SC platform is in proportion to the reward (e.g., the profit is 20% of the reward when α = 20%) and the remaining reward will be allocated to workers. We just focus on the profit of SC platform while ignoring the reward allocation mechanism of workers.

Definition 5 (Optimal Available Worker Set (OptAWS)) An available worker set, AWS(s), is optimal if every of its proper subsets can only achieve a less-than-PAWS(s) platform profit.

Definition 6 (Spatial Task Assignment) Given a set of workers W and a set of tasks S, a spatial task assignment, denoted by A, consists of a set of < task,AWS > pairs in the form of < s1,AWS(s1) >, < s2,AWS(s2) >,. . . , < s|S|, AWS(s|S|) >, where ⋂|S| i=1 AWS(si) = ∅.

Let A.P denote the total profit of SC platform for task assignment A, i.e., A.P = ∑<s,AWS(s)>∈A PAWS(s), and A denote all possible ways of assignments. The PTA problem can be formally stated as follows: given a worker set W and a task set S, the PTA problem aims to find the global optimal assignment Aopt, such that ∀Ai ∈ A, Ai.P ≤ Aopt.P. We then prove the hardness of PTA problem.

Theorem 1 The PTA problem is NP-hard.

Theorem 1 can be proved by doing the reduction from the 0-1 knapsack problem, which is proven to be NP-hard [Vazirani, 2013].

3 Reward PricingModel Construction

In order to design a cost-effective task assignment algorithm, a reasonable reward pricing model has to be established firstly to quantify the temporal constraints of tasks. In particular, we consider a single task s and one of its available worker set, where the the requester specifies the task's expected completion time s.e, deadline s.d, maximum reward s.maxR and penalty rate s.pr. The model focuses on the task completion time and reward (i.e., the requester's real payment for the task), which are directly associated with the platform profit.

Definition 7 (Task Completion Time) Given a task s and an available worker set AWS(s), the task's completion time can be calculated as follows:

where s.t0 (s.t0 ≥ s.p) is the assignment time, from which we assign task s to worker set AWS(s), aw(s.l) is the arrival time of w at task s, s.wl is the required workload (i.e., the required time to complete task s) and ∑w∈AWS(s) (aw(s.l)-s.p)+s.wl |AWS(s)| denotes the time beginning from s.t0 and ending to the completion of task s.

With the two main time (i.e., s.e and s.d) and maximum reward constraints, the mathematical model (shown in Fig. 2) of the real reward can be expressed as followed:

where T(AWS(s)) is s's completion time with AWS(s).

4 Task Assignment

4.1 Optimal Task Assignment (OTA)

It is easy to know that the global optimal result is the union of one possible Optimal Available Worker Set (OptAWS) of all tasks. In this section, we apply a tree-decompositionbased algorithm [Zhao et al., 2017; Zhao et al., 2019b] to achieve the optimal task assignment, which consists of following steps:

1) Find the reachable workers for each task. The reachable worker subset for a task s, denoted as RWs, should satisfy

• the following conditions: ∀w ∈ RWs, t(w.l, s.l) ≤ s.d and d(w.l, s.l) ≤ w.r. The above two conditions guarantee that w can reach s directly before it expires in her reachable range.
• Find OptAWSs for each task. Given the reachable worker set for each task, we can utilize a dynamic programming algorithm that iteratively expands the sets of tasks in the ascending order of set size and find all OptAWSs in each iteration. The process is omitted due to space limit.
• Apply the tree-decomposition-based algorithm [Zhao et al., 2017] to find the optimal task assignment with maximal profits. In particular, we first use a tree-decomposition technique to separate all tasks into independent clusters (i.e., tasks in different clusters do not share same available workers) and organize them into a tree structure, such that the tasks in sibling nodes of the tree do not share the same available workers. Then the tree can be traversed in depth-first manner to find the optimal assignment.

Consider the example in Fig. 1. With OTA algorithm, we can get the profit of 8.72 for SC platform.

4.2 Greedy Task Assignment (GTA)

For the sake of efficiency, we propose a basic Greedy Task Assignment (GTA) solution to solve the PTA problem by giving higher priorities to the tasks with higher reward per unit of work and workers with less travel cost.

The procedure of GTA is shown in Algorithm 1, which takes a worker set W and a task set S as input, and returns a suitable task assignment set A, unassigned worker set W ′ and unassigned task set S′ . We first sorts the tasks in S′ in descending order according to their reward per unit of work (line 2). Then for each task s in S′ , we try to assign the first arrival worker in W ′ to perform s until s can be completed in expected time s.e (line 3-13). If there are no sufficient workers to complete task s, s will be skipped and the workers will not be assigned (line 7-8). The time complexity of GTA is O(max{|S| · log |S|, |S| · |W| · log |W|}). GTA can obtain a task assignment, {< s2, {w1, w2, w5} >,< s3, {w3, w4} >}, with the profit of 5.3 in Fig. 1.

4.3 GTAwith RandomTuning Optimization

GTA is a polynomial-time greedy algorithm that finds a task assignment set A with promising solutions. However, there are some issues in GTA. First, GTA always tries to complete a task in expected completion time while ignoring its penalty rate, which is also related to the final profit. Moreover, GTA assigns the closest workers without considering time utilization ratio of workers. For instance, when a task is far away from all the workers, assigning the closest workers to perform this task may lead to a low profit for the whole platform.

To overcome these limitations, we improve GTA with Random Tuning Optimization (GTA-RTO), which contains two tuning strategies: coarse and fine tuning. Coarse tuning randomly abandons the low-valuable tasks (e.g., tasks with low time utilization ratio of workers) and fine tuning randomly reassigns partial workers to find a better task assignment.

GTA-RTO is shown in Algorithm 2, which starts from a pre-assignment by GTA (line 1). Then the current task assignment A′ (= A), unassigned worker set W ′ and unassigned task set S′ enter in the tuning loop (line 3 - 12), wherein the

Algorithm 1 GTA

Input: W, S Output: A, W ′ , S′ 1 A = ∅, W ′ =W, S′ = S; 2 sorting tasks in S′ according to s.maxR s.wl in descending order; 3 foreach s ∈ S′ do 4 Wassign = ∅; 5 sorting workers in W ′ according to their arrival time in increasing order; 6 while s is not completed in expected time do 7 if W ′ is ∅ then 8 break; 9 w = closest worker in W ′ ; 10 Wassign =Wassign ∪ {w}; 11 if s is completed then 12 A = A ∪ {< s, Wassign >}; 13 S′ = S′ - {s}; W ′ = W ′ -Wassign; 14 return A, W ′ , S′ ;

Algorithm 2 GTA-RTO

Input: W, S Output: A 1 A′ ,W ′ , S′ = GTA(W, S); 2 A = A′ ; 3 repeat 4 A′ , W ′C , S′C = CT(A′ ); 5 W ′ =W ′ ∪W ′ c ; S′ = S′ ∪ S′C ; 6 A′ , W ′P , S′P = FT(A′ ); 7 W ′ =W ′ ∪W ′ c ; S′ = S′ ∪ S′C ; 8 AG, W ′ , S′ = GTA(W ′ , S′ ); 9 A′ = A′ ∪AG; if A′ .P > A.P then A = A′ ;

10 11 12 until there is no improvement until n rounds;

Coarse Tuning (CT) algorithm and Fine Tuning (FT) algorithm are invoked in order, followed by GTA. Specifically, we first apply CT algorithm with A′ as input to generate an unassigned worker set W ′C and an unassigned task set S′C as well as a modified A′ (line 4). Then worker set W ′ and task set S′ are updated (line 5). In the similar way, we update A′ , W ′ and S′ by invoking FT (line 6 - 7). GTA is invoked to generate a task assignment AG based on W ′ and S′ (line 8). Subsequently, a new task assignment is updated by the union of A′ and AG. Once the profit of A′ is higher than that of A, we replace A with A′ (line 9- 11). Algorithm 2 stops when there is no improvement for n rounds, in which n can be specified by the SC platform.

Coarse Tuning (CT)

CT aims to abandon the low-valuable tasks. The possibility P CT s,W that task s with assigned worker set W will be aban-

Algorithm 3 CT

Input: A Output: A′ , W ′ , S′ 1 A′ = A,W ′ = ∅, S′ = ∅; 2 foreach task-worker pair < s,AWS(s) >∈ A′ do 3 calculate pCT s,AWS(s) based on Equation 1; 4 if pCT s,AWS(s) < ζ then 5 A′ = A′- < s, AWS(s) >; 6 S′ = S′ ∪ s; W ′ =W ′ ∪AWS(s); 7 return A′ , W ′ , S′ ;

doned in CT is defined as follows:

where pCT m +pCT t +pCT r = 1, T(W) is the completion time of task s with assigned worker set W, R(s,W) is the final reward of task s, and aw(s.l) is the time worker w arrives at task s. ∑w∈W aw(s.l)-s.p (T(W)-s.p)∗|W| represents the travel time ratio of

workers to complete task s and R(s,W) s.maxR is the rate of return. pCT m is the minimumpossibility that a task can be abandoned. pCT t and pCT r are the parameters controlling the contributions of the time utilization ratio of workers and the rate of return.

CT algorithm is shown in Algorithm 3. The input variables is task assignment set A. The output variables are a new task assignment set A′ , unassigned worker set W ′ and unassigned task set S′ . We first calculate the abandoned possibility of each task s in A′ (line 3) and remove the task-worker pair < s, AWS(s) > from A′ if the abandoned possibility (line 4 and 5) is less than a random number ζ (0 ≤ ζ ≤ 1).

Fine Tuning (FT)

In FT processing, no task will be completely abandoned and only a small number of workers will be reassigned, ensuring that tasks can be completed before deadline. The possibility P FT s,w,W that worker w(∈ W) assigned to task s will be reassigned is defined as follows:

where T(W) is the completion time of task s with assigned worker set W, and aw(s.l) is the time that worker w arrives at task s. pFT m is the minimum possibility that a worker will be reassigned, pFT t means howmuch the time utilization ratio of worker w affects the possibility, and pFT m +pFT t = 1.

Algorithm 4 outlines the FT algorithm with same input and output of CT algorithm. Firstly, we calculate the abandoned possibility of each task s in A′ (line 4) and the reassigned possibility of each assigned worker w (line 5). Subsequently we randomly remove one worker w from the current task assignment by weights P FT s,w,AWS(s) (i.e., a worker is more likely to be removed with a higher weight) when the abandoned possibility is less than a random number ζ (0 ≤ ζ ≤ 1) and s can be finished without w (line 6 - 11).

Algorithm 4 FT

Input: A Output: A′ , W ′ , S′ 1 A′ = A,W ′ = ∅, S′ = ∅; 2 foreach task-worker pair < s,AWS(s) >∈ A′ do 3 A′ = A′- < s,AWS(s) >; 4 calculate pCT s,AWS(s) based on Equation 1; 5 calculate P F T s,w,AWS(s) for each worker w ∈ AWS(s) based on Equation 2; 6 while pCT s,AWS(s) < ζ do 7 random choose a worker w by weights P FT s,w,AWS(s) ; 8 if s cannot be completed without w then 9 break; 10 AWS(s) = AWS(s) - {w}; 11 W ′ =W ′ ∪ {w}; 12 A′ = A′∪ < s,AWS(s) >; 13 return A′ , W ′ , S′ ;

Taking the case in Fig. 1, we employ GTA-RTO algorithm to get the task assignment, i.e., {< s1, {w2,w5} >, < s2, {w1} >, < s3, {w3,w4} >}, with profit of 8.72, which is same with the profit generated by the OTA algorithm. That demonstrates the superiority of our GTA-RTO algorithm, which can obtain a near optimal result.

5 Experiment

5.1 Experimental Setup

We perform experiments on two datasets, gMission and synthetic dataset. gMission is an open source SC platform [Chen et al., 2014], where each task is associated with its publish time, location and reward. Since gMission data is not associated with an expected completion time and penalty rate, we generate the attributes following uniform distribution. For synthetic dataset, based on the observation from real dataset, the location and the publish time of a task follow uniform distribution, and its maximum reward follows Gaussian distribution.

We evaluate performance of the following algorithms: 1) OTA: Optimal Task Assignment; 2) GTA: basic Greedy Task Assignment; 3) GTA + CT: GTA with Coarse Tuning; 4) GTA + FT: GTA with Fine Tuning; 5) GTA-RTO: GTA with Random Tuning Optimization (including coarse and fine tuning); 6) k-MTA: Maximum Task Assignment [Kazemi and Shahabi, 2012] with Minimum Cost Maximum Flow technique. In MTA, the weight between the worker (w) vertex and task (s) vertex is set as 1 d(w.l,s.l) , and capacity between the task vertex and the fictitious destination vertex is set to k (k = 1, 2, 3). Two metrics are compared among the algorithms: Profit-gaining Ratio (PR, the ratio between the real and optimal total platform profit) and CPU time for finding the task assignment. All the algorithms are implemented on an Intel Core i5-2400 CPU @ 3.10G HZ with 8 GB RAM. The default values of all parameters are summarized in Tab. 1.

5.2 Experimental Results

Effect of |S|. We first study the effect of |S|. In Fig. 3a and 4a, naturally OTA achieves the highest profit-gaining ratio (i.e., PR = 1), followed by GTA-RTO, GTA+FT, GTA+CT, GTA and k-MTA. GTA-RTO can improve the total profit by up to 25.56% when comparing with GTA. While the profits generated by all the MTA methods decline with the growth of |S|. In Fig. 3b, 3c, 4b and 4c, although the CPU cost of all methods increases as |S| increases, the GTA related approaches perform better than the MTA approaches. OTA deteriorates much faster and cannot even return a result within tolerated time when |S| > 400 in gMission dataset and |S| > 7000 in synthetic dataset.

Effect of |W|. In Fig. 5a and 6a, GTA-RTO performs better than all the other greedy methods and MTA algorithms when |W| varies. Fig. 5b, 5c, 6b and 6c depict that all greedy methods run faster than OTA and MTA, showing the superiority of the greedy methods.

Effect of pCT m . In this part we evaluate the effect of pCT m , a parameter in coarse tuning representing the basic probability when abandoning tasks. In Fig. 7a and 8a, GTA-RTO achieves the highest profit among the greedy methods especially when pCT m is a middle value, which reminds us that too conservative and too aggressive strategies are not suitable. In Fig. 7b and 8b, the CPU cost of coarse tuning increases when pCT m increases since a more radical exploration strategy is more likely to make more workers reassigned. Besides, the performance of GTA and GTA+FT k.pdf stable in Fig. 7 and 8 since only coarse tuning is affected by pCT m . Due to the similar results of gMission and synthetic dataset, we only report the results of synthetic dataset in the subsequent experiments.

Effect of pFT m . We also evaluate the effect of pFT m , a basic probability parameter in fine tuning. In Fig. 9a, compared with the greedy approaches, GTA-RTO can obtain the highest profit. The CPU cost of fine tuning increases when pFT m increases (see Fig. 9b) with the same reason of the effect of pCT m . Moreover, the performance of GTA and GTA+CT does not change in Fig. 9 since only fine tuning is affected by pFT m .

Effect of n. Finally we study the effect of n, a parameter in GTA-RTO determining the termination condition. GTA-RTO will keep searching until the total profit stops improving for n iterations. In Fig. 10a, the profit of GTA increases when n grows since a higher n leads to a higher possibility to find a better result. Obviously, the CPU cost of GTA increases in Fig. 10b as n getting enlarged, since a higher n means more iterations during searching process.

Cost and profit analysis. We compute the reward loss s.rl (caused by overtime) for each task, i.e., s.rl = (s.tc - s.e) × s.pr (when s.tc > s.e), where s.tc is task's completion time, and further get the average reward loss, ¯ rl. For the task s that cannot obtain maximum reward from the requester, the reward loss shows a linearly growth trend with the increasing s.tc, matching the task reward pricing model. GTA with a low ¯ rl can only assign a small number of tasks and MTA with a high ¯ rl makes more tasks assigned, each of which generates a low platform profit. However, OTA and GTA-RTO can achieve a high profit by trading off various factors comprehensively.

Summary of our empirical study. Our empirical study can be summarize as follows: 1) OTA achieves the maximum profit but sacrifices a great deal of efficiency; 2) GTA-RTO achieves good balance between efficiency and effectiveness.

6 Conclusions

In this paper we study a novel SC problem, called Profitdriven Task Assignment (PTA), to find the optimal task assignment with maximal profit for SC platform. In order to achieve high effectiveness and efficiency, we addressed a few challenges by designing a reward pricing model to quantify the relationship between the task reward and its completion time, and developing optimal and efficient algorithms to assign tasks. To the best of our knowledge, it is the first work in SC that maximizes the profit from the point of SC platform when assigning tasks. Extensive empirical study based on both real and synthetic datasets confirms the superiority of our proposed algorithms.

Acknowledgements

This work was partially supported by NSFC (No. 61836007, 61832017, 61532018, 61525205 and 61872258), Alibaba Innovation Research (AIR) and A Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions (PAPD).