Assigning tasks to workers based on historical data: Online task assignment with two-sided arrivals

John P. Dickerson, Karthik Abinav Sankararaman, Aravind Srinivasan, Pan Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

31 Scopus citations

Abstract

Efficient allocation of tasks to workers is a central problem in crowds ourcing. In this paper, we consider a special setting inspired from spatial crowdsourcing platforms where both workers and tasks arrive dynamically. Additionally, we assume all tasks are heterogen eous and each worker-task assigmnent brings a distinct reward. The natural challenge lies in how to incorporate the uncertainty in the arrivals from both workers and tasks into our online allocation policy such that the total expected rewards are maximized. To att ack this challenge, we assume the arrival patterns of worker types and task type? are not erratic and can be predicted from historical data. To be more specific, we consider a finite time horizon T and assume in each time-step, a single worker and task are sampled (i.e., arriv) from two respective distributions independently, and this sampling process repeats identically and independently for the entire T online time-steps. Our model, called Online TaskAssignment with Two-Sided Arri vol (OTA-TSA), is a significant generalization of the classical online task assignment where the set of tasks is assumed to be available offline. For the general version of OTA-TSA. we present an optimal non-adaptive algorithm which achieves an online competitive ratio of 0.295. For the special case of OTA-TSA where the reward is a function of just the worker type, we present an improved algorithm (which is adaptive) and achieves a competitive ratio of at least 0.343. On the hardness side, along with showing that the ratio obtained by our non-adaptive algorithm is the best possible among all nona daptive algorithms, we further show that no (adaptive) algorithm can achieve a ratio better than 0.581 (unconditionally), even for the special case of OTA-TSA with homogenous tasks (i.e., all rewards are same). At the heart of our analysis lies a new technical tool (which is a refined notion of the birth-death process), called the two-stage birth-death process, which may be of independent intere st. Finally, we perform numerical experiments on two real-world datasets obtained from crowdsourcing platforms to complement our theoretical results.

Original languageEnglish (US)
Title of host publication17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages318-326
Number of pages9
ISBN (Print)9781510868083
StatePublished - 2018
Externally publishedYes
Event17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018 - Stockholm, Sweden
Duration: Jul 10 2018Jul 15 2018

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume1
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Conference

Conference17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018
Country/TerritorySweden
CityStockholm
Period7/10/187/15/18

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering

Keywords

  • Crowdsourcing model
  • Online matching
  • Randomized algorithms

Fingerprint

Dive into the research topics of 'Assigning tasks to workers based on historical data: Online task assignment with two-sided arrivals'. Together they form a unique fingerprint.

Cite this