Perfect clustering from pairwise comparisons
Siddhartha Satpathi · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 2017
We consider a pairwise comparisons model with n users and m items. Each user is shown a few pairs of items, and when a pair of items is shown to a user, he or she expresses a preference for one of the items based on a probabilistic model. The goal is to group users into clusters so that users within each cluster have similar preferences. We present an algorithm which clusters all users correctly with high probability using a number of pairwise comparisons which is within a polylog factor of a lower bound.