Statistical Inference for Incomplete Ranking Data:
The Case of Rank-Dependent Coarsening

Mohsen Ahmadi Fahandar 1 Eyke Hüllermeier 1 Inés Couso 2

arXiv:1712.01158v1 [stat.ML] 4 Dec 2017

Abstract
We consider the problem of statistical inference
for ranking data, specifically rank aggregation, under the assumption that samples are incomplete in
the sense of not comprising all choice alternatives.
In contrast to most existing methods, we explicitly
model the process of turning a full ranking into
an incomplete one, which we call the coarsening
process. To this end, we propose the concept of
rank-dependent coarsening, which assumes that
incomplete rankings are produced by projecting
a full ranking to a random subset of ranks. For a
concrete instantiation of our model, in which full
rankings are drawn from a Plackett-Luce distribution and observations take the form of pairwise
preferences, we study the performance of various
rank aggregation methods. In addition to predictive accuracy in the finite sample setting, we
address the theoretical question of consistency, by
which we mean the ability to recover a target ranking when the sample size goes to infinity, despite
a potential bias in the observations caused by the
(unknown) coarsening.

1. Introduction
The analysis of rank data has a long tradition in statistics,
and corresponding methods have been used in various fields
of application, such as psychology and the social sciences
(Marden, 1995). More recently, applications in information
retrieval and machine learning have caused a renewed interest in the analysis of rankings and topics such as “learningto-rank” (Liu, 2011) and preference learning (Fürnkranz &
Hüllermeier, 2011).
In most applications, the rankings observed are incomplete
or partial in the sense of including only a subset of the
underlying choice alternatives (subsequently referred to as
1
Paderborn University, Germany 2 University of Oviedo, Spain.
Correspondence to: Eyke Hüllermeier <eyke@upb.de>.

Proceedings of the 34 th International Conference on Machine
Learning, Sydney, Australia, PMLR 70, 2017. Copyright 2017 by
the author(s).

“items”), whereas no preferences are revealed about the remaining ones—pairwise comparisons can be seen as an
important special case. Somewhat surprisingly, most methods for learning from ranking data, including methods for
rank aggregation, simply ignore the process of turning a full
ranking into an incomplete one. Or, they implicitly assume
that the process is unimportant from a statistical point of
view, because the subset of items observed is independent
of the underlying ranking.
Obviously, this assumption is often not valid, as shown by
practically relevant examples such as top-k observations.
Motivated by examples of this kind, we propose the concept
of rank-dependent coarsening, which assumes that incomplete rankings are produced by projecting a full ranking to
a random subset of ranks. The notion of “coarsening” is
meant to indicate that an incomplete ranking can be associated with a set of complete rankings, namely the set of its
consistent extensions—set-valued data of that kind is also
called “coarse data” in statistics (Heitjan & Rubin, 1991;
Gill et al., 1997). The idea of coarsening is similar to the interpretation of partial rankings as “censored data” (Lebanon
& Mao, 2008). The assumption of rank-dependent coarsening can be seen as orthogonal to standard marginalization,
which acts on items instead of ranks (Rajkumar & Agarwal,
2014; Sibony et al., 2015).
In addition to introducing a general statistical framework for
analyzing incomplete ranking data (Section 3), we outline
several problems and learning tasks to be addressed in this
framework. Learning of the entire model will normally not
be feasible, even under restrictive assumptions on the coarsening. A specifically interesting question, therefore, is to
what extent and in what sense successful learning is possible for methods that are agnostic of the coarsening process.
We investigate this question, both practically (Section 6)
and theoretically (Section 7), for several ranking methods
(Section 5) and a concrete instantiation of our framework, in
which full rankings are drawn from a Plackett-Luce distribution and observations take the form of pairwise preferences
(Section 4). In particular, we are interested in the property
of consistency, by which we mean the ability to recover a
target ranking when the sample size goes to infinity, despite
a potential bias in the observations caused by the coarsening.

Statistical Inference for Incomplete Ranking Data

2. Preliminaries and Notation
Let SK denote the collection of rankings (permutations)
over a set U = {a1 , . . . , aK } of K items ak , k ∈ [K] =
{1, . . . , K}. We denote by π : [K] −→ [K] a complete
ranking (a generic element of SK ), where π(k) denotes the
position of the k th item ak in the ranking, and by π −1 the
ordering associated with a ranking, i.e., π −1 (j) is the index
of the item on position j. We write rankings in brackets and
orderings in parentheses; for example, π = [2, 4, 3, 1, 5] and
π −1 = (4, 1, 3, 2, 5) both denote the ranking a4  a1 
a3  a2  a5 .
For a possibly incomplete ranking, which includes only
some of the items, we use the symbol τ (instead of π). If
the k th item does not occur in a ranking, then τ (k) = 0 by
definition; otherwise, τ (k) is the rank of the k th item. In
the corresponding ordering, the missing items do simply not
occur. For example, the ranking a4  a1  a2 would be
encoded as τ = [2, 3, 0, 1] and τ −1 = (4, 1, 2), respectively.
We let I(τ ) = {k : τ (k) > 0} ⊂ [K] and denote the set of
all rankings (complete or incomplete) by SK .
An incomplete ranking τ can be associated with its set of
linear extensions E(τ ) ⊂ SK , where π ∈ E(τ ) if π is
consistent with the order of items in I(τ ), i.e., (τ (i) −
τ (j))(π(i) − π(j)) ≥ 0 for all i, j ∈ I(τ ). An important
special case is an incomplete ranking τ = τi,j = (i, j) in
the form of a pairwise comparison ai  aj (i.e., τ (i) = 1,
τ (j) = 2, τ (k) = 0 otherwise), which is associated with
the set of extensions
E(τ ) = E(ai  aj ) = {π ∈ SK : π(i) < π(j)} .
Modeling an incomplete observation τ by the set of linear
extensions E(τ ) reflects the idea that τ has been produced
from an underlying complete ranking π by some “coarsening” or “imprecisiation” process, which essentially consists
of omitting some of the items from the ranking. E(τ ) then
corresponds to the set of all consistent extension π if nothing is known about the coarsening, except that it does not
change the relative order of any items.

