Optimal Permutation Estimation in CrowdSourcing problems
众包问题中的最优排列估计
Motivated by crowdsourcing applications, we consider a model where we have partial observations from a bivariate isotonic n×d matrix with an unknown permutation π∗ acting on its rows. Focusing on the twin problems of recovering the permutation π∗ and estimating the unknown matrix, we introduce a polynomial-time procedure achieving the minimax risk for these two problems, this for all possible values of n, d, and all possible sampling efforts. Along the way we establish that,…