Statistical Depth Functions for Ranking Distributions:
Definitions, Statistical Learning and Applications

Morgane Goibert Stéphan Clémençon Ekhine Irurozki Pavlo Mozharovskyi

Télécom Paris Criteo Télécom Paris Télécom Paris Télécom Paris

###### Abstract

The concept of median/consensus has been widely investigated in order to
provide a statistical summary of ranking data, i.e. realizations of a random
permutation $\Sigma$ of a finite set, $\\{1,\;\ldots,\;n\\}$ with $n\geq 1$
say. As it sheds light onto only one aspect of $\Sigma$’s distribution $P$, it
may neglect other informative features. It is the purpose of this paper to
define analogues of quantiles, ranks and statistical procedures based on such
quantities for the analysis of ranking data by means of a metric-based notion
of depth function on the symmetric group. Overcoming the absence of vector
space structure on $\mathfrak{S}_{n}$, the latter defines a center-outward
ordering of the permutations in the support of $P$ and extends the classic
metric-based formulation of consensus ranking (medians corresponding then to
the deepest permutations). The axiomatic properties that ranking depths should
ideally possess are listed, while computational and generalization issues are
studied at length. Beyond the theoretical analysis carried out, the relevance
of the novel concepts and methods introduced for a wide variety of statistical
tasks are also supported by numerous numerical experiments.

##  1 Introduction

The statistical analysis of ranking data as recently received much attention
(e.g. [1] and references therein), fed by the increasing number of modern
applications involving preferences data (search engines, recommender systems,
etc.). Such data usually consist of $N\geq 1$ permutations
$\sigma_{1},\;\ldots,\;\sigma_{N}$ on an ensemble of $n\geq 1$ items, indexed
by $i\in\\{1,\;\ldots,\;n\\}$. The major scientific challenge arises from the
absence of any vector space structure on the set of all permutations, the
symmetric group $\mathfrak{S}_{n}$. Given the impossibility of ’averaging’ the
$\sigma_{j}$’s in a straightforward manner, the issue of summarizing a ranking
dataset by a single permutation, referred to as Consensus Ranking or Ranking
Aggregation, has concentrated much interest (seminal works of [17, 13] in
social choice theory, [53] in bioinformatics, [18] in meta-search engines,
[15] in competition ranking, etc.). Two approaches to Consensus Ranking have
been studied. The first one, initiated by Condorcet in the 18th century, is
based on probabilistic modelling. The second one is a metric-based: equipped
with a (pseudo-) distance on $\mathfrak{S}_{n}$, a barycentric permutation,
referred to as a ranking median, is found. However, central measures such as
medians shed light on only one aspect of a multivariate distribution and
ignore other interesting characteristics. Thus, the informative nature of
ranking medians about the distribution $P$ of a random permutation $\Sigma$,
i.e. a r.v. takings its values in $\mathfrak{S}_{n}$, is limited and must be
complemented by additional quantities, providing information analogous to that
illuminated by quantiles for a univariate distribution.

This article is devoted to defining such quantities for ranking data. We
extend the statistical depth concept, originally introduced so as to define
quantiles for probability distributions on $\mathbb{R}^{d}$ with $d\geq 2$
(see e.g. [51]), to ranking distributions. Some basics in statistical depth
theory are briefly recalled in section 2, while section 3 introduced an
extension of the notion of depth function tailored to ranking data. Desirable
properties for ranking depths are listed therein, and shown to hold under mild
conditions, e.g. stochastic transitivity. Based on a pseudo-metric on
$\mathfrak{S}_{n}$, the depth of a ranking $\sigma$ relative to $P$ measures
its expected closeness to the random permutation $\Sigma$. Hence, ranking
medians correspond to the deepest rankings. In section 4, statistical
guarantees are provided for the ranking depth and its by-products, in the form
of non-asymptotic bounds for the deviations between the ranking depth function
and its statistical counterpart in particular. A trimming algorithm, based on
the ranking depth concept, to recover automatically a stochastically
transitive version of the empirical ranking distribution is also proposed
therein. Beyond the theoretical/algorithmic concepts introduced and analyzed
here, the relevance of the notion of ranking depth is motivated by a wide
variety of statistical applications, illustrated by several numerical
experiments in section 5.

The main contributions of the paper are summarized below:

  * •

Statistical depth and related axiomatic properties are extended to ranking
data, in order to emulate quantiles/ranks for r.v.’s valued in
$\mathfrak{S}_{n}$.

  * •

A finite-sample analysis ensures the usability of the notion of ranking depth
introduced.

  * •

An algorithm of great simplicity that uses ranking depth to build
stochastically transitive empirical ranking distributions (based on which,
crucial statistical tasks such as consensus ranking are straightforward) is
proposed.

  * •

The ranking depth and the related quantile regions in $\mathfrak{S}_{n}$ it
defines can be used for the statistical analysis of rankings: 1) fast and
robust recovery of medians in consensus ranking, 2) informative graphical
representations of ranking data, 3) anomaly/novelty detection, 4) homogeneity
testing.

##  2 Background and Preliminaries

We start with recalling some basics in statistical depth theory, together with
key notions of the statistical analysis of ranking data involved in the
subsequent analysis. Throughout the paper the indicator function of any event
$\mathcal{E}$ is denoted by $\mathbb{I}\\{\mathcal{E}\\}$, the Dirac mass at
any point $a$ by $\delta_{a}$, the floor function by
$u\in\mathbb{R}\mapsto\lfloor u\rfloor$, the convolution product of two real
valued functions $f$ and $g$ defined on the real line, when well-defined, by
$f*g$, the cardinality of any finite set $E$ by $\\#E$ and the set of
permutations of $\\{1,\;\ldots,\;n\\}$ by $\mathfrak{S}_{n}$ for $n\geq 1$.

###  2.1 Depth Functions for Multivariate Data

In absence of any ’natural order’ on $\mathbb{R}^{d}$ with $d\geq 2$, the
concept of statistical depth permits to define a center-outward ordering of
points in the support of a probability distribution $P$ on $\mathbb{R}^{d}$,
so as to extend the notions of order and (signed) rank statistics to
multivariate data, see e.g. [51]. A depth function
$D_{P}:\mathbb{R}^{d}\rightarrow\mathbb{R}_{+}$ relative to $P$ should ideally
assign the highest values $D_{P}(x)$ to points $x\in\mathbb{R}^{d}$ near the
”center” of the distribution. Originally introduced in the seminal
contribution [60], the half-space depth of $x$ in $\mathbb{R}^{d}$ relative to
$P$ is the minimum of the mass $P(H)$ taken over all closed half-spaces
$H\subset\mathbb{R}^{d}$ such that $x\in H$. Many alternatives have been
proposed since then, see e.g. [40, 44, 36, 9, 52, 61, 10, 64]. To compare the
merits and drawbacks of different notions of depth function, an axiomatic
nomenclature has been introduced in [64], listing four properties that
statistical depths should ideally satisfied, see [23, 51] for a different
formulation of a statistically equivalent set of properties.

  * $(i)$

(Affine invariance) Denoting by $P_{X}$ the distribution of any r.v. $X$
taking its values in $\mathbb{R}^{d}$, it holds: $D_{P_{AX+b}}(Ax+b)=D_{P}(x)$
for all $x\in\mathbb{R}^{d}$, any r.v. $X$ valued in $\mathbb{R}^{d}$, any
$d\times d$ nonsingular matrix $A$ with real entries and any vector $b$ in
$\mathbb{R}^{d}$.

  * $(ii)$

(Maximality at center) For any probability distribution $P$ on
$\mathbb{R}^{d}$ that possesses a symmetry center $x_{P}$ (for different
notions of center), the depth function $D_{P}$ takes its maximum value at it,
i.e. $D_{P}(x_{P})=\sup_{x\in\mathbb{R}^{d}}D_{P}(x)$.

  * $(iii)$

(Monotonicity relative to deepest point) For any probability distribution $P$
on $\mathbb{R}^{d}$ with deepest point $x_{P}$, the depth at any point $x$ in
$\mathbb{R}^{d}$ decreases as one moves away from $x_{P}$ along any ray
passing through it, i.e. $D_{P}(x)\leq D_{P}(x_{P}+\alpha(x-x_{P}))$ for any
$\alpha$ in $[0,1]$.

  * $(iv)$

(Vanishing at infinity) For any probability distribution $P$ on
$\mathbb{R}^{d}$, the depth function $D_{P}$ vanishes at infinity, i.e.
$D_{P}(x)\rightarrow 0$ as $||x||$ tends to infinity.

As the distribution $P$ of interest is generally unknown in practice, its
analysis relies on the observation of $N\geq 1$ independent realizations
$X_{1},\;\ldots,\;X_{N}$ of $P$. A statistical version of $D_{P}(x)$ can be
built by replacing $P$ with its empirical counterpart
$\widehat{P}_{N}=(1/N)\sum_{i=1}^{N}\delta_{X_{i}}$, yielding the empirical
depth function $D_{\widehat{P}_{N}}(x)$. Its consistency and asymptotic
normality have been studied for various notions of depth, refer to e.g. [21,
65], and concentration results for empirical depth and contours have been
recently proved in the half-space depth case, see [5, 4].

###  2.2 Consensus Ranking

Given a certain metric $d(.,\;.)$ on $\mathfrak{S}_{n}$ and a r.v. $\Sigma$
defined on a probability space $(\Omega,\;\mathcal{F},\;\mathbb{P})$ and drawn
from an unknown probability distribution $P$ on $\mathfrak{S}_{n}$ (i.e.
$P(\sigma)=\mathbb{P}\\{\Sigma=\sigma\\}$ for any
$\sigma\in\mathfrak{S}_{n}$), the metric approach to consensus ranking
consists in finding a ranking $\sigma^{*}\in\mathfrak{S}_{n}$ whose expected
distance to $\Sigma$ is minimum, i.e. such that

$L_{P}(\sigma^{*})=\min_{\sigma\in\mathfrak{S}_{n}}L_{P}(\sigma),$ (1)

where $L_{P}(\sigma)=\mathbb{E}_{P}[d(\Sigma,\sigma)]$ is referred to as the
ranking risk of any median candidate $\sigma$ in $\mathfrak{S}_{n}$ w.r.t. $d$
and $\Sigma$. The ranking median $\sigma^{*}$ (not necessarily unique) is
viewed as an informative summary of $P$ and $L_{P}(\sigma^{*})$ as a
dispersion measure. The choice of the (pseudo) distance $d(.,\;.)$ is crucial,
regarding the theoretical properties of the corresponding medians and the
computational feasibility, see section 3. Various distances have been
considered in the literature, see e.g. [19], the most popular choices being
listed below: $\forall(\sigma,\sigma^{\prime})\in\mathfrak{S}_{n}^{2}$,

$\displaystyle d_{\tau}(\sigma,\sigma^{\prime})$ $\displaystyle=$
$\displaystyle\sum_{i<j}\mathbb{I}\left\\{\left(\sigma(i)-\sigma(j))(\sigma^{\prime}(i)-\sigma^{\prime}(j)\right)<0\right\\},$
$\displaystyle d_{2}(\sigma,\sigma^{\prime})$ $\displaystyle=$
$\displaystyle\left(\sum_{i=1}^{n}(\sigma(i)-\sigma^{\prime}(i))^{2}\right)^{1/2},$
$\displaystyle d_{1}(\sigma,\sigma^{\prime})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\left|\sigma(i)-\sigma^{\prime}(i)\right|,$
$\displaystyle d_{H}(\sigma,\sigma^{\prime})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\mathbb{I}\left\\{\sigma(i)\neq\sigma^{\prime}(i)\right\\},$

known respectively as the Kendall $\tau$, the Spearman $\rho$, the Spearman
footrule and the Hamming distances. The literature has essentially focused on
solving a statistical version of the minimization problem (1), see e.g. [30],
[20] or [2]. Assuming that $N\geq 1$ independent copies
$\Sigma_{1},\;\ldots,\;\Sigma_{N}$ of the generic r.v. $\Sigma$ are observed,
a natural empirical estimate of $L_{P}(\sigma)$ is
$\widehat{L}_{N}(\sigma)=(1/N)\sum_{s=1}^{N}d(\Sigma_{s},\sigma)=L_{\widehat{P}_{N}}(\sigma)$,
where $\widehat{P}_{N}=(1/N)\sum_{i=1}^{N}\delta_{\Sigma_{i}}$ is the
empirical measure. The set $\mathfrak{S}_{n}$ being of finite cardinality, an
empirical ranking risk minimizer always exists, just like a solution to (1),
not necessarily unique however. Generalization guarantees and fast rate
conditions for empirical consensus ranking have been investigated in [11].

##  3 Depth Functions for Ranking Data

In order to define relevant extensions of the concept of statistical depth to
ranking data, we define axiomatic properties that candidate functions on
$\mathfrak{S}_{n}$ should satisfy. We next show that the metric-based ranking
depths we propose to analyze ranking distributions satisfy these properties
under mild conditions.

###  3.1 Ranking Depths - Axioms

Just like in the multivariate setup (see subsection 2.1), a list of key
properties the ranking depth function $D_{P}$ should ideally satisfy can be
made. These properties are essential to emulate the information provided by
quantiles (resp. quantile regions) of univariate distributions (resp.
multivariate distributions) in a relevant manner. Let $P$ be a ranking
distribution, $d$ a distance on $\mathfrak{S}_{n}$, the properties desirable
for any ranking depth $D_{P}:\mathfrak{S}_{n}\rightarrow\mathbb{R}_{+}$ are
listed below.

######  Property 1.

(Invariance) For any $\pi\in\mathfrak{S}_{n}$, consider the ranking
distribution $\pi P$ defined by: $(\pi P)(\sigma)=P(\sigma\pi^{-1})$ for all
$\sigma\in\mathfrak{S}_{n}$. It holds that: $D_{P}(\sigma)=D_{\pi
P}(\sigma\pi)$ for all $(\sigma,\;\pi)\in\mathfrak{S}_{n}^{2}$.

######  Property 2.

(Maximality at center) For any probability distribution $P$ on
$\mathfrak{S}_{n}$ that possesses a symmetry center $\sigma_{P}$ (in a certain
sense, e.g. w.r.t. to a given metric $d$ on $\mathfrak{S}_{n}$), the depth
function $D_{P}$ takes its maximum value at it, i.e.
$D_{P}(\sigma_{P})=\max_{\sigma\in\mathfrak{S}_{n}}D_{P}(\sigma)$.

######  Property 3.

(Local monotonicity relative to deepest ranking) Assume that the deepest
ranking $\sigma^{*}$ is unique. The quantity $D_{P}(\sigma)$ decreases as
$d(\sigma^{*},\sigma)$ locally increases, i.e. for any $\pi$ such that
$d(\sigma^{*},\sigma\pi)=d(\sigma^{*},\sigma)+1$, then we have
$D_{P}(\sigma)>D_{P}(\sigma\pi)$.

Note that, insofar as $\mathfrak{S}_{n}$ is of finite cardinality, there is no
relevant analogue of the ’vanishing at infinity’ property for multivariate
depth. A stronger monotonicity property can also be formulated.

######  Property 4.

(Global monotonicity) Assume that the deepest ranking $\sigma^{*}$ is unique.
The quantity $D_{P}(\sigma)$ decreases as $d(\sigma^{*},\sigma)$ globally
increases, i.e. $d(\sigma^{*},\sigma^{\prime})>d(\sigma^{*},\sigma)\Rightarrow
D_{P}(\sigma^{\prime})<D_{P}(\sigma)$.

###  3.2 Metric-based Ranking Depth Functions

Seeking to define a ranking depth that satisfies the properties listed above
and such that the medians $\sigma_{P}^{*}$ of $P$ have maximal depth, the
metric approach provides natural candidates, just like for consensus ranking.

######  Definition 1.

(Metric-based ranking depth) Let $d$ be a distance and $P$ a distribution on
$\mathfrak{S}_{n}$. The ranking depth based on $d$ is defined as:
$D_{P}^{(d)}$: $\forall\sigma\in\mathfrak{S}_{n}$,
$D_{P}^{(d)}(\sigma)=\mathbb{E}_{P}[||d||_{\infty}-d(\sigma,\Sigma)]=||d||_{\infty}-L_{P}(\sigma)$,
with
$||d||_{\infty}=\max_{(\sigma,\sigma^{\prime})\in\mathfrak{S}_{n}^{2}}d(\sigma,\sigma^{\prime})$.

The shift induced by $||d||_{\infty}\geq
L^{\star}=\max_{\sigma\in\mathfrak{S}_{n}}L_{P}(\sigma)$ simply guarantees
non-negativity, in accordance with Definition 2.1 in [64], while defining the
same center-outward ordering of the permutations $\sigma$ in
$\mathfrak{S}_{n}$ as $-L_{P}$. Notice that metric-based ranking depths can be
viewed as extensions of multivariate depth functions of type A in the
nomenclature proposed in [64]. For simplicity, we omit the superscript $(d)$
and rather write $D_{P}$ when no confusion is possible about the distance
considered.

