Achieving Budget-optimality with Adaptive Schemes in Crowdsourcing
Adaptive schemes, where tasks are assigned based on the data collected thus far, are widely used in practical crowdsourcing systems to efficiently allocate the budget. However, existing theoretical analyses of crowdsourcing systems suggest that the gain of adaptive task assignments is minimal. To bridge this gap, we investigate this question under a strictly more general probabilistic model, which has been recently introduced to model practical crowdsourcing datasets. Under this generalized Dawid-Skene model, we characterize the fundamental trade-off between budget and accuracy. We introduce a novel adaptive scheme that matches this fundamental limit. A given budget is allocated over multiple rounds. In each round, a subset of tasks with high enough confidence are classified, and increasing budget is allocated on remaining ones that are potentially more difficult. On each round, decisions are made based on the leading eigenvector of (weighted) non-backtracking operator corresponding to the bipartite assignment graph. We further quantify the gain of adaptivity, by comparing the tradeoff with the one for non-adaptive schemes, and confirm that the gain is significant and can be made arbitrarily large depending on the distribution of the difficulty level of the tasks at hand.
The paper looks at adaptive schemes in crowdsourcing and analyzes theoretically the trade-off between cost and accuracy under a generalized Dawid-Skene model. It also proposes an adaptive algorithm that achieves the theoretical limit and is strictly better than any non-adaptive algorithm.
 The paper provides a theoretical analysis of adaptive schemes in crowdsourcing. This is quite interesting work as many papers about crowdsourcing do not give any theoretical guarantees for their proposed solutions.  I am not very well-versed in the theoretical aspects mentioned in this paper, so I found it quite dense and had difficulty following the proofs. I will therefore focus in my comments on the aspects that would be of greater interest to a practitioner of crowdsourcing.  The algorithm: The description/pseudocode is not easy to understand. The explanation in the text helps considerably, however some details are not explained (for example, why are X and s_t set the way they are?). Also, what is the running time? Is it impractical to run on large data sets, or is it fast enough?  The simulation results focus on quite large numbers of queries per task. In practice it is uncommon to use more than 5 or 10 workers per task. A smaller range is not shown in the graphs (it's hard to say at what number they actually start, but looks like 20) and this range is also where the adaptive algorithm seems to perform the same or worse than the non-adaptive. Does this mean that the proposed algorithm is mainly of theoretical interest? Is it better in practice to stick with the non-adaptive version for small number of queries per task? It would have been nice to see the x-axis in the charts starting from 2 or 3 and go higher.   Summary/conclusions section is missing. It should summarize what was achieved and give directions to other research that naturally follows these results.     There are some problems in the references:  - The formatting is mixed. There are authors with full first name and others with initial. There are titles missing (e.g. [15]). - Many references are not mentioned in the text: [1, 2, 5, 6, 9, 12, 13, 17, 20, 21] - [10] and [11] are the same reference. [15] and [16] are also probably the same reference.     Other issues: - line 53: support - line 101: simulations confirm - both figures: the caption should explain what is on the left vs right - line 237: Theorem 2.4 is the incorrect number - line 250: at least - line 284: error rate ... is dominated - the supplementary material is out of order, theorem 2.2 is first, but 2.1 is last. - why does the proof of lemma 3.1 have its own section 4?