3. General Setting and Problems
The type of data we assume as observations is incomplete
rankings τ ∈ SK . Statistical inference for this type of
data requires a probabilistic model of the underlying data
generating process, that is, a probability distribution on SK .
3.1. A Stochastic Model for Incomplete Rankings
Recalling our idea of a coarsening process, it is natural to
consider the data generating process as a two step procedure,
in which a full ranking π is generated first and turned into an
incomplete ranking τ afterward. We model this assumption
in terms of a distribution on SK × SK , which assigns a

degree of probability to each pair (τ, π). More specifically,
we assume a parameterized distribution of the following
form:
pθ,λ (τ, π) = pθ (π) · pλ (τ | π)
(1)
Thus, while the generation of full rankings is determined by
the distribution
pθ : SK −→ [0, 1] ,

(2)

the coarsening process is specified by a family of conditional
probability distributions

pλ (· | π) : π ∈ SK , λ ∈ Λ ,
(3)
where λ collects all parameters of these distributions;
pθ,λ (τ, π) is the probability of producing the data (τ, π) ∈
SK × SK . Note, however, that π is actually not observed.
3.1.1. R ANK -D EPENDENT C OARSENING
In its most general form, the coarsening process (3) is extremely rich, even if being restricted by the consistency
assumption pλ (τ | π) = 0 for π 6∈ E(τ ). In fact, since the
number of probabilities to be specified is of the order 2K K!,
inference about λ will generally be difficult. Therefore,
pλ certainly needs to be restricted by further assumptions.
Apart from practical reasons, such assumptions are also
indispensable for successful learning. Otherwise, observations could be arbitrarily biased in favor or disfavor of
items, so that an estimation of the underlying (full) preferences, as reflected by pθ , becomes completely impossible.
For example, the coarsening process may leave a ranking
π unchanged whenever item a1 is on the last position, and
remove a1 from π otherwise. Obviously, this item will then
appear to have a very low preference.
As shown by this example, the estimation of preferences will
generally be impossible unless the coarsening is somehow
more “neutral”. The assumption we make here is a property
we call rank-dependent coarsening. A coarsening procedure
is rank-dependent if the incompletion is only acting on
ranks (positions) but not on items. That is, the procedure
randomly selects a subset of ranks and removes the items
on these ranks, independently of the items themselves. In
other words, an incomplete observation τ is obtained by
projecting a complete ranking π on a random subset of
positions A ∈ 2[K] , i.e., the family (3) of distributions
pλ (· | π) is specified by a single measure on 2[K] . Or, stated
more formally,


p π −1 (A) | π −1 = p σ −1 (A) | σ −1
for all π, σ ∈ SK and A ⊂ [K], where π −1 (A) denotes the
projection of the ordering π −1 to the positions in A.
The assumption of rank-dependent coarsening can be seen
as orthogonal to standard marginalization: while the latter projects a full ranking to a subset of items, the former

Statistical Inference for Incomplete Ranking Data

projects a ranking to a subset of positions. The practically
relevant case of top-k observations is a special (degenerate)
case of rank-dependent coarsening, in which

1 if A = {1, . . . , k}
p(A) =
0 otherwise
This model could be weakened in various ways. For example, instead of fixing the length of observed rankings to
a constant, k could be a random variable. Or, one could
assume that positions are discarded with increasing probability, though independently of each other; thus, the probability
to observe a subset of items on ranks A ⊆ {1, . . . , K} is
given by
Y
Y
P (A) =
λi ·
(1 − λj ) .
i∈A

j6∈A