A ranking $\sigma$ in $\mathfrak{S}_{n}$ is said to be deeper than another one
$\sigma^{\prime}$ relative to the ranking distribution $P$ iff
$D_{P}(\sigma^{\prime})\leq D_{P}(\sigma)$ and we write
$\sigma^{\prime}\preceq_{D_{P}}\sigma$. The ranking depth ordering
$\preceq_{D_{P}}$ is the preorder related to the depth function $D_{P}$.
Equipped with this notion of depth on $\mathfrak{S}_{N}$, medians $\sigma^{*}$
of $P$ w.r.t. the metric $d$ correspond to the deepest rankings. If $P$ is a
Dirac mass $\delta_{\sigma_{0}}$, the ranking depth then simply reduces to the
measure of closeness defined by the distance $d$ chosen:
$D_{P}(\sigma)=||d||_{\infty}-d(\sigma_{0},\sigma)$. In contrast, if $P$ is
the uniform distribution, the ranking depth relative to a classic distance on
$\mathfrak{S}_{n}$ is constant over $\mathfrak{S}_{n}$. The depth function
also permits to partition the space $\mathfrak{S}_{n}$ into subsets of
rankings with equal depth.

######  Definition 2.

(Depth regions/contours) For any $u\in\mathbb{R}$, the region of depth $u$ is
the superlevel set
$\mathcal{R}_{P}(u)=\\{\sigma\in\mathfrak{S}_{n}:\;D_{P}(\sigma)\geq u\\}$ of
$D_{P}$, while the ranking contour of depth $u$ is the set
$\partial\mathcal{R}_{P}(u)=\\{\sigma\in\mathfrak{S}_{n}:\;D_{P}(\sigma)=u\\}$.

Equipped with this notation, $\partial\mathcal{R}_{P}(-L_{P}^{*})$ is the set
of medians of $P$ w.r.t. the metric $d$.

######  Definition 3.

(Depth survivor function) The ranking depth survivor function is
$S_{P}:u\in\mathbb{R}\mapsto S_{P}(u)=\mathbb{P}\\{D_{P}(\Sigma)\geq u\\}$.

Based on the metric-based ranking depth, the quantile regions are defined as
follows.

######  Definition 4.

(Quantile regions in $\mathfrak{S}_{n}$) Let $\alpha\in(0,1)$. The depth
region with probability content $\alpha$ is the region of depth
$S_{P}^{-1}(\alpha)=\inf\\{u\in\mathbb{R}:\;S_{P}(u)\leq 1-\alpha\\}$:
$R_{P}(\alpha)=\mathcal{R}_{P}(S_{P}^{-1}(\alpha))$. The mapping
$\alpha\in(0,1)\mapsto S_{P}^{-1}(\alpha)$ is called the ranking quantile
function.

###  3.3 The Metric Approach - Main Properties

We now state results showing that, under mild conditions and for popular
choices of $d$, the metric-based ranking depth introduced in Definition 1
satisfies the key properties listed in subsection 3.1. Technical proofs are
postponed to the Supplementary Material.

######  Proposition 1.

(Invariance) Suppose that $d$ is right-invariant, i.e.
$d(\nu\pi,\sigma\pi)=d(\nu,\sigma)$ for all
$(\nu,\pi,\sigma)\in\mathfrak{S}_{n}^{3}$, the ranking depth $D_{P}^{(d)}$
satisfies the Property 1.

We point out that Spearman $\rho$, Spearman footrule, Kendall $\tau$, Hamming,
Ulam and Cayley distances are all right-invariant. Hence, the invariance
property is satisfied for any ranking distribution in many situations.
Checking the other properties is more challenging. We recall the following
notion.

######  Definition 5.

(Stochastic transitivity) A probability distribution $P$ on $\mathfrak{S}_{n}$
is said to be stochastically transitive (ST) iff, for all
$(i,j,k)\in[\\![n]\\!]^{3}$, we have: $p_{i,j}\geq 1/2\text{ and }p_{j,k}\geq
1/2\;\Rightarrow\;p_{i,k}\geq 1/2.$ If, in addition, $p_{i,j}\neq 1/2$ for all
$i<j$, one says that $P$ is strictly stochastically transitive (SST).

The stochastic transitivity property [26, 16] is fulfilled by some widely used
ranking distributions (e.g. Mallows) and shown to facilitate various
statistical tasks, see e.g. [57, 58]. In particular, if $P$ is SST, Kemeny’s
median (i.e. the median $\sigma^{*}$ w.r.t. Kendall $\tau$ distance) is
unique, see e.g. [11].

######  Proposition 2.

(Maximality at the center): The Spearman’s footrule ranking depth satisfies
Property 2 for any distribution $P$ with a symmetry center. If $P$ is SST in
addition, then Kendall $\tau$ ranking depth satisfies Property 2 as well.

######  Proposition 3.

(Local monotonicity) If the distribution $P$ is SST, then the Kendall $\tau$
ranking depth satisfies Property 3.

######  Proposition 4.

(Global monotonicity) If the distribution P is SST and
$||d_{\tau}||_{\infty}=\binom{n}{2}<h/s$ with $h=\min_{i,j}|p_{i,j}-1/2|$ and
$s=\max_{(i,j)\neq(k,l)}|p_{i,j}-p_{k,l}|$, then the Kendall $\tau$ ranking
depth satisfies Property 4.

In the Kendall $\tau$ case, additional useful results can be stated. In
particular, the ranking depth is then entirely determined by the pairwise
probabilities $p_{i,j}=\mathbb{P}\\{\Sigma(i)<\Sigma(j)\\}$, $1\leq i\neq
j\leq n$.

######  Proposition 5.

We have: $\forall\;\sigma\in\mathfrak{S}_{n}$,
$D_{P}(\sigma)=\binom{n}{2}-\sum_{i<j}p_{i,j}\mathbb{I}\\{\sigma(i)>\sigma(j)\\}-\sum_{i<j}(1-p_{i,j})\mathbb{I}\\{\sigma(i)<\sigma(j)\\}$.

This case is computationally attractive, the complexity being of order
$O(n^{2})$. In addition, note that the computation of $D_{P}$ involves
pairwise comparisons solely, which means an alternative statistical framework
can be considered, where observation take the form of binary variables
$\\{\Sigma(\mathbf{i})<\Sigma(\mathbf{j})\\}$, $(\mathbf{i},\;\mathbf{j})$
being a random pair in $\\{(i,j):\;1\leq i<j\leq n\\}$, independent from
$\Sigma$.

######  Proposition 6.

Suppose that the ranking distribution $P$ is stochastichally transitive. The
following assertions hold true.

  * (i)

The largest ranking depth value is
$D_{P}^{*}=\sum_{i<j}\left\\{\frac{1}{2}+\left|p_{i,j}-\frac{1}{2}\right|\right\\}$.
The deepest rankings relative to $P$ and $d_{\tau}$ are the permutations
$\sigma\in\mathfrak{S}_{n}$ such that: $\forall i<j$ s.t. $p_{i,j}\neq 1/2$,
$(\sigma(j)-\sigma(i))\cdot(p_{i,j}-1/2)>0$.

  * (ii)

The smallest ranking depth value is
$\underline{D}_{P}=\sum_{i<j}\left\\{\frac{1}{2}-\left|p_{i,j}-\frac{1}{2}\right|\right\\}$.
The least deep rankings relative to $P$ and $d_{\tau}$ are the permutations
$\sigma\in\mathfrak{S}_{n}$ such that: $\forall i<j$ s.t. $p_{i,j}\neq 1/2$,
$(\sigma(j)-\sigma(i))\cdot(p_{i,j}-1/2)<0$.

  * (iii)

If, in addition, $P$ is SST, then we have
$\partial\mathcal{R}_{P}(D_{P}^{*})=\\{\sigma^{*}\\}$ and
$\partial\mathcal{R}_{P}(\underline{D}_{P})=\\{\underline{\sigma}\\}$, where
$\sigma^{*}(i)=1+\sum_{j\neq
i}\mathbb{I}\\{p_{i,j}<1/2\\}=n-\underline{\sigma}(i)$ for
$i\in\\{1,\;\ldots,\;n\\}$. We also have
$D_{P}^{*}-D_{P}(\sigma)=2\sum_{i<j}|p_{i,j}-1/2|+D_{P}(\sigma)-\underline{D}_{P}=2\sum_{i<j}|p_{i,j}-1/2|\cdot\mathbb{I}\\{(\sigma(j)-\sigma(i))(p_{i,j}-1/2)<0\\}$.

##  4 Statistical Issues

The ranking depth $D_{P}$ is generally unknown, just like the ranking
distribution $P$, and must be replaced by an empirical estimate based on
supposedly available ranking data in practice. Here we establish nonasymptotic
statistical guarantees for the empirical counterpart of the ranking depth and
other related quantities. We also propose an algorithm, based on the ranking
depth, that permits to build, from any ranking dataset, an empirical ranking
distribution fulfilling the crucial (strict) stochastic transitivity property,
see subsection 3.3.

###  4.1 Generalization - Learning Rate Bounds

Based on the observation of an i.i.d. sample
$\Sigma_{1},\;\ldots,\;\Sigma_{N}$ drawn from $P$ with $N\geq 1$, statistical
versions of the quantities introduced in subsection 3.2 can be built by
replacing $P$ with the empirical distribution $\widehat{P}_{N}$. The empirical
ranking depth is thus given by: $\forall\sigma\in\mathfrak{S}_{n}$,
$\widehat{D}_{N}(\sigma)=D_{\widehat{P}_{N}}(\sigma)=||d||_{\infty}-\widehat{L}_{N}(\sigma)$.
Similarly, the empirical ranking depth regions are
$\widehat{\mathcal{R}}_{N}(u)=\\{\sigma\in\mathfrak{S}_{n}:\widehat{D}_{N}(\sigma)\geq
u\\}$ for $u\geq 0$. In order to build an estimator of the ranking depth
survivor function $S_{P}(u)$ with a tractable dependence structure, a 2-split
trick can be used, yielding the statistic

$\widehat{S}_{N}(u)=\frac{1}{N-\lfloor N/2\rfloor}\sum_{i=1+\lfloor
N/2\rfloor}^{N}\mathbb{I}\\{\widehat{D}_{\lfloor N/2\rfloor}(\Sigma_{i})\geq
u\\}.$

As the r.v. $D_{P}(\Sigma)$ is discrete, the use of smoothing/interpolation
procedures is required to ensure good statistical properties for the survivor
function estimator and for the empirical quantiles it defines, see [59, 48].
For instance, a kernel smoothed version of $S_{P}$ can be computed by means of
a non-negative differentiable Parzen-Rosenblatt kernel
$K:\mathbb{R}\to\mathbb{R}_{+}$ s.t.
$||K^{\prime}||_{\infty}=\sup_{u\in\mathbb{R}}|K^{\prime}(u)|<\infty$ and
$\int_{\mathbb{R}}K(u)du=+1$ and a smoothing bandwidth $h>0$, namely:
$\widetilde{S}_{P}(u)=K_{h}*S_{P}$, which can be estimated by
$\widetilde{S}_{N}(u)=K_{h}*\widehat{S}_{N}$, where $K_{h}(u)=K(u/h)/h$ for
$u\in\mathbb{R}$. One may then define a smooth estimate of the ranking depth
region with probability content $\alpha\in[0,1]$ as well:
$\widehat{R}_{N}(\alpha)=\widehat{\mathcal{R}}_{N}(\widetilde{S}_{N}^{-1}(\alpha))$.
The result below provides bounds of order $O_{\mathbb{P}}(1/\sqrt{N})$ for the
maximal deviations between $D_{P}$ (resp. $\widetilde{S}_{P}$) and its
empirical version.

######  Proposition 7.

The following assertions hold true.

  * (i)

For any $\delta\in(0,1)$, we have with probability at least $1-\delta$:
$\forall N\geq 1$,

$\sup_{\sigma\in\mathfrak{S}_{n}}|\widehat{D}_{N}(\sigma)-D_{P}(\sigma)|\leq||d||_{\infty}\sqrt{\frac{\log(2\;n!/\delta)}{2N}}.$

  * (ii)

For any $\delta\in(0,1)$ and $h>0$, we have with probability at least
$1-\delta$: $\forall N\geq 1$,

$\sup_{u\geq
0}|\widetilde{S}_{N}(u)-\widetilde{S}_{P}(u)|\leq\sqrt{\frac{\log(4/\delta)}{2N}}+||d||_{\infty}\sqrt{\frac{\log(4n!/\delta)}{2N}}.$

For the technical proof, refer to the Supplementary Material, where the
asymptotic rate for the empirical ranking quantile function is also given.

###  4.2 Depth Trimming for Consensus Ranking

As discussed in subsection 3.3, (strict) stochastic transitivity greatly
facilitates the computation of Kemeny medians (see Proposition 6) as well as
the verification of the maximality or monotonicity properties, cf Propositions
2, 3 and 4. However, although this occurs with a controlled probability (see
Proposition 14 in [11]), the empirical counterpart $\widehat{P}_{N}$ of a
(strictly) stochastically transitive ranking distribution $P$ can be of course
non (S)ST. We propose below a trimming strategy based on the empirical ranking
depth to recover a close (S)ST empirical ranking distribution and overcome
this issue.

Input : Ranking dataset $\mathcal{D}_{N}=\\{\Sigma_{1},...\Sigma_{N}\\}$ and
distribution $\widehat{P}_{N}=(1/N)\sum_{i=1}^{N}\delta_{\Sigma_{i}}$.

Output : Dataset $\mathcal{D}\subset\mathcal{D}_{N}$ of size
$N_{\mathcal{D}}\leq N$ and (S)ST ranking distribution
$\widehat{P}_{\mathcal{D}}=(1/N_{\mathcal{D}})\sum_{\sigma\in\mathcal{D}}\delta_{\sigma}$

\- Initialize: $\mathcal{D}=\mathcal{D}_{N}$;

while  _$\hat{P}_{\mathcal{D}}$ is not (S)ST_ do

\- Determine the least deep rankings in $\mathcal{D}$:
$\mathcal{O}_{\mathcal{D}}:=\arg\min_{\sigma\in\mathcal{D}}D_{\hat{P}_{N}}(\sigma)$;

\- Update the ranking dataset
$\mathcal{D}\setminus\mathcal{O}_{\mathcal{D}}\to\mathcal{D}$

Algorithm 1 Ranking Depth Trimming

Based on the ranking dataset $\mathcal{D}$ output by Algorithm 1, a (S)ST
empirical distribution $\widehat{P}_{\mathcal{D}}$ can be computed, whose
Kemeny medians are obtained in a straightforward manner, cf Proposition 6,
avoiding the search of solutions of a NP-hard minimization problem of type
(1), see [30]. As empirically supported by the experiments displayed in the
next section, this procedure allows for a fast, accurate and robust recovery
of consensus rankings.

##  5 Applications - Experiments

In order to illustrate the relevance of ranking depth notion, we now show that
it can be used to perform a wide variety of tasks in the statistical analysis
of ranking data, including those listed below:

  * •

Fast and robust consensus ranking

  * •

Ranking data visualization

  * •

Detection of outlying rankings

  * •

The two-sample (homogeneity) problem in $\mathfrak{S}_{n}$.

Further experimental results on real ranking data are provided and discussed
in the Supplementary Material.

###  5.1 Fast/Robust Consensus Ranking

The trimming strategy proposed in sec 4.2 shows that we can recover smooth SST
distributions from any empirical data, and perform ranking aggregation by
simply identifying the deepest ranking: this procedure is fast,
straightforward, and robust, in the sense that we can recover accurate medians
even in contaminated settings. We support this claim by both experiments and a
theoretical proposition below.

(a) | (b)
---|---
|
(c) | (d)
|
Figure 1: Depth plots before (a) and after (b) trimming with adversarial (red)
and clean (blue) points; evolution of candidate median (deepest ranking)
distance to real median and number of cycles through trimming (c); evolution
of median depth and sample dispersion through trimming (d).

We consider a dataset drawn from a ”clean” distribution $P$ (10000 points
drawn from a Mallows distribution with $n=12$ items, center $\sigma_{0}$ and
$\phi=0.90$) that has been contaminated by rankings from another distribution
(2000 points drawn from a Mallows distribution with opposite center and
$\phi=0.40$). We use the trimming strategy described in algorithm 1 to remove
rankings until the empirical distribution becomes SST and thus considered
clean once again. We show in Figure 1 the depth of clean (blue) and
adversarial (red) rankings before trimming (a) and after trimming (b), the
performance of the median computed at each step of the trimming procedure
evaluated as its Kendall $\tau$ distance to the real center of the clean
Mallows distribution (c), and the depth of the median during the trimming
procedure (d). The depth function is able to identify mainly adversarial
rankings and remove them during the trimming procedure, which conducts to a
cleaner dataset after the procedure and a far more accurate median
$\sigma^{*}$.

