Maximizing the expected value of experimentation for finding top-κ rank via aggregation of pairwise comparisons

Expected Value of Experimentation (EVE) is a decision analysis tool that allows one to measure the amount of useful “actionable information” to be gained upon carrying out an “experiment,” accounting for its possible stochastic outcomes. The EVE assessment also allows one to select a “most informative” experiment out of a set of experiments that can be conducted en route to solving a decision problem. We address the following problem: find a best-vs.-worst consensus partition of objects (top-κ set) by aggregating the results from several pairwise comparisons of these objects. We use EVE to determine which pair of objects should be assigned to an annotator for evaluation, to gain more information about them. A challenge in evaluating the EVE is high computational cost, exponential in the size of the decision space: this has limited EVE to use in small problems with only few alternative experiments in consideration. We tackle this challenge in our problem through the modeling and perturbation analysis of random walks on the space of the compared objects. This advance enhances the appeal of using EVE in decision analysis applications reliant on pairwise comparisons. Specifically, we use it for informing the interactive teaching/learning activity Create-Rank-Compete Crowdlearning. We also show that EVE-Informed Active Sampling algorithm’s performance compares favorably to the state-of-the-art Active Ranking algorithm.