{'fraction_non_alphanumeric': 0.04296124597139092, 'fraction_numerical': 0.011478559067744138, 'mean_word_length': 4.042267050912584, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Rank Centrality: Ranking from Pair-wise Comparisons

The question of aggregating pairwise comparisons to obtain a global ranking over a collection of objects has been of interest for a very long time: be it ranking of online gamers (e.g. MSR's TrueSkill system) and chess players, aggregating social opinions, or deciding which product to sell based on transactions. In most settings, in addition to obtaining a ranking, finding `scores' for each object (e.g. player's rating) is of interest for understanding the intensity of the preferences. In this paper, we propose Rank Centrality, an iterative rank aggregation algorithm for discovering scores for objects (or items) from pairwise comparisons. The algorithm has a natural random walk interpretation over the graph of objects with an edge present between a pair of objects if they are compared; the score, which we call Rank Centrality, of an object turns out to be it's stationary probability under this random walk. To study the efficacy of the algorithm, we consider the popular Bradley-Terry-Luce (BTL) model in which each object has an associated score which determines the probabilistic outcomes of pairwise comparisons between objects. We bound the finite sample error rates between the scores assumed by the BTL model and those estimated by our algorithm. In particular, the number of samples required to learn the score well with high probability depends on the structure of the comparison graph. When the Laplacian of the comparison graph has a strictly positive spectral gap, e.g. each item is compared to a subset of randomly chosen items, this leads to an order-optimal dependence on the number of samples. Experimental evaluations on synthetic datasets generated according to the BTL model show that our algorithm performs as well as the Maximum Likelihood estimator for that model and outperforms a recently proposed algorithm by Ammar and Shah (2011).


Introduction
Rank aggregation is an important task in a wide range of learning and social contexts arising in recommendation systems, information retrieval, and sports and competitions. Given n items, we wish to infer relevancy scores or an ordering on the items based on partial orderings provided through many (possibly contradictory) samples. Frequently, the available data that is presented to us is in the form of a comparison: player A defeats player B; book A is purchased when books A and B are displayed (a bigger collection of books implies multiple pairwise comparisons); movie A is liked more compared to movie B. From such partial preferences in the form of comparisons, we frequently wish to deduce not only the order of the underlying objects, but also the scores associated with the objects themselves so as to deduce the intensity of the resulting preference order.
For example, the Microsoft TrueSkill engine assigns scores to online gamers based on the outcomes of (pairwise) games between players. Indeed, it assumes that each player has inherent "skill" and the outcomes of the games are used to learn these skill parameters which in turn lead to scores associated with each player. In most such settings, similar model-based approaches are employed.
In this paper, we have set out with the following goal: develop an algorithm for the above stated problem which (a) is computationally simple, (b) works with available (comparison) data only, and (c) when data is generated as per a reasonable model, then the algorithm should do as well as the best model aware algorithm. The main result of this paper is an affirmative answer to all these questions.
Related work. Most rating based systems rely on users to provide explicit numeric scores for their interests. While these assumptions have led to a flurry of theoretical research for item recommendations based on matrix completion (cf. Candès and Recht (2009), Keshavan et al. (2010), Negahban and Wainwright (2012)), it is widely believed that numeric scores provided by individual users are generally inconsistent. Furthermore, in a number of learning contexts as illustrated above, it is simply impractical to ask a user to provide explicit scores.
These observations have led to the need to develop methods that can aggregate such forms of ordering information into relevance ratings. In general, however, designing consistent aggregation methods can be challenging due in part to possible contradictions between individual preferences.
For example, if we consider items A, B, and C, one user might prefer A to B, while another prefers B to C, and a third user prefers C to A. Such problems have been well studied starting with (and potentially even before) Condorcet (1785). In the celebrated work by Arrow (1963), existence of a rank aggregation algorithm with reasonable sets of properties (or axioms) was shown to be impossible.
In this paper, we are interested in a more restrictive setting: we have outcomes of pairwise comparisons between pairs of items, rather than a complete ordering as considered in (Arrow 1963).
Based on those pairwise comparisons, we want to obtain a ranking of items along with a score for each item indicating the intensity of the preference. One reasonable way to think about our setting is to imagine that there is a distribution over orderings or rankings or permutations of items and every time a pair of items is compared, the outcome is generated as per this underlying distribution. With this, our question becomes even harder than the setting considered by Arrow (1963) as, in that work, effectively the entire distribution over permutations was already known! Indeed, such hurdles have not stopped the scientific community as well as practical designers from designing such systems. Chess rating systems and the more recent MSR TrueSkill Ranking system are prime examples. Our work falls precisely into this realm: design algorithms that work well in practice, makes sense in general, and perhaps more importantly, have attractive theoretical properties under common comparative judgment models.
With this philosophy in mind, in a recent work, Ammar and Shah (2011) presented an algorithm that tries to achieve the goal with which we have set out. However, their algorithm requires information about comparisons between all pairs, and for each pair it requires the exact pairwise comparison 'marginal' with respect to the underlying distribution over permutations. Indeed, in reality, not all pairs of items can typically be compared, and the number of times each pair is compared is also very small. Therefore, while an important step is taken by Ammar and Shah (2011), it stops short of achieving the desired goal. Another such work is Duchi et al. (2010), where a regret/optimization based framework is presented.
In a related work by Braverman and Mossel (2008), the authors present an algorithm that produces an ordering based on O(n log n) pair-wise comparisons on adaptively selected pairs. They assume that there is an underlying true ranking and one observes noisy comparison results. Each time a pair is queried, we are given the true ordering of the pair with probability 1/2 + γ for some γ > 0 which does not depend on the items being compared. One limitation of this model is that it does not capture the fact that in many applications, like chess matches, the outcome of a comparison very much depends on the opponents that are competing.
Such considerations have naturally led to the study of noise models induced by parametric distributions over permutations. An important and landmark model in this class is called the Bradley-Terry-Luce (BTL) model (Bradley andTerry 1955, Luce 1959), which is also known as the Multinomial Logit (MNL) model (cf. McFadden (1973)). It has been the backbone of many practical system designs including pricing in the airline industry, e.g. see Talluri and VanRyzin (2005). Adler et al. (1994) used such models to design adaptive algorithms that select the winner from small number of rounds. Interestingly enough, the (near-)optimal performance of their adaptive algorithm for winner selection is matched by our non-adaptive algorithm for assigning scores to obtain global rankings of all players.
Finally, earlier work by Dwork et al. (2001) proposed a number of Markov chain based methods for rank aggregation, which are very similar to the Rank Centrality presented here. However, the precise form of the algorithm proposed is distinctly different and this precise form does matter: the empirical results using synthetic data presented in Section 3.3 make this clear. In summary, our work provides firm theoretical grounding for Markov chain based ranking algorithms.
Our contributions. In this paper, we consider Rank Centrality, an iterative algorithm that takes the noisy comparison answers between a subset of all possible pairs of items as input and produces scores for each item as the output. The proposed algorithm has a nice intuitive explanation. Consider a graph with nodes/vertices corresponding to the items of interest (e.g. players). Construct a random walk on this graph where at each time, the random walk is likely to go from vertex i to vertex j if items i and j were ever compared; and if so, the likelihood of going from i to j depends on how often i lost to j. That is, the random walk is more likely to move to a neighbor who has more "wins". How frequently this walk visits a particular node in the long run, or equivalently the stationary distribution, is the score of the corresponding item. Thus, effectively this algorithm captures preference of the given item versus all of the others, not just immediate neighbors: the global effect induced by transitivity of comparisons is captured through the stationary distribution.
Such an interpretation of the stationary distribution of a Markov chain or a random walk has been an effective measure of relative importance of a node in wide class of graph problems, popularly known as the network Centrality (Newman 2010). Notable examples of such network centralities include the random surfer model on the web graph for the version of the PageRank (Brin and Page 1998) which computes the relative importance of a web page, and a model of a random crawler in a peer-to-peer file-sharing network to assign trust value to each peer in EigenTrust (Kamvar et al. 2003).
The computation of the stationary distribution of the Markov chain boils down to 'power iteration' using transition matrix lending to a nice iterative algorithm. To establish rigorous properties of the algorithm, we analyze its performance under the BTL model described in Section 2.1.
Formally, we establish the following result: given n items, when comparison results between randomly chosen O(n poly(log n)) pairs of them are produced as per an (unknown) underlying BTL model, the stationary distribution (or scores) produced by Rank Centrality matches the true score (induced by the BTL model). It should be noted that Ω(n log n) is a necessary number of (random) comparisons for any algorithm to even produce a consistent ranking (due to connectivity threshold of random graph). In that sense, up to poly(log n) factor, our algorithm is optimal in terms of sample complexity.
In general, the comparisons may not be available between randomly chosen pairs. Let G = ([n], E) denote the graph of comparisons between these n objects with an edge (i, j) ∈ E if and only if objects i and j are compared. In this setting, we establish that with O(ξ −2 n poly(log n)) comparisons, our algorithm learns the true score of the underlying BTL model. Here, ξ is the spectral gap for the Laplacian of G and this is how the graph structure of comparisons plays a role. Indeed, as a special case when comparisons are chosen at random, the induced graph is Erdös-Rényi for which ξ turns out to be strictly positive, leading to the (order) optimal performance of the algorithm as stated earlier.
To understand the performance of our algorithm compared to the other options, we perform an empirical experimental study. It shows that the performance of our algorithm is identical to the ML estimation of the BTL model. Furthermore, it handsomely outperforms other popular choices including the algorithm by Ammar and Shah (2011). In summary, rank Centrality (a) is computationally simple, (b) always produces a solution using available data, and (c) has near optimal performance with respect to a reasonable generative model. Some remarks about our analytic technique. Our analysis boils down to studying the induced stationary distribution of the random walk or Markov chain corresponding to the algorithm. Like most such scenarios, the only hope to obtain meaningful results for such 'random noisy' Markov chain is to relate it to stationary distribution of a known Markov chain. Through recent concentration of measure results for random matrices and comparison technique using Dirichlet forms for characterizing the spectrum of reversible/self-adjoint operators, along with the known expansion property of the random graph, we obtain the eventual result. Indeed, it is the consequence of such powerful results that lead to near-optimal analytic results for random comparison model and characterization of the algorithm's performance for general setting.
As an important comparison, we provide analysis of sample complexity required by the maximum likelihood estimator (MLE) using the state-of-art analytic techniques, cf. Negahban and Wainwright (2012). This leads to the conclusion that Ω(n 2 log n) samples are needed to learn the parameters accurately using the MLE in contrast to O(n poly(log n)) using Rank Centrality. The comparable (near optimal) empirical performance of MLE and Rank Centrality seem to suggest that the stateof-art methods for analyzing statistical performance of optimization based methods has room for improvement.
Organization. The remainder of the paper is organized as follows. In Section 2, we describe the model, problem statement and the rank Centrality algorithm. Section 3 describes the main results -the key theoretical properties of rank Centrality as well as it's empirical performance in the context of two real datasets from NASCAR and One Day International (ODI) cricket. We provide comparison of the Rank Centrality with the maximum likelihood estimator using the existing Article submitted to Operations Research; manuscript no. (Please, provide the mansucript number!) analytic techniques in the same section. We derive the Cramer-Rao lower bound on the square error for estimating parameters by any algorithm -across range of parameters, the performance of Rank Centrality and MLE matches the lower bound implied by Cramer-Rao bound as explained in Section 3 as well. Finally, Section 4 details proofs of all results. We discuss and conclude in Section 5.
Notation. In the remainder of this paper, we use C, C , etc. to denote absolute constants, and their value might change from line to line. We use A T to denote the transpose of a matrix.
The Euclidean norm of a vector is denoted by x = i x 2 i , and the operator norm of a linear operator is denoted by A 2 = max x x T Ax/x T x. When we say with high probability, we mean that the probability of a sequence of events A n goes to one as n grows: lim n→∞ P(A n ) = 1. Also define [n] = {1, 2, . . . , n} to be the set of all integers from 1 to n.

Model
In this section, we discuss a model of comparisons between various items. This model will be used to analyze the Rank Centrality algorithm.
Bradley-Terry-Luce model for comparative judgment. When comparing pairs of items from n items of interest, represented as [n] = {1, . . . , n}, the Bradley-Terry-Luce model assumes that there is a weight or score w i ∈ R + ≡ {x ∈ R : x > 0} associated with each item i ∈ [n]. The outcome of a comparison for pair of items i and j is determined only by the corresponding weights w i and w j . Let Y l ij denote the outcome of the l-th comparison of the pair i and j, such that Y l ij = 1 if j is preferred over i and 0 otherwise. Then, according to the BTL model, Furthermore, conditioned on the score vector w = {w i }, it is assumed that the random variables Y l ij 's are independent of one another for all i, j, and l. Since the BTL model is invariant under the scaling of the scores, an n-dimensional representation of the scores is not unique. Indeed, under the BTL model, a score vector is the equivalence class [w] = {w ∈ R n |w = a w, for some a > 0}. The outcome of a comparison only depends on the equivalence class of the score vector.
To get a unique representation, we represent each equivalence class by its projection onto the standard orthogonal simplex such that i w i = 1. This representation naturally defines a distance between two equivalent classes as the Euclidean distance between two projections: Our main result provides an upper bound on the (normalized) distance between the estimated score vector and the true underlying score vector.
Bradley-Terry-Luce is equal to Multi Nomial Logit (MNL). We take a brief detour to remind the reader that the BTL model is identical to the MNL model in the sense that the pair-wise distributions between objects induced under BTL are identical to that under MNL. Consider an equivalent way to describe an MNL model. Each object i has an associated score w i > 0. A random ordering over all n objects is drawn as follows: iteratively fill the ordered positions 1, . . . , n by choosing object i(k) for position k, amongst the remaining objects (not chosen in the first 1, . . . , k − 1 positions) with probability proportional to it's weight w i(k) . It can be easily verified that in the random ordering of n objects generated as per this process, i is ranked higher than j with probability w i /(w i + w j ).
Sampling model. We also assume that we perform a fixed k number of comparisons for all pairs i and j that are considered (e.g. a best of k series). This assumption is mainly to simplify notations, and the analysis as well as the algorithm easily generalizes to the case when we might have a different number of comparisons for different pairs. Given observations of pairwise comparisons among n items according to this sampling model, we define a comparisons graph G = ([n], E, A) as a graph of n items where two items are connected if we have comparisons data on that pair and A denotes the weights on each of the edges in E.

Rank Centrality
In our setting, we will assume that a ij represents the fraction of times object j has been preferred to object i, for example the fraction of times chess player j has defeated player i. Given the notation above, we have that a ij = (1/k) k l=1 Y l ij . Consider a random walk on a weighted directed graph G = ([n], E, A), where a pair (i, j) ∈ E if and only if the pair has been compared. The weight edges are defined based on the outcome of the comparisons: A ij = a ij /(a ij + a ji ) and A ji = a ji /(a ij + a ji ) (note that a ij + a ji = 1 in our setting). We let A ij = 0 if the pair has not been compared. Note that by the Strong Law of Large Numbers, as the number k → ∞ the quantity A ij converges to w j /(w i + w j ) almost surely.
A random walk can be represented by a time-independent transition matrix P , where P ij = P(X t+1 = j|X t = i). By definition, the entries of a transition matrix are non-negative and satisfy j P ij = 1. One way to define a valid transition matrix of a random walk on G is to scale all the edge weights by 1/d max , where we define d max as the maximum out-degree of a node. This rescaling Article submitted to Operations Research; manuscript no. (Please, provide the mansucript number!) ensures that each row-sum is at most one. Finally, to ensure that each row-sum is exactly one, we add a self-loop to each node. Concretely, (1) The choice to construct our random walk as above is not arbitrary. In an ideal setting with infinite samples (k → ∞) per comparison the transition matrix P would define a reversible Markov chain under the BTL model. Recall that a Markov chain is reversible if it satisfies the detailed balance equation: there exists v ∈ R n + such that v i P ij = v j P ji for all i, j; and in that case, π ∈ R n + defined as π i = v i /( j v j ) is its unique stationary distribution. In the ideal setting (say k → ∞), we will have P ij =P ij ≡ (1/d max )w j /(w i + w j ). That is, the random walk will move from state i to state j with probability proportional to the chance that item j is preferred to item i. In such a setting, it is clear that v = w satisfies the reversibility conditions. Therefore, under these ideal conditions it immediately follows that the vector w/ i w i acts as a valid stationary distribution for the Markov chain defined byP , the ideal matrix. Hence, as long as the graph G is connected and at least one node has a self loop then we are guaranteed that our graph has a unique stationary distribution proportional to w. If the Markov chain is reversible then we may apply the spectral analysis of self-adjoint operators, which is crucial in the analysis of the behavior of the method.
In our setting, the matrix P is a noisy version (due to finite sample error) of the ideal matrix P discussed above. Therefore, it naturally suggests the following algorithm as a surrogate. We estimate the probability distribution obtained by applying matrix P repeated starting from any initial condition. Precisely, let p t (i) = P(X t = i) denote the distribution of the random walk at time t with p 0 = (p 0 (i)) ∈ R n + be an arbitrary starting distribution on [n]. Then, In general, the random walk converges to a stationary distribution π = lim t→∞ p t which may depend on p 0 . When the transition matrix has a unique largest eigenvector (unique stationary distribution), starting from any initial distribution p 0 , the limiting distribution π is unique. This stationary distribution π is the top left eigenvector of P , which makes computing π a simple eigenvector computation. Formally, we state the algorithm, which assigns numerical scores to each node, which we shall call Rank Centrality:
The stationary distribution of the random walk is a fixed point of the following equation: This suggests an alternative intuitive justification: an object receives a high rank if it has been preferred to other high ranking objects or if it has been preferred to many objects.
One key question remains: does P have a well defined stationary distribution? Since the Markov chain has a finite state space, there is always a stationary distribution or solution of the above stated fixed-point equations. However, it may not be unique if the Markov chain P is not irreducible.
The irreducibility follows easily when the graph is connected and for all edges (i, j) ∈ E, a ij > 0, a ji > 0. Interestingly enough, we show that the iterative algorithm produces a meaningful solution with near optimal sample complexity as stated in Theorem 2 when the pairs of objects that are compared are chosen at random.

Main Results
The main result of this paper derives sufficient conditions under which the proposed iterative algorithm finds a solution that is close to the true solution (under the BTL model) for general model of comparison (i.e. any graph G). This result is stated as Theorem 1 below. In words, the result implies that to learn the true score correctly as per our algorithm, it is sufficient to have number of comparisons scaling as O(ξ −2 n poly(log n)) where ξ is the spectral gap of the Laplacian of the graph G. This result explicitly identifies the role played by the graph structure in the ability of the algorithm to learn the true scores.
In the special case, when the pairs of objects to be compared are chosen at random, that is the induced G is an Erdös-Rényi random graph, the ξ turns out to be constant and hence the resulting number of comparisons required scales as O(npoly(log n)). This is effectively the optimal sample complexity.
The bounds are presented as the rescaled Euclidean norm between our estimate π and the underlying stationary distributionP . This error metric provides us with a means to quantify the relative certainty in guessing if one item is preferred over another.
After presenting our main theoretical result, we describe illustrative simulation results. We also present application of the algorithm in the context of two real data-sets: results of NASCAR race for ranking drivers, and results of One Day International (ODI) Cricket for ranking teams. We shall discuss relation between Rank Centrality, the maximum likelihood estimator and the Cramer-Rao's bound to conclude that our algorithm is effectively as good as the best possible.
Article submitted to Operations Research; manuscript no. (Please, provide the mansucript number!)

Rank Centrality: Error bound for general graphs
Recall that in the general setting, each pair of objects or items are chosen for comparisons as per the comparisons graph G([n], E). For each such pair, we have k comparisons available. The result below characterizes the performance of Rank Centrality for such a general setting.
Before we state the result, we present a few necessary notations. Let d i denote the degree of node i in G; let the max-degree be denoted by d max ≡ max i d i and min-degree be denoted by and 0 otherwise. The Laplacian, defined thus, can be thought of as a transition matrix of a reversible random walk on graph G: from each node i, jump to one of its neighbors j with equal probability. Given this, it is well known that the Laplacian of the graph has real eigenvalues denoted as We shall denote the spectral gap of the Laplacian as Now we state the result establishing the performance of Rank Centrality.
Theorem 1. Given n objects and a comparison graph G = ([n], E), let each pair (i, j) ∈ E be compared for k times with outcomes produced as per a BTL model with parameters w 1 , . . . , w n . Then, there exists positive universal constants C and C such that for k ≥ 4C 2 (1 + (b 5 κ 2 /d max ξ 2 ) log n), the following bound on the normalized error holds with probability at least 1 − n −C : The constant C can be made as large as desired by increasing the constant C.

Rank Centrality: Error bound for random graphs
Now we consider the special case when the comparison graph G is an Erdös-Rényi random graph with pair (i, j) being compared with probability d/n. When d is poly-logarithmic in n, we provide a strong performance guarantee. Specifically, the result stated below suggests that with O(npoly(log n)) comparisons, Rank Centrality manages to learn the true scores with high probability.
Theorem 2. Given n objects, let the comparison graph G = ([n], E) be generated by selecting each pair (i, j) to be in E with probability d/n independently of everything else. Each such chosen pair of objects is compared k times with the outcomes of comparisons produced as per a BTL model with parameters w 1 , . . . , w n . Then, there exists positive universal constants C, C and C such that when d ≥ C log n, k ≥ C , and k d ≥ C b 5 log n, the following bound on the error rate holds with probability at least 1 − n −C : π −π π ≤ Cb 5/2 log n k d , The C can be made as large as desired by increasing the constants C and C .
Remarks. Some remarks are in order. First, Theorem 2 implies that as long as we choose d = Θ(log 2 n) and k = ω(1) the error goes to 0. For k = Θ(log n), it goes down at a rate 1/ log n as n increases. Since we are sampling each of the n 2 pairs with probability d/n and then obtaining k comparisons per pair, we obtain O(n log 3 n) comparisons in total with k = Θ(log n) and d = Θ(log 2 n). Due to classical results on Erdos-Renyi graphs, the induced graph G is connected with high probability only when total number of pairs sampled scales as Ω(n log n)-we need at least those many comparisons. Thus, our result can be sub-optimal only up to log 2 n (log n if k = log n and d = log n).
Second, the b parameter should be treated as constant. It is the dynamic range in which we are trying to resolve the uncertainty between scores. If b were scaling with n, then it would be really easy to differentiate scores of items that are at the two opposite end of the dynamic range; in which case one could focus on differentiating scores of items that have their parameter values near-by. Therefore, the interesting and challenging regime is where b is constant and not scaling.
Third, for a general graph, Theorem 1 implies that by choice of kd max = O(κ 2 ξ −2 log n), the true scores can be learnt by Rank Centrality. That is, effectively the Rank Centrality algorithm requires O(nκ 2 ξ −2 poly(log n)) comparisons to learn scores well. Ignoring κ, the graph structure plays a role through ξ −2 , the squared inverse of the spectral gap of Laplacian of G, in dictating the performance of Rank Centrality. A reversible natural random walk on G, whose transition matrix is the Laplacian, has its mixing time scaling as ξ −2 (precisely, relaxation time). In that sense, the mixing time of natural random walk on G ends up playing an important role in the ability of Rank Centrality to learn the true scores.

Experimental Results
Under the BTL model, define an error metric of an estimated ordering σ as the weighted sum of pairs (i, j) whose ordering is incorrect: where I(·) is an indicator function. This is a more natural error metric compared to the Kemeny distance, which is an unweighted version of the above sum, since D w (·) is less sensitive to errors between pairs with similar weights. Further, assuming without loss of generality that w is normalized such that i w i = 1, the next lemma connects the error in D w (·) to the bound provided in Theorem 2. Hence, the same upper bound holds for D w error. A proof of this lemma is provided in Appendix.
Lemma 1. Let σ be an ordering of n items induced by a scoring π. Then, Synthetic data. To begin with, we generate data synthetically as per a BTL model for a specific choices of scores. A representative result is depicted in Figure.  algorithms. Next, we provide a brief description of various algorithms that we shall compare with.
Regularized Rank Centrality. When there are items that have been compared only a few times, the scores to those items might be sensitive to the randomness in the outcome of the comparisons, or even worse the resulting comparisons graph might not be connected. To make the random walk irreducible and get a ranking that is more robust against comparisons noise in those edges with only a few comparisons, one can add regularization to Rank Centrality. A reasonable way to add regularization is to consider the transition probability P ij as the prediction of the event that j beats i, given data (a ij , a ji ). The Rank Centrality, in non regularized setting, uses the Haldane prior of Beta(0, 0), which gives P ij ∝ a ij /(a ij + a ji ). To add regularization, one can use different priors, for example Beta(ε, ε), which gives Maximum Likelihood Estimator (MLE). The ML estimator directly maximizes the likelihood assuming the BTL model (L. R. Ford 1957). If we reparameterize the problem so that θ i = log(w i ) then we obtain our estimates θ by solving the convex program which is pair-wise logistic regression. The MLE is known to be consistent (L. R. Ford 1957). The finite sample analysis of MLE is provided in Section 3.5.
For comparison with Regularized Rank Centrality, we provide regularized MLE or regularized Logistic Regression: Borda Count. The Borda Count method, analyzed recently by Ammar and Shah (2011) Spectral Ranking Algorithms. Rank Centrality can be classified as part of the spectral ranking algorithms, which assign scores to the items according to the leading eigenvector of a matrix that represents the data. Different choices of the matrix based on data can lead to different algorithms.
Few prominent examples are Ratio matrix in (Saaty 2003) and those in Dwork et al. (2001). In Ratio matrix algorithm, the scores are assigned as per the top eigenvector of the ratio matrix, whose (i, j)-th entry is a ij /a ji . Dwork et al. (2001) introduced four spectral ranking algorithms called MC1, MC2, MC3 and MC4. They are all based on a random walk very similar (but distinctly different) to that of Rank Centrality.
We make note of the following observations from Figure 1   shown in the figure -like Borda count and Ratio matrix, for fixed d, n, despite k increasing the error remains finite (and at times gets worse!).
Real data-sets. Next we show that Rank Centrality also improves over existing spectral ranking approaches on real datasets, which are not necessarily derived from the BTL model. in the dataset, and the resulting graph is a complete graph on these 67 nodes. We used Rank Centrality and other algorithms to aggregate this data. We use this data-set primarily to check the 'robustness' of algorithms rather than understanding their ability to identify ground truth as by design it is not available.
Now each algorithm gives different ground truth rankings for each algorithm. This ground truth is compared to a ranking we get from only a subset of the data, which is generated by sampling each edge with a given sampling rate and revealing only the data on those sampled edges. We want to measure how much each algorithm is effected by eliminating edges from the complete graph. Let σ GT be the ranking we get by applying our choice of rank aggregation algorithm to the complete dataset, and σ Sample be the ranking we get from sampled dataset. To measure the resulting error in the ranking, we use the following metric: Experimental results on a real dataset shows that Rank Centrality, Logit Regression and MC2 are less sensitive to having limited data. Dataset 3: ODI Cricket. Table 2 shows ranking of international cricket teams from the 2012 season of the One Day International (ODI) cricket match. Like NASCAR dataset, in Table 2, teams with smaller number of matches, such as Scotland and Ireland, are moved towards the middle with regularization, and New Zealand is moved towards the end. Notice that regularized or not, the ranking from Rank Centrality is different from the simple ranking from average place or winning ratio, because we give more score for winning against stronger opponents.

Information-theoretic lower bound
In previous sections, we presented the achievable error rate based on a particular low-complexity algorithm. In this section, we ask how this bound compares to the fundamental limit under BTL model.
Our result in Theorem 2 provides an upper bound on the achievable error rate between estimated scores and the true underlying scores. We provide a constructive argument to lower bound the minimax error rate over a class of BTL models. Concretely, we consider the scores coming from a simplex with bounded dynamic range defined as  Table 2 Applying ε-regularized Rank Centrality to One Day International (ODI) cricket match results from 2012. The degree of a team in the comparisons graph is the number of teams it has played against.
We constrain the scores to be on the simplex, because we represent the scores by its projection onto the standard simplex as explained in Section 2.1. Then, we can prove the following lower bound on the minimax error rate.
Theorem 3. Consider a minimax scenario where we first choose an estimator π that estimates the BTL weights from given observations and, for this particular estimator π, nature chooses the worst-case true BTL weightsπ. Then, we can show that for any estimator π that we choose, there exists a true score vectorπ with dynamic range at most b such that no algorithm can achieve an expected normalized error smaller than the following minimax lower bound: where the infimum ranges over all estimators π that are measurable functions over the observations, we observe the outcomes of k comparisons for each pair of items, and we compare each pair of items with probability d/n.
By definition the dynamic range is always at least one. When b = 1, we can trivially achieve a minimax rate of zero. Since the infimum ranges over all measurable functions, it includes a trivial estimator which always outputs (1/n)1 regardless of the observations, and this estimator achieves zero error when b = 1. In the regime where the dynamic range b is bounded away from one and bounded above by a constant, Theorem 3 establishes that the upper bound obtained in Theorem 2 is minimax-optimal up to factors logarithmic in the number of items n.

MLE: Error bounds using state-of-art method
It is well known that the maximum-likelihood estimate of a set of parameters is asymptotically normal with mean 0 and covariance equal to the inverse Fisher information of the set of parameters.
Article submitted to Operations Research; manuscript no. (Please, provide the mansucript number!) In this section we wish to show the behavior of the estimates obtained through the logistic regression based approach for estimating the parameters θ * i = log w i in a finite sample setting.

Model
Recall that the logistic regression based method reparameterizes the model so that given items i and j the probability that i defeats j is .
In order to ensure identifiability we also assume that i θ * i = 0, so that we also enforce the constraint θ i = 0. We also recall that we let b = w max /w min . Similarly, we let b := θ * max − θ * min and enforce the constraint that θ max − θ min ≤ b where b ≤ b . For simplicity we assume that b = b.
Finally, recall that we are given m i.i.d. observations. We take l ∈ {1, 2, . . . , n} and let v l to be the outcome of the l th comparison. Furthermore, if during the l th competition item i competed against item j we take x l = e i − e j where e i is the standard basis vector with entries that are all zero except for the i th entry, which equals one. Note that in this context the ordering of the competition does matter. Finally, we define the inner-product between two vectors x, y ∈ R n to be x, y = n i=1 x i y y . Therefore, under the BTL model with parameters θ * we have that v l = 1 with probability exp x l , θ * /(1 + exp x l , θ * ) 0 otherwise. Now the estimation procedure is of the form 3.5.2. Results Before proceeding we recall that θ * 2 ≤ b √ n. With that in mind we have the following theorem.
With the assumption that θ * ∞ ≤ b, we have θ * 2 ≤ b √ n.  Figure 3 Comparisons of Rank Centrality, the ML estimator, and the Cramér-Rao bound. All three lines are almost indistinguishable for all ranges of model parameters.

Cramér-Rao lower bound
The Fisher information matrix (FIM) encodes the amount of information that the observed measurements carry about the parameter of interest. The Cramér-Rao bounds we derive in this section provides a lower bound on the expected squared Euclidean norm E[ π − π 2 ] and is directly related to the (inverse of) Fisher information matrix.
Denote the log-likelihood function as The Fisher information matrix with the BTL weightsπ is defined as Let π denote our estimate of the weights. Applying the Cramé-Rao bound (Rao 1945), we get the following lower bound.
This bound depends onπ and the graph structure. Although a closed form expression is difficult to get, we can compare our numerical experiments with a numerically computed Cramér-Rao bound on the same graph and the weightsπ.
3.6.1. Numerical comparisons In Figure 3, the average normalized root mean squared error (RMSE) is shown as a function of various model parameters. We fixed the control parameters as For all ranges of model parameters k, d, and b, RMSE achieved using Rank Centrality is almost indistinguishable from that of the ML estimate and also the Cramér-Rao bound (CRB).
CRB provides a lower bound on the expected mean squared error. Although we are plotting average root mean squared error, as opposed to average mean squared error, we do not expect any estimator to achieve RMSE better than the CRB as long as there is a concentration.
The ML estimator in (7) with λ = 0 finds an estimate π = eθ that maximizes the log-likelihood, and in general ML estimate does not coincide with the minimum mean squared error estimator.
From the figure we see that it intact achieves the minimum mean squared error and matches the CRB.
What is perhaps surprising is that for all the parameters that we experimented with, the RMSE achieved by Rank Centrality is almost indistinguishable with that of ML estimate and the CRB.
Thus, coupled with the minimax lower-bounds, one cannot do better than Rank Centrality.

Proofs
We may now present proofs of Theorems 1 and 2. We first present a proof of convergence for general graphs in Theorem 1. This result follows from Lemma 2 that we state below, which shows that our algorithm enjoys convergence properties that result in useful upper bounds. The lemma is made general and uses standard techniques of spectral theory. The main difficulty arises in establishing that the Markov chain P satisfies certain properties that we will discuss subsequently. Given the proof for the general graph, Theorem 2 follows by showing that in the case of Erdös-Renyi graphs, certain spectral properties are satisfied with high probability.
The next set of proofs involve the information-theoretic lower bound stated in Theorem 3 and the proof of Theorem 4 establishing the finite sample error analysis of MLE.

Proof of Theorem 1: General graph
In this section, we characterize the error rate achieved by our ranking algorithm. Given the random Markov chain P , where the randomness comes from the outcome of the comparisons, we will show that it does not deviate too much from its expectationP , where we recall is defined as Recall from the discussion following equation (1) that the transition matrix P used in our ranking algorithm has been carefully chosen such that the corresponding expected transition matrixP has two important properties. First, the stationary distribution ofP , which we denote withπ is proportional to the weight vectors w. Furthermore, when the graph is connected and has self loops (which at least one exists), this Markov chain is irreducible and aperiodic so that the stationary distribution is unique. The next important property ofP is that it is reversible-π(i)P ij =π(j)P ji .
This observation implies that the operatorP is symmetric in an appropriate defined inner product space. The symmetry of the operatorP will be crucial in applying ideas from spectral analysis to prove our main results.
Let ∆ denote the fluctuation of the transition matrix around its mean, such that ∆ ≡ P −P . The following lemma bounds the deviation of the Markov chain after t steps in terms of two important quantities: the spectral radius of the fluctuation ∆ 2 and the spectral gap 1 − λ max (P ), where λ max (P ) ≡ max{λ 2 (P ), −λ n (P )} .
Since λ(P )'s are sorted, λ max (P ) is the second largest eigenvalue in absolute value.
Lemma 2. For any Markov chain P =P + ∆ with a reversible Markov chainP , let p t be the distribution of the Markov chain P when started with initial distribution p 0 . Then, whereπ is the stationary distribution ofP ,π min = min iπ (i),π max = max iπ (i), and ρ = λ max (P ) + ∆ 2 π max /π min .
The above result provides a general mechanism for establishing error bounds between an estimated stationary distribution π and the desired stationary distributionπ. It is worth noting that the result only requires control on the quantities ∆ 2 and 1 − ρ. We may now state two technical lemmas that provide control on the quantities ∆ 2 and 1 − ρ, respectively.
Lemma 3. For k ≥ 13 and kd max ≥ C log n with appropriately large constant C, the error matrix with probability at least 1 − n −C : constant C can be made large at the cost of possibly making C and C larger.
The next lemma provides our desired bound on 1 − ρ. Lemma 4. When ∆ 2 ≤ C log n/(kd max ) and k ≥ 4C 2 b 5 d max log n(1/d min ξ) 2 , the spectral radius Proof of Theorem 1. With the above results in hand we may now proceed with the proof of the main result of our interest. When there is a positive spectral gap such that ρ < 1, the first term in (11) vanishes as t grows. The rest of the first term is bounded and independent of t. Formally, we haveπ max /π min ≤ b , π ≥ 1/ √ n , and p 0 −π ≤ 2 , by the assumption that max i,j w i /w j ≤ b and the fact thatπ(i) = w i /( j w j ). Hence, the error between the distribution at the t th iteration p t and the true stationary distributionπ is dominated by the second term in equation (11). Substituting the bounds in Lemma 3 and Lemma 4, the dominant second term in equation (11) is bounded by In fact, we only need t = Ω(log n + log b + log(d max log n/(d 2 min kξ 2 ))) to ensure that the above bound holds up to a constant factor. This finishes the proof of Theorem 1. Notice that in order for this result to hold, we need the following two conditions: kd max ≥ C log n for Lemma 3 and k ≥ 4C 2 b 5 d max log n(1/d min ξ) 2 for Lemma 4. Since b ≥ 1, d max ≥ d min , and 0 ≥ ξ ≤ 1, the second condition always implies the first for any choice of 4C 2 ≥ C . 4.1.1. Proof of Lemma 2 Due to the reversibility ofP , we can view it as a self-adjoint operator on an appropriately defined inner product space. This observation allows us to apply the well-understood spectral analysis of self-adjoint operators. In order to establish this fact define an inner product space L 2 (π) as a space of n-dimensional vectors with Similarly, we define a π = a, a π as the 2-norm in L 2 (π). For a self-adjoint operator A in L 2 (π), we define A π,2 = max a Aa π / a π as the operator norm. These norms are related to the corresponding norms in the Euclidean space through the following inequalities.
Further, the asymmetric matrixP and the symmetric matrix S have the same set of eigenvalues.
By Perron-Frobenius theorem, the eigenvalues are at most one. Let 1 = λ 1 ≥ λ 2 ≥ . . . ≥ λ n ≥ −1 be the eigenvalues, and let u i be the left eigenvector of S corresponding to λ i . Then the ith left eigenvector ofP is v i =Π 1/2 u i . Since the first left eigenvector ofP is the stationary distribution, i.e. v 1 =π, we have u 1 (i) =π(i) 1/2 .
For the Markov chain P =P + ∆, whereP is a reversible Markov chain such thatπ TP =π, we let p T t = p T t−1 P . Then, Define S 0 = λ 1 u 1 u T 1 to be the rank-1 projection of S, and a corresponding matrixP 0 =Π −1/2 S 0Π 1/2 .

Proof of Lemma 3
Our interest is in bounding ∆ 2 . Now ∆ = P −P so that for where C ij is distributed as per B(k, p ij ) − kp ij if (i, j) ∈ E and C ij = 0 otherwise. Here B(k, p ij ) is a Binomial random variable with parameter k and p ij ≡ w j w i +w j . It should be noted that C ij + C ji = 0 and C ij are independent across all the pairs with i < j. For 1 ≤ i ≤ n Article submitted to Operations Research; manuscript no. (Please, provide the mansucript number!) Given the above dependence between diagonal and off-diagonal entries, we shall bound ∆ 2 as follows: let D be the diagonal matrix with D ii = ∆ ii for 1 ≤ i ≤ n and∆ = ∆ − D. Then, We shall establish the bound of O log n kdmax for both D 2 and ∆ 2 to establish the Lemma 3.
For a given fixed i, as per (15)- (16), kd max ∆ ii can be expressed as summation of at most kd max independent, zeromean random variables taking values in the range of at most 1. Therefore, by an application of Azuma-Hoeffding's inequality, it follows that By selection of t = C √ kd max log n for appropriately large constant, it follows from above display In summary, we have Bounding ∆ 2 when d max ≤ log n. Towards this goal, we shall make use of the following standard inequality: for any square matrix M , where M 1 = max i j |M ij | and M ∞ = M T 1 . In words, M 2 2 is bounded above by product of the maximal row-sum and column-sum of absolute values of M . Since ∆ ij and ∆ ji are identically distributed and entries along each row (and hence each column) are independent, it is sufficient to obtain a high probability bound (≥ 1 − 1/poly(n)) for maximal row-sum of absolute values of∆; exactly the same bound will apply for column-sum using a union bound.
To that end, consider the sum of the absolute values of the ith row-sum of∆ and for simplicity let us denote it by R i . Then, where recall that C ij = X ij − kp ij with X ij an independent Binomial random variable with parameters k, p ij . Therefore, for any s > 0, Next, we bound E[exp(θ|C ij |)]. To that end, observe that for any x ∈ R and θ > 0, exp(θ|x|) ≤ exp(θx) + exp(−θx).
From this, it follows that Now for any φ ∈ R, using the fact that X ij is Binomial distribution and 1 + x ≤ exp(x) for any x ∈ R, we have Using second-order Taylor's expansion, for any φ ∈ [− ln 4/3, ln 4/3], we obtain that Using above display in (25), we have ave From (24) and (27), we have that for 0 ≤ θ ≤ ln 4/3, Replacing (28) in (23) and recalling the fact the degree of node d i ≤ d max , we have that for 0 ≤ θ ≤ ln 4/3, Using (29), the optimal choice of θ is θ = (3/4)s. Choosing s = 8 3kdmax c ln n + d max ln 2 , for a given c > 1, we obtain Article submitted to Operations Research; manuscript no. (Please, provide the mansucript number!) To ensure that θ = (3/4)s ≤ ln 4/3, we need 8 3kd max c ln n + d max ln 2 ≤ 4 3 ln 4 3 , which holds when kd max ≥ C log n and k ≥ 13 for some positive constant C. From above, and an application of union bound across rows and columns, it follows that with probability at least 1 − O(n −c+1 ), as long as kd max = Ω(log n) with appropriately large enough constant, we have that for an appropriate choice of constant c . Note that the above inequality reduces to the desired claim of Lemma 3 for any d max = O(log n).
Bounding ∆ 2 when d max ≥ log n. Towards this goal, we shall make use of the recent results on the concentration of sum of independent random matrices. For completeness, we recall the following result (Tropp 2011).
Lemma 5 (Theorem 6.2 (Tropp 2011)). Consider a finite sequence {Z ij } i<j of independent random self-adjoint matrices with dimensions n × n. Assume that Then, for all t ≥ 0, We wish to prove concentration results on∆ = ∆ − D = i<j Z ij where and Z ij = 0 if i and j are not connected. The Z ij 's as defined are zero-mean and independent, however, they are not self-adjoint. Nevertheless, we can symmetrize it by applying the dilation ideas presented in the paper (Tropp 2011): Now we can apply the above lemma to these self-adjoint, independent and zero-mean random matrices.
To find R andÃ ij 's that satisfy the conditions of the lemma, first consider a set of matrices if (i, j) ∈ E and zero otherwise. In the following, we show that the condition on p-th moment is satisfied with R = 1/ kd 2 max and (Ã ij ) 2 = (1/(kd 2 max ))(A ij ) 2 such that We can also show thatσ 2 ≡ i<j (Ã ij ) 2 2 = 1/(kd max ), since where I (·) is the indicator function. Therefore, we can apply the results of Lemma 5 to obtain a bound on .
Under our assumption that d max ≥ log n and choosing t = C log n/(kd max ), the tail probability is bounded by 2n exp{−(C 2 log n/2)(1/(1 + C))}. Hence, we get the desired bound that ∆ − D 2 ≤ C log n/(kd max ) with probability at least 1 − 2n −(C 2 −2C−2)/(2C+2) . Now we are left to prove that the condition (33) holds. A quick calculation shows that Furthermore, we can verify that the eigenvalues of A ij are either 1 or −1. Hence, (A ij ) p (A ij ) 2 for all p ≥ 1. Thus, given the fact thatZ ij ]|(A ij ) 2 for all p. This fact follows since for any constant c ∈ R, cA ij |c|(A ij ) 2 and c(A ij ) 2 |c|(A ij ) 2 . Hence, coupling these observation with the identities presented in equation (34) we have where we used Jensen's inequality for |E[∆ p ij ]| ≤ E[|∆ ij | p ]. Next, it remains to construct a bound on E|∆ p ij |: From (15), we have ∆ ij = P ij −P ij = 1 kdmax C ij . Therefore, Applying Azuma-Hoeffding's inequality to C ij , we have that That is, 1 kdmax C ij is a sub-Gaussian random variable. And therefore, it follows that for p ≥ 2, This proves the desired bound in (35).
In this section we prove that there is a positive gap: (d min /2 b 2 d max ) ξ. We will first prove that This implies that we have the desired eigangap for k ≥ 4C 2 b 5 d max log n (1/d min ξ) 2 such that To prove (36), we use comparison theorems (Diaconis and Saloff-Coste 1993), which bound the spectral gap of the Markov chainP of interest using a few comparison inequalities related to a more tractable Markov chain, which is the simple random walk on the graph. We define the transition matrix of the simple random walk on the graph G as and the stationary distribution of this Markov chain is µ The following key lemma is a special case of a more general result (Diaconis and Saloff-Coste 1993) proved for two arbitrary reversible Markov chains, which are not necessarily defined on the same graph. For completeness, we provide a proof of this lemma later in this section, following a technique similar to the one in (Boyd et al. 2005) used to prove a similar result for a special case when the stationary distribution is uniform.
This finishes the proof of the desired bound.

Proof of Theorem 2: Random sampling
Given the proof of Theorem 1 in the previous section, we only need to prove that for an Erdös-Renyi graph with average degree d ≥ C log n the following are true: Then, it follows that κ ≤ 3 and (1/2)d ≤ d max ≤ (3/2)d. By Theorem 1, it follows that π −π π ≤ Cb 5/2 log n k d , for some positive constant C and for kd ≥ 288C 2 b 5 log n with probability at least 1 − n −C .
Finally, we finish the proof with a lower bound on the spectral gap ξ = 1 − λ max (D −1 B). To establish this, we use celebrated results on the spectral gap of random graphs, first proved by Kahn and Szmerédie for d-regular random graphs (Friedman et al. 1989), and later extended to Erdös-Rényi graphs in (Feige and Ofek 2005). Let B be the adjacency matrix of an Erdös-Rényi random graph G(n, d/n), then it is shown in (Feige and Ofek 2005) that for d ≥ C log n, with probability at least 1 − n −C , for some numerical constants C, C , C , where C can be made as large as we want by increasing C and C . Since we are interested in the eigenvalues of L = D −1 B, we define a more tractable matrix with the same set of eigenvalues: L is a symmetric matrix, the eigenvalues are the same as the singular values up to a sign. Let σ 1 (L) ≥ σ 2 (L) ≥ . . . denote the ordered singular values ofL. Then, it is enough to show that Then, and for d ≥ C log n, this can be made as close to one as we want by increasing C . This proves the desired lower bound in (41).
We are left to prove the bound in (43) using the variational representation of σ 2 (L): where H 2 is the set of all 2-dimensional subspaces in R n and d min is the minimum degree. By concentration of measure inequalities, we know that d min ≥ (1/2)d.

Proof of Theorem 3: Information-theoretic lower bound
In this section, we prove Theorem 3 using an information-theoretic method that allows us to reduce the stochastic inference problem into a multi-way hypothesis testing problem.
This estimation problem can be reduced to the following hypothesis testing problem. Consider a set {π (1) , . . . ,π (M (δ)) } of M (δ) vectors on the standard orthogonal simplex which are separated by δ, such that π ( 1 ) −π ( 2 ) ≥ δ for all 1 = 2 . To simplify the notations, we are going to use M as a shorthand for M (δ). Suppose we choose an index L ∈ {1, . . . , M } uniformly at random. Then, we are given noisy outcomes of pairwise comparisons with w =π (L) from the BTL model. We use X to denote this set of observations. Let π be the estimation produced by an algorithm using the noisy observations. Given this, the best estimation of the "index" isL, whereL = arg min ∈[M ] π −π ( ) .
By construction of our packing set, when we make a mistake in the hypothesis testing, our estimate is at least δ/2 away from the true weightπ (L) . Precisely,L = L implies that π −π (L) ≥ δ/2. Then, where I(·; ·) denotes the mutual information between two random variables and the second inequality follows from Fano's inequality.
These random vectors form a Markov chain L -π (L) -X -π -L , where X -Y -Z indicates that X and Z are conditionally independent given Y . Let P L,X ( , x) denote the joint probability function, and P X|L (x| ), P L ( ) and P X (x) denote the conditional and marginal probability functions.
Then, by data processing inequality for a Markov chain, we get I(L;L) ≤ I(L; X) where D KL (· ·) is the Kullback-Leibler (KL) divergence and the last inequality follows from the convexity of KL divergence and Jensen's inequality.
The KL divergence between the observations coming from two different BTL models depend on how we sample the comparisons. We are sampling each pair of items for comparison with probability d/n, and we are comparing each of these sampled pairs k times. Let X ij denote the outcome of k From Lemma 7, it follows that π ( ) ≤ 2/ √ n for all . Then, scaling the bound by 1/ π ( ) , the normalized minimax rate is lower bounded by (b − 1)/(240(b + 1) √ 10kd). Also, for this choice of δ, the dynamic range is at most b. From Lemma 7, the dynamic range is upper bounded by This is monotonically increasing in δ for δ < 1/(2 √ 10n). Hence, for δ ≤ which is always true for our choice of δ, the dynamic range is upper bounded by b. This finishes the proof of the desired bound on normalized minimax error rate for general b.
i . By construction, the resulting vector is on the standard orthogonal simplex: iπ ( ) i = 1. Also, applying Hoeffding's inequality forȲ ( ) , we get that By union bound, this holds uniformly for all with probability at least 1 − 2e −63n/128 . In particular, this implies that for all i ∈ [n] and ∈ [M ].
Next, we use standard concentration results to bound the distance between two vectors: Applying Hoeffding's inequality for the first term, we get P | i (Y (1/2)α 2 δ 2 ≤ 2e −n/32 . Similarly for the second term, we can show that P | i (Y (1/4)αδ √ n ≤ 2e −n/32 . Substituting these bounds, we get 1 10 α 2 δ 2 ≤ π ( 1 ) −π ( 2 ) 2 ≤ 13 10 α 2 δ 2 , with probability at least 1 − 4e −n/32 . Applying union bound over M 2 ≤ e n/64 pairs of vectors, we get that the lower and upper bound holds for all pairs 1 = 2 with probability at least 1 − 4e −n/64 . The probability that both conditions (47) and (48) are satisfied is at least 1 − 4e −n/64 − 2e −63n/128 . For n ≥ 90, the probability of success is strictly positive. Hence, we know that there exists at least one set of vectors that satisfy the conditions. Setting α = √ 10, we have constructed a set that satisfy all the conditions.

Proof of Theorem 4: Finite sample analysis of MLE
The proof of this theorem will follow in two parts. First we will show that if the gradient of the loss ∇L m evaluated at θ * is small, then the error between θ * and θ is also small. To that end we begin with a simple inequality: L m ( θ) ≤ L m (θ * ).
We appeal to the following lemma for the lower-bound.
Finally, we present the following lemma that establishes an upper-bound on ∇L m (θ * ) 2 .
Lemma 9. Given m observations (v l , x l ) we have that ∇L m (θ * ) 2 ≤ 2 log n m with probability at least 1 − 1/n. Therefore, putting everything together we have that ∆ 2 ≤ 6(1 + b) 2 /b n 2 log n m , which establishes the desired result.

Proof of Lemma 8
To prove this lemma we note that Thus, it is sufficient to prove a lower-bound on λ min ( 1 m m l=1 x l x T l ). In order to do so we may again appeal to recent results on random matrix theory Tropp (2011).
Lemma 10 (Theorem 1.4 (Tropp 2011)). Consider a finite sequence {X k } of independent, random, self-adjoint matrices with dimensions d. Assume that each random matrix satisifes EX k = 0 and λ max (X k ) ≤ R almost surely. Then, for all t ≥ 0, and X for a matrix X represents the operator norm of X or its larges singular value.
In order to apply the above lemma we let X l = x l x T l − 2/n(I − 11 T /n). Therefore, the X l are zeromean, i.i.d., and symmetric. Furthermore, X l ≤ 2 and EX 2 l = 4/n(I − 11 T /n) − 4/n 2 (I − 11 T /n). Therefore, applying the above lemma to both X l and −X l yields the inequality P l X l /m ≥ t ≤ 2n exp −t 2 /2 4 nm + 2t/(3m) .
Article submitted to Operations Research; manuscript no. (Please, provide the mansucript number!) Hence, as long as 12n log n < m, then 1 m l X l ≤ 4 2 log n nm , with probability at least 1 − 1/n.
With the above result in hand we now have that 1 m m l=1 x l x T l − 2 n (I − 11 T /n) ≤ 4 2 log n nm .
Therefore, 1 m m l=1 where we have used the fact that ∆ = θ − θ * and i θ i = i θ * i = 0. Recalling that, m > 12n log n the above inequality can be lower bounded by 1 3n ∆ 2 2 , establishing the desired result. Therefore, Using arguments similar to those to establish the results in Section 4.4.1 we have that with probability at least 1 − 2/n ∇L m ∞ ≤ 2 log n nm , as desired.

Discussion
The main contribution of this paper is the design and analysis of Rank Centrality: an iterative algorithm for rank aggregation using pair-wise comparisons. We established the efficacy of the algorithm by analyzing its performance when data is generated as per the popular Bradley-Terry-Luce (BTL) or Multi-nomial Logit (MNL) model. We have obtained an analytic bound on the finite sample error rates between the scores assumed by the BTL model and those estimated by our algorithm. As shown, these lead to near-optimal dependence on the number of samples required to learn the scores well by our algorithm under random select of pairs for comparison.
The experimental evaluation show that Rank Centrality performs as well as the Maximum Likelihood Estimator of the BTL model and outperforms other known competitors included the recently proposed algorithm by Ammar and Shah (Ammar and Shah 2011). Given the simplicity of the algorithm, analytic guarantees and wide utility of the problem of rank aggregation, we strongly believe that this algorithm will be of great practical value.
An important open question is the near-optimality of the MLE in terms of finite sample bound -as noted, the bounds obtained using the state-of-art analytic methods is quite weak; but the empirical performance of MLE is essentially the same as that of Rank Centrality.

Appendix. Proof of Lemma 1
Without loss of generality, let us consider two items i and j such that w i > w j . When we estimate a higher score for item j then we make a mistake in the ranking of these two items.
When this happens, such that π j − π i > 0, it naturally follows that w i − w j ≤ w i − w j + π j − π i ≤ |w i − π i | + |π j − w j |. For a general pair i and j, we have (w i − w j )(σ i − σ j ) > 0 implies that |w i − w j | ≤ |w i − π i | + |w j − π j |. Substituting this into the definition of the weighted distance D w (·), and using the fact that (a + b) 2 ≤ 2a 2 + 2b 2 , we get This proves that the distance D w (σ) is upper bounded by the normalized Euclidean distance w − π / w . Endnotes 1. http://www.washingtonpost.com/wp-srv/interactivity/worst-year-voting.html 2. http://www.allourideas.org