##### Mechanical Turk Dots dataset.

We show the robustness of depth-based medians on a real dataset where
participants ranked point clouds according to their size [50]. A ground truth
ranking exists, and we contaminated 1/4 of the dataset by swapping random
rankings before trimming: figure 2 (b) shows that we indeed recovered the
ground truth ranking after the trimming strategy even if contaminated rankings
were not obviously different from clean one (fig. 2 (a)).

(a) | (b)
---|---
|
Figure 2: Depth plots before trimming with swapped (red) and clean (blue)
points; evolution of candidate median (deepest ranking) distance to real
median and number of cycles through trimming (b)

##### Theoretical robustness result.

We derive specific robustness results when using depth-based trimming by
emulating the classical notion of breakdown point (see [21]). Let us consider
the classical Borda estimator (which orders the items based on the score
$B(i)=\sum_{\sigma\in S_{N}}\sigma(i)$, see [22, 27, 8, 12]) and a depth-
trimmed Borda estimator based on the scores $B_{\mu}(i)=\sum_{\sigma\in
S_{N}}w(\sigma)\sigma(i)$, where $w(\sigma)=\mathbb{I}(D_{N}(\sigma)>\mu)$
(only the rankings with depth higher than $\mu$ are kept). Let
$\sigma_{S}^{\text{B}}$ (resp. $\sigma_{S}^{\text{DT-B}}$) be the Borda (resp.
depth-trimmed Borda) estimator of a sample $S$. The Borda estimator is said to
be $\delta$-broken for sample size $N$ and for a distribution $P$ if for any
sample $S_{N}\sim P$ of size $N$, there exists an adversarial sample $A$ such
that $d_{\tau}(\sigma_{S_{N}}^{\text{B}},\sigma_{S_{N}\cup
A}^{\text{B}})\geq\delta$. The smallest cardinality of the adversarial sample
$A$ such that the estimator is $\delta$-broken for size $N\to\infty$ is called
here the $\delta$-breakdown points of the estimator on distribution $P$, and
we write $\epsilon^{\text{B}}_{\delta}(P)$ (resp.
$\epsilon^{\text{DT-B}}_{\delta}(P)$) such statistic for the Borda (resp.
depth-trimmed Borda) estimator. Breakdown points measure the robustness of an
estimator on a given distribution: we state that the classical Borda estimator
is less robust than the depth-trimmed one on generic distributions.

######  Proposition 8.

Let $\mu$ be the trimming threshold and $P$ a distribution such that
$\mathbb{E}_{P}[D_{P}(\Sigma)]>\mu$. Let
$\sigma^{*}=\arg\max_{\sigma\in\mathfrak{S}_{n}}D_{P}(\sigma)$ be the deepest
ranking and
$\pi=\arg\max_{\sigma|d_{\tau}(\sigma^{*},\sigma)=\delta}D(\sigma)$ the
ranking with highest depth among those at distance $\delta$ from the deepest
ranking $\sigma^{*}$. Then, the breakdown points for Borda and depth-trimmed-
Borda on $P$ are related as follows,

$\begin{split}\frac{\epsilon^{\text{B}}_{\delta}(P)}{\epsilon^{\text{DT-B}}_{\delta}(P)}<\frac{D_{P}(\pi)}{\mu}<1.\end{split}$
(2)

The proof, as well as more results on the robustness of Borda estimators, are
provided in section B.4 of the supplementary.

###  5.2 Graphical Methods and Visual Inference

The analysis of rankings suffers from the lack of graphical displays and
diagrams, such as probability plots or histograms, for gaining insight into
the structure of the data. Ranking depths can be readily used to design a
visual diagnostic tool for ranking data, extending the Depth _vs._ Depth plot
($DD$-plot in abbreviated form) originally introduced [43] for multivariate
data. For two samples of rankings
$\boldsymbol{\Sigma^{1}}=\\{\sigma^{1}_{1},\;\ldots,\;\sigma^{1}_{N_{1}}\\}$
and
$\boldsymbol{\Sigma^{2}}=\\{\sigma^{2}_{1},\;\ldots,\;\sigma^{2}_{N_{2}}\\}$,
with corresponding empirical measures $\widehat{P^{1}}_{N_{1}}$ and
$\widehat{P^{2}}_{N_{2}}$, the ranking $DD$-plot is obtained by plotting in
the Euclidean plane the points:

$\bigl{\\{}\bigl{(}D_{\widehat{P^{1}}_{N_{1}}}(\sigma),D_{\widehat{P^{2}}_{N_{2}}}(\sigma\bigr{)}\,:\,\sigma\in\boldsymbol{\Sigma^{1}}\cup\boldsymbol{\Sigma^{2}}\bigr{\\}}.$
(3)

Position | $d_{\tau}(\sigma_{1}^{*},\sigma_{2}^{*})$ | $\phi_{1}$ | $\phi_{2}$ | $N_{1}$ | $N_{2}$
---|---|---|---|---|---
(a) | $15$ | $\mathrm{e}^{-1}$ | $\mathrm{e}^{-1}$ | $250$ | $250$
(b) | $0$ | $\mathrm{e}^{-0.5}$ | $\mathrm{e}^{-2}$ | $250$ | $250$
(c) | $15$ | $\mathrm{e}^{-0.5}$ | $\mathrm{e}^{-2}$ | $250$ | $250$
(d) | $15$ | $\mathrm{e}^{-0.5}$ | $\mathrm{e}^{-2}$ | $400$ | $100$
Table 1: Parameters for pairs of samples drawn from Mallows-Kendall
distribution used for Figure 3.

Depending on the distance $d$ chosen, such a plot allows to reflect location
and scatter of two distributions on $\mathfrak{S}_{n}$, and their mutual
position. To illustrate its diagnostic capacity, we plot in Figure 3 the
ranking $DD$-plots relative to the Kendall $\tau$ distance and four pairs of
samples stemming from Mallows distribution with parameters defined in Table 1.
(In this and subsequent figures the depth is re-scaled to $[0,1]$ by diving by
$\|d\|_{\infty}$.) A few remarks can be made: For distributions differing in:
1) location only (a), the ranking $DD$-plot is symmetric w.r.t. the diagonal,
2) scatter only (b), observations from one distribution will be attributed
systematically higher depth values, 3) both location and scatter (c), they can
be distinguished and 4) number of the observations, it does not influence the
general picture (d).

(a) | (b)
---|---
|
(c) | (d)
|
Figure 3: Ranking $DD$-plot corresponding to Mallows distributions with
parameters described in Table 1.

###  5.3 Outlier Detection in Ranking Data

(a) | (b)
---|---
|
(c) | (d)
|
Figure 4: Depth plots (a,c) and $DD$-plots (b,d) for a mixture of Mallows-
Kendall distributions. (a)-(b): distant centers and different size for the two
components of the mixture. (c)-(d): closer centers and same size.

We now place ourselves in the situation where a single sample of rankings is
observed. For simplicity, we consider the case where the underlying ranking
distribution is an unbalanced mixture of two Mallows distributions (for
$n=10$), strongly differing in size ($N_{1}=35$ and $N_{2}=215$), with distant
centers ($d_{\tau}(\sigma^{*}_{1},\sigma^{*}_{2})=15$) and parameters
$\phi_{1}=\mathrm{e}^{-0.5}$ and $\phi_{2}=\mathrm{e}^{-2.5}$. Figure 4 (a)
shows the ranking depth (relative to Kendall $\tau$) of each observation
computed w.r.t. to the entire sample. We observe, that despite the
unavailability of labels, the ranking depth clearly distinguishes the two
different components. It thus permits to perform a typical anomaly detection
task in the context of ranking data, where the differing minority of
permutations are viewed as abnormal rankings. The diagnostic ranking $DD$-plot
(b) based on the identified information about the components confirms the
differences.

Consider next the case of a mixture with closer centers
($d_{\tau}(\sigma_{1}^{*},\sigma_{2}^{*})=11$) and equal sizes
($N_{1}=N_{2}=125$), with parameters $\phi_{1}=\mathrm{e}^{-0.25}$ and
$\phi_{2}=\mathrm{e}^{-2.5}$. The depth plot (c) w.r.t. to the entire sample
reflects how easily we can cluster the ranking dataset into two components (we
deliberately shuffle the indices and keep colors for illustrative purposes),
and we suggests a separating threshold (on the level of depth $=0.71$), which
in this particular case allows for two mistaking assignments. For the
diagnostic ranking $DD$-plot (d), we honestly include this mistake, and change
the colors to underline this impurity.

###  5.4 Rankings - Homogeneity Testing

Depth can further be used to provide a formal inference, which we exemplify as
a nonparametric test of homogeneity between two Plackett-Luce distributions
[14] with $n=10$. The first one (red in Figure 5) is generated using the
parameters $\boldsymbol{w}_{1}=(\mathrm{e}^{9},...,\mathrm{e}^{0})$, the
second one represents its changed version
$\boldsymbol{w}_{2}=(\mathrm{e}^{\gamma 9},...,\mathrm{e}^{\gamma 0})$. We
gradually increase $\gamma$ from $0.5$ (substantial difference) to $1$ (equal
in distribution), and provide the $p$-values of the Wilcoxon rank-sum test
averaged over $100$ repetitions in Figure 5. The test is performed using the
reference sample (of size $500$) from the first distribution, with tested
sample sizes being equal ($=50$) for both distributions (see [37] for details
on the testing procedure and [44] for more details). Figure 5 shows how the
$p$-values detect very well the difference between the two distributions when
it is the case, giving a formal inference to the ranking $DD$-plot
visualization, whereas, remarkably, the (parametric) nature of the underlying
ranking models is not used at all by the procedure. We also underline that, in
a similar fashion, ranking depth-based goodness-of-fit statistics could be
computed, in order to evaluate how well a specific ranking model fits a
ranking dataset.

$\gamma=0.5$ | $\gamma=0.75$
---|---
|
$\gamma=1$ |  $p$-values
|
Figure 5: $DD$-plots of a pair of P-L distributions with gradually decreasing
difference between them based on parameter $\gamma$ and the corresponding
average $p$-values for the test of homogeneity.

##### Student dataset.

