# profitdriven_task_assignment_in_spatial_crowdsourcing__c762d672.pdf

Proﬁt-driven Task Assignment in Spatial Crowdsourcing

Jinfu Xia1 , Yan Zhao1 , Guanfeng Liu2 , Jiajie Xu1 , Min Zhang1 and Kai Zheng3

1Institute of Artiﬁcial Intelligence, School of Computer Science and Technology, Soochow University 2Macquarie University 3University of Electronic Science and Technology of China jfxia@stu.suda.edu.cn, zhaoyan@suda.edu.cn, guanfeng.liu@mq.edu.au, {xujj, minzhang}@suda.edu.cn, zhengkai@uestc.edu.cn

In Spatial Crowdsourcing (SC) systems, mobile users are enabled to perform spatio-temporal tasks by physically traveling to speciﬁed locations with the SC platforms. SC platforms manage the systems and recruit mobile users to contribute to the SC systems, whose commercial success depends on the proﬁt attained from the task requesters. In order to maximize its proﬁt, an SC platform needs an online management mechanism to assign the tasks to suitable workers. How to assign the tasks to workers more cost-effectively with the spatio-temporal constraints is one of the most difﬁcult problems in SC. To deal with this challenge, we propose a novel Proﬁt-driven Task Assignment (PTA) problem, which aims to maximize the proﬁt of the platform. Speciﬁcally, we ﬁrst establish a task reward pricing model with tasks temporal constraints (i.e., expected completion time and deadline). Then we adopt an optimal algorithm based on tree decomposition to achieve the optimal task assignment and propose greedy algorithms to improve the computational efﬁciency. Finally, we conduct extensive experiments using real and synthetic datasets, verifying the practicability of our proposed methods.

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 proﬁt 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 proﬁt 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 proﬁt of SC system [Jain et al., 2009; Cooper et al., 2011], which are often difﬁcult to engineer non-monetary incentive schemes for tedious and repetitive work [Singer and Mittal, 2013] and unrealistic for commercial SC platform due to its proﬁt-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 proﬁt-based task assignment mechanisms have been developed in crowdsourcing system. For instance, considering the proﬁt 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 efﬁciency instead of improving the proﬁt. [Shah-Mansouri and Wong, 2015] proposes a proﬁt 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 proﬁt for the platform by designing different incentive mechanisms instead of paying attention to task assignment process. Fig. 1 illustrates an example of proﬁt-based task assignment problem with ﬁve 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.max R). The problem is to assign tasks to the suitable workers so as to maximize the total platform proﬁt. In SC, it is intuitive to assign the nearby tasks to workers without violating the spatio-temporal constraint, referred to as shortest

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

current time: 0

(1, 8) w1.r = 3

8 2 3 4 1 5 6 7

w3 w4 w5 (4, 3) w2.r = 3.2

(7, 4) w3.r = 2

(7, 3) w4.r = 3 (2, 3) w5.r = 3.2 shortest distance priority

our algorithm (GTA-RTO)

Figure 1: Running example

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 proﬁt of 5.7 (we assume the platform gets 80% of the reward as its proﬁt). However, this assignment algorithm leaves w4 and w5 unassigned, which may contribute more proﬁt for SC platform. To address these challenges, we propose a proﬁt-based task assignment framework that links the task assignment process with its economic performance in proﬁt. We ﬁrst formulate the Proﬁt-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 ﬁnds the optimal assignment result in terms of the total platform proﬁt. For the sake of efﬁciency, 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 ﬁnished 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 proﬁt 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 ﬁrst work that aims to maximize the proﬁt 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 efﬁciency of the proposed methods.

2 Problem Statement We deﬁne a set of preliminaries and formulate our PTA problem.

Deﬁnition 1 (Spatial Task) A spatial task, denoted by s = < s.l, s.p, s.e, s.d, s.wl, s.max R, s.pr >, is a task to be performed at location s.l, published at time s.p, expected to be ﬁnished at time s.e and will expire at deadline s.d. Each

