  For many queries in the Web retrieval setting there is an on-going ranking
competition: authors manipulate their documents so as to promote them in
rankings. Such competitions can have unwarranted effects not only in terms of
retrieval effectiveness, but also in terms of ranking robustness. A case in
point, rankings can (rapidly) change due to small indiscernible perturbations
of documents. While there has been a recent growing interest in analyzing the
robustness of classifiers to adversarial manipulations, there has not yet been
a study of the robustness of relevance-ranking functions. We address this
challenge by formally analyzing different definitions and aspects of the
robustness of learning-to-rank-based ranking functions. For example, we
formally show that increased regularization of linear ranking functions
increases ranking robustness. This finding leads us to conjecture that
decreased variance of any ranking function results in increased robustness. We
propose several measures for quantifying ranking robustness and use them to
analyze ranking competitions between documents' authors. The empirical findings
support our formal analysis and conjecture for both RankSVM and LambdaMART.