We now explore our homogeneity testing machinery on a real dataset (available
at https://github.com/ekhiru/students-dataset) composed of rankings from
students (with a ground truth answer) before (red) and after (blue) taking the
related course. The diagnostic $DD$-plot of the two cohorts together with
$p$-values over $1000$ random repetitions and the asymptotic density under
$H_{0}$ are indicated in Figure 6: they illustrate the improvement of the
students’ knowledge after the class.

|
---|---
Figure 6: Left: $DD$-plot for ’before class’ (red) and ’after class’ (blue)
students. Right: $p$-values of the homogeneity test.

## Conclusion

In this paper, we have extended the concept of statistical depth to ranking
data, in order to apply the notions of quantiles, order statistics and ranks
to the latter, overcoming hence the lack of natural order and vector space
structure on $\mathfrak{S}_{n}$. We have listed the desirable properties a
ranking depth should satisfy to emulate these notions appropriately and shown
that the same metric approach as that, widely used, to deal with ranking
aggregation, permits to build depth functions on $\mathfrak{S}_{n}$ that
fulfill them in many situations. Theoretical results proving that ranking
depths and related quantities can be accurately estimated by their empirical
versions with guarantees have been established. We have also shown that the
methodology promoted can be successfully applied to a wide variety of
problems, ranging from fast and robust consensus ranking to the design of
ranking data visualization techniques through the detection of outlying
rankings. Both the theoretical and empirical results are very encouraging and
paves the way to a more systematic use of the ranking depth concept for the
statistical analysis of ranking data.

## References

  * [1] M. Alvo and P. L. H. Yu.  Statistical Methods for Ranking Data.  Springer-Verlag, New York, 2014.
  * [2] J. J. Bartholdi III, C. A. Tovey, and M. A. Trick.  The computational difficulty of manipulating an election.  Social Choice and Welfare, 6(3):227–241, 1989.
  * [3] R. A. Bradley and M. E. Terry.  Rank analysis of incomplete block designs: I. The method of paired comparisons.  Biometrika, 39(3/4):324–345, 1952.
  * [4] V. E. Brunel.  Concentration of the empirical level sets of tukey’s halfspace depth.  Probability Theory and Relative Fields, 173:1165–1196, 2019.
  * [5] M. A. Burr and R. J. Fabrizio.  Uniform convergence rates for halfspace depth.  Statistics and Probability Letters, 124:33–40, 2017.
  * [6] R. Busa-Fekete, E. Hüllermeier, and B. Szörényi.  Preference-based rank elicitation using statistical models: the case of Mallows.  In Proceedings of International Conference on Machine Learning (ICML) 2014, pages 1071–1079, 2014.
  * [7] Róbert Busa-Fekete, Dimitris Fotakis, Balázs Szörényi, and Manolis Zampetakis.  Optimal Learning of Mallows Block Model.  In Conference on Learning Theory (COLT), 2019.
  * [8] I. Caragiannis, A. D. Procaccia, and N. Shah.  When do noisy votes reveal the truth?  In Proceedings of the Fourteenth ACM Conference on Electronic Commerce, pages 143–160, New York, 2013. ACM.
  * [9] P. Chaudhuri.  On a geometric notion of quantiles for multivariate data.  Journal of the American Statistical Association, 91(434):862–872, 1996.
  * [10] V. Chernozhukov, A. Galichon, M. Hallin, and M. Henry.  Monge–kantorovich depth, quantiles, ranks and signs.  The Annals of Statistics, 45(1):223–256, 2017.
  * [11] S. Clémençon, A. Korba, and E. Sibony.  A learning theory of ranking aggregation.  In Proceeding of AISTATS 2017, 2017.
  * [12] F. Collas and E. Irurozki.  Concentric mixtures of Mallows models for top-$k$ rankings: sampling and identifiability.  In International Conference on Machine Learning (ICML), 2021.
  * [13] N. Condorcet.  Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix.  L’Imprimerie Royale, Paris, 1785.
  * [14] D. E. Critchlow, M. A. Fligner, and J. S. Verducci.  Probability models on rankings.  Journal of Mathematical Psychology, 35(3):294–318, 1991.
  * [15] A. Davenport and D. Lovell.  Ranking pilots in aerobatic flight competitions.  Technical report, IBM Research Report RC23631 (W0506-079), TJ Watson Research Center, NY, 2005.
  * [16] D. Davidson and J. Marschak.  Experimental tests of a stochastic decision theory.  In C. W. Churchman and P. Ratoosh, editors, Measurement: Definitions and Theories, pages 233–269. John Wiley, 1959.
  * [17] J.-C. de Borda.  Mémoire sur les élections au scrutin, 1781.
  * [18] M. S. Desarkar, S. Sarkar, and P. Mitra.  Preference relations based unsupervised rank aggregation for metasearch.  Expert Systems with Applications, 49:86–98, 2016.
  * [19] M. Deza and T. Huang.  Metrics on permutations, a survey.  Journal of Combinatorics, Information and System Sciences, 1998\.
  * [20] P. Diaconis and R. L. Graham.  Spearman’s footrule as a measure of disarray.  Journal of the Royal Statistical Society. Series B (Methodological), 39(2):262–268, 1977.
  * [21] D. L. Donoho and M. Gasko.  Breakdown properties of location estimates based on halfspace depth and projected outlyingness.  The Annals of Statistics, 20:1803–1827, 1992.
  * [22] C. Dwork, R. Kumar, M. Naor, and D. Sivakumar.  Rank aggregation methods for the Web.  In International Conference on World Wide Web, pages 613–622, New York, 2001. ACM.
  * [23] R. Dyckerhoff.  Data depths satisfying the projection property.  Allgemeines Statistisches Archiv, 88(2):163–190, 2004.
  * [24] R. Dyckerhoff, C. Ley, and D. Paindaveine.  Depth-based runs tests for bivariate central symmetry.  Annals of the Institute of Statistical Mathematics, 67(5):917–941, 2015.
  * [25] R. Dyckerhoff and P. Mozharovskyi.  Exact computation of the halfspace depth.  Computational Statistics and Data Analysis, 98:19–30, 2016.
  * [26] P. C. Fishburn.  Binary choice probabilities: on the varieties of stochastic transitivity.  Journal of Mathematical psychology, 10(4):327–352, 1973.
  * [27] M. A. Fligner and J. S. Verducci.  Multistage ranking models.  Journal of the American Statistical Association, 83(403):892–901, 1988.
  * [28] Michael A Fligner and Joseph S Verducci.  Distance based ranking models.  Journal of the Royal Statistical Society, 48(3):359–369, 1986.
  * [29] T-K. Huang, R. C. Weng, and C-J. Lin.  Generalized bradley-terry models and multi-class probability estimates.  The Journal of Machine Learning Research, 7:85–115, 2006.
  * [30] O. Hudry.  NP-hardness results for the aggregation of linear orders into median orders.  Annals of Operations Research, 163:63–88, 2008.
  * [31] E. Irurozki, B. Calvo, and J. A. Lozano.  PerMallows: An R package for mallows and generalized mallows models.  Journal of Statistical Software, 71, 2019.
  * [32] E. Irurozki, B. Calvo, and J.A. Lozano.  Mallows and generalized Mallows model for matchings.  Bernoulli, 25(2), 2019.
  * [33] Y. Jiao, A. Korba, and E. Sibony.  Controlling the distance to a kemeny consensus without computing it.  In Proceeding of International Conference on Machine Learning (ICML) 2016, 2016.
  * [34] R. Jörnsten.  Clustering and classification based on the l1 data depth.  Journal of Multivariate Analysis, 90(1):67–89, 2004.
  * [35] T. Kamishima.  Nantonac collaborative filtering: Recommendation based on order responses.  In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 583–588, New York, 2013. Association for Computing Machinery.
  * [36] G. Koshevoy and K. Mosler.  Zonoid trimming for multivariate distributions.  The Annals of Statistics, 25(5):1998–2017, 1997.
  * [37] P. Lafaye De Micheaux, P. Mozharovskyi, and M. Vimond.  Depth for curve data and applications.  Journal of the American Statistical Association, 2020.  in press.
  * [38] T. Lange, K. Mosler, and P. Mozharovskyi.  Fast nonparametric classification based on data depth.  Statistical Papers, 55(1):49–69, 2014.
  * [39] G. Lebanon and J. Lafferty.  Cranking: Combining rankings using conditional probability models on permutations.  In Proceedings of the 19th International Conference on Machine Learning, pages 363–370, 2002.
  * [40] Liu.  On a notion of data depth based upon random simplices.  The Annals of Statistics, 18(1):405–414, 1990.
  * [41] Allen Liu and Ankur Moitra.  Efficiently learning mixtures of mallows models.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 627–638. IEEE, 2018.
  * [42] Ao Liu, Zhibing Zhao, Chao Liao, Pinyan Lu, and Lirong Xia.  Learning Plackett-Luce Mixtures from Partial Preferences.  Proceedings of the AAAI Conference on Artificial Intelligence, 2019\.
  * [43] R. Y. Liu, J. M. Parelius, and K. Singh.  Multivariate analysis by data depth: descriptive statistics, graphics and inference.  The Annals of Statistics, 27(3):783–858, 1999.  With discussion and a rejoinder by Liu and Singh.
  * [44] R. Y. Liu and K. Singh.  A quality index based on data depth and multivariate rank tests.  Journal of the American Statistical Association, 88(421):252–260, 1993.
  * [45] X. Liu, K. Mosler, and P. Mozharovskyi.  Fast computation of tukey trimmed regions and median in dimension $p>2$.  Journal of Computational and Graphical Statistics, 28(3):682–697, 2019.
  * [46] Tyler Lu and Craig Boutilier.  Effective Sampling and Learning for Mallows Models with Pairwise-Preference Data.  Journal of Machine Learning Research, 2014.
  * [47] R. D. Luce.  Individual Choice Behavior: A Theoretical Analysis.  John Wiley and Sons, New York, 1959.
  * [48] Y. Ma, M. G. Genton, and E. Parzen.  Asymptotic properties of sample quantiles of discrete distributions.  Annals of the Institute of Statistical Mathematics, 63(2):227–243, 2011.
  * [49] C. L. Mallows.  Non-null ranking models.  Biometrika, 44(1-2):114–130, 1957.
  * [50] A. Mao, A. Procaccia, and Y. Chen.  Better human computation through principled voting.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 27, 2013.
  * [51] K. Mosler.  Depth statistics.  In C. Becker, R. Fried, and S. Kuhnt, editors, Robustness and Complex Data Structures: Festschrift in Honour of Ursula Gather, pages 17–34. Springer, 2013.
  * [52] H. Oja.  Descriptive statistics for multivariate distributions.  Statistics and Probability Letters, 1(6):327–332, 1983.
  * [53] T. Patel, D. Telesca, R. Rallo, S. George, T. Xia, and A. E. Nel.  Hierarchical rank aggregation with applications to nnanotoxicology.  Journal of Agricultural, Biological, and Environmental Statistics, 18(2):159–177, 2013.
  * [54] R. L. Plackett.  The analysis of permutations.  Applied Statistics, 2(24):193–202, 1975.
  * [55] O. Pokotylo, P. Mozharovskyi, and R. Dyckerhoff.  Depth and depth-based classification with R-package ddalpha.  Journal of Statistical Software, Articles, 91(5):1–46, 2019.
  * [56] R. Serfling.  Depth functions in nonparametric multivariate inference.  DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 72, 2006.
  * [57] N. B. Shah, S. Balakrishnan, A. Guntuboyina, and M. J. Wainright.  Stochastically transitive models for pairwise comparisons: statistical and computational issues, 2015.  arXiv preprint arXiv:1510.05610.
  * [58] N. B. Shah and M. J. Wainwright.  Simple, robust and optimal ranking from pairwise comparisons, 2015.
  * [59] S. J. Sheather and J. S. Marron.  Kernel quantile estimators.  Journal of the American Statistical Association, 85(410):410–416, 1990.
  * [60] J. W. Tukey.  Mathematics and the picturing of data.  In R. D. James, editor, Proceedings of the International Congress of Mathematicians, volume 2, pages 523–531. Canadian Mathematical Congress, 1975.
  * [61] Y. Vardi and C.-H. Zhang.  The multivariate l1-median and associated data depth.  Proceedings of the National Academy of Sciences, 97(4):1423–1426, 2000.
  * [62] Valeria Vitelli, Øystein Sørensen, Marta Crispino, Arnoldo Frigessi, and Elja Arjas.  Probabilistic preference learning with the Mallows rank model.  Journal of Machine Learning Research, 18(1), 2018.
  * [63] Zhibing Zhao and Lirong Xia.  Learning Mixtures of Plackett-Luce Models from Structured Partial Orders.  In Advances in Neural Information Processing Systems, pages 10143–10153, 2019.
  * [64] Y. Zuo and R. Serfling.  General notions of statistical depth function.  The Annals of Statistics, 28(2):461–482, 2000.
  * [65] Y. Zuo and R. Serfling.  Structural properties and convergence results for contours of sample statistical depth functions.  The Annals of Statistics, 28(2):483–499, 2000.

Supplementary Material

###### Contents

  1. 1 Introduction
  2. 2 Background and Preliminaries
    1. 2.1 Depth Functions for Multivariate Data
    2. 2.2 Consensus Ranking
  3. 3 Depth Functions for Ranking Data
    1. 3.1 Ranking Depths - Axioms
    2. 3.2 Metric-based Ranking Depth Functions
    3. 3.3 The Metric Approach - Main Properties
  4. 4 Statistical Issues
    1. 4.1 Generalization - Learning Rate Bounds
    2. 4.2 Depth Trimming for Consensus Ranking
  5. 5 Applications - Experiments
    1. 5.1 Fast/Robust Consensus Ranking
    2. 5.2 Graphical Methods and Visual Inference
    3. 5.3 Outlier Detection in Ranking Data
    4. 5.4 Rankings - Homogeneity Testing
  6. A Ranking Distributions - Popular Examples
  7. B Technical Proofs
    1. B.1 Conditions for satisfying the desirable properties
      1. B.1.1 Proof of Proposition 1 (invariance)
      2. B.1.2 Proof of Proposition 2 (maximality at the center)
      3. B.1.3 Proofs of Propositions 3 and 4 (monotonicity)
    2. B.2 Proof Proposition 7 (learning rate bounds)
    3. B.3 Proofs of Propositions 5, 6 and 15 (results for Kendall $\tau$ \- Mallows model)
    4. B.4 Proof of Proposition 8 (Borda estimators’ robustness)
  8. C Further results
    1. C.1 Ranking quantile function
    2. C.2 Pairwise comparisons as an alternative statistical framework
  9. D Additional experiments
    1. D.1 Trimming strategy
    2. D.2 Visual analysis
    3. D.3 Application to real data
      1. D.3.1 Student dataset
      2. D.3.2 Sushi dataset
      3. D.3.3 Mechanical Turk Dots dataset
      4. D.3.4 Netflix Prize dataset

##  Appendix A Ranking Distributions - Popular Examples

Below we recall some popular ranking models. They will be next used to
illustrate some of the properties involved in the theoretical analysis carried
out.

######  Proposition 9.

The symmetry center property for rankings has two versions, a weak and a
strong one, see [14].

  1. 1.

Strong unimodality: ranking model $P$ is said to be strongly unimodal iff
there exists a modal ranking $\sigma^{*}$ such that for every pair $i,j$ such
that $\sigma^{*}(i)<\sigma(j)$ and any permutations $\sigma$ such that
$\sigma(i)=\sigma(j)-1$ then $P(\sigma)\geq P(\sigma\tau_{ij})$, where
$\sigma\tau_{ij}(i)=\sigma(j)$, $\sigma\tau_{ij}(j)=\sigma(i)$ and
$\sigma\tau_{ij}(k)=\sigma(k)$ for $k\neq i,j$.

  2. 2.

Complete consensus: ranking model $P$ is said to have complete consensus iff
there exists a modal ranking $\sigma^{*}$ such that for every pair $i,j$ such
that $\sigma^{*}(i)<\sigma(j)$ and any permutations $\sigma$ such that
$\sigma(i)<\sigma(j)$ then $P(\sigma)\geq P(\sigma\tau_{ij})$, where
$\sigma\tau_{ij}(i)=\sigma(j)$, $\sigma\tau_{ij}(j)=\sigma(i)$ and
$\sigma\tau_{ij}(k)=\sigma(k)$ for $k\neq i,j$. Complete consensus implies
strong unimodality.

######  Example 1.

(Mallows distribution) Taking $d=d_{\tau}$, the Mallows model introduced in
[49] is the unimodal distribution $P_{\theta}$ on $\mathfrak{S}_{n}$
parametrized by $\theta=(\sigma_{0},\phi_{0})\in\mathfrak{S}_{n}\times(0,1]$:
$\forall\sigma\in\mathfrak{S}_{n}$,

$P_{\theta}(\sigma)=(1/Z_{0})\exp(d_{\tau}(\sigma_{0},\sigma)\log\phi_{0}),$
(4)

where
$Z_{0}=\sum_{\sigma\in\mathfrak{S}_{n}}\exp(d_{\tau}(\sigma_{0},\sigma)\log\phi_{0})$
is a normalization constant. One may easily show that $Z_{0}$ is independent
from $\sigma_{0}$ and that
$Z_{0}=\prod_{i=1}^{n-1}\sum_{j=0}^{i}\phi_{0}^{j}$. When $\phi_{0}<1$, the
permutation $\sigma_{0}$ of reference is the mode of distribution
$P_{\theta_{0}}$, as well as its unique median relative to $d_{\tau}$. Observe
in addition that the smallest the parameter $\phi_{0}$, the spikiest the
distribution $P_{\theta_{0}}$. In contrast, $P_{\theta_{0}}$ is the uniform
distribution on $\mathfrak{S}_{n}$ when $\phi_{0}=1$. As explained in section
3, ranking depth functions relative to the Kendall $\tau$ distance can be
expressed as a function of the pairwise probabilities
$p_{i,j}=\mathbb{P}\\{\Sigma(i)<\Sigma(j)\\}$, $1\leq i\neq j\leq n$. Notice
also that $||d_{\tau}||_{\infty}=\binom{n}{2}$. Consider again the Mallows
model $P_{\theta}$ recalled in Example 1. In this case, a closed-from
expression of the $p_{i,j}$’s is available, see e.g. Theorem 2 in [6]. Setting
$h(k,\phi_{0})=k/(1-\phi_{0}^{k})$ for $k\geq 1$, one can then show that the
ranking depth function relative to $P_{\theta}$ and $d_{\tau}$ is:
$\forall\sigma\in\mathfrak{S}_{n}$, $D_{P_{\theta}}(\sigma)={n\choose
2}-\sum_{\sigma(i)>\sigma(j)}H(\sigma_{0}(j)-\sigma_{0}(i),\;\phi_{0})$, where
$H(k,\phi_{0})=h(k+1,\phi_{0})-h(k,\phi_{0})$ and
$H(-k,\phi_{0})=1-H(k,\phi_{0})$ for $k\geq 1$. Mallows is adapted naturally
to work with extensions of rankings, such as from pairwise preferences [46],
and partial rankings [62]

Mallows satisfies the complete consensus property, see Property 9, when
$\theta<1$.

The most popular extensions in the literature are Generalized Mallows models
[28], [32] and Mallows Block models [7]. They define different dispersion
parameters for different ranking positions to model distributions in which
there is high certainty in the top-ranked items and uncertainty at the bottom.
These models still satisfy the complete consensus property, see Property 9,
when $\theta<1$.

We also point out that model (4) can be extended in a straightforward manner,
by considering alternative distances $d$, including those described in Section
2.2 and other right invariant distances such as Cayley and Ulam, all of which
satisfy the complete consensus property, see Property 9, when $\theta<1$.

The maximality at center is broken in more general ranking distributions with
the form of mixtures of Mallows models. Mixtures have been studied in
practical and theoretical settings, see e.g. [39, 41, 12].

######  Example 2.

(Plackett-Luce (PL) distribution) PL assumes that rankings are generated in a
stage wise manner: the most preferred item is chosen first, then the second
preferred one, …There is independence among stages, that is, the probability
of an item being chosen at a particular stage is only proportional to the
remaining items at this stage and independent of the order of the items that
have already been chosen. Thus, PL is parametrized by
$\boldsymbol{v}\in\mathbb{R}^{n}$, where $v(i)$ is proportional to the
probability of choosing item $i$ as the preferred item at any stage (among the
remaining ones). The probability of each ranking is given as

$P_{v}(\sigma)=\prod_{i=1}^{n}\frac{\sigma^{-1}(i)}{\sum_{j=i}^{n}\sigma^{-1}(j)}.$
(5)

The median ranking is the permutation that orders the weights decreasingly.
The pairwise probabilities of items $i$ and $j$ have a closed-form expression
involving only the weights of bot items,
${p_{i,j}=\frac{v_{i}}{v_{i}+v_{j}}}$. PL’s stage wise ranking process implies
that adaptation to top-$k$ and rankings is natural [42].

The PL models satisfy the complete consensus property, see Property 9 for
every distribution other than the uniform. Clearly, the maximality at center
does not hold for mixtures of PL in general. Note that there is a body of
research on PL mixtures [42, 63].

######  Example 3.

(Mallows-Bradley-Terry distribution) Mallows-Bradley-Terry is a ranking model
induced by paired comparisons in which the pairwise probability of items $i$
and $j$ have the form

$p_{i,j}=\frac{v_{i}}{v_{i}+v_{j}},$

where $v_{i}$ is the parameter associated to item $i$ for
$\boldsymbol{v}\in\mathbb{R}^{n}$. The probability of ranking $\sigma$ is then

$p(\sigma)=Z(\boldsymbol{v})\prod_{i=1}^{n-1}(v_{\sigma^{-1}(i)})^{n-i},$

where $Z$ is a normalization constant. See [29] for generalizations.

######  Example 4.

(Pairwise distributions) All the above models can be written as a $n\times n$
matrix of pairwise probabilities $p_{i,j}$ (describing the probability of item
$i$ being preferred to item $j$) with restricted forms of its entries. Each of
the models imposes different restrictions in the entries of the pairwise
probabilities $p_{i,j}$ but one could consider arbitrary values. We next lines
characterize the properties of models with arbitrary entries $p_{i,j}$.

  * •

$P$ is strongly unimodal if and only if its entries are weakly stochastically
transitive for some reordering of the rows an columns, as defined in
Proposition 5.

  * •

$P$ has complete consensus if and only if its entries are strongly
stochastically transitive for some reordering of the rows an columns. A
probability distribution $P$ on $\mathfrak{S}_{n}$ is said to be strongly
stochastically transitive iff, for all $(i,j,k)\in[\\![n]\\!]^{3}$, we have:
$p_{i,j}\geq 1/2\text{ and }p_{j,k}\geq
1/2\;\Rightarrow\;p_{i,k}\geq\max\\{p_{i,j},p_{j,k}\\}$ and $p_{i,j}\neq 1/2$
for all $i<j$.

##  Appendix B Technical Proofs

###  B.1 Conditions for satisfying the desirable properties

####  B.1.1 Proof of Proposition 1 (invariance)

We elaborate now on the invariance property 1. Recall that a distance is right
invariant iff for every triplet of permutations
$(\sigma,\pi,\nu)\in\mathfrak{S}_{n}d(\sigma,\nu)=d(\sigma\pi,\nu\pi)$.
Finally, the inverse of permutation $\sigma$ is denoted by $\sigma^{-1}$.

Let us first recall the invariance property for distributions and for depths 1
and our proposition 1: See 1 See 1

###### Proof.

$\begin{split}D_{\pi P}(\sigma\pi)=&\mathbb{E}_{\pi
P}[||d||_{\infty}-d(\sigma\pi,\Sigma)]=||d||_{\infty}-\sum_{\nu\in\mathfrak{S}_{n}}(\pi
P)(\nu)d(\sigma\pi,\nu)\\\
=&||d||_{\infty}-\sum_{\nu\in\mathfrak{S}_{n}}P(\nu\pi^{-1})d(\sigma\pi,\nu)=||d||_{\infty}-\sum_{\nu^{\prime}\in\mathfrak{S}_{n}}P(\nu^{\prime}\pi\pi^{-1})d(\sigma\pi,\nu^{\prime}\pi)\\\
=&||d||_{\infty}-\sum_{\nu^{\prime}\in\mathfrak{S}_{n}}P(\nu^{\prime})d(\sigma,\nu^{\prime})=D_{P}(\sigma).\\\
\end{split}$ (6)

∎

####  B.1.2 Proof of Proposition 2 (maximality at the center)

First, we study the relation between the depth and the probability of
permutations which will be key for the results on the following sections.

######  Proposition 10.

Let $P$ be a SST distribution whose Kemeny’s median is $\sigma^{*}$, and
$\sigma^{*}(a)<\sigma^{*}(b)$. Let $\sigma$ be a ranking such that
$\sigma(a)+1=\sigma(b)$ and let $t_{ab}$ be a transposition, i.e.,
$t_{ab}(a)=b$, $t_{ab}(b)=a$ and $t_{ab}(k)=k$ for all $k\neq a,b$. Then,

$D(\sigma)>D(\sigma t).$

###### Proof.

First, note that the composition $\sigma t_{ab}$ exchanges the ranks of items
$a$ and $b$, so $d(\sigma,\sigma^{*})=d(\sigma t,\sigma^{*})-1$. We can
rewrite $D(\sigma)$ in the following way,

$\begin{split}D(\sigma)=&\binom{n}{2}-\sum_{i<j}p_{i,j}\mathbb{I}\\{\sigma(i)>\sigma(j)\\}-\sum_{i<j}p_{j,i}\mathbb{I}\\{\sigma(i)<\sigma(j)\\}\\\
=&\binom{n}{2}-\sum_{i<j\land i,j\neq
a,b}p_{i,j}\mathbb{I}\\{\sigma(i)>\sigma(j)\\}-\sum_{i<j\land i,j\neq
a,b}p_{j,i}\mathbb{I}\\{\sigma(i)<\sigma(j)\\}-\\\
&-p_{a,b}\mathbb{I}\\{\sigma(a)>\sigma(b)\\}-p_{ba}\mathbb{I}\\{\sigma(a)<\sigma(b)\\}\\\
=&\binom{n}{2}-\sum_{i<j\land i,j\neq
a,b}p_{i,j}\mathbb{I}\\{\sigma(i)>\sigma(j)\\}-\sum_{i<j\land i,j\neq
a,b}p_{j,i}\mathbb{I}\\{\sigma(i)<\sigma(j)\\}-p_{b,a}.\end{split}$ (7)

Where the first equality is the given by proposition 5. In the second we split
the sum for positions $i=a$ and $j=b$ in the latter term and the rest of the
pairs in the previous terms. In the third one, we recall that by assumption
$\sigma(a)=\sigma(b)-1$ and therefore $\mathbb{I}\\{\sigma(a)<\sigma(b)\\}=1$
and $\mathbb{I}\\{\sigma(a)>\sigma(b)\\}=0$. We rewrite in a similar way
$D(\sigma t_{ab})$. For this part, recall that $\sigma t_{ab}(a)=\sigma(b)$,
$\sigma t_{ab}(b)=\sigma(a)$ and $\sigma t_{ab}(k)=k$ for all $k\neq a,b$.

$\begin{split}D(\sigma
t_{ab})=\binom{n}{2}&-\sum_{i<j}p_{i,j}\mathbb{I}\\{\sigma t_{ab}(i)>\sigma
t_{ab}(j)\\}-\sum_{i<j}p_{j,i}\mathbb{I}\\{\sigma t_{ab}(i)<\sigma
t_{ab}(j)\\}\\\ =\binom{n}{2}&-\sum_{i<j\land i,j\neq
a,b}p_{i,j}\mathbb{I}\\{\sigma t_{ab}(i)>\sigma t_{ab}(j)\\}-\sum_{i<j\land
i,j\neq a,b}p_{j,i}\mathbb{I}\\{\sigma t_{ab}(i)<\sigma t_{ab}(j)\\}\\\
&-p_{a,b}\mathbb{I}\\{\sigma t_{ab}(a)>\sigma
t_{ab}(b)\\}-p_{b,a}\mathbb{I}\\{\sigma t_{ab}(a)<\sigma t_{ab}(b)\\}\\\
=\binom{n}{2}&-\sum_{i<j\land i,j\neq
a,b}p_{i,j}\mathbb{I}\\{\sigma(i)>\sigma(j)\\}-\sum_{i<j\land i,j\neq
a,b}p_{j,i}\mathbb{I}\\{\sigma(i)<\sigma(j)\\}-\\\
&-p_{a,b}\mathbb{I}\\{\sigma(a)<\sigma(b)\\}-p_{ba}\mathbb{I}\\{\sigma(a)>\sigma(b)\\}\\\
=\binom{n}{2}&-\sum_{i<j\land i,j\neq
a,b}p_{i,j}\mathbb{I}\\{\sigma(i)>\sigma(j)\\}-\sum_{i<j\land i,j\neq
a,b}p_{j,i}\mathbb{I}\\{\sigma(i)<\sigma(j)\\}-p_{a,b}\end{split}$ (8)

Therefore, for any two rankings $\sigma$ and $\sigma t_{ab}$ such that
$D(\sigma)>D(\sigma t_{ab})$, the following holds,

$\begin{split}D(\sigma)&>D(\sigma t_{ab})\\\
\Leftrightarrow&\binom{n}{2}-\sum_{i<j\land i,j\neq
a,b}p_{i,j}\mathbb{I}\\{\sigma(i)>\sigma(j)\\}-\sum_{i<j\land i,j\neq
a,b}p_{j,i}\mathbb{I}\\{\sigma(i)<\sigma(j)\\}-p_{b,a}\\\
&>\binom{n}{2}-\sum_{i<j\land i,j\neq
a,b}p_{i,j}\mathbb{I}\\{\sigma(i)>\sigma(j)\\}-\sum_{i<j\land i,j\neq
a,b}p_{j,i}\mathbb{I}\\{\sigma(i)<\sigma(j)\\}-p_{a,b}\\\
\Leftrightarrow&p_{b,a}<p_{a,b}.\end{split}$ (9)

For any SST model $P$ with whose median is $\sigma^{*}$, and where
$\sigma^{*}(a)<\sigma^{*}(b)$, it holds (by definition) that
$p_{b,a}<p_{a,b}$, which concludes the proof. ∎

Let us first recall Property 2 (maximality) and Proposition 2. See 2 See 2

We now discuss what is precisely meant by center in the ranking context. We
derive two main definitions for a center:

  * •

Following [60, 64], we emulate the notion of half-space symmetry (which is a
very generic notion of symmetry) and define a notion of $H$-center, from which
our proposition in the main paper stems from. Appart from our maximality
proposition, we further provide results for distributions $P$ having a
$H$-center.

  * •

We define a simpler notion of center based on a natural metric approach. We
also provide maximality results based on this different notion of center,
called a $M$-center.

##### H-center and maximality at center.

The following results (1) define a symmetry center inspired in the classical
formulation of half-space symmetry [60, 64] and (2) shows that the
Kendall’s-$\tau$ and Spearman’s footrule distances satisfy the maximality at
center for the defined center.

######  Proposition 11.

Let us call ”hyperplane” the sets $H_{i,j}=\\{\sigma:\sigma(i)<\sigma(j)\\}$,
we define the H-center $\sigma$ as $\sigma=\cap H_{i,j}$ for all
$\\{(i,j):\sigma_{0}(i)<\sigma_{0}(j)\\}$. For any $P$ such that
$p_{i,j}>p_{j,i}$ for all $\\{(i,j):\sigma_{0}(i)<\sigma_{0}(j)\\}$ the
H-center is $\sigma_{0}$.

###### Proof.

Firstly, we show that $P(\Sigma\in H_{i,j})>P(\Sigma\in H_{j,i})$. This can be
done by construction: For any ranking $\sigma\in H_{i,j}$ (for which
$\sigma(i)=\sigma(j)$) we can construct $\sigma^{\prime}\in H_{j,i}$ that
swaps positions $i$ and $j$. This construction defines a bijection between the
rankings in both sets. The following relation holds:
$p(\sigma^{\prime})=p(\sigma)p_{j,i}/p_{i,j}<p(\sigma)$. Therefore,
$P(\Sigma\in\cap H_{i,j})>P(\Sigma\in\cap H_{j,i})$.

Secondly, it is clear that there is one and only one permutation in $\cap
H_{i,j}$ and this is $\sigma_{0}$. We remark that its possible an H-center is
defined (for this choice of $P$) by a smaller number of subsets, i.e., those
$H_{i,j}$ for which $\sigma(i)=\sigma(j)-1$. ∎

######  Proposition 12.

Let $P$ be distribution for which there is an H-center both Kendall’s-$\tau$
and Spearman’s footrule based depths satisfy the maximality at center property
for the H-center in Definition 11.

###### Proof.

As shown in Proposition 11, the H-center is $\sigma_{0}$ It remains to recall
that Equation(9) in Proposition 10 states that for SST models and the
Kendall’s-$\tau$ distance $D(\sigma)>D(\sigma t_{i,j})\Leftrightarrow
p_{j,i}<p_{i,j}$.

For the Spearman’s distance, let us show that $D_{P}(\sigma_{0})\geq
D_{P}(\sigma_{1})\Leftrightarrow\mathbb{E}_{P}(d(\Sigma,\sigma_{0}))\leq\mathbb{E}_{P}(d(\Sigma,\sigma_{1}))$,
and the proof of our proposition will follow from direct application of this
result.

Let $\sigma$ be any permutation.

$\begin{split}d(\sigma,\sigma_{1})&=\sum_{k=1}^{N}|\sigma(k)-\sigma_{1}(k)|\\\
&=\sum_{k\neq
i,j}|\sigma(k)-\sigma_{0}(k)|+|\sigma(i)-\sigma_{0}(i)-1|+|\sigma(j)-\sigma_{0}(j)+1|\\\
&=\begin{cases}d(\sigma,\sigma_{0})\text{ if
}{\color[rgb]{0.0600000000000001,0.46,1}\sigma(i)<\sigma(j)\leq\sigma_{0}(i)<\sigma_{0}(j)\text{
or }\sigma_{0}(i)<\sigma_{0}(j)\leq\sigma(i)<\sigma(j)}\\\ \quad\quad\text{ or
}{\color[rgb]{1,0.49,0}\sigma(j)<\sigma(i)\leq\sigma_{0}(i)<\sigma_{0}(j)\text{
or }\sigma_{0}(i)<\sigma_{0}(j)\leq\sigma(j)<\sigma(i)}\\\
d(\sigma,\sigma_{0})+2\text{ if
}{\color[rgb]{0.0600000000000001,0.46,1}\sigma(i)<\sigma_{0}(i)<\sigma_{0}(j)<\sigma(j)}\\\
d(\sigma,\sigma_{0})-2\text{ if
}{\color[rgb]{1,0.49,0}\sigma(j)\leq\sigma_{0}(i)<\sigma_{0}(j)\leq\sigma(i)}\end{cases}\end{split}$

Notice the use of color: in blue are cases where $i$ and $j$ are ranked by
$\sigma$ the same way as does $\sigma_{0}$, and in orange are the opposite
cases. Then

$\begin{split}&\mathbb{E}_{P}(d(\sigma,\sigma_{0}))\leq\mathbb{E}_{P}(d(\sigma,\sigma_{1}))\\\
\Leftrightarrow&\sum_{\sigma}\left[\mathbb{I}({\color[rgb]{0.0600000000000001,0.46,1}\text{blue
cases}})-\mathbb{I}({\color[rgb]{1,0.49,0}\text{orange
cases}})\right]\mathbb{P}(\Sigma=\sigma)\geq 0\\\
\Leftrightarrow&p_{i,j}-(1-p_{i,j})\geq 0\\\ \Leftrightarrow&p_{i,j}\geq
1/2\end{split}$

This concludes the proof. ∎

#####  $M$-center definition.

Let us focus on a more natural, metric-based center definition.

######  Definition 6.

$\sigma_{0}$ is $M$-center for distance $d$ and distribution $P$ if:
$\forall(\sigma_{1},\sigma_{2},\sigma_{3})$ such that
$d(\sigma_{0},\sigma_{1})=d(\sigma_{0},\sigma_{2})<d(\sigma_{0},\sigma_{3})$,
we have:
$\mathbb{P}(\Sigma=\sigma_{1})=\mathbb{P}(\Sigma=\sigma_{2})\geq\mathbb{P}(\Sigma=\sigma_{3})$.

We have the following proposition:

######  Proposition 13.

If $d$ is a symmetric distance, and if distribution $P$ has a $M$-center for
$d$, the maximality property is satisfied for distance $d$.

Most distances (as the one studied in this paper) are symmetric. In addition,
the proposition applies to Mallows models as they do exhibit a $S$-center.

###### Proof.

Let $\sigma_{0}$ be a $M$-center for $P$ and distance $d$, with $(i,j)$ such
that $\sigma_{0}(i)<\sigma_{0}(j)=\sigma_{0}(i)+1$. Let $\sigma_{1}$ be the
same ranking as $\sigma_{0}$ except it swaps the ranks of $i$ and $j$.

We show that $D_{P}(\sigma_{0})>D_{P}(\sigma_{0})$ i.e.
$\mathbb{E}_{P}(d(\Sigma,\sigma_{0}))<\mathbb{E}_{P}(d(\Sigma,\sigma_{1}))$
i.e.
$\sum_{\sigma}\mathbb{P}(\Sigma=\sigma)\left[d(\sigma_{1},\sigma)-d(\sigma_{0},\sigma)\right]>0$.

Let $\sigma$ be any ranking such that $d(\sigma_{0},\sigma)=d$. We have:

  * •

(1) $d(\sigma_{0},\sigma)<d(\sigma_{1},\sigma)=d+c_{i,j}$ iff $(i,j)$ is
ranked the same way in $\sigma_{0}$ and $\sigma$

  * •

(2) $d(\sigma_{0},\sigma)>d(\sigma_{1},\sigma)=d-c_{i,j}$ else,

where $c_{i,j}>0$ is a constant depending only on $(i,j)$. For example, if $d$
is Kendall’s tau, $c_{i,j}=1$, if $d$ is Spearman’s footrule, $c_{i,j}=2$, if
$d$ is Spearman’s rho, $c_{i,j}=2|\sigma(j)-\sigma(i)|$.

In addition, let us write $\\#d$ the number of rankings at distance $d$ from
$\sigma_{0}$, which we can divide into the two groups (1) and (2). Let us then
write $\\#d(1)$ (resp. $\\#d(2)$) the number of rankings $\sigma$ at distance
$d$ from $\sigma_{0}$ that rank $i$ and $j$ the same way (resp. differently)
as $\sigma_{0}$. We suppose the following: if $d\leq||d||_{\infty}/2$, then
$\\#d(1)\geq\\#d(2)$ (and if $d>||d||_{\infty}/2$, then $\\#d(1)\leq\\#d(2)$),
and more precisely,
$|\\#d(1)-\\#d(2)|=k(d)=k(||d||_{\infty}-d)\;\forall\;d\leq||d||_{\infty}/2$,
meaning that this cardinality difference depends only on the distance to half
of the maximal distance.

Let us also write $P_{d}=\mathbb{P}(\Sigma=\sigma)$ for any $\sigma$ at
distance $d$ from $\sigma_{0}$.

$\begin{split}\sum_{\sigma}\mathbb{P}(\Sigma=\sigma)\left[d(\sigma_{1},\sigma)-d(\sigma_{0},\sigma)\right]&=\sum_{d=0}^{||d||_{\infty}}P_{d}\times\\#d\times|c_{i,j}|\\\
&=\sum_{d=0}^{||d||_{\infty}}P_{d}\times(\\#d(1)-\\#d(2))\times c_{i,j}\\\
&=\sum_{d=0}^{||d||_{\infty}/2}P_{d}\times k(d)\times
c_{i,j}-\sum_{d^{\prime}=||d||_{\infty}/2+1}^{||d||_{\infty}}\underbrace{P_{d^{\prime}}}_{<P_{||d||_{\infty}-d^{\prime}}}\times
k(d^{\prime})\times c_{i,j}\\\ &>\sum_{d=0}^{||d||_{\infty}/2}P_{d}\times
c_{i,j}\times(k(d)-k(||d||_{\infty}-d))\\\ &>0\end{split}$

∎

####  B.1.3 Proofs of Propositions 3 and 4 (monotonicity)

The Monotonicity properties 3 and 3 do not hold in general. As an
illustration, fig. 7 shows the distance to the median as a function of depth
for every rankings in sample generated by Mallows or Placket-Luce
distributions.

Figure 7: Each permutation in $\mathfrak{S}_{6}$ is a point displaying its
depth (X-axis) and distance to the median (Y-axis). The ranking models are (a)
Mallows model with $\phi=\mathrm{e}^{-0.375}$, (b) Mallows model with
$\phi=\mathrm{e}^{-0.625}$, (c) Plackett-Luce with
$\boldsymbol{w}_{2}=(\mathrm{e}^{n},...,\mathrm{e}^{1})$, (b) Plackett-Luce
with $\boldsymbol{w}_{2}=({n},...,{1})$.

However, we derive two conditions making these monotonicity properties to
hold, restricting ourselves to the case where the distance $d$ used is Kendall
$\tau$, and also to distributions $P$ that are strictly stochastically
transitive (SST) to ensure uniqueness of the central ranking $\sigma^{*}$ (see
[11]).

First, let us recall the local monotonicity property and our local
monotonicity proposition: See 3 See 3

The first part of this proposition follows immediately form Proposition 10: as
we move further from the median (as measured by the Kendall $\tau$ distance)
swapping adjacent ranks, the depth is strictly decreasing.

Now, we derive a second, stronger local monotonicity property. The following
propostion explicit the conditions under which it is satisfied.

######  Proposition 14.

For a generic SST distribution $P$, if two rankings $\sigma$ and
$\sigma^{\prime}$ with $d=d(\sigma^{*},\sigma)$ and
$d^{\prime}=d(\sigma^{*},\sigma^{\prime})$ satisfies the following:

$2\left[\sum_{(i,j)|p_{i,j}<1/2,\;\sigma\text{
correct},\;\sigma^{\prime}\text{
incorrect}}p_{i,j}-\sum_{(i,j)|p_{i,j}<1/2,\;\sigma\text{
incorrect},\;\sigma^{\prime}\text{ correct}}p_{i,j}\right]-(d^{\prime}-d)\leq
0$

Then the following property holds:

$d=d(\sigma^{*},\sigma)<d^{\prime}=d(\sigma^{*},\sigma^{{}^{\prime}})\Longrightarrow
D_{P}(\sigma)\geq D_{P}(\sigma^{{}^{\prime}}),$ (10)

where $d$ is Kendall $\tau$, $\sigma^{*}$ is Kemeny’s median and ”$\sigma$
correct on $(i,j)$” means that $\sigma$ and $\sigma^{*}$ order the pair
$(i,j)$ the same way.

The proof of this proposition can be directly derived from the proof of
Proposition 4 (eq. 11)

Second, we recall the global monotonicity property and our proposition: See 4
See 4

###### Proof.

$P$ is SST so $\forall\;(i,j,l),p_{i,j}>1/2$ and $p_{j,l}>1/2\Longrightarrow
p_{i,l}>1/2$. WLOG, let us suppose that $\forall i<j,p_{i,j}<1/2$. As
$\sigma^{*}$ is the unique Kemeny’s median, we have
$\sigma^{*}(n)<\sigma^{*}(n-1)<...<\sigma^{*}(1)$ (i.e $n\succ
n-1\succ...\succ 1$).

Let $(\sigma,\sigma^{{}^{\prime}})$ be two rankings such that
$d=d(\sigma^{*},\sigma)<d(\sigma^{*},\sigma^{{}^{\prime}})=d^{\prime}$. Let us
write
$k:=\\#\\{(i,j)|\mathbb{I}\left((\sigma^{*}(i)-\sigma^{*}(j))(\sigma(i)-\sigma(j))\right)>0\times\mathbb{I}\left((\sigma^{*}(i)-\sigma^{*}(j))(\sigma^{\prime}(i)-\sigma^{\prime}(j))\right)<0\\}$,
which means that there are $k$ pairs $(i,j)$ on which $\sigma$ agrees with
$\sigma^{*}$ (i.e. $\sigma$ is ”correct” on $(i,j)$) but $\sigma^{\prime}$
disagrees with $\sigma^{*}$ (i.e. $\sigma^{\prime}$ is ”incorrect” on
$(i,j)$). We define $k^{\prime}$ similarly by interchanging the roles of
$\sigma$ and $\sigma^{\prime}$.

Our goal is then to find a condition on the distribution of rankings $P$ such
that:

$\max_{\sigma,\sigma^{\prime}}L_{P}(\sigma)-L_{P}(\sigma^{\prime})<0,\quad\text{
with }k>k^{\prime}$

First, let us study the range of possible values for $k$. Let us divide the
$n(n-1)/2$ pairs $i<j$ following:

$\displaystyle 1)\quad\sigma\text{ agrees with }\sigma^{*}\text{ and
}\sigma^{\prime}\text{ disagrees with }\sigma^{*}$ $\displaystyle\to k\text{
pairs}$ $\displaystyle 2)\quad\sigma\text{ agrees with }\sigma^{*}\text{ and
}\sigma^{\prime}\text{ agrees with }\sigma^{*}$ $\displaystyle\to a\text{
pairs}$ $\displaystyle 3)\quad\sigma\text{ disagrees with }\sigma^{*}\text{
and }\sigma^{\prime}\text{ agrees with }\sigma^{*}$ $\displaystyle\to
k^{\prime}\text{ pairs}$ $\displaystyle 4)\quad\sigma\text{ disagrees with
}\sigma^{*}\text{ and }\sigma^{\prime}\text{ disagrees with }\sigma^{*}$
$\displaystyle\to b\text{ pairs}$

