Monte Carlo Sort for unreliable human comparisons
This addresses the challenge of subjective ranking tasks in fields like HR and sports, though it is an incremental improvement in sorting algorithms for noisy data.
The paper tackles the problem of sorting lists based on unreliable human comparisons, such as in marketing or recruiting, by developing a novel algorithm that minimizes human input while handling errors. The result is a method that efficiently identifies the correct sorted order by requesting the most informative comparisons.
Algorithms which sort lists of real numbers into ascending order have been studied for decades. They are typically based on a series of pairwise comparisons and run entirely on chip. However people routinely sort lists which depend on subjective or complex judgements that cannot be automated. Examples include marketing research; where surveys are used to learn about customer preferences for products, the recruiting process; where interviewers attempt to rank potential employees, and sporting tournaments; where we infer team rankings from a series of one on one matches. We develop a novel sorting algorithm, where each pairwise comparison reflects a subjective human judgement about which element is bigger or better. We introduce a finite and large error rate to each judgement, and we take the cost of each comparison to significantly exceed the cost of other computational steps. The algorithm must request the most informative sequence of comparisons from the user; in order to identify the correct sorted list with minimum human input. Our Discrete Adiabatic Monte Carlo approach exploits the gradual acquisition of information by tracking a set of plausible hypotheses which are updated after each additional comparison.