Finish them! Pricing algorithms for human computation

Yihan Gao, Aditya Parameswaran

Research output: Contribution to journalConference article

Abstract

Given a batch of human computation tasks, a commonly ignored aspect is how the price (i.e., the reward paid to human workers) of these tasks must be set or varied in order to meet latency or cost constraints. Often, the price is set up-front and not modified, leading to either a much higher monetary cost than needed (if the price is set too high), or to a much larger latency than expected (if the price is set too low). Leveraging a pricing model from prior work, we develop algorithms to optimally set and then vary price over time in order to meet a (a) user-specified deadline while minimizing total monetary cost (b) user-specified monetary budget constraint while minimizing total elapsed time. We leverage techniques from decision theory (specifically, Markov Decision Processes) for both these problems, and demonstrate that our techniques lead to upto 30% reduction in cost over schemes proposed in prior work. Furthermore, we develop techniques to speed-up the computation, enabling users to leverage the price setting algorithms on-the-fly.

Original languageEnglish (US)
Pages (from-to)1965-1976
Number of pages12
JournalProceedings of the VLDB Endowment
Volume7
Issue number14
DOIs
StatePublished - Oct 2014
Event3rd Workshop on Spatio-Temporal Database Management, STDBM 2006, Co-located with the 32nd International Conference on Very Large Data Bases, VLDB 2006 - Seoul, Korea, Republic of
Duration: Sep 11 2006Sep 11 2006

Fingerprint

Costs
Decision theory

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Computer Science(all)

Cite this

Finish them! Pricing algorithms for human computation. / Gao, Yihan; Parameswaran, Aditya.

In: Proceedings of the VLDB Endowment, Vol. 7, No. 14, 10.2014, p. 1965-1976.

Research output: Contribution to journalConference article

Gao, Yihan ; Parameswaran, Aditya. / Finish them! Pricing algorithms for human computation. In: Proceedings of the VLDB Endowment. 2014 ; Vol. 7, No. 14. pp. 1965-1976.
@article{a5c4fcbcd34243e88fad6daede4acbc8,
title = "Finish them!: Pricing algorithms for human computation",
abstract = "Given a batch of human computation tasks, a commonly ignored aspect is how the price (i.e., the reward paid to human workers) of these tasks must be set or varied in order to meet latency or cost constraints. Often, the price is set up-front and not modified, leading to either a much higher monetary cost than needed (if the price is set too high), or to a much larger latency than expected (if the price is set too low). Leveraging a pricing model from prior work, we develop algorithms to optimally set and then vary price over time in order to meet a (a) user-specified deadline while minimizing total monetary cost (b) user-specified monetary budget constraint while minimizing total elapsed time. We leverage techniques from decision theory (specifically, Markov Decision Processes) for both these problems, and demonstrate that our techniques lead to upto 30{\%} reduction in cost over schemes proposed in prior work. Furthermore, we develop techniques to speed-up the computation, enabling users to leverage the price setting algorithms on-the-fly.",
author = "Yihan Gao and Aditya Parameswaran",
year = "2014",
month = "10",
doi = "10.14778/2733085.2733101",
language = "English (US)",
volume = "7",
pages = "1965--1976",
journal = "Proceedings of the VLDB Endowment",
issn = "2150-8097",
publisher = "Very Large Data Base Endowment Inc.",
number = "14",

}

TY - JOUR

T1 - Finish them!

T2 - Pricing algorithms for human computation

AU - Gao, Yihan

AU - Parameswaran, Aditya

PY - 2014/10

Y1 - 2014/10

N2 - Given a batch of human computation tasks, a commonly ignored aspect is how the price (i.e., the reward paid to human workers) of these tasks must be set or varied in order to meet latency or cost constraints. Often, the price is set up-front and not modified, leading to either a much higher monetary cost than needed (if the price is set too high), or to a much larger latency than expected (if the price is set too low). Leveraging a pricing model from prior work, we develop algorithms to optimally set and then vary price over time in order to meet a (a) user-specified deadline while minimizing total monetary cost (b) user-specified monetary budget constraint while minimizing total elapsed time. We leverage techniques from decision theory (specifically, Markov Decision Processes) for both these problems, and demonstrate that our techniques lead to upto 30% reduction in cost over schemes proposed in prior work. Furthermore, we develop techniques to speed-up the computation, enabling users to leverage the price setting algorithms on-the-fly.

AB - Given a batch of human computation tasks, a commonly ignored aspect is how the price (i.e., the reward paid to human workers) of these tasks must be set or varied in order to meet latency or cost constraints. Often, the price is set up-front and not modified, leading to either a much higher monetary cost than needed (if the price is set too high), or to a much larger latency than expected (if the price is set too low). Leveraging a pricing model from prior work, we develop algorithms to optimally set and then vary price over time in order to meet a (a) user-specified deadline while minimizing total monetary cost (b) user-specified monetary budget constraint while minimizing total elapsed time. We leverage techniques from decision theory (specifically, Markov Decision Processes) for both these problems, and demonstrate that our techniques lead to upto 30% reduction in cost over schemes proposed in prior work. Furthermore, we develop techniques to speed-up the computation, enabling users to leverage the price setting algorithms on-the-fly.

UR - http://www.scopus.com/inward/record.url?scp=84936873985&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84936873985&partnerID=8YFLogxK

U2 - 10.14778/2733085.2733101

DO - 10.14778/2733085.2733101

M3 - Conference article

AN - SCOPUS:84936873985

VL - 7

SP - 1965

EP - 1976

JO - Proceedings of the VLDB Endowment

JF - Proceedings of the VLDB Endowment

SN - 2150-8097

IS - 14

ER -