PARWiS: Winner determination from Active Pairwise Comparisons under a Shoestring Budget

Published in "To appear in the proceddings of the 21st IEEE International Conference on Data Mining (ICDM 2021)"
Dev Yashpal Sheth , Arun Rajkumar

We consider the problem of determining a winner among a set of 𝑛 items by actively comparing pairs of items. We focus on a practical scenario where we are given a shoestring budget (say 𝑐𝑛 for a small 𝑐 such as 2 or 3) where the usual sample complexity bounds for winner recovery become useless. We focus on the Bradley-Terry-Luce model for noisy comparisons and propose PARWiS, a novel algorithm for Pairwise Active Recovery of Winner under a Shoestring budget. Our algorithm is based on an active version of a spectral ranking procedure combined with a pair selection procedure. We consider several natural disruption measures for the pair selection procedure and show that they are theoretically equivalent to moving along certain gradient directions of popular estimation objectives. We perform extensive synthetic and real-world experiments to show that our algorithm recovers the item at the top effectively with shoestring budgets and outperforms several state-of-the-art algorithms.