We then have

$\left\\{\begin{aligned} &k^{\prime}+b=d\\\ &k+b=d^{\prime}\\\
&k+a+k^{\prime}+b=n(n-1)/2\end{aligned}\right.\text{ so }\\\
\left\\{\begin{aligned} &k^{\prime}=k+d-d^{\prime}\\\ &b=d^{\prime}-k\\\
&a=n(n-1)/2-k-d\end{aligned}\right.$

Finally, since we have $0\leq k,k^{\prime},a,b\leq n(n-1)/2$, we end up having
the following relevant conditions on $k$:

$d^{\prime}-d\leq k\leq d^{\prime}$

Now, let us write $p^{(m)}$ the $m$-th hightest element of the vector
$(p_{i,j})_{i<j}$ of size $n(n-1)/2$, so that
$1/2>p^{(1)}>p^{(2)}>...>p^{(n(n-1)/2)}$. Then, we have

$\displaystyle\max_{\sigma,\sigma^{\prime}}L_{P}(\sigma)-L_{P}(\sigma^{{}^{\prime}})$
$\displaystyle=\max_{\sigma,\sigma^{\prime}}\sum_{i<j}p_{i,j}\left[\mathbb{I}\\{\sigma(i)-\sigma(j)>0\\}-\mathbb{I}\\{\sigma^{{}^{\prime}}(i)-\sigma^{{}^{\prime}}(j)>0\\}\right]+$
$\displaystyle\quad\quad\quad\quad(1-p_{i,j})\left[\mathbb{I}\\{\sigma(i)-\sigma(j)<0\\}-\mathbb{I}\\{\sigma^{{}^{\prime}}(i)-\sigma^{{}^{\prime}}(j)<0\\}\right]$
$\displaystyle=\max_{\sigma,\sigma^{\prime}}\sum_{i<j}(2p_{i,j}-1)\left[\mathbb{I}\\{\sigma(i)-\sigma(j)>0\\}+\mathbb{I}\\{\sigma^{{}^{\prime}}(i)-\sigma^{{}^{\prime}}(j)<0\\}-1\right]$
$\displaystyle=\max_{\sigma,\sigma^{\prime}}\sum_{i<j;\sigma\text{corr.},\sigma^{{}^{\prime}}\text{
incorr.}}(2p_{i,j}-1)-\sum_{i<j;\sigma\text{
incorr.},\sigma^{{}^{\prime}}\text{ corr.}}(2p_{i,j}-1)$
$\displaystyle\leq\max_{\sigma,\sigma^{\prime}}2\left[\sum_{i<j;\sigma\text{
corr.},\sigma^{{}^{\prime}}\text{ incorr.}}p_{i,j}-\sum_{i<j;\sigma\text{
incorr.},\sigma^{{}^{\prime}}\text{ corr.}}p_{i,j}\right]-(k-k^{\prime})$
$\displaystyle\text{ with }k^{\prime}=k-(d^{\prime}-d)$ (11)
$\displaystyle\leq 2\left[\underbrace{p^{(1)}+...+p^{(k)}}_{k\text{
elements}}-\underbrace{p^{(n(n-1)/2-k^{\prime}-1)}-...-p^{(n(n-1)/2)}}_{k^{\prime}=k-(d^{\prime}-d)\text{
elements}}\right]-(d^{\prime}-d)$ $\displaystyle\leq
2\left[(p^{(1)}-p^{(n(n-1)/2-k^{\prime}-1)})+...+(p^{(k^{\prime})}-p^{(n(n-1)/2)})+\right.$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\left.p^{(k^{\prime}+1)}+...+p^{(k)}\right]-(d^{\prime}-d)$
$\displaystyle\leq 2\left[(k^{\prime}\times
s+(1/2-h)(d^{\prime}-d)\right]-(d^{\prime}-d)$ $\displaystyle\leq 2(d\times
s-h)$ $\displaystyle\leq 0$

∎

Note also that if $P$ is non-SST, then the global monotonicity property never
holds, which can be easily proven by taking a counter-example and following
the same proof structure.

###  B.2 Proof Proposition 7 (learning rate bounds)

Here we prove the finite sample results stated in the proposition below.

See 7

###### Proof.

Hoeffding inequality combined with the union bound yields: $\forall t>0$,

$\mathbb{P}\left\\{\sup_{\sigma\in\mathfrak{S}_{n}}\left|\widehat{D}_{N}(\sigma)-D_{P}(\sigma)\right|>t\right\\}\leq\sum_{\sigma\in\mathfrak{S}_{n}}\mathbb{P}\left\\{\frac{1}{N}\left|\sum_{i=1}^{N}\left\\{d(\Sigma_{i},\sigma)-\mathbb{E}_{P}[d(\Sigma,\sigma)]\right\\}\right|>t\right\\}\leq
2n!\exp\left(-\frac{N2t^{2}}{||d||_{\infty}^{2}}\right),$

which establishes assertion $(i)$.

Turning to the proof of assertion $(ii)$, we introduce

$\bar{S}_{P}(u)=\mathbb{P}_{\Sigma}\\{\widehat{D}_{\lfloor
N/2\rfloor}(\Sigma)\geq u\\},\;\;u\geq 0.$

By triangular inequality, we have with probability one:

$\sup_{u\geq 0}\left|(K_{h}\ast\widehat{S}_{N})(u)-(K_{h}\ast
S_{P})(u)\right|\leq\sup_{u\geq
0}\left|(K_{h}*\widehat{S}_{N})(u)-(K_{h}*\bar{S}_{P})(u)\right|+\\\
\sup_{u\geq 0}\left|(K_{h}*S_{P})(u)-(K_{h}*\bar{S}_{P})(u)\right|.$ (12)

Observe that we almost-surely have:

$\sup_{u\geq
0}\left|(K_{h}*\widehat{S}_{N})(u)-(K_{h}*\bar{S}_{P})(u)\right|\leq\sup_{u\geq
0}\left|\widehat{S}_{N}(u)-\bar{S}_{P}(u)\right|.$

By virtue of Dvoretsky-Kiefer-Wolfovitz inequality, we have, for all $t\geq
0$,

$\mathbb{P}\left\\{\sup_{u\geq
0}\left|\widehat{S}_{N}(u)-\bar{S}_{P}(u)\right|\geq
t\right\\}=\mathbb{E}\left[\mathbb{P}\left\\{\sup_{u\geq
0}\left|\widehat{S}_{N}(u)-\bar{S}_{P}(u)\right|\geq
t\mid\Sigma_{1},\;\ldots,\;\Sigma_{\lfloor N/2\rfloor}\right\\}\right]\leq
2\exp(-2nt^{2}).$ (13)

Let $s>0$, we introduce the event, independent from $\Sigma$,

$\mathcal{E}_{N,s}=\left\\{\sup_{\sigma\in\mathfrak{S}_{n}}\left|\widehat{D}_{\lfloor
N/2\rfloor}(\sigma)-D_{P}(\sigma)\right|\leq s\right\\}.$

We almost-surely have: $\forall u\geq 0$,

$\bar{S}_{P}(u)=\mathbb{P}_{\Sigma}\\{D_{P}(\Sigma)\geq
u+D_{P}(\Sigma)-\widehat{D}_{\lfloor N/2\rfloor}(\Sigma)\\}.$

Consequently, on the event $\mathcal{E}_{N,s}$, it holds that: $\forall u\geq
0$,

$(K_{h}*S_{P})(u+s)-(K_{h}*S_{P})(u)\leq(K_{h}*\bar{S}_{P})(u)-(K_{h}*\widehat{S}_{N})(u)\leq(K_{h}*S_{P})(u)-(K_{h}*S_{P})(u-s),$

as well as

$\sup_{u\geq
0}\left|(K_{h}*S_{P})(u)-(K_{h}*\bar{S}_{P})(u)\right|\leq||K^{\prime}||_{\infty}(s/h),$
(14)

since the mapping $K_{h}*S_{P}$ being differentiable, with derivative bounded
by $||K^{\prime}||_{\infty}/h$ in absolute value. Hence, using the union
bound, combining (12) with assertion $(i)$ and (13)-(14), we get that for all
$\delta\in(0,1)$, with probability larger than $1-\delta$:

$\sup_{u\geq 0}\left|(K_{h}\ast\widehat{S}_{N})(u)-(K_{h}\ast
S_{P})(u)\right|\leq\left(\sqrt{\log(4/\delta)}+||d||_{\infty}\sqrt{\log(4n!/\delta)}\right)/\sqrt{2N}.$

This proves assertion $(ii)$. ∎

###  B.3 Proofs of Propositions 5, 6 and 15 (results for Kendall $\tau$ \-
Mallows model)

See 5

###### Proof.

The proof is a simple computation, recalling that $\forall i\neq
j,p_{i,j}=\mathbb{P}(\Sigma(i)<\Sigma(j))$. Then,
$D_{P}(\sigma)=||d||_{\infty}-\mathbb{E}_{P}(d_{\tau}(\Sigma,\sigma))=\binom{n}{2}-\sum_{i<j}\mathbb{P}\left((\Sigma(i)-\Sigma(j))(\sigma(i)-\sigma(j))<0\right)=\binom{n}{2}-\sum_{i<j}p_{i,j}\mathbb{I}(\sigma(i)>\sigma(j))-\sum_{i<j}(1-p_{i,j})\mathbb{I}(\sigma(i)<\sigma(j))$
by simple conditioning. ∎

See 6

###### Proof.

Observing that $n(n-1)/2=L_{P}(\sigma)+L_{P}(n-\sigma)$ for all
$\sigma\in\mathfrak{S}_{n}$ in the Kendall $\tau$ case, the result is
essentially a reformulation of Theorem 5 in [11] in terms of ranking depth,
insofar as $D_{P}=n(n-1)/2-L_{P}$. ∎

Let us recall some classical results about the Mallows distribution. Taking
$d=d_{\tau}$, the Mallows model introduced in [49] is the unimodal
distribution $P_{\theta}$ on $\mathfrak{S}_{n}$ parametrized by
$\theta=(\sigma_{0},\phi_{0})\in\mathfrak{S}_{n}\times(0,1]$:
$\forall\sigma\in\mathfrak{S}_{n}$,
$P_{\theta}(\sigma)=(1/Z_{0})\exp(d_{\tau}(\sigma_{0},\sigma)\log\phi_{0})$,
where
$Z_{0}=\sum_{\sigma\in\mathfrak{S}_{n}}\exp(d_{\tau}(\sigma_{0},\sigma)\log\phi_{0})$
is a normalization constant.

One may easily show that $Z_{0}$ is independent from $\sigma_{0}$ and that
$Z_{0}=\prod_{i=1}^{n-1}\sum_{j=0}^{i}\phi_{0}^{j}$. When $\phi_{0}<1$, the
permutation $\sigma_{0}$ of reference is the mode of distribution
$P_{\theta_{0}}$, as well as its unique median relative to $d_{\tau}$. Observe
in addition that the smallest the parameter $\phi_{0}$, the spikiest the
distribution $P_{\theta_{0}}$. In contrast, $P_{\theta_{0}}$ is the uniform
distribution on $\mathfrak{S}_{n}$ when $\phi_{0}=1$.

A closed-from expression of the pairwise probabilities $p_{i,j}$ is available
(see e.g. Theorem 2 in [6]). Setting $h(k,\phi_{0})=k/(1-\phi_{0}^{k})$ for
$k\geq 1$, one can then show the following: that the ranking depth function
relative to $P_{\theta}$ and $d_{\tau}$ is given by:

######  Proposition 15.

If $P=P_{\theta}$ the Mallows distribution and $d=d_{\tau}$ the Kendall $\tau$
distance, then $\forall\sigma\in\mathfrak{S}_{n}$,
$D_{P_{\theta}}(\sigma)={n\choose
2}-\sum_{\sigma(i)>\sigma(j)}H(\sigma_{0}(j)-\sigma_{0}(i),\;\phi_{0})$, where
$H(k,\phi_{0})=h(k+1,\phi_{0})-h(k,\phi_{0})$ and
$H(-k,\phi_{0})=1-H(k,\phi_{0})$ for $k\geq 1$.

where $h(k,\phi_{0})=k/(1-\phi_{0}^{k})$ for $k\geq 1$

###### Proof.

Theorem 2 in [6] states that, for the Mallows model and using our notations,
$\forall i\neq j,p_{i,j}=H(\sigma_{0}(j)-\sigma_{0}(i),\phi_{0})$. The results
follows from direct application of proposition 5 ∎

.

###  B.4 Proof of Proposition 8 (Borda estimators’ robustness)

Proposition 8 refers to the robustness of the depth-trimmed-Borda compared to
the classical Borda. See 8

In this subsection, we will in fact proves some auxiliary results as well as a
generalization of this proposition.

Let us first recall some definitions and results about the Borda estimators.
Borda is an approximation to the barycentric ranking median (which is NP-hard
for $n>4$ [22]) for a sample of complete rankings drawn from a MM [27].
Moreover, Borda is quasi-linear in time and outputs the correct median w.h.p.
with a polynomial number of samples [8]. A robust aggregation procedure for
top-$k$ rankings in very noisy settings is proposed in [12].

The Borda median estimator for sample $X$ orders the items increasingly by
their Borda score, defined as $B(i)=\sum_{\sigma\in X}\sigma(i)$.

We define the depth-weighted-Borda as a generalization of the classic and
depth-trimmed-Borda in which there exists a weight associated with each
ranking. It generalizes Borda in the following way: For each item $i$, the
Borda score is computed as $B(i)=\sum_{\sigma\in X}w(\sigma)\sigma(i)$. The
final estimator for the median is the ranking that orders the items by their
Borda score. The depth-weighted-Borda is equivalent to replicating the
rankings proportionally to their weight. This analysis generalizes to any
weights are increasing function of the depths. In particular, the depth-
trimmed-Borda is the case of depth-weighted-Borda in which
$w(\sigma)=\mathbb{I}\\{D(\sigma)>\mu\\}$.

We settle here the notation for the following lines. We denote by $S_{N}\sim
P$ a sample of rankings (of size N) and $A$ an adversarial sample.

######  Definition 7.

Let $P$ be a distribution, let us write $S_{N}\sim P$ a sample drawn from $P$
of size $N$ and $\sigma^{T}_{S_{N}}$ the median based on the estimator method
$T$ on sample $S_{N}$.

The estimator $T$ is said to be $\delta$-broken (for Kendall’s $\tau$) for
sample size $N$ and distribution $P$ if for any $S_{N}\sim P$ of size $N$,
there exists an adversarial sample $A$ such that
$d_{\tau}(\sigma^{T}_{S_{N}},\sigma^{T}_{S_{N}\cup A})\geq\delta$.

The next result characterizes the carnality of a sample that breaks the Borda
estimator of a sample $S_{N}$ distributed according to $P$. This is an
auxiliary result for Proposition 8.

######  Proposition 16.

Let $S_{N}\sim P$. Let $A^{-}$ be the adversarial sample that $\delta$-breaks
the Borda estimator (for sample size $N$ and distribution $P$) such that
$A^{-}$ is of minimal cardinality. Let $\bar{r}_{N}(i)=N^{-1}\sum_{\sigma\in
S_{N}}\sigma(i)$ and $\bar{r}(i)=(\\#A^{-})^{-1}\sum_{\sigma\in
A^{-}}\sigma(i)$ be the average ranking of item $i$ in $S_{N}$ and $A^{-}$
respectively. Finally, let $\bar{R}$ be the ordered vector composed of
$\frac{\bar{r}_{N}(j)-\bar{r}_{N}(i)}{\bar{r}(i)-\bar{r}(j)}$ for all $(i,j)$
such as both the numerator and denominator are positive. Then

$\\#A^{-}=\lceil N\left[\bar{R}\right]_{(\delta)}\rceil$

where $[x]_{(\delta)}$ denotes the $\delta$-th quantile of a vector $x$.

###### Proof.

By definition, $A^{-}$ $\delta$-breaks Borda iff the following holds.

$\begin{split}d&(\sigma^{B}_{S_{N}},\sigma^{B}_{S_{N}\cup A^{-}})=\delta\\\
&\Leftrightarrow\delta=\\#\\{(i<j):\sum_{\sigma\in
S_{N}}\sigma(i)+\sum_{\sigma\in A^{-}}\sigma(i)\geq\sum_{\sigma\in
S_{N}}\sigma(j)+\sum_{\sigma\in A^{-}}\sigma(j)\\}\\\
&\Leftrightarrow\delta=\\#\\{(i<j):\sum_{\sigma\in
S_{N}}\sigma(i)-\sigma(j)\geq\sum_{\sigma\in A^{-}}\sigma(j)-\sigma(i)\\}\\\
&\Leftrightarrow\delta=\\#\\{(i<j):\sum_{\sigma\in
S_{N}}\sigma(j)-\sigma(i)\leq\sum_{\sigma\in A^{-}}\sigma(i)-\sigma(j)\\}\\\
&\Leftrightarrow\delta=\\#\\{(i,j):0<\sum_{\sigma\in
S_{N}}\sigma(j)-\sigma(i)\leq\sum_{\sigma\in
A^{-}}\sigma(i)-\sigma(j)\\}\end{split}$ (15)