task is also labelled with a required workload s.wl to ﬁnish task s by a normal worker (we simply use the time required to ﬁnish a task to denote s.wl). s.max R 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. Deﬁnition 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. Deﬁnition 3 (Available Worker 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) P w AW S(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 ﬁnish s. Deﬁnition 4 (Platform Proﬁt) Given a task s to be assigned and an available worker set AWS(s) for s, the proﬁt of SC platform can be computed as PAW S(s) = αRAW S(s), where PAW S(s) and RAW S(s) (0 RAW S(s) s.max R) are the proﬁt of SC platform to ﬁnish 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, RAW S(s), will be elaborated in Section 3. Note that we simply assume the proﬁt of an SC platform is in proportion to the reward (e.g., the proﬁt is 20% of the reward when α = 20%) and the remaining reward will be allocated to workers. We just focus on the proﬁt of SC platform while ignoring the reward allocation mechanism of workers. Deﬁnition 5 (Optimal Available Worker Set (Opt AWS)) An available worker set, AWS(s), is optimal if every of its proper subsets can only achieve a less-than-PAW S(s) platform proﬁt. Deﬁnition 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 T|S| i=1 AWS(si) = . Let A.P denote the total proﬁt of SC platform for task assignment A, i.e., A.P = P <s,AW S(s)> A PAW S(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 ﬁnd 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].

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

real reward

task completion time expected completion time

maximum rewared θ

penalty rate (pr) = 𝑡𝑎𝑛θ

Figure 2: Task reward pricing model

3 Reward Pricing Model Construction In order to design a cost-effective task assignment algorithm, a reasonable reward pricing model has to be established ﬁrstly 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 speciﬁes the task s expected completion time s.e, deadline s.d, maximum reward s.max R 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 proﬁt.

Deﬁnition 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:

T(AWS(s)) = s.t0 +

w AW S(s) (aw(s.l) s.p) + s.wl

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 P

w AW S(s) (aw(s.l) s.p)+s.wl

|AW S(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:

s.max R, T(AWS(s)) s.e s.max R s.pr (T(AWS(s)) s.e), s.e < T(AWS(s)) s.d 0, T(AWS(s)) > s.d

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 (Opt AWS) 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. 2) Find Opt AWSs 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 ﬁnd all Opt AWSs in each iteration. The process is omitted due to space limit. 3) Apply the tree-decomposition-based algorithm [Zhao et al., 2017] to ﬁnd the optimal task assignment with maximal proﬁts. In particular, we ﬁrst 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-ﬁrst manner to ﬁnd the optimal assignment. Consider the example in Fig. 1. With OTA algorithm, we can get the proﬁt of 8.72 for SC platform.

4.2 Greedy Task Assignment (GTA) For the sake of efﬁciency, 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 ﬁrst 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 ﬁrst arrival worker in W to perform s until s can be completed in expected time s.e (line 3-13). If there are no sufﬁcient 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 proﬁt of 5.3 in Fig. 1.

4.3 GTA with Random Tuning Optimization GTA is a polynomial-time greedy algorithm that ﬁnds 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 ﬁnal proﬁt. 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 proﬁt for the whole platform. To overcome these limitations, we improve GTA with Random Tuning Optimization (GTA-RTO), which contains two tuning strategies: coarse and ﬁne tuning. Coarse tuning randomly abandons the low-valuable tasks (e.g., tasks with low time utilization ratio of workers) and ﬁne tuning randomly reassigns partial workers to ﬁnd 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

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

Algorithm 1 GTA

Input: W, S Output: A, W , S

1 A = , W = W, S = S;

2 sorting tasks in S according to s.max R

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

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);

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;

10 if A .P > A.P then

12 until there is no improvement until n rounds;

13 return A;

Coarse Tuning (CT) algorithm and Fine Tuning (FT) algorithm are invoked in order, followed by GTA. Speciﬁcally, we ﬁrst 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 modiﬁed 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 proﬁt of A is higher than that of A, we replace A with A (line 911). Algorithm 2 stops when there is no improvement for n rounds, in which n can be speciﬁed 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 p CT s,AW S(s) based on Equation 1;

