B1736
Title: Optimal ranking in crowdsourcing
Authors: Alexandra Carpentier - Universitaet Potsdam (Germany) [presenting]
Emmanuel Pilliat - Universite Montpellier (France)
Nicolas Verzelen - INRAE (France)
Abstract: Consider a crowdsourcing problem where we have $n$ experts and $d$ tasks. The average ability of each expert for each task is stored in an unknown matrix $M$, which is only observed in noise and incompletely. We make no (semi) parametric assumptions, but assume that both experts and tasks can be perfectly ranked: so that if an expert is better than another, she performs on average better on all tasks than the other - and that the same holds for the tasks. This implies that if the matrix $M$ is permuted so that the experts and tasks are perfectly ranked, then the permuted matrix $M$ is bi-isotonic. We focus on the problem of recovering the optimal ranking of the experts in the $l_2$ norm, when the questions are perfectly ranked. We provide a minimax-optimal and computationally feasible method for this problem, based on hierarchical clustering, PCA, and the exchange of information among the clusters. We prove, in particular, - in the case where $d$ is larger than $n$- that the problem of estimating the expert ranking is significantly easier than the problem of estimating the matrix $M$.