From a statistical perspective, we can bound the cardinality of $A^{-}$ as
follows: let $(i,j)$ be a pair of index belonging to the set define just
above.

$\begin{split}&\sum_{\sigma\in S_{N}}\sigma(j)-\sigma(i)\leq\sum_{\sigma\in
A^{-}}\sigma(i)-\sigma(j)\\\ &\Leftrightarrow
N\>(\bar{r}_{N}(j)-\bar{r}_{N}(i))\leq\\#A^{-}(\bar{r}(i)-\bar{r}(j))\\\
&\Rightarrow\\#A^{-}\geq\frac{N\>(\bar{r}_{N}(j)-\bar{r}_{N}(i))}{\bar{r}(i)-\bar{r}(j)},\end{split}$
(16)

which holds for exactly $\delta$ pairs of items $(i,j)$. We conclude the proof
by recalling that $A^{-}$ is of minimal cardinality. ∎

The next auxiliary result shows that provided certain conditions, if a sample
breaks the depth-weighted-Borda then it breaks Borda.

######  Proposition 17.

Let $S_{N}\sim P$. Let $A^{-}$ (resp. $A^{-}_{w}$) be the adversarial sample
that $\delta$-breaks the Borda (resp. depth-weighted Borda) estimator (for
sample size $N$ and distribution $P$) such that $A^{-}$ (resp. $A^{-}_{w}$) is
of minimal cardinality. Let $\bar{r}_{N}(i)=N^{-1}\sum_{\sigma\in
S_{N}}\sigma(i)$ and $\bar{r}_{w}(i)=(\\#A^{-}_{w})^{-1}\sum_{\sigma\in
A^{-}_{w}}\sigma(i)$ be the average ranking of item $i$ in $S_{N}$ and
$A^{-}_{w}$ respectively.