4 if p CT s,AW S(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 deﬁned as follows:

P CT s,W = p CT m + p CT t P w W aw(s.l) s.p (T(W) s.p) |W|

+ p CT r (1 R(s, W)

s.max R ), (1)

where p CT m + p CT t + p CT r = 1, T(W) is the completion time of task s with assigned worker set W, R(s, W) is the ﬁnal 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.max R is the rate of return. p CT m is the minimum possibility that a task can be abandoned. p CT t and p CT 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 ﬁrst 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 F T s,w,W that worker w( W) assigned to task s will be reassigned is deﬁned as follows:

P F T s,w,W = p F T m + p F T t aw(s.l) s.p

T(W) s.p , (2)

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. p F T m is the minimum possibility that a worker will be reassigned, p F T t means how much the time utilization ratio of worker w affects the possibility, and p F T m + p F T 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 F T s,w,AW S(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 ﬁnished without w (line 6 - 11).

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

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 p CT s,AW S(s) based on Equation 1;

5 calculate P F T s,w,AW S(s) for each worker w AWS(s) based on Equation 2;

6 while p CT s,AW S(s) < ζ do

7 random choose a worker w by weights P F T s,w,AW S(s);

8 if s cannot be completed without w then

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 proﬁt of 8.72, which is same with the proﬁt 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, g Mission and synthetic dataset. g Mission is an open source SC platform [Chen et al., 2014], where each task is associated with its publish time, location and reward. Since g Mission 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 ﬁne 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 ﬁctitious destination vertex is set to k (k = 1, 2, 3). Two metrics are compared among the algorithms: Proﬁt-gaining Ratio (PR, the ratio between the real and optimal total platform proﬁt) and CPU time for ﬁnding 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.

Parameter Default value

Number of tasks 500 (g Mission), 5000 (synthetic) Number of workers 500 (g Mission), 5000 (synthetic) Early stop round n 10 Parameters in CT p CT m = 0.2, p CT t = 0.4, p CT r = 0.4 Parameters in FT p F T m = 0.4, p F T t = 0.6

Table 1: Experiment parameters

5.2 Experimental Results

Effect of |S|. We ﬁrst study the effect of |S|. In Fig. 3a and 4a, naturally OTA achieves the highest proﬁt-gaining ratio (i.e., PR = 1), followed by GTA-RTO, GTA+FT, GTA+CT, GTA and k-MTA. GTA-RTO can improve the total proﬁt by up to 25.56% when comparing with GTA. While the proﬁts 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 g Mission 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 p CT m . In this part we evaluate the effect of p CT m , a parameter in coarse tuning representing the basic probability when abandoning tasks. In Fig. 7a and 8a, GTA-RTO achieves the highest proﬁt among the greedy methods especially when p CT 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 p CT 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 p CT m . Due to the similar results of g Mission and synthetic dataset, we only report the results of synthetic dataset in the subsequent experiments.

Effect of p F T m . We also evaluate the effect of p F T m , a basic probability parameter in ﬁne tuning. In Fig. 9a, compared with the greedy approaches, GTA-RTO can obtain the highest proﬁt. The CPU cost of ﬁne tuning increases when p F T m increases (see Fig. 9b) with the same reason of the effect of p CT m . Moreover, the performance of GTA and GTA+CT does not change in Fig. 9 since only ﬁne tuning is affected by p F T 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 proﬁt stops improving for n iterations. In Fig. 10a, the proﬁt of GTA increases when n grows since a higher n leads to a higher possibility to ﬁnd 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.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

100 200 300 400 500

OTA GTA+CT GTA+FT GTA-RTO

GTA 1-MTA 2-MTA 3-MTA

100 200 300 400 500

GTA GTA+CT GTA+FT GTA-RTO

1-MTA 2-MTA 3-MTA

(b) CPU cost

100 200 300 400 500

OTA GTA-RTO

(c) CPU cost

Figure 3: Effect of |S| on g Mission dataset

1k 3k 5k 7k 9k

OTA GTA+CT GTA+FT GTA-RTO

GTA 1-MTA 2-MTA 3-MTA

0 0.2 0.4 0.6 0.8

1k 3k 5k 7k 9k

GTA GTA+CT GTA+FT GTA-RTO

1-MTA 2-MTA 3-MTA

(b) CPU cost

1k 3k 5k 7k 9k

OTA GTA-RTO

(c) CPU cost

Figure 4: Effect of |S| on synthetic dataset

100 200 300 400 500

OTA GTA+CT GTA+FT GTA-RTO

GTA 1-MTA 2-MTA 3-MTA

100 200 300 400 500

GTA GTA+CT GTA+FT GTA-RTO

1-MTA 2-MTA 3-MTA

(b) CPU cost

100 200 300 400 500

OTA GTA-RTO

(c) CPU cost

Figure 5: Effect of |W| on g Mission dataset

1k 3k 5k 7k 9k

OTA GTA+CT GTA+FT GTA-RTO

GTA 1-MTA 2-MTA 3-MTA

0 0.2 0.4 0.6 0.8

1k 3k 5k 7k 9k

GTA GTA+CT GTA+FT GTA-RTO

1-MTA 2-MTA 3-MTA

(b) CPU cost

1k 3k 5k 7k 9k

OTA GTA-RTO

(c) CPU cost

Figure 6: Effect of |W| on synthetic dataset

Cost and proﬁt 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 proﬁt. However, OTA and GTA-RTO can achieve a high proﬁt by trading off various factors comprehensively.

Summary of our empirical study. Our empirical study can be summarize as follows: 1) OTA achieves the maximum proﬁt but sacriﬁces a great deal of efﬁciency; 2) GTA-RTO achieves good balance between efﬁciency and effectiveness.

