Crowdsourcing — ranking workers & estimating ability
Crowdsourcing · ranking & ability estimation
A crowd answers a pile of tasks — each worker getting some right, some wrong. From the answers alone, can you rank the workers and estimate how good each one is?
Each worker \(i\) and task \(k\) has a hidden score \(M_{ik} \in [0,1]\), bi-isotonic: the workers can be ordered so one is uniformly better than another (higher score on every task), and the tasks likewise from easy to hard. We never see \(M\) — only noisy answers. Two models: Bernoulli (binary answers in {0,1}, correct with a probability that rises with \(M\) up to a peak ability) and Gaussian (\(M\) observed as \(M + \mathcal N(0,\sigma^2)\)).
Top: the true matrix \(M\) — left as the bi-isotonic score curves, right as a heat-map (it never changes; only the data below does). Bottom: the answers we actually observe. Shuffle the rows and/or columns to hide the orderings — that’s exactly what a ranking algorithm must undo.
The model in one line
Workers and tasks each have a hidden rank; the score matrix \(M_{ik}\) is non-decreasing as the worker gets better and as the task gets easier (bi-isotonicity). We only see one noisy draw per entry, yet the monotone shape lets us borrow strength across rows and columns to recover the orderings and the scores at the optimal rate.
Removing the row constraint — the isotonic model
Now drop bi-isotonicity on the rows: we keep only that every task ranks the workers the same way (each column is non-decreasing in worker ability), but a single worker’s scores across tasks may be arbitrary. The workers are still totally ordered — so the ranking is recoverable — yet the tasks carry no order. The latent matrix \(M\) is on the left, the noisy answers on the right; shuffle the rows to hide the worker ranking the algorithm has to rebuild.
The final step — recovering the labels
Everything above assumed we knew the right answers and only ranked workers or estimated \(M\). The last paper drops that. Each task \(k\) now carries an unknown binary label \(x^*_k \in \{-1,+1\}\), and all we see are the votes: worker \(i\) answers task \(k\) correctly with probability \(\tfrac{1+M_{ik}}{2}\), i.e. \(Y_{ik} = x^*_k\) with probability \(\tfrac{1+M_{ik}}{2}\) and \(-x^*_k\) otherwise — where \(M_{ik}=1\) is a perfect worker and \(M_{ik}=0\) a coin flip — with entries possibly missing (each vote observed with probability \(\lambda\)). The ability matrix \(M\) is isotonic after an unknown worker permutation, exactly the structure visualised just above. Plain majority vote can be barely better than chance when abilities are low; the COLT 2025 paper gives the first polynomial-time estimator that recovers \(x^*\) at the minimax-optimal rate — and, as a by-product, recovers the earlier ranking and estimation guarantees as special cases.
Each column below is a task with a hidden label \(x^*_k\); the workers’ \(\pm1\) votes fill the matrix (green \(-1\), blue \(+1\)). The two strips compare the true labels with the majority vote — drag ability down or remove workers and watch majority vote start making errors (outlined red).