Stanford InfoLab Publication Server

tDP: An Optimal-Latency Budget Allocation Strategy for Crowdsourced MAXIMUM Operations

Verroios, Vasilis and Lofgren, Peter and Garcia-Molina, Hector tDP: An Optimal-Latency Budget Allocation Strategy for Crowdsourced MAXIMUM Operations. Technical Report. Stanford InfoLab.


[img]PDF - Draft Version


Latency is a critical factor when using a crowdsourcing platform to solve a problem like entity resolution or sorting. In practice, most frameworks attempt to reduce latency by heuristically splitting a budget of questions into rounds, so that after each round the answers are analyzed and new questions are selected. We focus on one of the most extensively studied crowdsourcing operations, the MAX operation (finding the best element in a collection under human criteria), and we study the problem of budget allocation into rounds for this operation. We provide a polynomial-time dynamic-programming budget allocation algorithm that minimizes the latency when questions form tournaments in each round. Furthermore, we study the general case where questions can be asked in any arbitrary way in each round. Our theoretical results for the general case indicate that our approach is also optimal under certain worst and average-case scenarios. We compare our approach to alternatives on Amazon Mechanical Turk, where many of our theory assumptions do not necessarily hold. We find that our approach is also optimal in practice and achieves a notable improvement over alternatives in most cases.

Item Type:Techreport (Technical Report)
ID Code:1129
Deposited By:vasilis verroios
Deposited On:21 Mar 2015 23:06
Last Modified:21 Mar 2015 23:06

Download statistics

Repository Staff Only: item control page