The coarsening is then defined by the K parameters λ1 >
λ2 > . . . > λK .
3.2. Learning Tasks
Suppose a sample of (training) data D = {τ1 , . . . , τN } to
be given. As for statistical inference about the process (1),
several problems could be tackled.
• The most obvious problem is to estimate the complete
distribution on SK , i.e., the parameters θ and λ. As
already explained before, this will require specific assumptions about the coarsening.
• A somewhat weaker goal is to estimate the “precise
part”, i.e., the parameter θ. Indeed, in many cases, θ
will be the relevant part of the model, as it specifies the
preferences on items, whereas the coarsening is rather
considered as a complication of the estimation. In this
case, λ is of interest only in so far as it helps to estimate
θ. Ideally, it would even be possible to estimate θ
without any inference about λ, i.e., by simply ignoring
the coarsening process.
• An even weaker goal is to estimate, not the parameter θ
itself, but only an underlying “ground truth” ranking π ∗
associated with θ. Indeed, in the context of learning to
rank, the ultimate goal is typically to predict a ranking,
not necessarily a complete distribution. For example,
the ranking π ∗ could be the mode of the distribution
pθ , or any other sort of representative statistics. This
problem is especially relevant in practical applications
such as rank aggregation, in which π ∗ would play the
role of a consensus ranking.
Here, we are mainly interested in the third problem, i.e.,
the estimation of a ground-truth ranking π ∗ . Moreover, due
to reasons of efficiency, we are aiming for an estimation
technique that circumvents direct inference about λ, while

being robust in the sense of producing reasonably good
results for a wide range of coarsening procedures.

4. Specific Setting and Problems
The development and analysis of methods is only possible
for concrete instantiations of the setting introduced in the
previous section. An instantiation of that kind will be proposed in this section. The first part of our data generating
process, pθ , will be modeled by the Plackett-Luce model
(Plackett, 1975; Luce, 1959). To make the second part, pλ ,
manageable, we restrict observations to the practically relevant case of pairwise comparisons (i.e., incomplete rankings
of length 2).
4.1. The Plackett-Luce Model
The Plackett-Luce (PL) model is parameterized by a vector
θ = (θ1 , θ2 , . . . , θK ) ∈ Θ = RK
+ . Each θi can be interpreted as the weight or “strength” of the option ai . The
probability assigned by the PL model to a ranking represented by a permutation π ∈ SK is given by
plθ (π) =

K
Y

θπ−1 (i)
θ −1 + θπ−1 (i+1) + . . . + θπ−1 (K)
i=1 π (i)

(4)

Obviously, the PL model is invariant toward multiplication
of θ with a constant c > 0, i.e., plθ (π) = plcθ (π) for all
π ∈ SK and c > 0. Consequently, θ can be normalized
without loss of generality (and the number of degrees of
freedom is only K − 1 instead of K). Note that the most
probable ranking, i.e., the mode of the PL distribution, is
simply obtained by sorting the items in decreasing order of
their weight:
π ∗ = arg max plθ (π) = arg sort{θ1 , . . . , θK } .
π∈SK

(5)

k∈[K]

As a convenient property of PL, let us mention that it allows
for an easy computation of marginals, because the marginal
probability on a subset U 0 = {ai1 , . . . , aiJ } ⊂ U of J ≤ K
items is again a PL model parametrized by (θi1 , . . . , θiJ ).
Thus, for every τ ∈ SK with I(τ ) = U 0 ,
plθ (τ ) =

J
Y

θτ −1 (j)
θ −1 + θτ −1 (j+1) + . . . + θτ −1 (J)
j=1 τ (j)

In particular, this yields pairwise probabilities
pi,j = plθ (τi,j ) =

θi
,
θi + θj

(6)

where τi,j = (i, j) represents the preference ai  aj . This
is the well-known Bradley-Terry-Luce model (Bradley &
Terry, 1952), a model for the pairwise comparison of alternatives. Obviously, the larger θi in comparison to θj , the

Statistical Inference for Incomplete Ranking Data

higher the probability that ai is chosen. The PL model can
be seen as an extension of this principle to more than two
items: the larger the parameter θi in (4) in comparison to
the parameters θj , j 6= i, the higher the probability that ai
appears on a top rank.
4.2. Pairwise Preferences
If rank-dependent coarsening is restricted to the generation of pairwise comparisons, the entire distribution pλ is
specified by the set of K(K − 1)/2 probabilities
n
X
λi,j | 1 ≤ i < j ≤ K, λi,j ≥ 0,

o
λi,j = 1 ,

(7)

i, j

1, 2

1, 3

2, 3

2, 1

3, 1

3, 2

pi,j

840
1140
665
1140
665
931

1064
1140
133
1140
133
175

950
1140
19
1140
19
34

300
1140
266
1140
266
931

76
1140
42
1140
42
175

190
1140
15
1140
15
34

qi,j
0
qi,j

While the pi,j are completely coherent with a PL model
0
(namely plθ with θ = (14, 5, 1)), the qi,j and qi,j
no longer
are.
A special case where coarsening is guaranteed to not introduce any bias is the uniform distribution λ ≡ 2/(K 2 − K).
In this case, random projection to ranks effectively coincides
with random selection to items.

1≤i<j≤K

4.4. Problems
where λi,j denotes the probability that the ranks i and j are
selected.
The problem of ranking based on pairwise comparisons
has been studied quite extensively in the literature, albeit
without taking coarsening into account, i.e., without asking
where the pairwise comparisons are coming from (or implicitly assuming they are generated as marginals). Yet, worth
mentioning is a recent study on rank breaking (Soufiani
et al., 2014), that is, of the estimation bias (for models such
as PL) caused by replacing full rankings in the training data
by the set of all pairwise comparisons—our study of the
bias caused by coarsening is very much in the same spirit.
4.3. The Data Generating Process
Combining the PL model (4) with the coarsening process
(7), we obtain a distribution q on SK such that
q(τi,j ) = qi,j =

