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 α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 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Õ 1 βα 3 4 ratings per worker, andÕ 1 β 2 ratings by the manager, where β is the fraction of high-quality items. Our results extend to the more general setting of peer prediction, including peer grading in online classrooms.
This paper considers the problem of aggregating the work of many crowdsourcing workers, each of whom is capable of providing ratings on a set of m available items. The goal is to have the workers provide ratings for only a small fraction of the items, and still recover the "top K" items (with limited error) despite the potential for adversarial workers who can provide false or damaging ratings to the system. The authors provide a set of algorithms in how to assign workers to tasks, and then from their responses how to estimate the highest-quality items. The main result of the paper is  an associated bound that specifies how many ratings per worker are required to get a good estimate of the top group in terms of the error rate of the workers, the number of "top items" required, and the fraction of poor workers. 
 My overall evaluation of this work is that I find it quite interesting, but with some caveats and concerns. Here are the high-level points:  1. The goal of the paper, which is to design an algorithm to find highly-desired items in a large pool, seems very natural to me. I am also quite satisified with the worker model, which I think is reasonably realistic: some fraction of the workers provide accurate and high-quality ratings with few errors, whereas another fraction of the workers provide poor or potentially-harmful ratings, and the algorithm is able to obtain a small number of "gold standard ratings". Within this setting, the authors provide a very straightforward solution using a "matrix completion"-like algorithm, and they combine a number of interesting ideas (matrix concentration, nuclear-norm regularization, etc.) to obtain their result. The natural question to ask is "how many worker ratings and gold-standard ratings are needed?" and the bound proven by the authors provides a reasonably sufficient and clear answer.  2. One of the downsides of the paper is that it seems to be trying to do a lot in 8 pages. The paper proposes one main algorithm, but includes about 3-4 other subroutines, each of which involves some significant complexity and detail. There is an application of randomized rounding, the authors need to apply a Lagrangian duality argument, there is the use of a matrix optimization with a trace-norm constraint, etc. There is a lot of notation as well, and keeping it all straight while reading is quite a challenge. So one major objection is that the authors simply tried to do too much here, and maybe went a little overboard without describing in suitable detail all of the pieces.  3. A bigger concern is that the paper is sloppy in a number of places, and one has the impression that it was written in a hurry without a careful reading. Here are just a few (big) examples: -- In the definition of the setting, the authors refer to "when i \in [m] and j \in [m]" which suggests that the #workers and #items are the same (which is suggested in the intro as well). But later it's clear that the authors probably meant "i \in [n]" -- The description in Figure 1 says "indicated by \tilde{r}" but I don't see that character anywhere in the figure (and I wanted to understand what it means) -- The authors refer to "rating it ourself" -- who is "ourself"??! This was a very confusing way of describing what I can only assume to be a "gold standard oracle". -- I tried to look at references in the main body of the document to see what papers were being cited and... I found nothing. Where is Moitra et al? Agarwal et al? Mannor/Tsitsiklis? These missing references were very suspicious to me, and it makes it very hard to evaluate the novelty. -- This seems to be a highly-relevant paper which doesn't appear to have been cited: *Who Moderates the Moderators? Crowdsourcing Abuse Detection in User-Generated Content* A Ghosh, S Kale, P McAfee  I would lean towards acceptance for this paper, as many of the issues above can be fixed with a good revision. But indeed some doubts still linger.