0.1 0.2 0.3 0.4

OTA GTA GTA-RTO

GTA+CT GTA+FT

0 0.1 0.2 0.3 0.4 0.5 0.6

0.1 0.2 0.3 0.4

GTA GTA-RTO

GTA+CT GTA+FT

(b) CPU cost

Figure 7: Effect of p CT m on g Mission dataset

0.1 0.2 0.3 0.4

OTA GTA GTA-RTO

GTA+CT GTA+FT

0.1 0.2 0.3 0.4

GTA GTA-RTO

GTA+CT GTA+FT

(b) CPU cost

Figure 8: Effect of p CT m on synthetic dataset

0.2 0.4 0.6 0.8

OTA GTA GTA-RTO

GTA+CT GTA+FT

0.2 0.4 0.6 0.8

GTA GTA-RTO

GTA+CT GTA+FT

(b) CPU cost

Figure 9: Effect of p F T m on synthetic dataset

OTA GTA GTA-RTO

GTA+CT GTA+FT

GTA GTA-RTO

GTA+CT GTA+FT

(b) CPU cost

Figure 10: Effect of n on synthetic dataset

6 Conclusions In this paper we study a novel SC problem, called Proﬁtdriven Task Assignment (PTA), to ﬁnd the optimal task assignment with maximal proﬁt for SC platform. In order to achieve high effectiveness and efﬁciency, 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 efﬁcient algorithms to assign tasks. To the best of our knowledge, it is the ﬁrst work in SC that maximizes the proﬁt from the point of SC platform when assigning tasks. Extensive empirical study based on both real and synthetic datasets conﬁrms 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).

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