X

plθ (π) λπ(i),π(j)

(8)

π∈E(ai aj )

for pairwise preferences τi,j = (i, j), and q(τ ) = 0 otherwise. Clearly, the pairwise probabilities (8) will normally
not agree with the pairwise marginals (6). Instead, they may
provide a biased view of the pairwise preferences between
items. Please note, however, that the marginals pi,j are not
directly comparable with the qi,j , because
the latter is a disP
tribution on incomplete rankings ( i,j qi,j = 1) whereas
the former is a set of marginal distributions (pi,j + pj,i = 1).
0
Instead, pi,j should be compared to qi,j
= qi,j /(qi,j + qj,i ),
which is the probability that, in the coarsened model, ai is
observed as a winner, given it is paired with aj .
As an illustration, consider a concrete example with K =
3, θ = (14, 5, 1), and degenerate coarsening distribution
specified by λ1,2 = 1 (top-2 selection). One easily derives
the probabilities of pairwise marginals (6) and coarsened
(top-2) observations (8) as follows:

Of course, in spite of the inconsistency of the pairwise
observations in the above example, a PL model could still
be estimated, for example using the maximum likelihood
principle. The corresponding estimate θ̂ will also yield an
estimate π̂ of the target ranking π ∗ (which is simply obtained
by sorting the items ai in decreasing order of the estimated
scores θi ). As already said, there is little hope that θ̂ could
be an unbiased estimate of θ; instead θ̂ will necessarily be
biased. There is hope, however, to recover the target ranking
π ∗ . Indeed, the ranking will be predicted correctly provided
θ̂ is comonotonic with θ, i.e., (θ̂i − θ̂j )(θi − θj ) > 0 for all
i, j ∈ [K]. Roughly speaking, a small bias in the estimate
can be tolerated, as long as the order of the parameters is
preserved.
Obviously, these considerations are not restricted to the
PL model. Instead, any method for aggregating pairwise
comparisons into an overall ranking can be used to predict
π ∗ . This leads us to the following questions:
• Practical performance: What is the performance of a
rank aggregation method in the finite sample setting,
i.e., how close is the prediction π̂ to the ground truth
π ∗ ? How is the performance influenced by the coarsening process?
• Consistency: Is a method consistent in the sense that π ∗
is recovered (with high probability) with an increasing
sample size N → ∞, either under specific assumptions
on the coarsening process, or perhaps even regardless
of the coarsening (i.e., only assuming the property of
rank-dependence)?

5. Rank Aggregation Methods
In this section, we discuss different rank aggregation methods that operate on pairwise data, categorized according to
the some basic principles. To this end, let us define the comparison matrix C with entries ci,j , where ci,j denotes the

Statistical Inference for Incomplete Ranking Data

number of wins of ai over aj , i.e., the number of times the
preference ai  aj is observed. Correspondingly, we define
ci,j
the probability matrix P̂ with entries p̂i,j = ci,j +c
, which
j,i
can be seen as estimates of the winning probabilities pi,j
(often also interpreted as weighted preferences). All rank
aggregation methods produce rankings π̂ based on either
matrix C or P̂ .
5.1. Statistical Estimation
5.1.1. B RADLEY-T ERRY-L UCE M ODEL (BTL)
The Bradley-Terry-Luce model is well-known in the literature on discrete choice (Bradley & Terry, 1952). It starts
from the parametric model (6) of pairwise comparisons, i.e.,
the marginals of the PL model, and estimates the parameters
by likelihood maximization:
Y  θi ci,j
θ̂ ∈ arg max
θi + θj
θ∈RK
1≤i6=j≤K

The predicted ranking is obtained by sorting items according
to their estimated strengths: π̂ = arg sort(θ̂).
As already explained, coarsening of rankings may cause a
bias in the number of observed pairwise preferences. In
particular, it may happen that some (pairs of) items are observed much more often than others. Therefore, in addition
to the BTL problem as formalized above, we also consider
the same problem with relative winning frequencies p̂i,j
instead of absolute frequencies ci,j ; we call this approach
BTL(R).

favor of each item:
π̂ = arg sort{s1 , . . . , sK } ,
PK
where si = i=1 p̂i,j .
5.2.2. C OPELAND (CP)
Copeland (Copeland, 1951) works in the same way as
Borda, except that scores are derived from binary instead of
weighted votes:


K
X
1
si =
I p̂i,j >
.
2
i=1
5.3. Spectral Methods
The idea of deriving a consensus ranking from the stationary
distribution of a suitably constructed Markov chain has been
thoroughly studied in the literature (Seeley, 1949; Vigna,
2009; Brin & Page, 1998). The corresponding Markov chain
with transition probabilities Q is defined by the pairwise
preferences. Then, if Q is an irreducible, aperiodic Markov
chain, the stationary distribution π̄ can be computed, and
the predicted ranking is given by π̂ = arg sort(π̄).
5.3.1. R ANK C ENTRALITY (RC)
The rank centrality algorithm (Negahban et al., 2012) is
based on the following transition probabilities:
1

if i 6= j

 K p̂i,j
Qi,j =
1 X

