On The Structure of Parametric Tournaments with Application to Ranking from Pairwise Comparisons
Year: 2021

Abstract:
We consider the classical problem of finding the minimum feedback arc set on tournaments (MFAST). The problem is NP-hard in general and we study it for important classes of tournaments that arise naturally in the problem of learning to rank from pairwise comparisons. Specifically, we consider tournaments classes that arise out of parametric preference matrices that can lead to cyclic preference relations. We investigate their structural properties via forbidden sub tournament configurations. Towards this, we introduce Tournament Dimension a combinatorial parameter that characterizes the size of a forbidden configuration for rank r tournament classes i.e., classes that arise out of pairwise preference matrices which lead to rank r skew-symmetric matrices under a suitable link function. Our main result is a polynomial-time algorithm Rank2Rank that solves the MFAST problem for the rank 2 tournament class. This is achieved via a geometric characterization that relies on our explicit construction of a forbidden configuration for this class. Building on our understanding of the rank-2 tournament class, we propose a very general and flexible parametric pairwise preference model called the localglobal model which subsumes the popular Bradley-Terry-Luce/Thurstone classes to capture locally cyclic as well as globally acyclic preference relations. We develop a polynomial-time algorithm BlockRank2Rankto solve the MFAST problem on the associated Block-Rank 2 tournament class. As an application, we study the problem of learning to rank from pairwise comparisons under the proposed local-global preference model. Exploiting our structural characterization, we propose PairwiseBlockRank a pairwise ranking algorithm for this class. We show sample complexity bounds of PairwiseBlockRank to learn a good ranking under the proposed model. Finally, we conduct experiments on synthetic and real-world datasets to show the efficacy of the proposed algorithm.

heading: 1 Introduction
text: A tournament is a complete directed graph. Given a tournament T, the classical feedback arc set on tournament (MFAST) problem asks for the minimum number of edges that must be removed (or whose orientation reversed) in T to make it acyclic [3]. The problem is known to be NP-hard for general tournaments [6]. We investigate the MFAST problem for several classes of tournaments which naturally occur in learning to rank from pairwise comparisons. In particular, we wish to study the MFAST problem on tournament classes which arise out of parametric pairwise preference classes.
Popular parametric preference models such as the Bradley-Terry-Luce (BTL) [4; 17] and Thurstone models [25] give rise to acyclic tournament matrices for which the MFAST problem is trivial. Our
∗Cohesity, Inc, has neither endorsed nor sponsored this research or its publication in any way; the author’s research opinions and findings are his own.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
goal is to identify and study non-trivial classes of parametric preference matrices which give rise to potentially cyclic tournaments. Cyclic tournaments arise naturally in several real world preference datasets. Figure 1 shows a few real world cyclic tournament structures and Figure 2 shows the fraction of tournaments out of 290 real world tournaments that are acyclic and those that are cyclic and can arise out of the models proposed in this paper. Clearly, simple models such as BTL/Thurstone are insufficient to model these tournaments.
Every pairwise preference matrix P ∈ (0, 1)n×n can be associated to a tournament via a skew symmetric link function φ i.e, φ(P) is a skew symmetric matrix and the tournament T associated to P has an edge from i to j if and only if φ(Pij) > 0. While preference matrices themselves are always of high rank [11], several well studied pairwise preference classes give rise to skew symmetric matrices of low rank under a suitable link function. For example, the BTL model gives rise to a rank 2 skew symmetric matrix under the logit link whereas the Thurstone Model does so under a probit link [22]. It is important to understand the possible tournaments any parametric preference class can give rise to. Indeed, it might be natural and much easier for a modeller/domain expert to make a structural statement such as The class of tournaments of interest should contain cycles of length at most 4 as opposed to an algebraic statement like The class of tournaments should be associated with a preference matrix which on a skew symmetric transformation leads to a rank 8 matrix.
We study the structure of rank r tournament class i.e, tournaments which arise out of preference matrices that lead to some rank r matrix under a skew-symmetric transformation. This class can be interpreted as each node in the tournament having an embedding in Rr and the preference relation between nodes depends on a suitable notion of similarity between the embeddings (see Section 4 for details). It is known that such classes can model cyclic relations [22]. To investigate the MFAST problem for the rank r tournament classes, we first structurally understand these tournament via the notion of forbidden configurations [8]. Forbidden configurations in tournaments have been studied in other non-parametric contexts. The simplest example is the class of acyclic tournaments which has the 3 cycle as a forbidden configuration. A complicated forbidden configuration class using Möbius ladders was studied in [8; 9]. In both these cases, the MFAST problem is poly-time solvable.
Our Contributions. Our first contribution is to derive upper and lower bounds for the size of a forbidden configuration for any rank r tournament class. We do this by introducing a novel combinatorial parameter that we call the Tournament Dimension. When rank r = 2, we completely characterize the associated tournament class by identifying the exact forbidden configuration. We use this forbidden configuration to understand the geometry of this tournament class and propose an algorithm (Rank2Rank) to solve the MFAST problem in polynomial time for this class of tournaments.
Our next contribution is to propose a flexible class of tournaments called the Block Rank 2 class which builds on the rank 2 class. Tournaments in this class can arise from the local-global model - a general pairwise preference model that we propose. The model can capture locally cyclic relations as well as globally acyclic relations and is well suited for several practical applications including those in Figure 1. The model subsumes several popular pairwise ranking models including the BTL and
Thurstone models. We show that the MFAST problem on the associated Block Rank 2 tournament class is polynomial time solvable and propose an algorithm (BlockRank2Rank) for the problem.
Our third contribution is to study an application of our work to the problem of learning to rank from pairwise comparisons. We propose a matrix completion based algorithm called PairwiseBlockRank for this problem and derive sample complexity bounds for the same under the proposed local-global preference model. Finally, we evaluate our algorithms on real world and synthetic data-sets and show improved performance over several existing algorithms.

