Abstract

Most existing works on crowdsourcing assume that the workers follow the Dawid-Skene model, or the one-coin model as its special case, where every worker makes mistakes independently of other workers and with the same error probability for every task. We study a significant extension o this restricted model. We allow almost half of the workers to deviate from the one-coin model and for those workers, their probabilities of making an error to be task-dependent and to be arbitraril correlated. In other words, we allow for arbitrary adversaries, for which not only error probabilitie can be high, but which can also perfectly collude. In this adversarial scenario, we design an efficie algorithm to consistently estimate the workers’ error probabilities.