Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer
  Prediction
  We consider a crowdsourcing model in which $n$ workers are asked to rate the
quality of $n$ items previously generated by other workers. An unknown set of
$\alpha n$ workers generate reliable ratings, while the remaining workers may
behave arbitrarily and possibly adversarially. The manager of the experiment
can also manually evaluate the quality of a small number of items, and wishes
to curate together almost all of the high-quality items with at most an
$\epsilon$ fraction of low-quality items. Perhaps surprisingly, we show that
this is possible with an amount of work required of the manager, and each
worker, that does not scale with $n$: the dataset can be curated with
$\tilde{O}\Big(\frac{1}{\beta\alpha^3\epsilon^4}\Big)$ ratings per worker, and
$\tilde{O}\Big(\frac{1}{\beta\epsilon^2}\Big)$ ratings by the manager, where
$\beta$ is the fraction of high-quality items. Our results extend to the more
general setting of peer prediction, including peer grading in online
classrooms.