heading: 2 Related Work
text: Several works have considered learning from transitive pairwise models especially focusing on the Bradley-Terry-Luce (BTL) model[12; 20; 21; 24; 14]. As we focus on cyclic relations, we discuss only the models which can lead to cyclic preferences. While the BTL model can be seen as using a 1 dimensional embedding of the item using a score vector, studies have considered higher dimensional embeddings. A 2 dimensional embedding was considered in [5]. While their model can give rise to cyclic tournaments, it is not clear what type of cycles are possible. [18; 19] propose the Majority vote model which is a random utility model (RUM) with a d dimensional feature embedding for each item. The Majority vote model is powerful enough to produce arbitrarily long cycles and can express any probability sub-matrix over a fixed triplet. The Rank 2 model we study is as powerful as the Majority vote model. Furthermore, we give a complete structural characterization of the tournaments of our model which is not known for the Majority vote model. The Blade-Chest inner (BCI) model [7] embeds each item into two d dimensional vectors (blade vector and a chest vector) and a score vector s where the probability of i being preferred over j depends on < ichest, jblade > − < iblade, jchest > +si − sj . The rank-2 model can be seen as a special case of the BCI model where d = 1 and s is a constant vector. When d is O(n), the BCI model can give rise to any tournament as there are O(n2) parameters and so the MFAST problem becomes intractable. We focus on the special case of d = 1 where there are only 2n parameters and propose algorithms to obtain optimal rankings. Finally, we discuss the low rank pairwise rank (LRPR) class of models which result in a low rank matrix under a transformation using a suitable link function [22]. Previous work [12,22] have proposed matrix completion based algorithms to obtain optimal ranking for the LRPR type models assuming transitivity of preferences. In this work, we make no such assumptions.