References [Chen et al., 2014] Zhao Chen, Rui Fu, Ziyuan Zhao, Zheng Liu, Leihao Xia, Lei Chen, Peng Cheng, Caleb Chen Cao, Yongxin Tong, and Chen Jason Zhang. gmission: A general spatial crowdsourcing platform. VLDB, 7(13):1629 1632, 2014. [Cheng et al., 2015a] Peng Cheng, Xiang Lian, Lei Chen, and Jinsong Han. Task assignment on multi-skill oriented spatial crowdsourcing. TKDE, 28(8):2201 2215, 2015. [Cheng et al., 2015b] Peng Cheng, Xiang Lian, Zhao Chen, Rui Fu, Lei Chen, Jinsong Han, and Jizhong Zhao. Reliable diversity-based spatial crowdsourcing by moving workers. VLDB, 8(10):1022 1033, 2015. [Cooper et al., 2011] Seth Cooper, Firas Khatib, Ilya Makedon, Hao Lu, Janos Barbero, David Baker, James Fogarty, Zoran Popovi c, et al. Analysis of social gameplay macros in the foldit cookbook. In FDG, pages 9 14, 2011. [Deng et al., 2015] Dingxiong Deng, Cyrus Shahabi, and Linhong Zhu. Task matching and scheduling for multiple workers in spatial crowdsourcing. In SIGSPATIAL, page 21, 2015. [Jain et al., 2009] Shaili Jain, Yiling Chen, and David C. Parkes. Designing incentives for online question and answer forums. In EC, pages 129 138, 2009. [Kazemi and Shahabi, 2012] Leyla Kazemi and Cyrus Shahabi. Geocrowd: Enabling query answering with spatial crowdsourcing. In SIGSPATIAL, pages 189 198, 2012. [Li et al., 2015] Yu Li, Manlung Yiu, and Wenjian Xu. Oriented online route recommendation for spatial crowdsourcing task workers. SSTD, pages 137 156, 2015. [Shah-Mansouri and Wong, 2015] Hamed Shah-Mansouri and Vincent W. S. Wong. Proﬁt maximization in mobile crowdsourcing: A truthful auction mechanism. In ICC, pages 3216 3221, 2015. [Singer and Mittal, 2013] Yaron Singer and Manas Mittal. Pricing mechanisms for crowdsourcing markets. In WWW, pages 1157 1166, 2013. [Song et al., 2017] Tianshu Song, Yongxin Tong, Libin Wang, Jieying She, Bin Yao, Lei Chen, and Ke Xu. Trichromatic online matching in real-time spatial crowdsourcing. In ICDE, pages 1009 1020, 2017. [Tong et al., 2016a] Yongxin Tong, Jieying She, Bolin Ding, Lei Chen, Tianyu Wo, and Ke Xu. Online minimum matching in real-time spatial data: Experiments and analysis. VLDB, 9(12):1053 1064, 2016. [Tong et al., 2016b] Yongxin Tong, Jieying She, Bolin Ding, and Libin Wang. Online mobile micro-task allocation in spatial crowdsourcing. In ICDE, pages 49 60, 2016. [Tong et al., 2017] Yongxin Tong, Libin Wang, Zimu Zhou, Bolin Ding, Lei Chen, Jieping Ye, and Ke Xu. Flexible online task assignment in real-time spatial data. VLDB, 10(11):1334 1345, 2017. [Tong et al., 2018a] Yongxin Tong, Libin Wang, Zimu Zhou, Lei Chen, Bowen Du, and Jieping Ye. Dynamic pricing in

spatial crowdsourcing: A matching-based approach. In SIGMOD, pages 773 788, 2018. [Tong et al., 2018b] Yongxin Tong, Yuxiang Zeng, Zimu Zhou, Lei Chen, Jieping Ye, and Ke Xu. A uniﬁed approach to route planning for shared mobility. VLDB, 11(11):1633 1646, 2018. [Vazirani, 2013] Vijay V Vazirani. Approximation algorithms. Springer Science & Business Media, 2013. [Yang et al., 2012] Dejun Yang, Guoliang Xue, Fang Xi, and Tang Jian. Crowdsourcing to smartphones: incentive mechanism design for mobile phone sensing. In Mobi Com, pages 173 184, 2012. [Zhao et al., 2017] Yan Zhao, Yang Li, Yu Wang, Han Su, and Kai Zheng. Destination-aware task assignment in spatial crowdsourcing. In CIKM, pages 297 306, 2017. [Zhao et al., 2019a] Yan Zhao, Jinfu Xia, Guanfeng Liu, Han Su, Defu Lian, Shuo Shang, and Kai Zheng. Preference-aware task assignment in spatial crowdsourcing. In AAAI, pages 80 87, 2019. [Zhao et al., 2019b] Yan Zhao, Kai Zheng, Yang Li, Han Su, Jiajun Liu, and Xiaofang Zhou. Destination-aware task assignment in spatial crowdsourcing: A worker decomposition approach. TKDE, pages 219 233, 2019.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)