Journal article
Adversarial Top-K Ranking
IEEE transactions on information theory, Vol.63(4), pp.2201-2225
04/01/2017
DOI: 10.1109/TIT.2017.2659660
Abstract
We study the top-K ranking problem where the goal is to recover the set of top-K ranked items out of a large collection of items based on partially revealed preferences. We consider an adversarial crowdsourced setting where there are two population sets, and pairwise comparison samples drawn from one of the populations follow the standard Bradley-Terry-Luce model (i.e., the chance of item i beating item j is proportional to the relative score of item i to item j), while in the other population, the corresponding chance is inversely proportional to the relative score. When the relative size of the two populations is known, we characterize the minimax limit on the sample size required (up to a constant) for reliably identifying the top-K items, and demonstrate how it scales with the relative size. Moreover, by leveraging a tensor decomposition method for disambiguating mixture distributions, we extend our result to the more realistic scenario, in which the relative population size is unknown, thus establishing an upper bound on the fundamental limit of the sample size for recovering the top-K set.
Details
- Title: Subtitle
- Adversarial Top-K Ranking
- Creators
- Changho Suh - Korea Advanced Institute of Science and TechnologyVincent Y. F. Tan - Natl Univ Singapore, Dept Elect & Comp Engn, Singapore 117583, SingaporeRenbo Zhao - National University System
- Resource Type
- Journal article
- Publication Details
- IEEE transactions on information theory, Vol.63(4), pp.2201-2225
- Publisher
- IEEE
- DOI
- 10.1109/TIT.2017.2659660
- ISSN
- 0018-9448
- eISSN
- 1557-9654
- Number of pages
- 25
- Grant note
- R-263-000-B37-133 / National University of Singapore (NUS) through the NUS Young Investigator Award; National University of Singapore R-263-000-C12-112 / MoE AcRF Tier 1 Grant 2015R1C1A1A02036561 / National Research Foundation of Korea within MSIP through the Korean Government; National Research Foundation of Korea
- Language
- English
- Date published
- 04/01/2017
- Academic Unit
- Business Analytics
- Record Identifier
- 9984446263902771
Metrics
1 Record Views