p̂k,i if i = j

1 − K
k6=i

5.1.2. L EAST S QUARES /H ODGE R ANK (LS)
The HodgeRank algorithm (Jiang et al., 2011) is based on
a least squares approach. First, the probability matrix P̂ is
mapped to a matrix X as follows:
 


log p̂i,j
if i 6= j and p̂j,i ∈ (0, 1),
p̂j,i
Xi,j =

0
otherwise
Then, π̂ = arg sort(θ∗ ), where
θ∗ ∈ arg min

X 

(θj − θi ) − Xi,j

2

,

5.3.2. MC2 AND MC3
Dwork et al. (2001) introduce four spectral ranking algorithms, two of which we consider for our study (namely
MC2 and MC3), translated to the setting of pairwise preferences. For MC2, the transition probabilities are given as
follows:

1

 PK
p̂j,i if i 6= j
Qi,j =
j=1 p̂i,j


0
if i = j

5.2. Voting Methods

The MC3 algorithm is based on the transition probabilities

1


if i 6= j

 deg(ai ) p̂i,j
Qi,j =
X
1


1−
p̂k,i if i = j


deg(ai )

5.2.1. B ORDA C OUNT (B ORDA )

where

θ∈RK

(i,j)∈E


and E = (i, j) | 1 ≤ i < j ≤ K, Xi,j 6= 0 .

Borda (Borda, 1781) is a scoring rule that sorts items according to the sum of weighted preferences or “votes” in

k6=i

deg(ai ) = max

X
K
i=1

I(p̂i,j > 0),

K
X
i=1


I(p̂j,i > 0) .

Statistical Inference for Incomplete Ranking Data

5.4. Graph-based Methods

5.5.2. M ETHOD BY P RICE ET AL . (P RICE )

5.4.1. F EEDBACK A RC S ET (FAS)

Price et al. (1994) propose the following parameter estimation for each i ∈ [K]:

If the ci,j are interpreted as (weighted) preferences, the
degree of inconsistency of ranking ai before aj is naturally
quantified in terms of cj,i . Starting from a formalization
in terms of a graph whose nodes correspond to the items
and whose edges are labeled with the weighted preferences,
the weighted feedback arc set problem (Saab, 2001; Fomin
et al., 2010) is to find the ranking that causes the lowest sum
of penalties:
X
π̂ = arg min
cj,i
π∈SK

(i,j): π(i)<π(j)

For the same reason as in the case of BTL, we also consider
the FAS problem with edge weights given by relative winning frequencies p̂i,j and binary preferences I(p̂i,j > 1/2)
instead of absolute frequencies ci,j ; we call the former approach FAS(R) and the latter FAS(B).
5.5. Pairwise Coupling
A common approach to multi-class classification is the allpairs decomposition, in which one binary classifier hi,j is
trained for each pair of classes ai and aj (Fürnkranz, 2002).
At prediction time, each classifier produces a prediction,
which can be interpreted as a vote, or weighted vote p̂i,j
in case of a probabilistic classifier, in favor of item ai over
aj . The problem of combining these predictions into an
overall prediction for the multi-class problem is also called
pairwise coupling (Hastie & Tibshirani, 1998).
To the best of our knowledge, pairwise coupling has not
been used for rank aggregation so far. In fact, the original
purpose of this technique is not to rank items but merely
to identify a single winner. Nevertheless, since coupling
methods are eventually based on scoring items, they can be
generalized for the purpose of ranking in a straightforward
way. Indeed, they have been used for that purpose in the
context of label ranking (Hüllermeier et al., 2008).
5.5.1. M ETHOD BY H ASTIE AND T IBSHIRANI (HT)
Hastie & Tibshirani (1998) tackle the problem in the following way: Given relative frequencies P̂ , they suggest to find
the probability vector p = (p1 , . . . , pK ) that minimizes the
(weighted) Kullback-Leibler (KL) distance


