Alexandra Carpentier (University of Potsdam)

“Optimal ranking in crowd-sourcing”

Abstract: Consider a crowd sourcing 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 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 exchange of informations among the clusters. We prove in particular – in the case where d > n – that the problem of estimating the expert ranking is significantly easier than the problem of estimating the matrix M.
This talk is based on joint work with Emmanuel Pilliat and Nicolas Verzelen.