Sequential Rank Aggregation from Pairwise Comparison

• Activity Number: 321 - Modern Statistical Learning for Ranking and Crowdsourcing
• Type: Topic Contributed
• Date/Time: Tuesday, August 1, 2017 : 10:30 AM to 12:20 PM
• Sponsor: Section on Statistical Learning and Data Science
• Author(s): Xiaoou Li* and Xi Chen and Yunxiao Chen and Jingcheng Liu and Zhiliang Ying
• Companies: University of Minnesota Twin Cities and NYU and Emory University and Columbia University and Columbia University
• Keywords: sequential analysis ; rank aggregation ; crowdsourcing

Abstract

The problem of inferring the ranking over a set of objects finds many applications in recommendation systems, web search, social choice, among many others. Recent development in crowdsourcing services makes it possible to collect pairwise comparison labels from a large number of crowd workers with a fixed amount of monetary cost for each comparison. For a requestor, it is desirable to adaptively decide the next pair of objects for comparison and to stop collecting labels to save for budget once the collected information is sufficient.

In this talk, I will first present several sequential ranking aggregation procedures, then show that these procedures are asymptotically optimal among all possible sequential and adaptive procedures.