  We study the problem of rank aggregation where the goal is to obtain a global
ranking by aggregating pair-wise comparisons of voters over a set of items. We
consider an adversarial setting where the voters are partitioned into two sets.
The first set votes in a stochastic manner according to the popular score-based
Bradley-Terry-Luce (BTL) model for pairwise comparisons. The second set
comprises malicious Byzantine voters trying to deteriorate the ranking. We
consider a strongly-adversarial scenario where the Byzantine voters know the
BTL scores, the votes of the good voters, the algorithm, and can collude with
each other. We first show that the popular spectral ranking based
Rank-Centrality algorithm, though optimal for the BTL model, does not perform
well even when a small constant fraction of the voters are Byzantine. We
introduce the Byzantine Spectral Ranking Algorithm (and a faster variant of
it), which produces a reliable ranking when the number of good voters exceeds
the number of Byzantine voters. We show that no algorithm can produce a
satisfactory ranking with probability > 1/2 for all BTL weights when there are
more Byzantine voters than good voters, showing that our algorithm works for
all possible population fractions. We support our theoretical results with
experimental results on synthetic and real datasets to demonstrate the failure
of the Rank-Centrality algorithm under several adversarial scenarios and how
the proposed Byzantine Spectral Ranking algorithm is robust in obtaining good
rankings.