Let $\pi_{w}=\arg\max_{\sigma\in A^{-}_{w}}w(\sigma)$ and $\mu=w(\pi_{w})$ the
threshold of maximum depth for adversarial rankings.

Finally, suppose that $\hat{P}_{N}$ and $w$ satisfy:
$\mathbb{E}_{\hat{P}_{N}}(w(\Sigma))>w(\pi_{w})=\mu$ and
$\;\forall\;(i,j)\text{ s.t.
}\mathbb{E}_{\hat{P}_{N}}(\Sigma(j)-\Sigma(i))>0$,
$\mathbb{E}_{\hat{P}_{N}}(w(\Sigma)(\Sigma(j)-\Sigma(i))\geq\mathbb{E}_{\hat{P}_{N}}(w(\Sigma))\mathbb{E}_{\hat{P}_{N}}(\Sigma(j)-\Sigma(i))$
(these two assumptions enforce the use of a weight function that is in
accordance with $\hat{P}_{N}$)

Then, the cardinality of $A^{-}$ and $A^{-}_{w}$ are related as follows:

$\\#A^{-}_{w}\geq\frac{N^{-1}\sum_{\sigma\in S_{N}}w(\sigma)}{\mu}\\#A^{-}.$

###### Proof.

Since $A^{-}_{w}$ $\delta$-breaks the depth-weighted-Borda, we can follow the
same proof outline as for proposition 16 and bound the cardinality
$\\#A^{-1}_{w}$ as follows,

$\begin{split}&\sum_{\sigma\in
S_{N}}w(\sigma)(\sigma(j)-\sigma(i))\leq\sum_{\sigma\in
A^{-}_{w}}w(\sigma)(\sigma(i)-\sigma(j))\\\ &\Rightarrow
N\times\>N^{-1}\sum_{\sigma\in
S_{N}}w(\sigma)(\sigma(j)-\sigma(i))\leq\\#A^{-}_{w}w(\pi)(\bar{r}_{w}(i)-\bar{r}_{w}(j))\\\
&\Rightarrow\\#A^{-}_{w}\geq\frac{N\>(\bar{r}_{n}(j)-\bar{r}_{N}(i))}{\bar{r}_{w}(i)-\bar{r}_{w}(j)}\frac{N^{-1}\sum_{\sigma\in
S_{N}}w(\sigma)}{\mu}\\\ \end{split}$ (17)

Since $\frac{N^{-1}\sum_{\sigma\in S_{N}}w(\sigma)}{\mu}$ is independent of
$i,j$ and $A^{-}_{w}$ also $\delta$-breaks the Borda estimator, we can
conclude:

$\begin{split}\\#A^{-}_{w}\geq\\#A^{-}\frac{N^{-1}\sum_{\sigma\in
S_{N}}w(\sigma)}{\mu}.\end{split}$ (18)

∎

We are finally ready to prove a generalization of our proposition 8 stated in
the main paper. Let us first define our notion of $\delta$-breakdown point,
which extends the classical concept.

######  Definition 8.

Let $P$ be a distribution. The $\delta$-breakdown point for an estimator $T$
with respect to distribution $P$ is defined as the smallest cardinality of an
adversarial sample that $\delta$-breaks $T$ in the limit when $N\to\infty$ for
distribution $P$.

More specifically, $\epsilon_{\delta}^{T}(P)=\min\\#A$ s.t.
$\lim_{N\to\infty}d_{\tau}(\sigma^{T}_{S_{N}},\sigma^{T}_{S_{N}\cup
A})=\delta$

In the following proposition, we write $\epsilon^{B}_{\delta}(P)$ (resp.
$\epsilon^{DW-B}_{\delta}(P)$) the $\delta$-breakdown point for the Borda
(resp. depth-weighted Borda) estimator with respect to distribution $P$.

######  Proposition 18 (breakdown points ratio).

Let $P$ be a distribution such that $\mathbb{E}_{P}[w(\Sigma)]>w(\pi)$, where
$\pi=\arg\max_{\sigma\;|\;d_{\tau}(\sigma^{*},\sigma)=\delta}w(\sigma)$ and
$\sigma^{*}=\arg\max_{\sigma\in\mathfrak{S}_{n}}D_{P}(\sigma)$. Let $P$ and
$w$ satisfy: $\forall(i,j)\text{ s.t. }\mathbb{E}_{P}(\Sigma(j)-\Sigma(i))>0$,
$\mathbb{E}_{P}(w(\Sigma)(\Sigma(j)-\Sigma(i)))\geq\mathbb{E}(w(\Sigma))\mathbb{E}(\Sigma(j)-\Sigma(i))$.
Then,

$\begin{split}\lim_{N\to\infty}\frac{\epsilon_{\delta}^{B}(P)}{\epsilon_{\delta}^{DW-B}(P)}<\frac{w(\pi)}{\mathbb{E}_{P}[w(\Sigma)]}<1.\end{split}$
(19)

###### Proof.

We start by noting that for $S_{N}$ to be $\delta$-broken then the adversarial
sample has to be at least at distance $\delta$ regardless the distribution for
the weights. Then, we denote
$z=\mathbb{E}_{P}[w(\Sigma)]/w(\pi)=\lim_{N\to\infty}N^{-1}\sum_{\sigma\in
S_{N}}w(\sigma)/w(\pi)$ (by the law of large numbers) and take Proposition 17
to write the limiting ratio of the breakdown points when the number of samples
tends to infinity as follows.

$\begin{split}\lim_{N\to\infty}\frac{\epsilon_{\delta}^{B}(P)}{\epsilon_{\delta}^{DW-B}(P)}=\lim_{N\to\infty}\frac{\frac{\\#A^{-}}{\\#A^{-}+N}}{\frac{\\#A^{-}_{w}}{\\#A^{-}_{w}+N}}<\lim_{N\to\infty}\frac{\frac{\\#A^{-}}{\\#A^{-}+N}}{\frac{\\#A^{-}\cdot
z}{\\#A^{-}\cdot
z\;+\;N}}<\frac{1}{z}=\frac{w(\pi)}{\mathbb{E}_{P}[w(\Sigma)]}<1\end{split}$
(20)

∎

This is the main result related to the robustness of the Borda median
estimator. It shows that the breakdown point of Borda is smaller than the
breakdown point for the depth-trimmed-Borda provided certain conditions. We
denote by $\mu$ the threshold of the depth-trimmed-Borda.

Then, our proposition 8 is straightforward when we choose the weight function
$w$ so that $w(\sigma)=\mathbb{I}(D_{P}(\sigma)\geq\mu)$ in Proposition 18.

##  Appendix C Further results

###  C.1 Ranking quantile function

In Proposition 7, rate bounds for the deviation between empirical and
theoretical versions of the depth function (respectively, of the smoothed
depth survivor function) have been stated. We here give some indications for
obtaining similar results for the ranking quantile function.

As the considered distribution is discrete, finite and real-valued (because
depth is real-valued), the results of [48] can be directly applied. Using
their notations, we have:

$\Sigma$ is a random variable of distribution $P$ on $\mathfrak{S}_{n}$ that
takes distinct values $\sigma_{1},\;\ldots,\;\sigma_{m}$ with respective
propabilities $\rho_{1},\;\ldots,\;\rho_{m}$. Each element
$\sigma_{i}\in\\{\sigma_{1},...,\sigma_{m}\\}$ has a depth $\delta_{i}$, which
leads us to write $D_{P}(\Sigma)$ the random variable associated to the depth.

Now, let us reorder the indices and write the distinct depth values
$\delta_{1}<...<\delta_{d}$ with respective probabilities of occurrence
$p_{1},\;\ldots,\;p_{d}$, where $\forall\;i\in[\\![1,d]\\!],p_{i}=\sum_{1\leq
j\leq m}\rho_{j}\mathbb{1}(\delta_{j}=\delta_{i})$. Let us define the mid-
function $F_{mid}(x)=\mathbb{P}(D_{P}(\Sigma)\leq
x)-1/2\mathbb{P}(D_{P}(\Sigma)=x)$ and the ranking quantile function based on
mid-functions:

$Q(\alpha)=F_{mid}^{-1}(\alpha)=\begin{cases}\delta_{1}&\text{if $\alpha\leq
p_{1}/2$}\\\ \lambda\delta_{k}+(1-\lambda)\delta_{k+1}&\text{if
$\alpha=\lambda\pi_{k}+(1-\lambda)\pi_{k+1}$}\\\ &\quad\quad\text{for any
$\lambda\in[0,1]$ and $1\leq k\leq d-1$}\\\ \delta_{d}&\text{if
$\alpha\geq\pi_{d}$}\end{cases},$ (21)

