A crowdsourcing project is usually comprised of many unit tasks known as Human Intelligence Tasks (HITs). As answers to each HIT varies between workers, each HIT is often contracted to more than one worker to obtain a reliable and consistent enough answer. When implementing a project, an important design decision is how to formulate HITs and how to aggregate workers' answers. These decisions have strong impact on the quality of results and cost of elicitation process. One way to design an efficient elicitation procedure is to use adaptive stopping rules, which allows terminating the elicitation process as soon as a high quality result is guaranteed. Adaptively deciding how many times to issue a HIT is mostly well understood for the case of binary-answer HITs, thanks to the work of Abraham et al. [3, 2, 1]. In this line of work the authors focused on plurality-based stopping rules and provided their theoretical analysis. As a decision rule (when many alternatives are offered), it is well known that plurality may be inferior to other rules, such as the Condorcet method. We argue that for large number of possible answers, plurality-based stopping rules may also be terribly inefficient. In other words, one may need to elicit answers from many workers (at least linear in the number of answers) in order to get any reasonable approximation of the plurality answer. Somewhat surprisingly, we show that Condorset-based stopping rules may be much more efficient (with the number of workers to find the approximate Condorset winner depending only logarithmically on the number of answers). Moreover, in an important case of restricted domains, namely single-peaked domains, we show that the stopping time to find an approximate Condorcet-based winner does not depend on the number of answers at all. Overall, our results suggest that both crowdsourcing platform developers and HIT designers, should consider Condorcet-based adaptive stopping rules as a useful tool in their toolboxes.
展开▼
