On The Structure of Parametric Tournaments with Application to Ranking from Pairwise Comparisons
Authors: Vishnu Veerathu
Arun Rajkumar
Venue: NeurIPS 2021 Poster (2021)
Keywords: ranking
pairwise
intransitive
low-rank

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 \emph{Tournament Dimension} - a combinatorial parameter that characterizes the size of a forbidden configuration for rank $r$ tournament classes i.e., classes that arise out pairwise preference matrices which lead to rank $r$ skew-symmetric matrices under a suitable link function. Our main result is a polynomial-time algorithm - \texttt{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 local-global 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 - \texttt{BlockRank2Rank}- to 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  \texttt{PairwiseBlockRank} - a pairwise ranking algorithm for this class. We show sample complexity bounds of \texttt{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.

On The Structure of Parametric Tournaments with Application to Ranking from Pairwise Comparisons
Vishnu Veerathu" Cohesity Inc. ofrissimueerattuugmalllccm com
Arun Rajkumar
Indian Institute of Technology. Madras Robert Bosch Center for Data Science and Al arunrêcse. iitm. ai. in
Abstract
We consider the classical problem of finding the minimum feedback are 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, consider tournaments classes that arise out of parametric preference matrices that can lead cyclic preference relations. We investigate their structural properties via forbidden sub tournament configurations. Towards this, we introduce Tournament Dimension a combinato- rial parameter that characterizes the size of forbidden configuration for rank r tournament classes i.c., classes that arise out of pairwise preference matrices which lead to rank skew-symmetric matrices under suitable link function. Our main sult is a polynomial-time algorithm Rank2Rank that solves the MFAST problem for the rank tournament class. This is achieved via a geometric characterization that relies on our explicit construction of a forbidden configuration for this class. Building our understanding of the rank-2 tournament class, we propose a very general and flexible parametric pairwise preference model called the local- global model which subsumes the popular Mondley-Terry-Leee Leanry-Lue//Thustoon Thurstone classes to capture locally eyclic well as globally acyclic preference relations. We develop polynomial-time algorithm- Bl BlockRank2Rank- to solve the MFAST problem on the associated Block-Rank 2 tournament class.
As an application, we study the problem learning to rank from pairwise compar- isons under the proposed local-gtt global preference model. Exploiting structural characterization. we propose BairiseeBockKaan for this class. We show sample complexity bounds of PairviseBlockRanl learn a good ranking under the proposed model. Finally, we conduct experiments on synthetic and real-world datasets show the efficacy of the proposed algorithm.
a pairwise ranking algorithm
Introduction
tournament a complete directed graph. Given a tournament T, the classical feedback are set tournament (MFAST) problem asks for the minimum number of edges that must be removed (or whose orientation reversed) in T to make acyclic K 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 of parametric pairwise preference classes.
Popular parametric preference models such as the Bradley-Tery Terry-Leeee (BTL) 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 any way; the author's rescarch opinions and findings are his own.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Frnction Tournaments
CYCLIC our muskd
0.0.0.000
CYCLIC + Our model
ELECTEAT OARDERATEE PREPERIEEE ECOMRAMEET
SCSIC PREFERIIC TCURHAMIIT
0.
ACYCLIC
Our uadel Previuu models
ACYCLIC
O-
10 K- Touruaments with at least K nodes
20
Several tournaments that arise out of real world datasets exhibit eyclic structure. (Source: www. www.prelib... org). Figure shows six such examples in varied application domains. Except the Sushi Preference Tournament, none of the others can be modelled using acyelic preference models like -rradey-Terry-LLeeeThhae Thw.///hrsstoee. The local-global model described in Section and the associated Block- T3" class defined in this paper induces all these flexible tournament structures.
Figure 1:
Out of 290 real world tournaments from www www preflib...b... org. figure shows the fraction of tournaments that are acyclic and the fraction of cyclic tournaments that satisfy the Block- Rank 2 model we propose.
Figure 2:
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 shows a few real world cyclic tournament structures and Figure saarre[sshws the fraction of tournaments out of 290 real world tournaments that 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 E (0. 10.1) can be associated to 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 to j if and only if ((P;)) > O. While preference matrices themselves are always of high rank [T]. 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 modeller/domain expert to make structural statement such as The class of tournaments of interest should contain cycles of length at most 4 as opposed to algebraic statement like The class of tournaments should be associated with a preference matrix which on a skew synmetric transformation leads to a rank 8 matrix.
We study the structure of rank 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 R' and the preference relation between nodes depends on a suitable notion of similarity between the embeddings (see Section for details). It is known that such classes model cyclic relations 22) To investigate the MFAST problem for the rank 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 acyelic tournaments which has the 3 cycle forbidden configuration. A complicated forbidden configuration class using Möbius ladders was studied in [ [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 call the Tournament Dimension. When rank = 2, 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 flexible class of tournaments called the Block Rank 2 class which builds on the rank 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 acyelic relations and well suited for several practical applications including those in Figure I 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 polynomial time solvable and propose an algorithm (BlockRank2Ranik) 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 matrix completion based algorithm called PairwiseBlockRand 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.
2 Related Work
Several works have considered learning from transitive pairwise models especially focusing on
the Bradley-Terry-Luee (BTL) model 20 21
24 14). As we focus cyclic relations, we
discuss only the models which can lead to cyclic preferences. While the BTL model can be seen as using 1 dimensional embedding of the item using 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, is not clear what type of cycles are possible. [T8] [9] propose the Majority vote model which is 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- sub-matrix over 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 score vector where the probability of i being preferred over depends on < fchest: Jblade > < Ublade Jehest > +& sy. The rank-2 model can be seen as a special case of the BCI model where d = 1 and is constant vector. When d is (n)), the BCI model can give rise to any tournament as there are (n²²) parameters and so the MFAST problem becomes intractable. We focus the special case of d = I 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 low rank matrix under transformation using a suitable link function [22]. Previous work [2 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.
3 Preliminaries
A Tournament is a complete directed graph. We use i >T j to denote that there is a directed edge from node to j in the tournament T. We call set of edges F, in a tournament T as the feedback arc set of permutation a w.r.t T if (i) > (ji) (j ranked ahead of in σ) but i > j. Indeed, if one reverses the orientation of the F' edges in T, one gets an acyelic tournament whose topological sort would yield a. We call a permutation o² as MFAST-Optimal for T if o² E arg min, [Fal.
vi + We assume P.j * 0.5 j. We will say Tp is a tournament associated with P if a directed edge from node i to is present in Tp if and only if P.j > 0.5. We call P rank preference matrix w.nt link function & if rank(o(P)) P))== where the function ø is applied element-wise to P. We will call 6 a skew symmetric link function if d(P) is skew symmetric matrix for any pairwise preference matrix P. Examples of such é include the logit and probit t links where logit(x) = log(2/(1 (1 - x)) and probit(x) = x- (p)( where & is the standard normal edf. We use T to denote the class of all tournaments n nodes which are associated with a rank preference matrix w.r.t øb
We call P (0. 1)mxx pairwise preference matrix if Pij + Py:
Our goal is the study the tournament class T.a. where @ is a skew symmetric link function. Skew- symmetric matrices are naturally associated to tournaments where the edge directions in the tour- nament 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.r. when it is clear from the context. As skew symmetric matrices have even rank, T 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 was known earlier that for the special case when r = 2, T, contains both cyclic and acyclic tournaments 22.. However, nothing further was known about this class.
3

---

Algorithm Tournament Game
1: Input: Integers k,
2: Player-1 chooses
labelled { E Rd
dataset
((x1,1),,... vi).....e. (Xx: va)) where D
induces Tournament, y44 (+1,-1}
3: Player-2 chooses a Tournament preserving mapping
w.I.t
4: if 3w 1Rd such that sign(w" f(x:)) yı vi [k]
then
5: Player-2 wins the game
Figure 3: Forbidden configu- rations for any induced tourna- ment on 4 nodes in T2"
6: else
7: Player-1 wins the game
8: end if
Definition A class of tournamenss T is said to have a forbidden configuration of size if is the smallest integer such that there exists tournament T l nodes which does not appear induced tobbtoummmment for any T E
In other words, induced sub-tournament on nodes of T E T is isomorphic to T For example, the class of all acyclic tournaments Tasyclic has C the 3-cycle as a forbidden configuration. Taking immediately
advantage of this forbidden configuration, the MFAST problem on Tacyelse indeed, a topological sort solves this problem. Our interest is to understand if there are similar forbidden configurations for the class T, Towards this, start the next section by defining a novel combinatorial parameter called the Tournament dimension.
up with algorithm solve
Tournament Dimension
Let d be integer. We say set of points D fx,,...,,.x xx) Rd induces tournament T if x; is a d-dimensional embedding of node i and a directed edge from node i to exists in T if and only if x A, O. Here, Aoo E gdxd is the block diagonal matrix with á blocks where each - block of size 2 a rotation matrix [0- - 1; 0 Note that x." A = xx Ar"xx, Vi, and the
tournament inducing property of 'D excludes datapoints such that x? A = O. We note that d being even is not a restriction on the embedding. If is odd, one can increase the embedding to + 1 dimensions w.l.o.g where the last component is 1 for all x;.
Lemma 1. Let D (xi,..., { E &Rd induce a tournament T. Then T E Th. Furthermore, every E Th there exists a dataset 'D with & vectors in Id that induces T.
We call a mapping f Rd Rd as Tournament-preserinn if (xx,)) ATo f(x,) > = (x] A 0) Vx,,X, D. We define the Tournament game between two players as described Algorithm[
w.r.t. a tournament inducing dataset D
Definition 2. The Tournament dimension for d TourDim(d) is the largest value of ls for which Player always has a winning strategy in the Tournament game (Algorithm) 7p.
Remark. TourDim(d) k implies that Player 1 has winning strategy for all values > k: + 1. In particular, there tournament T E Th induced by the dataset D and labelling [y1..... yk strategically chosen by Player such that there does not exist a T-preserving mapping for which Player can find E ad that labels all points in D correctly. The inability to find such is equivalent to the inability to add one more node to T whose edge direction to node of T specified by the label y, Thus, there must be forbidden configuration on k + nodes.
The Theorem below formalizes above remark.
Theorem 2. T, has a forbidden configuration of size TourDim(r) + for every even integer and every n 2 TowrDim(r) +2.
"The matrix TT is fundamental to skew-symmette matrices. In fact, any keem-symmetric bilinear form can be represented under suitable basis using Fo and additional diagonal blocks necessary [X]

---

5 (Seporator of and
S = 2
S =
S
0o0
(Seporator of 5
(Separotor of ard
S = C
o
00
00
S, (Seporotor of and 5))
(Separator 5.)
S3= B
S = Bg
Figure 4: (Left) Geometry of the embeddings of nodes in T2" where -S3 C cone (S U is highlighted. (Right) Structure of Tournament belonging to T2" for the example on the left. The sets (So..... (5, } are colored as per the left figure and mapped (A1, A2, B1, B2, C) as in Theorem
We bound the size of the forbidden configuration as follows Theorem 3. Let T," have a forbidden configuration of size f. Then feeen+221le +225522 +25152++++1
+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 general Corollary 1. T32 has 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 the next section.
Rank 2 Tournaments -T
In this section we focus the Rank 2 tournament class Tz,. To motivate this class, consider the following generalisation of the popular Bradley-Terry-Luee (BTL) preference model where for skew symmetric link function é, we define ((P.)) = U4y, u. The model is parameterized by two vectors u, v E R". When one 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 & skew symmetric link function that results in a rank matrix, then ((P) uv vu? for some u, v E R Such a model can be interpreted as each node i having two dimensional embedding h; [ug, v.]. Here, the direction of the edge between nodes and j in
the associated tournament depends on the sign of u,ū; 0;u, = h A where A E R is the rotation matrix [0- 1; 1 0j. With this background, we now proceed to characterize the class Tge
Geometric Characterization of T We start with the following key lemma:
Lemma 4. (Forbidden configurations) Let 4. Every induced tournament Ts on a subset of four nodes forbids the configurations in Figure
The above lemma can be used to geometrically characterize the two dimensional embeddings of the nodes in Tz. For this characterization, we need the following definition.
We call set of vectors 5 IR22 separator of two of vectors U, V R if the convex cone of U UUV contains -S i.c., the set of vectors in S rotated by 180 degrees is a subset of cone(U UV) Theorem 5. Let E TH" where each node i has a two dimensional embedding h, E R.? Then either T E Tecyclsc or 3k 2 such that the vectors h; can be partitioned into 2k + ordered sets where for each O.... 23. S, C R22 is separator of the sets S14k mod(2k+1) and S mod(2k+1)
Figure (left) shows how the embeddings of nodes that result in T," would look like geometrically. As one can observe, the example tournament has 5 sets of vectors and every set of vectors of the
5

---

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 acyelic tournaments. Indeed, tournaments arising out of the BTL/Thurstone models have this property and lead T E Tacyclle & T However, 72" is much more richer than the simple Tacyelie class.
Structural Characterization of T With the help of the geometric characterization, we next give the structural description of all tournaments in 72" For two sets of nodes A and B, We use A >- B denote that every node in has an outgoing edge to every node in B in the tournament T. Also, A T B whenever B T A
Theorem 6. Let 2 and T E Tz" Then either E Tecyctse or there exists k 2 1 such that the nodes can be partitioned into 2k + sets {Ai, A2...., AR, B1, . Bg, C} where
(a) The induced sub-tournament on each of the 2k + sets belong to aeyyelc
(b) A T
A, B, Bj
Vi j
(c) A T vi J: A <T Bj Vi <j
(d) B C Vi.j
Figure (right) gives a graphical representation of the structure of T2" described Theorem The following theorem sheds light on the rich expressivity of the T2 tournament class.
Theorem (Long Cycles and Arbitrary Triplets) Given any arbitrury ordered set of indices fii, .k............ ; k n, there exists T E T such that i >T 12 >T ... ... in >T it. Further- more. Given any P2,P2,P1 E (0, 1) and indices i1, 11,12,00 i3 E [n], there exists a pairwise preference matrix P whose associated Tp E T2" where P P(i,, i2) P1. P(2,, ((2,iz) p2, P(ig, 11) Ps.
5.1 Polynomial Time Algorithm for MFAST for T2"
We present polynomial time algorithm for MFAST for the T2" class. The algorithm Rank2Rank (Algorithm 2 takes as input tournament T and outputs a permutation o" that is MFAST-optimal for T whenever T E Tz". The algorithm finds such o² by relying crucially on the structural understanding gained in the previous section via forbidden configurations. In the following, given set of nodes A and a tournament we represent the induced tournament on by T TA.
Algorithm 2 Rank2Rank-R22
Algorithm BlockRank2Rank BR2R
1: Input: A tournament T
1: Input: A tournament T
2: T E Tacyelic then
2: if E Trayclicc then
3: Obtain by Topological sort of
3: Obtain o* by Topological sort of T
4: else
4: else
5:
Find {a, b, s.t
>T a)
5: Find {a, s.t (a >r >T >T a)
6:
c > 1 B [b) [ ( and >r
A = {a] (i
6:
5 = =i:: >T (a,
7:
7: S = = (a,b,c)
8:
C = Uf:: i a and b >>T/ i}
8:
S = |n]\fS+
9:
σo [R2R(Txx) R2R ()), (2)(T)))
a" [BR2R (2R(TTT) (R2R(TTT)))
10:
Let a be the permutation obtained by a cyclic shift of on by h positions.
10: end if
11: Output
11:
Let o be the permutation among d, vh which has the least size of the feedback are set w.r.t T i.c., o² = arg min Fo, h
12: end if Output a²
Theorem 8. I E T.h is given input to the Rank2Rank (Algorithm (2,, the output a² produced by the algorithu is MFAST-optimal for T. Furthermore, Ronk2Rank has a time complexity of poly(n).
Geometric Sweep Interpretation: One can also come up with geometric sweep algorithm to solve MFAST problem for 7,"h 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 TR² plane in the counter clockwise direction from the embedding of thus creating permutation do 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 Tg. We argue the appendix that the optimal that solves the MFAST problem w.r. T must necessarily be one of these permutations. We note that while the Geometric sweep algorithm needs the embeddings to be known, the Rank2Rank algorithm does not need the same.
6 Block T2" Class
Often in practical applications, items can be clustered into blocks such that within block they exhibit certain local pairwise preference whereas across blocks they exhibit 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-globel pairwise preference model.
6.1 Local-Global Preference Model
The local-global pairwise preference model is parameterized by three vectors s, u, V E R and ordered partition of [n] given by (H1,..., H&) 2(x] where Hh = [m] and H; n H = 1
Let g(ā) denote the partition in which item is present. We assume that > 8j * g < gū) ie.. 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
u,yy B. 3f s.t i, j He
(Pp.) =
8; 5j otherwise
F shows some flexible tournament structures that arise out of the local global model and Figure T shows several real world tournaments that have associated tournmments arising out of this model.
One can interpret the above model as follows: The set [n] items is divided into blocks/partittinn.. Restricted to each block, the local pairwise preference matrix has associated tournament that belongs to T2" which can potentially contain cycles. However, across partitions, the preference matrix behaves like standard BTI. type model parameterized by the score vector and hence the associated global block level tournament relation belongs to seyccli The tournament associated to the entire set of n nodes thus has 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 = 1 and 6 is the logit link.
We refer to the class of tournaments that arise out of a local-global model as the Block T class.
Theorem 9. I E Block-T?" is given as imput to the BlockRank2Rank (Algorithm) 3). the oulput a' produced by the algorithm if optiial for T. Furthermore, BlockRank2Rone ank has a time complexity of poly(n).
7 Learning to Rank From Pairwise Comparisons under Block-
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- Towards this, we propose the PairwiseelockRand algorithm (Algorithm 4.. Given a dataset of pairwise comparisons, the algorithm constructs the empirical pairwise comparison matrix. It applies the link function @ to construct empirical skew-symmetric matrix with missing entries (corresponding to pairs that are not compared in the dataset). The algorithm then applies matrix completion routine to complete the -kew-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 the number of blocks.
Lemma 10. Let T e Block-Te T with b blocks. Then T T," for some r S 4b.
The following theorem establishes sample complexity of learning for recovering the blocks correctly.
7

---

Algorithm 4 PairviseeBockRamu
1: Input: D = {(ik, Jk), ykk,, k {1, ...., m) link
function o, rank r
2: Compute Empirical pairwise preference matrix:
3: (i.j) = (ik, Jk for some & then
4:
P.j = k== (--()=)
(x== Ps. =
else
Ps = Ps: =0
end if
7: M = Matrix-Cooplation
Figure 5: Example of few Flexible Tournament Structures arising out of the local-global model with 1,2 and 3 blocks.
8: Construct Tournament T from M where (i.j) E
whenever M. >
9: a² = BlockRank2Rank BR2R(T)
10: Output o'
Theorem 11. (Block Recovery) Let the local global model be parameterized by vectors u1 V,8 E Th"" and ordered partitions (H1...., Ho) and a skew symmetric link function 6. Let m pairs be chosen uniformly at random from all subsets of (2) of size and let each pair be compared K times according to the corresponding preference matrix P. Let O = minss |1,31 - uuuyl where (i.j) are in the same partition and lel
min |s; 8و1 where (i.j) are different partitions. Let O < c < (2) Then with probability at least - 2 if is ((nblog(n)) and K is O ((bla((m)) ), the PairwiseBle ranking a that respects the bluck structure i.e. (i) < (j) whenever i E Hy and E He ve > k.
nă
algorithm on running with the dataset generated as above, returns
8 Experiments
Datasets: We use the following real world datasets (with n items to be ranked and m pairwise
comparisons): DoTA [ (n = 757, 10442). Tennis 2 (n 742, 23806), Sushi-A [TS]
(n = 10, m 100000), Sushi-B [15 (n = 100, m = 25000), Jester 13 (n- 100, m = 891404).
Given set of pairwise comparisons, we do a 70 30 trainttest split. We run the algorithms on the train data obtain ranking a. We test the performance of on the test set by computing the ratio of upsets(the pairs (i,j) for which a(j) < (ii) but the fraction of times being preferred over in the test set 2 0.5) and the number of unique pairs in the test data.
Setting + Performance measure:
Algorithms:
MC Copeland: We first complete the empirical preference matrix P using matrix-completion
(MC) routine with rank 2 and then the standard Copeland procedure 1T0 to get ranking.
MC Borda: Same as Copeland but the standard Borda algorithm 21 is used instead of Copeland to obtain ranking from the completed ranking.
Rank Centrality: spectral ranking algorithm that ranks based on computing a stationary distribution Markov chain associated with
Blade-Chest: A maximum likelihood based algorithm for the Blade-Chest model 7 where we set the dimension of the emdedding 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 real- world data, in each recursive call, procedure depending on whichever better for the given data.
either the ranking given by the algorithm or the Copeland
The results are presented in Table I averaged over 20 splits. As can be seen, the Pairwise 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
8

---

Algorithml
MC Copeland
MC + Borda
Rank Centrality
Blade-Chest
Pairwise Rank
Block-
Dataset
DOTA
0.311 1:001
0.368 +0.03
0.215 +0001
0.228 =:001
0.23
+0.03
Tennis
0.314 #0.005
0.314=0.006
0.285 #0.008
0.311 #0.006
0.281 #0,006
Sushi-A
0.002
0.18 +-002
0.042
+-001
0.06++0.01
0.034 +0.02
Sushi-B
0.176+000006
0.188=000005
0.176
+0.006
0.176 0.203=000066
Jester
0.05 =0.001
0.23 #0.002
0.05 =0.001
0.15
=0.022
0.05 #0.001
Table I: Results on real-world datasets. Algorithms with the best results are in boldface.
Upsets K with Known Traction-. - 21/mum blockstininin
Uppets vs Known Fraction with K- 10%/metrix renkrinnin
X5000
Outimal
50033
Optimal
40000
MC Copeland
45030
NC Copeland
MC Bords
<0033
NC Borda
35000
Park Centrality
Rank Centrality
35000
33000
25000
25003
20200
20000
15930
K. 24 multiple of (matrix rank)*in)
Known Fraction as multiple of (num blaccis)"n/jnn
Figure 6: Results for P under local-global model with 3 blocks. Refer Section & for details.
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 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 B. Known fraction (3) 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 3 and varied K and other where we fixed K and varied B. Thus for every experiment K.3. (800) comparisons are made in total. Figure shows the results from varying K and the known fraction. The results are averaged across 10 runs. As can be seen, for the MC + PairwiseeBockRear 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 3 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.
algorithm, the pairwise disagreements quickly approach
9 Conclusion
In this work, study the class of parametric preference matrices which induce cyelic tournaments. We propose algorithms that solve the MFAST problem on rank 2 classes and build on the rank 2 class to propose flexible model called the local-global model. For the general rank 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 acyelic relations. The broader impact 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.

---

References
[1] Dota data: http:://ww.datdoottt
[2] Tennis data:
[3] Noga Alon. Ranking tournaments. SIAM Journal on Discrete Mathematics, 20(1):137-142, 2006.
[4] Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4)3324 345, 1952.
[5] David Causeur and François Husson. 2-dimensional extension the bradley-terry model for paired comparisons. Journal of statistical planning and inference, 135(2):245-255) 2005.
[6] Pierre Charbit, Stéphan Thomassé, and Anders Yeo. The minimum feedback are set problem is np-hard for tournaments. Combinatorics, Probability and Computing, 16:01-04, 2007.
[7] Shuo Chen and Thorsten Joachims. Modeling intransitivity in matchup and comparison data. In Proceedings of the ninth acm international conference on web search and data mining, pages 227-236, 2016.
[8] Xujin Chen, Guoli Ding, Wenan Zang, and Qiulan Zhao. Ranking tournaments with no errors i: Structural description. Journal of Combinatorial Theory, Series B, 141:264-294, 2020.
[9] Xujin Chen, Guoli Ding, Wenan Zang, and Qiulan Zhao. Ranking tournaments with errors if: Minimax relation. Journal of Combinatorial Theory, Series B, 142:244-275, 2020.
[10] Don Coppersmith, Lisa Fleischer, and Atri Rudra. Ordering by weighted number of wins gives a good ranking for weighted tournaments. In Proceedings of the seventeenth amnual ACM-SIAM symposium on Discrete algorithm, pages 776-782, 2006.
[11] de Caen. The ranks of tournament matrices. The American mathematical monthly, 98()): 829-831, 1991.
[12] David F Gleich and Lek-heng Lim. Rank aggregation via nuclear norm minimization. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and dutu mining, pages 60 68, 2011.
[13] Ken Goldberg, Theresa Roeder, Dhruv Gupta, and Chris Perkins. Eigentaste: A constant time collaborative filtering algorithm. information retrieval, 4(2):133-151, 2001.
[14] Bruce Hajek, Sewoong Oh, and Jiaming Xu. Minimax-optimal inference from partial rankings. arXiv preprint arXiv:1406.5633 2014.
[15] Toshihiro Kamishima. Nantonac collaborative filtering: recommendation based order responses. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 583-588, 2003.
[16] Raghunandan H Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from noisy entries. The Journal of Machine Learning Research, 11:2057-2078, 2010.
[17] Duncan Luce. Individual choice behavior: A theoretical analysis. Courier Corporation, 2012.
[18] Rahul Makhijani. Social choice random utility models of intransitive pairwise comparisons. arXiv preprini 1810002511 2018.
[19] Rahul Makhijani and Johan Ugander. Parametric models for intransitivity in pairwise rankings. The World Wide Web Conference, pages 3056-3062, 2019.
[20] Sahand Negahban, Sewoong Oh, and Devavrat Shah. Rank centrality: Ranking from pair-wise comparisons, 2015.
[21] Arun Rajkumar and Shivani Agarwal. A statistical convergence perspective of algorithms for rank aggregation from pairwise data. In International Conference Muchine Learning, pages
1 118-126. PMLR, 2014.
10

---

[22] Arun Rajkumar and Shivani Agarwal. When can we rank well from comparisons of o (n llgg (n)) non-actively chosen pairs? In Conference on Learning Theory, pages 1376-1401. PMLR, 2016.
[23] Georg Schökle. Skew symmetric bilinear forms. URt/htt::/wwwwmmthh uni-konstanz de//algobraaPProsemnnnaa.a - http://arr....a2222.///aaaooo... /ttp/a/mooou.ccooeeeeepppptteeee pdf
[24] Nihar Shah, Sivaraman Balakrishnan, Joseph Bradley, Abhay Parekh, Kannan Ramchandran, and Martin Wainwright. Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence. In Artificial Intelligence and Statistics, pages 856-865. PMLR, 2015.
[25] Louis Thurstone. A law of comparative judgment. Psychological review, 34(4):273, 1927.

---

Checklist
Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section and the Broader
Impact section after conclusion.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See the Broader Impact section after conclusion.
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] The proofs are included in the supplementary material due to lack of space.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] Refer to & and supplementary.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (c.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A] Obtained data from source which gives permission for usage when cited.
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A] No personal data used.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "HR54EAbQF43", "reviewer": "Reviewer_qX9G", "summary": "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.  \n\nThe 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.\n \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The feedback arc set problem is certainly very important. However, I am not very convinced that the restriction considered (i.e., defined by such matrices) is very interesting in terms of applications. For instance, the results are applied to the so-called local-global preference model, which is defined in the paper, but whose importance is not really clear.\n \nThe writing is overall OK, but sloppy at times (see below).\n\nOverall, the paper is good, but the motivation and importance of this specific problem/model are unclear.\n \nSpecific Comments:\n\nLine 55: “See” should not be capitalized.\nLine 64: “as” should be removed.\nLine 74: “for the same” -- > “for the problem”.\nLine 115: explain what “cdf” is. \nStep 2 in Algorithm 1: a comma is missing before “(x_k, y_k)”.\nLine 144: remove “as”. “w.r.t” -- > “w.r.t.”.\nLine 152: “Inability” -- > “The inability”.\nLine 156: a period is missing at the end of the line. \nLine 181: “present the same”, please rephrase. \nLine 183: What is “cone (U \\cup V)”?\nLine 219: a period is missing at the end of the line. \nLine 257: extra space after “(“.\nLines 284 and 287: a period is missing at the end of each line. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "Gp7bCb-L5Ue", "reviewer": "Reviewer_fvcq", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality/Significance:\nThe results appear to be original and are very interesting from a complexity perspective. The proposed model and algorithm contribute significantly to both the optimization of the MFAST and tractable modeling of ranking from pairwise comparisons in practice. \n\nQuality:\nThe writing is of high quality. Due to very limited time I could not check the technical details and thus cannot judge correctness of the claims.\n\nClarity:\nThe paper is quite clear overall. Unfortunately, the authors did not number the references in the bibliography although they use number citations (they seemed to be in the right order, however).\n\nQuestions:\nIt would be great if the authors could point out how their results depend on the link function. In other words, are the claims still true if we simply assume an arbitrary skew-symmetric rank-2 matrix $M \\in \\mathbb R^{n \\times n}$ ? In this case the results would be even more interesting.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paragraph on broader impact is adequate.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "AsOL1ndwLWu", "reviewer": "Reviewer_AqtE", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper tackles an important problem and the solution provides a novel view of the classical problem. Eventhough the most theoretical contribution is restricted by the preference matrix with rank 2, the experiemnts in a flexible setting show promising results. \n\nHere are some questions and suggestions.\nIn the contribution, the authors claim that the proposed algorithm can solve MFAST problem with rank 2. However, in the synthetic experiments, the algorithm does not recover the optimal solution. Is this because the synthetic dataset is not a tournament? It might be good to include synthetic tournament experiments and analyzes the effect of preference matrix rank other than 2.\n\nThe performance metric is not normalizes, which makes it harder to compare across different datasets.\n\nThe algorithm 4 is named PairwiseBlockRank but Theorem 11 uses ParametricBlockRank. \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": " The authors adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers are satisfied with the author responses and agreed with acceptance. The authors incorporate reviewer feedback and additional experiments presented in the rebuttal in the final manuscript.
Decision: Accept (Poster)