X
p̂i,j
1 − p̂i,j
`(p) =
ni,j p̂i,j log
+ (1 − p̂i,j ) log
µi,j
1 − µi,j
i<j
i
between p̂i,j and µi,j = pip+p
, where ni,j = ci,j + cj,i . To
j
this end, the problem is formulated as a fixed point problem
and solved using an iterative algorithm. Once p is obtained,
the predicted ranking is determined by π̂ = arg sort(p).

θ̂i =

1

P

1


j6=i p̂i,j

− (K − 2)

Then, the predicted ranking is given by π̂ = arg sort(θ̂).
5.5.3. M ETHOD BY T ING -FAN W U ET AL . (WU1, WU2)
Wu et al. (2004) propose two methods. The first one (WU1)
is based on the Markov chain approach with transition matrix

if i 6= j

p̂i,j /(K − 1)
X
Qi,j =
p̂i,s /(K − 1) if i = j .


s6=i

Once the stationary distribution π̄ of Q is obtained, the predicted ranking is given by π̂ = arg sort(π̄). In their second
approach (WU2), the following optimization problem is
proposed:
min 2θT Qθ ,
θ

where
Qi,j



−p̂i,j p̂j,i
X
=
p̂2s,i



if i 6= j
if i = j

.

s6=i

Once the optimization is solved, the predicted ranking is
π̂ = arg sort(θ).

6. Practical Performance
6.1. Synthetic Data
To investigate the practical performance of the methods presented in the previous section, we first conducted controlled
experiments with synthetic data, for which the ground truth
π ∗ is known. To this end, data in the form of pairwise
observations was generated according to (1) with different
distributions pθ and pλ , predictions π̂ were produced and
compared with π ∗ in terms of the Kendall distance, i.e., the
number of pairwise inversions:
h
i
X
I sign(π ∗ (i) − π ∗ (j)) 6= sign(π̂(i) − π̂(j)) .
1≤i<j≤K

For each setting, specified by parameters K, θ, λ, we are
interested in the expected performance of a method as a
function of the sample size N , which was approximated by
averaging over 500 simulation runs.
6.1.1. PL D ISTRIBUTION
In a first series of experiments, synthetic data was produced
for K ∈ {3, 4, 5, 7}, pθ the PL model with ground truth

Statistical Inference for Incomplete Ranking Data

• Comparing the results for learning from incomplete
data with the baseline, it is obvious that coarsening
comes with a loss of information and makes learning
more difficult.
• The difficulty of the learning task increases with decreasing distance |i − j| between observed ranks and is
most challenging for the case of observing neighboring
ranks (i, i + 1).
• All methods perform rather well, although FAS is visibly worse while BTL is a bit better than the others. On
the one side, this could be explained by the fact that
the BTL model is consistent with the PL model, as it
corresponds to the marginals of pθ . On the other side,
like all other methods, BTL is agnostic of the coarsening pλ ; from this point of view, the strong performance
is indeed a bit surprising. As a side remark, BTL(R)
does not improve on BTL.
• While FAS is on a par with FAS(R), FAS(B) tends
to do slightly better, especially for a larger number
of items. However, as already said, FAS performs
generally worse than the others.
In another set of experiments, we examined the averaged
performance of methods over all coarsening positions. The
results are again shown in the supplementary material. It is
noticeable that, as the number of items increases, the performance of the FAS-based approaches decreases. Moreover,
as pointed out earlier, the BTL performs moderately better
than other approaches.
6.1.2. M ALLOWS D ISTRIBUTION
In a second series of experiments, we replaced the PL distribution with another well-known distribution on rankings,
namely the Mallows distribution. Thus, data is now generated with pθ in (1) given by Mallows instead of PL. This
experiment serves as a kind of sensitivity analysis, especially for those methods that (explicitly or implicitly) rely
on the assumption of PL.
The Mallows model (Mallows, 1957) is parametrized by a
reference ranking π ∗ (which is the mode) and a dispersion

0.5
●

0.4

●

●

●

0.4

●

0.3

0.3

0.2

0.2
●

●

●

●

●

●

0.1

0.1
●

0.0

●

●

●

0.0
RC
LS
Borda
CP
MC2
MC3
BTL
BTL(R)
FAS
FAS(R)
FAS(B)
Price
WU2
HT
WU1

Due to space restrictions, the results are only shown in the
supplementary material. The following observations can be
made:

0.5

RC
LS
Borda
CP
MC2
MC3
BTL
BTL(R)
FAS
FAS(R)
FAS(B)
Price
WU2
HT
WU1

parameter θ ∈ RK
+ , and coarsening rankings by projecting
to all possible pairs of ranks (i.e., using a degenerate distribution pλ with λi,j = 1 for some 1 ≤ i < j ≤ K). As a
baseline, we also produced the performance of each method
for the case of full pairwise information about a ranking, i.e.,
adding all pairwise preferences to the data (instead of only
aπ−1 (i)  aπ−1 (j) ) that can be extracted from a ranking π.

Figure 1. Results for the sushi data in terms of normalized Kendall
distance (one boxblot per method), experiment (a) on the left and
(b) on the right.

parameter φ, i.e., θ = (π ∗ , φ):
pπ∗ ,φ (π) =


1
exp − φD(π, π ∗ ) ,
Z(φ)

where D(π, π ∗ ) is the Kendall distance and Z(φ) a normalization constant.
The results and observations for this series of experiments
are quite similar to those for the PL model. What is notable,
however, is a visible drop in performance for BTL, whereas
Copeland ranking now performs much better than all other
algorithms. Furthermore, FAS(B) is significantly better than
FAS and FAS(R). These results might be explained by the
ordinal nature of the Mallows model, which is arguably
better fit by methods based on binary comparisons than by
score-based approaches.
6.2. Real Data
To compare the methods on a real world data set, we used the
Sushi data (Kamishima, 2003) that contains the preferences
(full rankings) of 5000 people over 10 types of sushi.
For this data set, there is no obvious ground truth π ∗ . There-

Statistical Inference for Incomplete Ranking Data

fore, we define a separate target for each data set individually, which is the ranking produced by that method on the
full set of pairwise comparisons that can be extracted from
the training data. The distance between this ranking and the
one predicted for coarsened data can essentially be seen as
a measure of the loss of information caused by coarsening.
We conduct this experiment for (a) degenerate coarsening
where λi,j = 1 for some (i, j) and (b) random coarsening
where λi,j = 2/(K 2 − K) for all (i, j). Note that, while
the information content is the same in both cases (one pairwise comparison per customer), random coarsening does
not introduce any bias, as opposed to degenerate coarsening.
The results (distributions for 100 repetitions) are shown in
Figure 1. Again, all methods are more or less on a par.
However, as expected, random coarsening does indeed lead
to better estimates, again suggesting that “real” coarsening
indeed makes learning harder.

7. Consistency
Recall the (specific) setting we introduced in Section 4, in
which full rankings are generated according to a PL model
with parameter θ = (θ1 , . . . , θK ), and the coarsening corresponds to a projection to a random pair of ranks; for technical reasons, we subsequently assume θi 6= θj for i 6= j.
Also recall that we denote by pi,j the probability of a ranking π in which ai precedes aj , and by qi,j the probability to
observe the preference ai  aj after coarsening. According
to PL, we have pi,j = θi /(θi + θj ), and the ground truth
ranking π ∗ is such that
(π(i) < π(j)) ⇔ (θi > θj ) ⇔ (pi,j > 1/2)
Finally, we denote by p̂i,j the estimate of the pairwise preference (probability) pi,j . If not stated differently, we always
assume estimates to be given by relative frequencies, i.e.,
p̂i,j = wi,j /(wi,j + wj,i ), with wi,j the observed number
of preferences ai  aj .
Definition 1: Let π̂N denote the ranking produced as a
prediction by a ranking method on the basis of N observed
(pairwise) preferences. The method is consistent if p(π̂N =
π ∗ ) → 1 for N → ∞.
The proofs of the following results are given in the supplementary material.
Lemma 2: Let us consider
a probability measure pθ over
P
SK . Consider qi,j = π∈E(ai aj ) pθ (π)λπ(i),π(j) , ∀ i 6=
j. (The model (8) with pθ (π) not necessarily PL). If
pθ (π) ≥ pθ (πi,j ) for all π ∈ E(ai  aj ), then qi,j > qj,i .
Lemma 3: Assume the model (8), θi 6= θj for i 6= j,
and θi > 0 for all i ∈ [K]. The coarsening (7) is orderpreserving for PL in the sense that pi,j > 1/2 if and only if
0
0
qi,j
> 1/2, where qi,j
= qi,j /(qi,j + qj,i ).

The last result is indeed remarkable: Although coarsening
will bias the pairwise probabilities pi,j , the “binary” preferences will be preserved in the sense that sign(pi,j − 1/2) =
0
sign(qi,j
− 1/2). Indeed, the result heavily exploits properties of the PL distribution and does not hold in general. For example, consider a distribution p on S3 such
that p([1, 2, 3]) = 0.8, p([3, 1, 2]) = p([3, 2, 1]) = 0.1.
Then, with a coarsening (7) such that λ2,3 = 1, we have
0
0
p1,2 = p1,3 = 0.8, but q1,2
= q1,3
= 0.
Lemma 4: Assume the model (8), θi 6= θj for i 6= j, and
θi > 0 for all i ∈ [K]. Let us take an arbitrarily small
∗ > 0. There exists N0 ∈ N such that θi > θj if and only
if p̂i,j > 1/2 for all i, j ∈ [K], with probability at least
1 − ∗ , after having observed at least N0 preferences.
Theorem 5: Copeland ranking is consistent.
Theorem 6: FAS, FAS(R), and FAS(B) are consistent.
Our experimental results so far suggest that consistency does
not only hold for Copeland and FAS, but also for most other
methods (including BTL), and hence that rank-dependent
coarsening is indeed somehow “good-natured”. Anyway,
for these cases, the proofs are still pending.

8. Summary and Conclusion
In this paper, we addressed the problem of learning from
incomplete ranking data and advocated an explicit consideration of the process of turning a full ranking into an incomplete one—a step that we referred to as “coarsening”. To
this end, we proposed a suitable probabilistic model and introduced the property of rank-dependent coarsening, which
can be seen as orthogonal to standard marginalization: while
the latter projects a ranking to a subset of items, the former
projects to a subset of ranks.
First experimental and theoretical results suggest that agnostic learning can be successful under rank-dependent coarsening: even if ignorance of the coarsening may lead to
biased parameter estimates, the ranking task itself can still
be solved properly. This applies at least to the specific setting that we considered, namely rank aggregation based on
pairwise preferences, with Plackett-Luce (or Mallows) as
an underlying distribution.
Needless to say, this paper is only a first step. Many questions are still open, for example regarding the consistency
of ranking methods, not only for the specific setting considered here but even more so for generalizations thereof. In
addition to theoretical problems of that kind, we are also
interested in practical applications such as “crowdordering”
(Matsui et al., 2014; Chen et al., 2013), in which coarsening
could play an important role.

Statistical Inference for Incomplete Ranking Data

References
Borda, J.C. Mémoire sur les élections au scrutin. Histoire
de l’Académie Royale des Sciences, 1781.
Bradley, R.A. and Terry, M.E.˙ The rank analysis of incomplete block designs I. The method of paired comparisons.
Biometrika, 39:324–345, 1952.
Brin, S. and Page, L. The anatomy of a large-scale hypertextual web search engine. In Proceedings of the
7th International Conference on World Wide Web, pp.
107–117, Amsterdam, The Netherlands, 1998. Elsevier
Science Publishers B. V.
Chen, X. Bennett, P.N. Collins-Thompson, K. and Horvitz,
E.˙ Pairwise ranking aggregation in a crowdsourced setting. In Proceedings of the 6th ACM International Conference on Web Search and Data Mining, pp. 193–202,
Rome, Italy, 2013.
Copeland, A. H. A ’reasonable’ social welfare function. In
Seminar on Mathematics in Social Sciences, University
of Michigan, 1951.
Dwork, C., Kumar, R., Naor, M., and Sivakumar, D. Rank
aggregation methods for the web. In Proceedings of
the 10th International Conference on World Wide Web,
WWW ’01, pp. 613–622, New York, USA, 2001. ACM.

Jiang, X., Lim, L., Yao, Y., and Ye, Y. Statistical ranking and
combinatorial hodge theory. Mathematical Programming,
127(1):203–244, 2011.
Kamishima, T. Nantonac collaborative filtering: Recommendation based on order responses. In Proceedings
of the 9th ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining, KDD ’03, pp.
583–588, New York, USA, 2003. ACM.
Lebanon, G. and Mao, Y. Nonparametric modeling of partially ranked data. Journal of Machine Learning Research,
9:2401–2429, 2008.
Liu, T.Y.˙ Learning to Rank for Information Retrieval.
Springer-Verlag, 2011.
Luce, R.D. Individual Choice Behavior: A Theoretical
Analysis. John Wiley and Sons, New York, 1959.
Mallows, C. Non-null ranking models. Biometrika, 44(1):
114–130, 1957.
Marden, J.I. Analyzing and Modeling Rank Data. London,
New York, 1995.
Matsui, T. Baba, Y. Kamishima, T. and Kashima, H.˙Crowdordering. In Proceedings of the 18th Pacific-Asia Conference on Advances in Knowledge Discovery and Data
Mining, pp. 336–347, Tainan, Taiwan, 2014.

Fomin, F.V., Lokshtanov, D., Raman, V., and Saurabh, S.
Fast local search algorithm for weighted feedback arc
set in tournaments. In Proceedings of the 24th AAAI
Conference on Artificial Intelligence, AAAI’10, pp. 65–
70. AAAI Press, 2010.

Negahban, S., Oh, S., and Shah, D. Iterative ranking from
pair-wise comparisons. In Advances in Neural Information Processing Systems (NIPS’12), pp. 2474–2482,
2012.

Fürnkranz, J. Round robin classification. Journal of Machine Learning Research, 2:721–747, 2002.

Plackett, R. The analysis of permutations. Applied Statistics,
24:193–202, 1975.

Fürnkranz, J. and Hüllermeier, E. Preference Learning.
Springer-Verlag, 2011.

Price, D., Knerr, S., Personnaz, L., and Dreyfus, G. Pairwise neural network classifiers with probabilistic outputs.
In Proceedings of the 7th International Conference on
Neural Information Processing Systems (NIPS’94), pp.
1109–1116, Cambridge, MA, USA, 1994. MIT Press.

Gill, R. D., Laan, M. J., and Robins, J. M. Coarsening at random: Characterizations, conjectures, counter-examples.
In Proceedings of the 1st Seattle Symposium in Biostatistics: Survival Analysis, pp. 255–294. Springer US, New
York, 1997.
Hastie, T. and Tibshirani, R. Classification by pairwise
coupling. In Advances in Neural Information Processing
Systems (NIPS’98). The MIT Press, 1998.

Rajkumar, A. and Agarwal, S.˙A statistical convergence perspective of algorithms for rank aggregation from pairwise
data. In Proceedings of the 31th International Conference on Machine Learning, pp. 118–126, Beijing, China,
2014.

Heitjan, D.F. and Rubin, D.B. Ignorability and coarse data.
The Annals of Statistics, 19(4):2244–2253, 1991.

Saab, Y. A fast and effective algorithm for the feedback arc
set problem. Journal of Heuristics, 7(3):235–250, May
2001.

Hüllermeier, E., Fürnkranz, J., Cheng, W., and Brinker, K.
Label ranking by learning pairwise preferences. Artificial
Intelligence, 172:1897–1917, 2008.

Seeley, J. R. The net of reciprocal influence; a problem in
treating sociometric data. Canadian Journal of Psychology, 3(4):234–240, Dec 1949.

Statistical Inference for Incomplete Ranking Data

Sibony, E. Clémençon, S. and Jakubowicz, J.˙ MRA-based
statistical learning from incomplete rankings. In Proceedings of the 32th International Conference on Machine
Learning, pp. 1432–1441, Lille, France, 2015.
Soufiani, H.A. Parkes, D.C. and Xia, L.˙ Computing parametric ranking models via rank-breaking. In Proceedings
of the 31th International Conference on Machine Learning, Beijing, China, 2014.
Vigna, S. Spectral ranking. CoRR, abs/0912.0238, 2009.
Wu, T.F., Lin, C.J., and Weng, R.C. Probability estimates for
multi-class classification by pairwise coupling. Journal
of Machine Learning Research, 5:975–1005, December
2004.

