THESIS
2020
xi, 80 pages : illustrations ; 30 cm
Abstract
With the booming mobile Internet and sharing economy, online spatial crowdsourcing
services, such as Uber and Didi, are becoming important infrastructures of our daily
life. Existing studies about spatial crowdsourcing usually focus on the platform interests
and ignore experiences of individual requesters and workers. Because of the dynamically
changed task demand and worker supply, the major experience issue, for both workers
and requesters, is caused by insufficient valid assignments. In this thesis we discuss the
problem of how to allocate limited assignment resources fairly to both worker and requester
sides.
For a requester, because his/her task needs to be assigned as soon as possible, the
resource is nearby available workers. Thus, we study the minimizing maximum delay...[
Read more ]
With the booming mobile Internet and sharing economy, online spatial crowdsourcing
services, such as Uber and Didi, are becoming important infrastructures of our daily
life. Existing studies about spatial crowdsourcing usually focus on the platform interests
and ignore experiences of individual requesters and workers. Because of the dynamically
changed task demand and worker supply, the major experience issue, for both workers
and requesters, is caused by insufficient valid assignments. In this thesis we discuss the
problem of how to allocate limited assignment resources fairly to both worker and requester
sides.
For a requester, because his/her task needs to be assigned as soon as possible, the
resource is nearby available workers. Thus, we study the minimizing maximum delay
spatial crowdsourcing (MMD-SC) problem and propose solutions aiming at achieving a
worst case controlled task assignment. The MMD-SC problem assumes that both workers
and requesters come dynamically and considers not only the workers’ traveling time
costs but also the buffering time of tasks, thus it is very challenging due to two-sided
online setting. To address these challenges, we propose a space embedding based online
random algorithm and two efficient heuristic algorithms.
For the worker side, the resource is new tasks which need to be distributed to workers
as equally as possible. The first challenge is to formally define the worker fairness
and combine it with existing platform level goals, and the second challenge is to conduct
task assignment with consideration of worker fairness and platform interests. To address
these challenges, we formally define an online bi-objective matching problem, namely the
worker-fairness-aware assignment problem (WFAA), and some special cases/variants of
it to fit in most spatial crowdsourcing scenarios. We give corresponding solutions for different
cases of WFAA. Particularly, we show that the dynamic sequential case, which is
a generalization of an existing fairness scheduling problem, can be solved with an O(n)
fairness cost bound (n is the total worker number), and give an O(n/m) fairness cost bound
for the m-sized general batch case (m is the minimum batch size).
In addition, we show the effectiveness and efficiency of our methods via extensive
experiments on both synthetic and real datasets.
Post a Comment