where $\forall
k\in[\\![2,d]\\!],\pi_{k}=\sum_{i=1}^{k-1}p_{i}+p_{k}/2=F_{mid}(\delta_{k})$.

Then, the following results hold:

$\displaystyle 1)$
$\displaystyle\;\hat{Q}_{N}(\alpha)\overset{\mathbb{P}}{\longrightarrow}\delta_{1}\text{
if $\alpha<p_{1}/2$}$ $\displaystyle 2)$
$\displaystyle\;\hat{Q}_{N}(\alpha)\overset{\mathbb{P}}{\longrightarrow}\delta_{d}\text{
if $\alpha>\pi_{d}$}$ $\displaystyle 3)$
$\displaystyle\;\sqrt{N}(\hat{Q}_{N}(\alpha)-(\lambda\delta_{k+1}+(1-\lambda)\delta_{k+2}))\overset{\mathbb{P}}{\longrightarrow}\mathcal{N}(0,sd(\alpha,\lambda,p_{k+1},p_{k+2}))$
if $\alpha=\lambda\pi_{k+1}+(1-\lambda)\pi_{k+2}$ for $0<\lambda<1$ and $0\leq
k\leq d-2$ $\displaystyle 4)$
$\displaystyle\;\sqrt{N}(\hat{Q}_{N}(\alpha)-\delta_{k+1})f(\hat{Q}_{N}(\alpha),\delta_{k+1})\overset{\mathbb{P}}{\longrightarrow}\mathcal{N}(0,\alpha(1-\alpha)-p_{k+1}/4)$
$\displaystyle\quad\quad\quad\quad\text{ if $\alpha=\pi_{k+1}$ for $0\leq
k\leq d-1$},$

where
$sd(\alpha,\lambda,p_{k+1},p_{k+2})=\alpha(1-\alpha)-(1-(\lambda-1)^{2})p_{k+1}/4-(1-\lambda^{2})p_{k+2}/4$
and
$f(\hat{Q}_{N}(\alpha),\delta_{k+1})=1/2(p_{k+1}+p_{k+2})/(\delta_{k+2}-\delta_{k+1})\text{
if $\hat{Q}_{N}(\alpha)>\delta_{k+1}$ and
}1/2(p_{k+1}+p_{k})/(\delta_{k+1}-\delta_{k})$ else.

These results provide us with asymptotic guarantees about the ranking quantile
function based on mid-functions, as defined in eq. 21. However, non-asymptotic
bounds as well as similar results for the depth regions should be investigated
further and are left for future work, like the discrepancy between empirical
and theoretical ranking depth regions, which can be measured by e.g. the
cardinality of their symmetric difference.

###  C.2 Pairwise comparisons as an alternative statistical framework

Since the computation of Kendall $\tau$ distance involves pairwise comparisons
only, one could compute empirical versions of the risk functional $L$ in a
statistical framework stipulating that the observations are less complete than
$\\{\Sigma_{1},\;\ldots,\;\Sigma_{N}\\}$ and formed by i.i.d. pairs:

$(\mathbf{e}_{k},\;\epsilon_{k}),\;k=1,\;\ldots,\;N,$

where the $\mathbf{e}_{k}=(\i_{k},\j_{k})$’s are independent from the
$\Sigma_{k}$’s and drawn from an unknown distribution $\nu$ on the set
$\mathcal{E}_{n}$ such that $\nu(e)>0$ for all $e\in\mathcal{E}_{n}$ and
$\epsilon_{k}=sgn(\Sigma_{k}(\j_{k})-\Sigma_{k}(\i_{k}))$ with
$\mathbf{e}_{k}=(\i_{k},\j_{k})$ for $1\leq k\leq N$. Based on these
observations, an estimate of the risk of any median candidate
$\sigma\in\mathfrak{S}_{n}$ is given by:

$\widetilde{L}_{N}(\sigma)=\sum_{i<j}\frac{1}{N_{i,j}}\sum_{k=1}^{N}\mathbb{I}\\{\mathbf{e}_{k}=(i,j),\;\epsilon_{k}(\sigma(j)-\sigma(i))<0\\},$
(22)

where $N_{i,j}=\sum_{k=1}^{N}\mathbb{I}\\{\mathbf{e}_{k}=(i,j)\\}$.

##  Appendix D Additional experiments

Here we display additional numerical results, completing those presented in
the main text. First, in Section LABEL:ssec:synthetic, we analyze the
sensitivity of the proposed depth notion to a difference between distributions
and its subsequent ability to provide formal inference. Second, in Section
LABEL:ssec:sushi, we detail a further application to real data. Please note,
that, as this is the case in the main text, in all visualizations the data
depth is re-scaled to $[0,1]$ interval by division by maximal possible
distance for given $n$.

###  D.1 Trimming strategy

Now we have characterized under which conditions the different properties of
Property LABEL:property:property_depth_rankings hold, we explore how to use
them in practice. For example, using Kendall $\tau$ distance and samples drawn
from a Mallows distribution easily make the invariance and maximality at the
center properties hold, but not necessarily the monotonicity property.

First, even though a Mallows model is SST, its empirical distribution
counterpart may not be. Second, the adjacent condition for local monotonicity
indicates that under such a model,the monotonicity property hold for the
median and any of its adjacent ranking. Moreover, the second local condition
is more likely to be satisfied for rankings close to (in terms of Kendall
$\tau$ distance) the median.

These two observations and the fact that the depth of a ranking $\sigma$
represents its centrality within the dataset make a trimming strategy highly
relevant for consensus ranking experiments. The intuition behind this strategy
is that least deep points corresponds to outliers for the dataset: removing
them step by step should make the dataset less noisy, so that the depth of the
remaining points get more and more accurate. To the extreme, when successively
trimming rankings in the dataset until there is only one ranking left should
leave us with an accurate median for the dataset. However, since the depth
function satisfies useful properties when the underlying distribution is SST,
a sufficient trimming strategy would stop there. The algorithm corresponding
to this strategy is defined in Algorithm 1 of the main paper, recalled here.
See 1

(a) | (b)
---|---
|
Figure 8: Trimming strategy: evolution of candidate median (deepest ranking)
normalized distance to real median and number of cycles through trimming (a);
evolution of median depth and sample dispersion through trimming (b).

Fig. 8 illustrates the trimming strategy for a Mallows model generated with
$n=8$ items, $\phi_{0}=0.985$, and $N=1000$ samples. We can see that trimming
indeed remove cycles from the empirical dataset and thus make the empirical
distribution SST, and that during trimming, the deepest rankings (saved as the
candidate medians) get closer (in Kendall $\tau$ distance) to the real median
used for generating the samples.

The depth function thus provide an alternative and relevant way to compute the
median of a dataset: by trimming until getting a SST distribution first, we
ensure that the depth function has desirable properties and thus that the
median we obtain in practice gets very close to the true median.

###  D.2 Visual analysis

With data depth being a nonparametric tool not exploiting a priori information
about the distribution, we focus on easy-to-manipulate Mallows model using
Kendall $\tau$ distance; we refer to the main text for the formal definition
and parameters’ notation, see Example 1.

$d_{\tau}(\sigma_{1}^{*},\sigma_{2}^{*})=0$ |  $d_{\tau}(\sigma_{1}^{*},\sigma_{2}^{*})=1$ |  $d_{\tau}(\sigma_{1}^{*},\sigma_{2}^{*})=3$ |  $d_{\tau}(\sigma_{1}^{*},\sigma_{2}^{*})=5$ |  $d_{\tau}(\sigma_{1}^{*},\sigma_{2}^{*})=7$
---|---|---|---|---
|  |  |  |
$d_{\tau}(\sigma_{1}^{*},\sigma_{2}^{*})=9$ |  $d_{\tau}(\sigma_{1}^{*},\sigma_{2}^{*})=11$ |  $d_{\tau}(\sigma_{1}^{*},\sigma_{2}^{*})=13$ |  $d_{\tau}(\sigma_{1}^{*},\sigma_{2}^{*})=15$ |  $d_{\tau}(\sigma_{1}^{*},\sigma_{2}^{*})=17$
|  |  |  |
Figure 9: $DD$-plots for pairs of distributions stemming from different
instances of the _location-shift model_. The two distributions contain $50$
observations each, drawn from two Mallows models using Kendall $\tau$ distance
with parameter $\phi_{1}=\phi_{2}=\mathbf{e}^{-1}$. Difference between
locations is indicated in each individual plot. Figure 10: $p$-values
(averaged over $100$ random repetitions) for the test of homogeneity for a
pair of Mallows distributions stemming from the _location-shift model_ with
location difference
$d_{\tau}(\sigma^{*}_{1},\sigma^{*}_{2})\in\\{0,...,17\\}$.

First, we consider a _location-shift model_ : a sequence of pairs of
distributions with parameter pairs $(\sigma^{*}_{1},\phi_{1})$ and
$(\sigma^{*}_{2},\phi_{2})$. Setting $\phi_{1}=\phi_{2}=\mathbf{e}^{-1}$, we
vary $\sigma^{*}_{2}$ so that
$d_{\tau}(\sigma^{*}_{1},\sigma^{*}_{2})\in\\{0,1,3,5,7,9,11,15,17\\}$. Figure
9, which contains visualization for each pair of parameters for $50$
observations from each distribution, illustrates gradual capturing by the
suggested visualization of the increasing location shift between the two laws.

Bearing in mind the same idea, using the same distributional settings, we now
provide a formal statistical inference by _homogeneity testing_. More
precisely, for each pair of distributions, taking one of them for a reference,
we perform the testing procedure $100$ times and indicate average $p$-values
in Figure 10 (where we stick to the same test setting as in the main text,
drawing $500$ observations for the reference distribution and using the
Wilcoxon rank-sum statistic). As expected, when there is no parameter
difference, the null hypothesis of the distribution’s equality cannot be
surely rejected. When the difference in the location increases, it is captured
very quickly by the testing procedure rejecting on the level $\leq 0.05$ when
$d_{\tau}(\sigma^{*}_{1},\sigma^{*}_{2})=3$ only, and with even higher
reliability for larger differences.

$\log\phi_{1}-\log\phi_{2}=0$ | $\log\phi_{1}-\log\phi_{2}=0.1$ | $\log\phi_{1}-\log\phi_{2}=0.2$ | $\log\phi_{1}-\log\phi_{2}=0.3$ | $\log\phi_{1}-\log\phi_{2}=0.4$
---|---|---|---|---
|  |  |  |
$\log\phi_{1}-\log\phi_{2}=0.5$ | $\log\phi_{1}-\log\phi_{2}=0.6$ | $\log\phi_{1}-\log\phi_{2}=0.7$ | $\log\phi_{1}-\log\phi_{2}=0.8$ | $\log\phi_{1}-\log\phi_{2}=0.9$
|  |  |  |
Figure 11: $DD$-plots for pairs of distributions stemming from different
instances of the _scale-difference model_. The two distributions contain $50$
observations each, drawn from two Mallows models (using Kendall $\tau$
distance) with the same center and with parameters $\phi_{1}=\mathbf{e}^{-1}$
and $\phi_{2}=\mathbf{e}^{\psi}$ where
$\psi\in\\{-1,-1.1,-1.2,-1.3,-1.4,-1.5,-1.6,-1.7,-1.8,-1.9\\}$. Difference
between scales’ logarithms is indicated in each individual plot. Figure 12:
$p$-values (averaged over $100$ random repetitions) for the test of
homogeneity for a pair of Mallows distributions stemming from the _scale-
difference model_ , i.e. with the same center and difference in scales
$\log\phi_{1}-\log\phi_{2}\in\\{0,...,1\\}$.

While being already challenging when having no (parametric) assumptions on the
distribution, traditional rank-based homogeneity testing procedures usually
assume location difference. Thus, we consider an even more disadvantageous
setting, the _scale-difference model_ : the location of the both distributions
is the same, and those differ in dispersion only. As above, the $DD$-plots for
$10$ scale difference values (on the equidistant grid with step $0.1$ on the
logarithmic scale) are presented in Figure 11. With increasing scale
difference, visual patterns dis-associate (less than in the previous setting
though) which intrigues the formal inference.

Finally, we repeat the previously used testing procedure and indicate the
average $p$-values in Figure 12. One observes that for difference in scale
(measured on the logarithmic scale) equal to $0.3$ or higher, the homogeneity
testing procedure distinguishes the distributions with level $\leq 0.05$ or
less.

###  D.3 Application to real data

Let us now explore the applicability of our depth function to different tasks
on real data.

####  D.3.1 Student dataset

Next, we consider a real data set which consists of students’ rankings before
($N_{1}=169$ students) and after ($N_{2}=179$ students) the class, with known
ground truth (correct answer = $(0,1,2,3)$) where $n=4$ (refer to
https://github.com/ekhiru/students-dataset for details about the dataset).
Simple computation indicates that $d_{\tau}$ from the average ranking to the
true one is $2$ before the class and $1$ after, thus suggesting that the
students improved after studying. We employ the same homogeneity testing
methodology as above to derive formal statistical inference. By taking $100$
randomly chosen observations from the ’before class’ cohort as the reference,
we use $69$ observations from the ’before class’ cohort and $79$ (also
randomly chosen) from the ’after class’ group. The diagnostic $DD$-plot of the
two cohorts together with $p$-values over $1000$ random repetitions and the
asymptotic density under $H_{0}$ are indicated in Figure 13, and illustrate
improvement of the students’ knowledge after the class.

|
---|---
Figure 13: Left: $DD$-plot for the two cohorts of students, ’before class’
(red) and ’after class’ (blue), respectively. Right: $p$-values of the
homogeneity test over $1000$ random repetitions together with asymptotic
density under $H_{0}$.

####  D.3.2 Sushi dataset

Figure 14: Exploratory statistics of the Sushi data set by [35]
(https://www.kamishima.net/sushi/). Left: The depth of each observation in the
set, in increasing depth order. Right: The comparative $DD$-plot for Eastern
(red) and Western (blue) Japan.

As a last application, we analyze the _Sushi_ data set, which contains
$5\,000$ rankings of $10$ sushi items. We refer the reader to [35]
(https://www.kamishima.net/sushi/) for the detailed description of the data
set. By means of the introduced depth notion, we explore this data set from
two angles. First, we provide depth based ranking of the entire data set,
which can be seen as the ranking equivalent of the cumulative distribution
function. The depth of each of the $5\,000$ observations (ordered
increasingly) is indicated in Figure 14 (left). Second, in view of the ten
considered items, we check the know difference between food preferences in
Eastern and Western Japan. The $DD$-plot of these two groups (containing
$3\,448$ and $1\,552$ observations each, respectively) is presented in Figure
14 (right). Since the two clouds of points substantially intersect, this
rather drives to conclusion that the mentioned above difference is not
connected with the choice of the sushi items used in the data set.

####  D.3.3 Mechanical Turk Dots dataset

The Mechanical Turk Dots dataset contains 800 full rankings of 4 items. Each
item corresponds to random dots presented to a user on Mechanical Turk, who is
asked to rank them from those containing the least dots (first) to those
containing the most dots (last). Thus, there is a ground truth ranking for
this dataset. 40 sets of puzzles were placed on Mechanical Turk and were
ranked by 20 users, leading to 800 rankings.

This dataset is SST and the deepest ranking corresponds to the ground truth.
We thus contaminate the dataset by swapping a random proportion of 1/4 of the
rankings, i.e. by taking the opposite ranking. Figure 15 (a) shows that there
is no obvious difference between the swapped and clean rankings, but in figure
15 (b), we see we recovered the ground truth ranking after the trimming
strategy.

(a) | (b)
---|---
|
Figure 15: Depth plots before trimming with swapped (red) and clean (blue)
points; evolution of candidate median (deepest ranking) distance to real
median and number of cycles through trimming (c)

####  D.3.4 Netflix Prize dataset

We selected one of the Netflix Prize dataset contains 1814 full rankings of 4
movies (Dirty Dancing, Maid in Manhattan, Shrek and Father of the Bride). This
dataset is SST and the deepest ranking corresponds to Shrek $\succ$ Father of
the Bride $\succ$ Maid in Manhattan $\succ$ Dirty Dancing, considered as the
real center of the dataset. We contaminated the dataset by swapping a random
proportion of 11% of the rankings, i.e. by taking the opposite ranking. Figure
16 (a) shows that there is no obvious difference between the swapped and clean
rankings, but in figure 16 (b), we the median computed after trimming is
closer to the real center than before.

(a) | (b)
---|---
|
Figure 16: Depth plots before trimming with swapped (red) and clean (blue)
points; evolution of candidate median (deepest ranking) distance to real
median and number of cycles through trimming (c)