Poisoning Attack against Estimating from Pairwise Comparisons
  As pairwise ranking becomes broadly employed for elections, sports
competitions, recommendations, and so on, attackers have strong motivation and
incentives to manipulate the ranking list. They could inject malicious
comparisons into the training data to fool the victim. Such a technique is
called poisoning attack in regression and classification tasks. In this paper,
to the best of our knowledge, we initiate the first systematic investigation of
data poisoning attacks on pairwise ranking algorithms, which can be formalized
as the dynamic and static games between the ranker and the attacker and can be
modeled as certain kinds of integer programming problems. To break the
computational hurdle of the underlying integer programming problems, we
reformulate them into the distributionally robust optimization (DRO) problems,
which are computationally tractable. Based on such DRO formulations, we propose
two efficient poisoning attack algorithms and establish the associated
theoretical guarantees. The effectiveness of the suggested poisoning attack
strategies is demonstrated by a series of toy simulations and several real data
experiments. These experimental results show that the proposed methods can
significantly reduce the performance of the ranker in the sense that the
correlation between the true ranking list and the aggregated results can be
decreased dramatically.
