Analysis of Crowdsourced Sampling Strategies for HodgeRank with Sparse Random Graphs

Crowdsourcing enables researchers to conduct social experiments on a heterogenous set of participants and at a lower economic cost than conventional laboratory studies. For example, researchers can harness internet users to conduct user studies on their personal computers. Among various approaches to conduct subjective tests, pairwise comparisons are expected to yield more reliable results. However, in crowdsourced studies, the individuals performing the ratings are diverse compared to more controlled settings, which is difficult to control for using traditional experimental designs; researchers have recently proposed several randomized methods to conduct user studies [1, 2, 3], which accommodate incomplete and imbalanced data. HodgeRank, as an application of combinatorial Hodge theory to the preference or rank aggregation problem from pairwise comparison data, possibly being incomplete and imbalanced, was first introduced by [4], and inspired a series of studies in statistical ranking [5, 6, 7, 8]. Hodge theory has also found applications in game theory [9] and computer vision [10, 11], in addition to traditional applications in fluid mechanics [12] etc. HodgeRank formulates the ranking problem in terms of the discrete Hodge decomposition of the pairwise data and shows that it can be decomposed into three orthogonal components: a gradient flow representing a global rating (optimal in the L