heading: 3 Preliminaries
text: A Tournament is a complete directed graph. We use i T j to denote that there is a directed edge from node i to j in the tournament T. We call a set of edges Fσ in a tournament T as the feedback arc set of permutation σ w.r.t T if σ(i) > σ(j) (j ranked ahead of i in σ) but i T j. Indeed, if one reverses the orientation of the Fσ edges in T, one gets an acyclic tournament whose topological sort would yield σ. We call a permutation σ∗ as MFAST-Optimal for T if σ∗ ∈ arg minσ |Fσ|. We call P ∈ (0, 1)n×n a pairwise preference matrix if Pij + Pji = 1 ∀i 6= j. We assume Pij 6= 0.5 ∀i, j. We will say TP is a tournament associated with P if a directed edge from node i to j is present in TP if and only if Pij > 0.5. We call P a rank r preference matrix w.r.t a link function φ if rank(φ(P)) = r where the function φ is applied element-wise to P. We will call φ a skew symmetric link function if φ(P) is a skew symmetric matrix for any pairwise preference matrix P. Examples of such φ include the logit and probit links where logit(x) = log(x/(1− x)) and probit(x) = Φ−1(p) where Φ is the standard normal cdf. We use T n,φr to denote the class of all tournaments on n nodes which are associated with a rank r preference matrix w.r.t φ.
Our goal is the study the tournament class T n,φr where φ is a skew symmetric link function. Skewsymmetric matrices are naturally associated to tournaments where the edge directions in the tournament are determined by the sign of the corresponding matrix entry. Our results would apply for any skew symmetric φ and so we will drop the φ in T n,φr when it is clear from the context. As skew symmetric matrices have even rank, T n,φr is non-empty only for even r. We wish to investigate the structural constraints on these tournament classes that arise out of the algebraic (rank) restriction that define them. We note that it was known earlier that for the special case when r = 2, T n,φ2 contains both cyclic and acyclic tournaments [22]. However, nothing further was known about this class.
Algorithm 1 Tournament Game 1: Input: Integers k, d 2: Player-1 chooses a labelled dataset {(x1, y1), . . . (xk, yk)} where D = {xi}ki=1 ∈ Rd induces a Tournament, yi ∈ {+1,−1}
3: Player-2 chooses a Tournament preserving mapping f w.r.t D 4: if ∃w ∈ Rd such that sign(wT f(xi)) = yi ∀i ∈ [k] then 5: Player-2 wins the game 6: else 7: Player-1 wins the game 8: end if
Definition 1. A class of tournaments T is said to have a forbidden configuration of size ` if ` is the smallest integer such that there exists a tournament T` on ` nodes which does not appear as an induced sub-tournament for any T ∈ T
In other words, no induced sub-tournament on l nodes of T ∈ T is isomorphic to T`. For example, the class of all acyclic tournaments T acyclic has C3 - the 3-cycle as a forbidden configuration. Taking advantage of this forbidden configuration, one can immediately come up with an algorithm to solve the MFAST problem on T acyclic - indeed, a topological sort solves this problem. Our interest is to understand if there are similar forbidden configurations for the class T n,φr . Towards this, we start the next section by defining a novel combinatorial parameter called the Tournament dimension.

heading: 4 Tournament Dimension
text: Let d be an even integer. We say a set of points D = {x1, . . . ,xk} ∈ Rd induces a tournament T if xi is a d-dimensional embedding of node i and a directed edge from node i to j exists in T if and only if xTi A
rotxj > 0. Here, Arot ∈ Rd×d is the block diagonal matrix with d2 blocks where each block of size 2 is a rotation matrix [0 − 1; 1 0] 2. Note that xTi Arotxj = −xTj Arotxi ∀i, j and the tournament inducing property of D excludes datapoints such that xTi Arotxj = 0. We note that d being even is not a restriction on the embedding. If d is odd, one can increase the embedding to d+ 1 dimensions w.l.o.g where the last component is 1 for all xi. Lemma 1. Let D = {x1, . . . ,xk} ∈ Rd induce a tournament T. Then T ∈ T kd . Furthermore, for every T ∈ T kd there exists a dataset D with k vectors in Rd that induces T.
We call a mapping f : Rd → Rd as Tournament-preserving w.r.t. a tournament inducing dataset D if (f(xi)TArotf(xj) > 0) ⇐⇒ (xTi Arotxj > 0) ∀xi,xj ∈ D. We define the Tournament game between two players as described in Algorithm 1. Definition 2. The Tournament dimension for d - TourDim(d) - is the largest value of k for which Player 2 always has a winning strategy in the Tournament game (Algorithm 1).
Remark. TourDim(d) = k implies that Player 1 has a winning strategy for all values ≥ k + 1. In particular, there is a tournament T ∈ T kd induced by the dataset D and a labelling {y1, . . . , yk} strategically chosen by Player 1 such that there does not exist a T-preserving mapping for which Player 2 can find a w ∈ Rd that labels all points in D correctly. The inability to find such a w is equivalent to the inability to add one more node to T whose edge direction to node i of T is specified by the label yi. Thus, there must be a forbidden configuration on k + 2 nodes.
The Theorem below formalizes the above remark. Theorem 2. T nr has a forbidden configuration of size TourDim(r) + 2 for every even integer r < n and every n ≥ TourDim(r) + 2.
2The matrix Arot is fundamental to skew-symmetric matrices. In fact, any skew-symmetric bilinear form can be represented under a suitable basis using Arot and additional zero diagonal blocks as necessary [23].
We bound the size of the forbidden configuration as follows Theorem 3. Let T nr have a forbidden configuration of size `. Then r + 2 ≤ ` ≤ 2r + r + 1
Remark. We believe that the upper bound in Theorem 3 is not tight in general and leave it as an open problem to improve this for a general r. Corollary 1. T n2 has a forbidden configuration of size 4.
While the above Corollary gives the size of the forbidden sub configuration, it does not specify what exactly the configuration is. As the rank 2 class occurs naturally in several learning to rank problems, we investigate this further in the next section.

heading: 5 Rank 2 Tournaments - T n2
text: In this section we focus on the Rank 2 tournament class T n2 . To motivate this class, consider the following generalisation of the popular Bradley-Terry-Luce (BTL) preference model where for a skew symmetric link function φ, we define φ(Pij) = uivj − viuj . The model is parameterized by two vectors u,v ∈ Rn. When one of these vectors is the all ones vectors and when the link function φ is the logit function, the model reduces to the standard BTL model.
In general for any P, if φ is a skew symmetric link function that results in a rank 2 matrix, then φ(P) = uvT − vuT for some u,v ∈ Rn. Such a model can be interpreted as each node i having a two dimensional embedding hi = [ui, vi]. Here, the direction of the edge between nodes i and j in the associated tournament depends on the sign of uivj − viuj = hTi Arothj where Arot ∈ R2×2 is the rotation matrix [0− 1; 1 0]. With this background, we now proceed to characterize the class T n2 . Geometric Characterization of T n2 : We start with the following key lemma: Lemma 4. (Forbidden configurations) Let n ≥ 4. Every induced tournament of T n2 on a subset of four nodes forbids the configurations in Figure 3.
The above lemma can be used to geometrically characterize the two dimensional embeddings of the nodes in T n2 . For this characterization, we need the following definition. We call a set of vectors S ⊂ R2 a separator of two sets of vectors U, V ⊂ R2 if the convex cone of U ∪ V contains −S i.e., the set of vectors in S rotated by 180 degrees is a subset of cone(U ∪ V ) Theorem 5. Let T ∈ T n2 where each node i has a two dimensional embedding hi ∈ R2. Then either T ∈ T acyclic or ∃k ≥ 1 such that the vectors hi can be partitioned into 2k + 1 ordered sets {S0, . . . , S2k} where for each i = 0, . . . , 2k, Si ⊂ R2 is a separator of the sets Si+k mod(2k+1) and Si+k+1 mod(2k+1)
Figure 4 (left) shows how the embeddings of nodes that result in T n2 would look like geometrically. As one can observe, the example tournament has 5 sets of vectors and every set of vectors of the
same color acts as a separator for two other sets of different colors. This is the crucial geometric insight that we obtain which characterizes this tournament class. We note that when the number of sets (colors) is just 1, the model leads to acyclic tournaments. Indeed, tournaments arising out of the BTL/Thurstone models have this property and lead to T ∈ T acyclic ( T n2 . However, T n2 is much more richer than the simple T acyclic class. Structural Characterization of T n2 : With the help of the geometric characterization, we next give the structural description of all tournaments in T n2 . For two sets of nodes A and B, We use A T B to denote that every node in A has an outgoing edge to every node in B in the tournament T. Also, A ≺T B whenever B T A Theorem 6. Let n ≥ 4 and T ∈ T n2 . Then either T ∈ T acyclic or there exists k ≥ 1 such that the n nodes can be partitioned into 2k + 1 sets {A1, A2, . . . , Ak, B1, B2, . . . , Bk, C} where (a) The induced sub-tournament on each of the 2k + 1 sets belong to T acyclic (b) Ai T Aj , Bi T Bj ∀i < j (c) Ai T Bj ∀i ≥ j, Ai ≺T Bj ∀i < j (d) Bi T C T Aj ∀i, j
Figure 4 (right) gives a graphical representation of the structure of T n2 described in Theorem 6. The following theorem sheds light on the rich expressivity of the T n2 tournament class. Theorem 7. (Long Cycles and Arbitrary Triplets) Given any arbitrary ordered set of indices {i1, i2, . . . , ik}, k ≤ n, there exists a T ∈ T n2 such that i1 T i2 T . . . T ik T i1. Furthermore, Given any p1, p2, p3 ∈ (0, 1) and indices i1, i2, i3 ∈ [n], there exists a pairwise preference matrix P whose associated TP ∈ T n2 where P(i1, i2) = p1,P(i2, i3) = p2,P(i3, i1) = p3.

heading: 5.1 Polynomial Time Algorithm for MFAST for T n2
text: We present a polynomial time algorithm for MFAST for the T n2 class. The algorithm Rank2Rank (Algorithm 2) takes as input a tournament T and outputs a permutation σ∗ that is MFAST-optimal for T whenever T ∈ T n2 . The algorithm finds such a σ∗ by relying crucially on the structural understanding gained in the previous section via forbidden configurations. In the following, given a set of nodes A and a tournament T, we represent the induced tournament on A by T as TA.
Algorithm 2 Rank2Rank-R2R 1: Input: A tournament T 2: if T ∈ T acyclic then 3: Obtain σ∗ by a Topological sort of T 4: else 5: Find {a, b, c} s.t (a T b T c T a) 6: A := {a} ∪ {i : i T b and c T i} 7: B := {b} ∪ {i : i T c and a T i} 8: C := {c} ∪ {i : i T a and b T i} 9: σ0 = [R2R(TA), R2R(TB), R2R(TC)] 10: Let σh be the permutation obtained by a cyclic shift of σ0 by h positions. 11: Let σ∗ be the permutation among σh ∀h which has the least size of the feedback arc set w.r.t T i.e., σ∗ = arg min
h |Fσh |
12: end if 13: Output σ∗
Algorithm 3 BlockRank2Rank - BR2R 1: Input: A tournament T 2: if T ∈ T acyclic then 3: Obtain σ∗ by a Topological sort of T 4: else 5: Find {a, b, c} s.t (a T b T c T a) 6: S+ = {i : i T {a, b, c}} 7: S− = {i : i ≺T {a, b, c}} 8: S = [n]\{S+ ∪ S−} 9: σ∗ = [BR2R(TS+), R2R(TS), BR2R(TS−)] 10: end if 11: Output σ∗
Theorem 8. If T ∈ T n2 is given as input to the Rank2Rank (Algorithm 2), the output σ∗ produced by the algorithm is MFAST-optimal for T. Furthermore, Rank2Rank has a time complexity of poly(n).
Geometric Sweep Interpretation: One can also come up with a geometric sweep algorithm to solve the MFAST problem for T n2 inspired by the geometric embedding based interpretation given earlier. Here, we assume that the embeddings of the items are given as input. The algorithm begins by fixing an arbitrary anchor item i and circular sweeps the R2 plane in the counter clockwise direction from the embedding of i thus creating a permutation σ0 of items corresponding to the order in which they
are encountered in the sweep. Starting to sweep from different anchors would give rise to n different cyclic shifts of σ0. We argue in the appendix that the optimal σ∗ that solves the MFAST problem w.r.t T must necessarily be one of these n permutations. We note that while the Geometric sweep algorithm needs the embeddings to be known, the Rank2Rank algorithm does not need the same.

heading: 6 Block T n2 Class
text: Often in practical applications, items can be clustered into blocks such that within block they exhibit a certain local pairwise preference whereas across blocks they exhibit a global pairwise preference. For example, consider the game of tennis where the top 3 players might have a cyclic preference among themselves whereas they strictly beat every other player in the bottom n− 3. To capture such effects, we next propose the local-global pairwise preference model.

heading: 6.1 Local-Global Preference Model
text: The local-global pairwise preference model is parameterized by three vectors s,u,v ∈ Rn and a ordered partition of [n] given by {H1, ...,Hb} ∈ 2[n] where ∪bk=1Hk = [n] and Hi ∩Hj = ∅ ∀i 6= j. Let g(i) denote the partition in which item i is present. We assume that si > sj ⇐⇒ g(i) < g(j) i.e., the parameter vector s aligns with the ordering of the partitions. The pairwise preference probability of item i being preferred over item j under a skew symmetric link function φ is given as
φ(Pij) = { uivj − viuj if ∃` s.t i, j ∈ H` si − sj otherwise
Figure 5 shows some flexible tournament structures that arise out of the local global model and Figure 1 shows several real world tournaments that have associated tournaments arising out of this model.
One can interpret the above model as follows: The set of [n] items is divided into b blocks/partitions. Restricted to each block, the local pairwise preference matrix has an associated tournament that belongs to T n2 which can potentially contain cycles. However, across partitions, the preference matrix behaves like a standard BTL type model parameterized by the score vector s and hence the associated global block level tournament relation belongs to T acyclic. The tournament associated to the entire set of n nodes thus has a block structure. Indeed, the model is determined by 3n parameters where 2n parameters determine the intra block local structure and n parameters the inter block global structure.
Remark. The standard BTL model and it’s generalization with 2n parameters are special cases of the above model where the number of blocks b = 1 and φ is the logit link.
We refer to the class of tournaments that arise out of a local-global model as the Block− T n2 class. Theorem 9. If T ∈ Block-T n2 is given as input to the BlockRank2Rank (Algorithm 3), the output σ∗ produced by the algorithm if MFAST-optimal for T. Furthermore, BlockRank2Rank has a time complexity of poly(n).
7 Learning to Rank From Pairwise Comparisons under Block-T n2
We now consider the application of the models discussed so far to the problem of learning to rank from pairwise comparisons under the local-global pairwise preference model which lead to tournaments in Block-T n2 . Towards this, we propose the PairwiseBlockRank algorithm (Algorithm 4). Given a dataset of pairwise comparisons, the algorithm constructs the empirical pairwise comparison matrix. It applies the link function φ to construct a empirical skew-symmetric matrix with missing entries (corresponding to pairs that are not compared in the dataset). The algorithm then applies a matrix completion routine to complete the skew-symmetric matrix. Once complete, the associated tournament is computed and the ranking obtained using the BlockRank2Rank algorithm.
Matrix completion routines (such as [16]) typically require an upper bound on the rank of the matrix being completed. The following Lemma establishes that this depends on b, the number of blocks.
Lemma 10. Let T ∈ Block-T n2 with b blocks. Then T ∈ T nr for some r ≤ 4b.
The following theorem establishes sample complexity of learning for recovering the blocks correctly.
8: Construct Tournament T from M̂ where (i, j) ∈ E
whenever M̂ij > 0 9: σ∗ = BlockRank2Rank - BR2R(T)
10: Output σ∗
Theorem 11. (Block Recovery) Let the local global model be parameterized by vectors u,v, s ∈ Rn and ordered partitions {H1, . . . ,Hb} and a skew symmetric link function φ. Let m pairs be chosen uniformly at random from all subsets of ( n 2 ) of size m and let each pair be compared K times according to the corresponding preference matrix P. Let θ = minij |uivj − viuj | where (i, j) are in the same partition and let ∆ = min |si − sj | where (i, j) are in different partitions. Let 0 < < n2( θ∆ ) 2. Then with probability at least 1− 2n3 , if m is O(nblog(n))) and K is O( b log(n) ∆2 ), the PairwiseBlockRank algorithm on running with the dataset generated as above, returns a ranking σ that respects the block structure i.e., σ(i) < σ(j) whenever i ∈ Hk and j ∈ H` ∀` > k.

heading: 8 Experiments
text: Datasets: We use the following real world datasets (with n items to be ranked and m pairwise comparisons): DoTA [1] (n = 757,m = 10442), Tennis [2] (n = 742,m = 23806), Sushi-A [15] (n = 10,m = 100000), Sushi-B [15] (n = 100,m = 25000), Jester [13] (n = 100,m = 891404).
Setting + Performance measure: Given a set of pairwise comparisons, we do a 70 : 30 train:test split. We run the algorithms on the train data to obtain a ranking σ. We test the performance of σ on the test set by computing the ratio of upsets(the pairs (i, j) for which σ(j) < σ(i) but the fraction of times i being preferred over j in the test set is ≥ 0.5) and the number of unique pairs in the test data. Algorithms: MC + Copeland: We first complete the empirical preference matrix P̂ using a matrix-completion (MC) routine with rank = 2 and then run the standard Copeland procedure [10] to get a ranking.
MC + Borda: Same as Copeland but the standard Borda algorithm [21] is used instead of Copeland to obtain a ranking from the completed ranking.
Rank Centrality: A spectral ranking algorithm [20] that ranks based on computing a stationary distribution of a Markov chain associated with P̂.
Blade-Chest: A maximum likelihood based algorithm for the Blade-Chest model [7] where we set the dimension of the emdedding to be 8 (Other choices perform poorly, see Supplementary). To obtain a ranking from the estimated MLE, we run the BlockRank2 algorithm of this paper (Other choices perform poorly, see Supplementary).
PariwiseBlockRank: The algorithm described in this paper. To make it more suitable for realworld data, in each recursive call, we use either the ranking given by the algorithm or the Copeland procedure depending on whichever is better for the given data.
The results are presented in Table 1 averaged over 20 splits. As can be seen, the PairwiseBlockRank algorithm performs better or comparably with the best algorithm for most of the datasets. In some cases, it produces similar results as the Copeland algorithm. Furthermore, the Blade-Chest model
performs poorly for all datasets. The Rank-centrality algorithm performs competitively. To understand this better, we run the following synthetic experiments to compare with rank centrality algorithm.
Synthetic Experiments: The synthetic data was generated to follow the local-global Model. We considered the number of items n = 600, and ran experiments on b = 3 (see Supplementary for other choices) block cases with equal sized blocks. From the constructed underlying probability preference matrix, we sampled entries according to two parameters, K and known fraction β. Known fraction (β) represents the fraction of total unique pairs that are uniformly chosen for comparison and K represents the number of Bernoulli comparisons for every such pair chosen. We did two types of experiments, one where we fixed the known fraction β and varied K and other where we fixed K and varied β. Thus for every experiment K.β. ( 600 2 ) comparisons are made in total. Figure 6 shows the results from varying K and the known fraction. The results are averaged across 10 runs. As can be seen, for the MC + PairwiseBlockRank algorithm, the pairwise disagreements quickly approach the optimal value when the known fraction is fixed, and K increases. For the other algorithms, the quality of ranking does not improve with increase in K. Similar trend is observed when the known fraction β is increased while fixing K. The results clearly indicate that with increasing samples, the proposed algorithm quickly converges to the optimal ranking whereas the others perform poorly.

heading: 9 Conclusion
text: In this work, we study the class of parametric preference matrices which induce cyclic tournaments. We propose algorithms that solve the MFAST problem on rank 2 classes and build on the rank 2 class to propose a flexible model called the local-global model. For the general rank r class, we initiate understanding the associated tournament class via the notion of tournament dimension. Going forward, we would like to understand the forbidden configurations of higher rank tournaments and pin down the difficulty in solving the MFAST problem using this approach.
Broader Impact We introduce a flexible parametric model that can capture potentially acyclic relations. The broader impact is that we look at the classical MFAST problem from a novel parametric viewpoint. We believe this can lead to broader impact in fundamental understanding of the hardness of this problem. Algorithms might be subject to bias if the data is inherently biased. The current approach does not focus on removing algorithmic bias that can arise in this fashion.

Review summaries:
The paper studies real-valued input matrices to the minimum feedback arc set problem on tournaments (MFAST). The matrices are assumed to have low rank and originate from pairwise preference matrices under certain link functions. The authors present a geometrical condition that enables a polynomial-time algorithm to solve MFAST for rank-2 matrices. They apply their algorithm in experiments on learning to rank from pairwise comparisons.

This paper focus on minimum feedback arc set problem in tournaments (MFAST) and characterizes the relation between the preference matrix rank with forbidden configuration. The authors propose a novel polynomial-time algorithm on MFAST with preference matrix rank 2. The authors further extend the setting to a block rank 2 tournament, where nodes can be clustered into several blocks and in each block, the preference matrix has rank 2. The proposed algorithm can also work on the non-tournament cases with a matrix-completion step. The experiments shows that the proposed algorithm reaches better performance than other works, in both synthetic (non-tournament) and real-world datasets.

The paper studies the minimum feedback arc set problem in certain classes of tournament graphs. In these classes, the edges of the tournament are defined by preference matrices of rank r. This study is motivated by arguing that such tournaments arise out of real-world data sets in various application domains.    The paper gives bounds on the size of forbidden configurations for rank-r tournaments. For rank 2 tournaments, the paper identifies the exact forbidden structures. The paper also studies a restricted class, called block rank 2 tournaments, which is claimed to subsume several practical models. It gives a polynomial-time algorithm for the minimum feedback arc set problem on instances of this class. Finally, it shows an application of their work to the problem of learning how to rank from pairwise comparisons and provide some experimental results.