Double or Nothing: Multiplicative Incentive Mechanisms for Crowdsourcing
  Crowdsourcing has gained immense popularity in machine learning applications
for obtaining large amounts of labeled data. Crowdsourcing is cheap and fast,
but suffers from the problem of low-quality data. To address this fundamental
challenge in crowdsourcing, we propose a simple payment mechanism to
incentivize workers to answer only the questions that they are sure of and skip
the rest. We show that surprisingly, under a mild and natural "no-free-lunch"
requirement, this mechanism is the one and only incentive-compatible payment
mechanism possible. We also show that among all possible incentive-compatible
mechanisms (that may or may not satisfy no-free-lunch), our mechanism makes the
smallest possible payment to spammers. We further extend our results to a more
general setting in which workers are required to provide a quantized confidence
for each question. Interestingly, this unique mechanism takes a
"multiplicative" form. The simplicity of the mechanism is an added benefit. In
preliminary experiments involving over 900 worker-task pairs, we observe a
significant drop in the error rates under this unique mechanism for the same or
lower monetary expenditure.
