A Theory of Tournament Representations
Authors: Arun Rajkumar
Vishnu Veerathu
Abdul Bakey Mir
Venue: ICLR 2022 Poster (2022)
Keywords: tournament
skew-symmetric
pairwise ranking

Abstract: Real-world tournaments are almost always intransitive. Recent works have noted that parametric models which assume  $d$ dimensional node representations can effectively model intransitive tournaments. However, nothing is known about the structure of the class of tournaments that arise out of any fixed $d$ dimensional representations. In this work, we develop a novel theory for understanding parametric tournament representations. Our first contribution is to structurally characterize the class of tournaments that arise out of $d$ dimensional representations. We do this by showing that these tournament classes have forbidden configurations that must necessarily be a union of flip classes, a novel way to partition the set of all tournaments. We further characterize rank $2$ tournaments completely by showing that the associated forbidden flip class contains just $2$ tournaments. Specifically, we show that the rank $2$ tournaments are equivalent to locally transitive tournaments. This insight allows us to show that the minimum feedback arc set problem on this tournament class can be solved using the standard Quicksort procedure. We also exhibit specific forbidden configurations for rank $4$ tournaments. For a general rank $d$ tournament class, we show that the flip class associated with a coned-doubly regular tournament of size $\mathcal{O}(\sqrt{d})$ must be a forbidden configuration. To answer a dual question, using a celebrated result of Froster, we show a lower bound of $\Theta(\sqrt{n})$ on the minimum dimension needed to represent all tournaments on $n$ nodes. For any given tournament, we show a novel upper bound on the smallest representation dimension that depends on the least size of the number of unique nodes in any feedback arc set of the flip class associated with a tournament. We show how our results also shed light on the upper bound of sign-rank of matrices. 

Published as a conference paper at ICLR 2022
A THEORY OF TOURNAMENT REPRESENTATIONS
Arun Rajkumar
Abdul Bakey Mir Indian Institute of Technology
Vishnu Veerathu Cohesity Inc
Indian Institute of Technology RBCDSAI, IITM
ABSTRACT
Real world tournaments are almost always intransitive. Recent works have noted that parametric models which assume d dimensional node representations can effectively model intransitive tournaments (Rajkumar & Agarwal (2016)). How- ever, nothing is known about the structure of the class of tournaments that arise out of any fixed d dimensional representations. theory for understanding parametric tournament representations. Our first contri- bution is to structurally characterize the class of tournaments that arise out of d dimensional representations. We do this by showing that these tournament classes have forbidden configurations which must necessarily be union of flip classes, a novel way partition the set of all tournaments. We further characterize rank 2 tournaments completely by showing that the associated forbidden flip class con- tains just tournaments. Specifically, we show that the rank 2 tournaments are equivalent to locally-transiin the minimum feedback are set problem on this tournament class can be solved using the standard Quicksort procedure. For general rank d tournament class, we show that the flip class associated with coned dooelyy regular tournament of size dVv)) must be a forbidden configuration. To answer a dual question, using a celebrated result of Forster & Simon (2006), we show lower bound of Si( (n)) on the minimum dimension needed to represent all tournaments on n nodes. For any given tournament, we show novel upper bound on the smallest representation dimension that depends on the least size of the number of unique nodes in any feedback set of the flip class associated with tournament. We show how results also shed light on upper bound of sign-rank matrices.
this work, we develop a novel
tournaments. This insight allows us to show that
INTRODUCTION
In this work, we lay the the foundations for theory of tournament representations. A tournament is complete directed graph and arises naturally in several applications including ranking from pairwise preferences, sports modeling, social choice, etc. We say that a tournament T on n nodes can be represented in d dimensions if there exists skew symmetric matrix M E R of rank d such that a directed edge from to j is present in T if and only if Myj > O. Real world tournaments are almost always intransitive (Tversky (199)); Klimenko (015)) and it is not known what type of tournaments can be represented in how many dimensions. This is important to understand because of the following reason: As a modeler of preference relations using tournaments, it is often more natural not have
to have structural domain knowledge such as 'The tournaments under consideration long cycles' opposed to algebraic domain knowledge such 'The rank of the skew symmelric matrix associated with the tournaments of interest is at most k'. However, algorithms that learn rankings from pairwise comparison data typically need as input the algebraic quantity the rank of the skew symmetric matrices associated with tournaments or cquivalently the dimension where they are represented (Rajkumar & Agarwal (2016)). To bridge the gap between the structural and the algebraic world, we ask and answer two fundamental questions regarding the representations of tournaments.
1) What structurally characterizes the class of tournaments that can be represented in d dimensions?
2) Given tournament T n. nodes, what is the minimum dimension d needed to represent it?.

---

We answer the first question by investigating the intricate structure of the rank tournament class via the notion of forbidden configurations. Specifically, we show that the set of forbidden config- uration for the rank d tournament class must necessarily be a union of flip classes, a novel way to partition the of all tournaments into equivalence classes. We explicitly characterize the forbidden configurations for the rank 2 tournament class and exhibit forbidden configuration for the general rank d tournament class. Specifically, transitive tournaments, a previously studied class of tournaments (Cohen et al. (2004). Our results throw light on the connections between transitive and locally transitive tournaments and also lets us develop classic Quicksort based algorithm to solve that the minimum feedback are set problem on rank 2 tournaments with O(n²) time complexity. Our results for the general rank d tournament class have connections to the classic long standing Hadamard conjecture and we discuss this well. Published as a conference paper at ICLR 2022
FLIP CLASS
FLIP CLASS
FLIP CLASS k
FLIP CLASS
Transitive
R- cone
Locally Transitive
2d-Representable
Forbidden
Representable
Forbidden
Figure I: (Left) Partitions of the set of all tournaments on n nodes using flip classes. Every shaded region is flip class partition and every circle indicates tournament. The flip class that contains the transitive tournament (Flip class 1) is precisely the set of all locally transitive tournaments. This is also the set of all tournaments that can be represented in dimensions (Section [p. Every flip class contains a canonical representative termed the R-cone (Section 4), indicated using the larger circle inside each flip class. The tournaments that cannot be represented using d dimensions appear as union of Forbidden Flip classes (Flip class k in Figure) (Section 4. (Right) Explicit flip class partition of the possible non-isomorphic tournaments on nodes. Tournaments in flip class can be represented using dimensions whereas tournaments in flip class 2 cannot (see Section
show that the rank tournaments equivalent locally
Figure gives a glimpse of some of the main results.
We answer the second question by proving lower and upper bounds the smallest dimension needed to represent a tournament on n nodes. We exhibit a lower bound of 92( (V( using a variation of the celebrated dimension complexity result of Forster & Simon (2006) for sign matrices. To show upper bounds, we introduce a novel parameter associated to a tournament called the Flip Feedback Node of Tournament. This quantity depends on the least number of unique nodes in any feedback are set of an associated tournament class for the tournament of interest and upper bounds linearly the representation dimension of any tournament. We show how our results can be used provide upper bounds on the classic notion of sign-rank of matrix. Previously known upper bounds for sign rank depended on the VC dimension of the associated binary function class (Alon et al. (2016)) Our upper bounds on the other hand have graph theoretic flavour.
Organization of the Paper:
We discuss briefly in Section 2 the foundational works this paper builds
upon. We introduce necessary preliminaries in Section 3 The answer to the first question about structural characterization of d dimensional tournament classes span Sections 5 and 6 We devote Section 7 answer the second question about the number of dimensions needed to represent a tournament.
connections of our results to upper bounds on the sign rank of sign matrix. Finally, conclude in Section 10] All proofs are defered to the Appendix.
2 RELATED WORK
The work in this paper builds on several pieces of work across different domains, We summarize below the most important related works under different categories:
2

---

Published as a conference paper at ICLR 2022
Intransitive Pairwise Preference Models: One of the main reasons to study representations of tournaments is to model pairwise preferences. Parametric pairwise preference models that can model intransitivityy have gained recent interest. Rajkumar & Agarwal| (206)) develop a low rank pairwise ranking model that can model intransitivity. However, their study and results were restricted to just the transitive tournaments in these classes. A generalization of the classical
-ornlly--Trry-Luuce model (Bradley& & Terry| (1952), Luce (2012) was studied in Causeur & Husson (2005). However, no structural characterization known. Same holds for the more recent models studied in Chen &
Joachims (0116) Makhijani & Ugander (2019) and Bower & Balzano (2020).
The notion of flip classes, novel way to partition the set of all tournaments on n nodes, was first introduced in Fiiherr & Ryan (1995). The goal however was completely different and was on studying equilibrium on certain generalized paek-paper-scissors games on tournaments. Interestingly, and perhaps surprisingly, the notion of flip classes turn out to be fundamental to our study of understanding forbidden configurations of d dimensional tournament classes.
Flip Classes:
Dimension Complexity and Sign Rank: Dimension complexity and sign rank of sign pattern matrices were studied in Forster (2002). These results have found significant applications in learning theory and lower bounds in computational complexity (Forster & Simon| (2006)). More recently. Alon cet al. (2016) study the sign rank for function classes with fixed Vapnik-Chervoneen Chervonenkis (VC) dimension and show upper bounds. Our upper bounds however depend on certain graph theoretic properties.
3 PRELIMINARIES
Tournaments: A tournament T is a complete directed graph i.e., graph on n nodes where for every pair of nodes (i.j) either an edge is oriented from to j or j to i. The number of nodes in T will be usually clear from the context or will be explicitly specified. For nodes i and in T, we say i > j if there is directed edge from to j. Given node i, we define the out and in neighbours of as T {j= : >T j} and T. = (i >T i) respectively. Given a set of nodes S, we denote by ((S) the induced sub-tournament of T the nodes in S.
Feedback Are Set and Pairwise Disagreement Error: Given a permutation a on n nodes, the feedback arc of w.r.t the tournament T is defined as E (T) ((i,)) (i) > oi), >T.j jj.. The pairwise diagrcement error of a w.r. T is given by [T]] It is known that finding the o that minimizes the pairwise disagreement error w.r.t general tournament T is a NP-hard problem (Charbit et al. (2007))
Skew Symmetric Tournament Classes: A square matrix M E Ra** is skew symmetric if Mij -M Vi, j. In this paper, whenever we refer to a skew symmetric matrix M E RRxx, we always assume Mij * O Vi * j and M, = O Vi. Given such an M, we denote by [(M} the tournament on nodes induced by M where >T j + My > O. We refer class of tournaments induced by rank d skew symmetric matrices as the rank d tournament class.
Forbidden Configurations: A tournament class a collection of tournaments. T is said to forbid a tournament T if no tournament in T has sub-tournament that is isomorphic to T. We call T a forbidden configuration for T if T forbids T but does not forbid any sub-tournament of T. For example, the class of all acyclic/tansitivee tournaments has the 3-cycle as forbidden configuration ie, the tournament T on three nodes i, A where >T j >T k >T i.
Representations and Tournaments: The matrix A rot E dd is defined for every even d and is block diagonal matrix which consists of d/2 blocks of 10-1; 00. This is the canonical representation of non-degenerate skew symmetric matrix i.e., any non-singular skew symmetric matrix can be brought to this form by a suitable basis transformation. Given a set of vectors in H = (h,,.... h where each h; Rd for some even d, we refer to the set H as a tournament inducing representation if by" A A hj # 0 for all i + j. Furthermore, we refer to the tournament induced by H as T[H) where a directed edge exits from node i to j if and only if h? A z hj > O. It is easy to verify that h A rot h = 0 for any h E Rd. Any skew symmetric matrix M E IR R of rank d can be written as M = H A rot H for some H E Rdxn a It follows that if M H A rot H. then T(M) T(H.
Positive Spans: A set of vectors H = (h,...., h where each h, E Rd said to positively span Rd if for any w Rdd. there exists non-negative constants -1.-..y Cr. 2 0 such that Σ, cah; If
3

---

Published as a conference paper at ICLR 2022
H positively spans R., then there does not exist E R such that wTh, 0 Vi. This is easy consequence of Farkas' Lemma.
Remark on Notation: tournament induced by a subset of nodes, the tournament induced by a skew symmetrie matrix and the tournament induced by representation of set of vectors respectively. These will be usually clear from the context.
We reiterate that we use T(-) and T mean different objects the
4 FLIP CLASSES, FORBIDDEN CONFIGURATIONS AND POSITIVE SPANS
The main purpose of this section is understand the space of forbidden configurations of rank d tournaments, The main result of this section shows that the forbidden configurations for rank d tournament classes occur as union of certain carefully defined equivalence classes of non-isomorphic tournaments.. Towards this, we define the notion of flip classes which was introduced first in (Fisher & Ryan 1995) although in different context:
Definition 1. Given a tournament on n nodes and a set S S [n], define os (T) to be the tournament obtained from T by reversing the orientation of all edges (1,3) such that S S.
In other words, (T) is obtained from T by reversing the edges across the cut (S, {(i,5) i S,j 5).
Definition 2. class of tournaments on n nodes is called cut-equivalent for every pair of tourna- ments T, T' in the class, there exists a 8 S [mz] such that T is isomorphic to (T(
is easy to show that the set of cut-equivalent tournaments form an equivalence relation over the of all tournaments on n nodes Fisher & Ryan (1995). The corresponding equivalence classes are called a flip classes. We denote by F(T) the flip class of T i.e., the equivalence class of all equivalivl tournaments T. In the following theorem we show the fundamental relation between flip classes and forbidden configurations.
Theorem 1. Let T, lournament on k nodes, be a forbidden configuration for some rank d tourna- ment class. Then every tournament in the flip class of is also a forbidden configuration for the rank d tournament class.
Corollary 1. (Structure of Forbidden configurations) Forbidden configurations of rank tourna- ment classes unions of flip classes.
Thus, to characterize the forbidden configuration of rank d tournament classes, we need to understand the flip classes. We begin with the following simple but useful definition.
Definition 3. tournament is called a R-cone there exists a node i such that
1" > j for all j o it (j GT it for all j ii)
. T(T)) (T(T))) is isomorphic to the tournament R.
R-cones are essentially the tournament R along with an additional node that either beats or loses to nodes in R. R-cones useful they be viewed in some sense canonical tournaments in flip classes. This is justified because of the following observation.
Proposition 1. Every flip class contains an R-cone for some tournament R.
The above observation says that to identify the forbidden configurations for given tournament class, it suffices to identify all forbidden R-cones. Then by Corollary [T] the associated flip classes will be the set of all forbidden configurations. However, does not throw light on what property the tournament R must satisfy. The following lemma establishes this.
Lemma 2. Let R be a tournament with the property that if R = R(H] for some representation H (b..... b,, Rdd then H positively spans Rdd Then rank d tournament class forbids R-cones.
The above lemma is extremely helpful in the sense that reduces the study forbidden configurations to the study of finding tournaments such that any representation that induces it must necessarily
4

---

Published as a conference paper at ICLR 2022
positively span the entire Euclidean space. Note that there may be several representations which positively span the entire space. This does not mean their the associated coned tournaments are forbidden configurations. Instead, start with R cone and conclude is forbidden if every representation that induces necessarily positively spans the entire space. It is a non-trivial problem to identify such tournaments R. for arbitrary dimension d.
In the following sections, we explicitly identify the only forbidden flip class for rank tournaments, one forbidden flip class for rank 4 and then (a potentially weaker) forbidden flip class for the general rank d case.
RANK 2 TOURNAMENTS
LOCALLY TRANSITIVE TOURNAMENTS
The goal of this section is to characterize the forbidden configurations of rank 2 tournaments. Thanks to Lemma this reduces to the problem of identifying a tournament whose representation necessarily span the entire space. The following lemma exhibits this tournament.
Lemma 3. Let H (h1, h2, h2} R be two dimensional representation of nodes which induce a 3 cycle tournament. Then the set H positively spans R22. Furthermore, the 3 cycle is the only such tournament 3 nodes.
The above lemma immediately implies that coned 3-cycle is the only forbidden configuration for rank 2 matrices. This is indeed true. However, for the purposes of generalizing our result (which as will will be useful when discussing the higher dimension case), will view the 3-cycle special case of a doubly regular tournament (defined next).
Definition 4. A tournament on n nodes is said to be n-doubly regular if i = IT for all i
and T TJt k for some fixed for all +
Trivially the 3-cycle is the only 3-doubly regular tournament. The following lemma establishes that flip class of coned doubly regular tournament only contains itself.
Proposition The flip class of r-ddubby--euular-ccne does not contain any other tournament.
Theorem 4. 3-doubly-regulad regular-conne cone is the only forbidden configuration for the rank tournament class.
We have thus far established that any rank tournament on n nodes forbids the 3-doubly-regular-con The advantage of this result is that we can go one step further and explicitly characterize the rank tournament class. To do this, we need the definition of a previously studied tournament class.
Definition 5. A tournament T is called locally transitive for every node in T, both T(T;) and T(T: are transitive tournaments
Before seeing why locally transitive tournaments are relevant to our study, we first show that they are intimately connected transitive tournaments via the following characterization.
Theorem 5. (Connection between Transitive and Locally Transitive Tournaments) The set of all non isomorphic locally transitive tournaments on n nodes is equivalent to the flip class of the transitive lournament n nodes.
We will next that this key result allows to immediately characterize the rank 2 tournament class. We will see later (Section[7 7 that this result also crucial in determining an upper bound on the dimension needed represent a given tournament.
Theorem 6. (Characterization of rank 2 tournaments) A tournament T nodes is locally transitive if and only if there exists a skew symmetric matric M E Raxx with rank(M) = such that the T [[M] T.
It is perhaps surprising that a purely structural description of tournament class namely that of local transitivity turns out to be exactly equivalent to the rank 2 tournament class. To the best of knowledge, this characterization appears novel and hasn't been previously noticed. One of the interesting consequence of the above characterization is that the minimum feedback are set problem rank 2 tournaments can be solved using standard quick sort procedure. This is formalized below.
5

---

Published as a conference paper at ICLR 2022
Theorem 7. (Minimum Feedback Are Set is Poly-time Solvable for Rank 2 tournaments) Let T be a locally transitive tourament on n. nodes and let 01 be the permutation returned by running standard quick sort algorithm choosing 1 the initial pivot node and where the outcome of comparison between items i and j is i if and only if TT j. Let ag be obtained from on by k - clockwise cyclic shifts for k [n]. Let E&g be the feedback are set of on w.r. T. Then ming [Egl achieves the minimum size of the feedback are ser T.
Proof. (Sketch) The proof involves two steps: first arguing that by fixing any pivot, quick sort would return ranking that is a eyclic shift of 01 The second step involves inductively arguing that one of the cyclic shift must necessarily minimize the feedback arc set.
5.1 RANK 4 TOURNAMENTS
We now turn to rank 4 tournaments. We could have direetly considered rank d tournaments, but it turns out that what we can show slightly stronger result for rank tournaments than the general case and tournament that necessitates the positive spanning property, it is not immediately clear in the rank 4 case. A first guess would be to consider the regular tournaments (as the 3 cycle for rank is also a regular tournament) on 5 nodes or 7 nodes. However, these turn out to be insufficient as one can construct counter examples of regular tournaments on up to 7 nodes with representations that don't t span the entire R. In fact, as we had defined earlier, the right way to generalize to higher dimension turns out to be using doubly regular tournaments.
focus on them separately. While it is arguably simple in the rank 2 case to identify the
Theorem 8. The 11
is forbidden configuration for rank 4 tournament class.
Note that while for the rank 2 case, we were able to prove that the only forbidden flip class is the one that contains a coned 3 cycle, we have not shown that the only forbidden configuration for rank 4 class is the 11 doubly regular cone. In fact, we believe that the smallest forbidden tournament for rank 4 class is the 7- doubly regular cone. However, we haven't 't been able to prove this. This appears to be a non-trivial problem. From our simulation experiments, we observe that the only flip class that could be forbidden on 8 nodes is the that contains the 7-doubly regular cone. In particular, we were able to produce examples of representations for all other flip classes on nodes. However, this does not imply that the ones where we could not produce forbidden configuration is in fact forbidden. Unfortunately, it seems tricky to prove this and we don't 't have way to show this at this point. On the other hand, as we will see in the next section, the result in Theorem 8 is still stronger than the result for the general rank d tournaments.
Having discussed rank 2 and rank 4 cases separately, we next turn our attention to the general rank d tournament class.
6 RANK d TOURNAMENTS AND THE HADAMARD CONJECTURE
From the understanding of rank and rank 4 tournament classes in the previous sections, and noting that the corresponding forbidden configurations are intimately related to doubly regular tournaments, is tempting to conjecture that this is true in general.
Conjecture 1. Rank 2d tournament class forbids 4d L-douuby--egular-coom
Ideally, the conjecture above must have qualifier 'if they exist' for the 4d - 1 doubly regular cone. This is because of the equivalence between doubly regular tournaments on 4d nodes and
Hadamard matrices in {+1, -1] -1]4dx4d (Reid & Brown 1972)). A matrix H E {+1, - 11)1.-111 ] is called Hadamard if H'H n where / is the identity matrix. It is known that there bijection between skew Hadamard matrices and doubly regular tournaments Reid & Brown (972)). A long standing unsolved conjecture about Hadamard matrices is the following:
Conjecture 2. (Hadamard) There exists Hadamard matrix of order 4d for every d > 0.
If Conjecture [ were truc, then it would imply the existence of 4d - 1-doubly regular tournament for every d and thus would imply the Hadamard conjecture is true. In fact, Conjecture Tbingg true would say more which we state below:
Conjecture 3. There exists skew symmetric Hadamard matrix of order Ad for every d > 0.

---

Published as a conference paper at ICLR 2022
The main result of this section is weaker form of the conjecture:
Theorem 9. Rank 2(d 1) tournament class forbids 12d 1-doubly-regallarccnes if they exist.
How MANY DIMENSIONS ARE NEEDED TO REPRESENT A TOURNAMENT?
The previous sections considered specific rank d tournament class and tried to characterize them using forbidden configurations. In this section, We turn to the dual question of understanding the minimum number of dimensions needed embed tournament. We start by not considering single tournament T but the set of all tournaments on n nodes. We show below a general result which provides a lower bound on the minimum dimension needed to embed any tournament on n nodes.
Theorem 10. (Lower Bound on minimum representation dimension) Let T be tournament on nodes. Then there exists H = (hi....,h,, E R such that T = T[ only if ( (T+))))) 2 n². Furthermore, let d be the minimum dimension needed to embed every tournament on nodes. Then, d 2 vn.
The result follows the arguments in the celebrated work of Forster & Simon (006). As Alon et al. (2016) point out, Forster's technique cannot be stretched further in obvious ways to get upper bounds.
The above theorem tells that in the worst case at least D (n)n) dimensions are necessary to represent all tourmaments on n nodes. In fact if Conjecture [ were true, the minimum dimension would be M(n). However, in practice one might not encounter tournaments with such extremal/worst-case properties.
The lower bound for the representation dimension of random tournaments (where the orientation of each edge is determined by an unbiased Bernoulii coin toss) will depend on the singular values of random tournaments. However, we don't 't expect the representation dimension to be of independent of n, the number of nodes. Loosely speaking, a doubly regular tournament is "like" random tournament (the associated Hadamard Tournament has been used in deterministic perturbation schemes as alternatives for random sign matrices (Bhatnagar et al. (2003)). On the other hand, the most interesting weal-world tournaments might be characterized by constant sized node representations and hence may be structurally much more constrained than random tournaments. Typically, a smaller number of dimensions might be enough to represent tournaments of practical interest.
Remark:
Our goal below is to upper bound on the number of dimensions needed to embed a given tournament T.
Recall that E" (T) denotes the feedback are set of a permutation a w.r.t a tournament T. We define the number of nodes involved in the feedback are set follows: A(,, T) Hi: Rj oi) > o(j), (i,j) E E (T))- We next define a crucial quantity ((T) which we term as the Flip Feedback Node set size. This quantity will determine an upper bound on the dimension where a tournament can be represented:
Definition 6. Given a tournament T, define the Flip Feedback Node Set Size as follows:
(T) = min min A(a, T') T'EF(T)
In words, given tournament T, the quantity (T) captures the minimum number of nodes involved in any feedback are set among all tournaments the flip class of T. For instance if T is a locally transitive tournament then (T)) would be 0 as T is necessarily in the flip class of transitive tournament and so the E corresponding to the topological ordering of the transitive tournament would have an empty feedback are set. As another example, consider T to be the coned 3-cycle. The flip class of this tournament contains only itself and the best permutation will have one edge in the feedback are set. Thus (T) 1. In general, it is trivially true that μ (T) is upper bounded by n, the number of nodes. Howeverı (T) could be much smaller than n depending on T. The main result of this section is the theorem below that shows that (T) gives an upper bound on the number of dimension needed to represent any tournament.
Theorem 11. (Upper Bound on minimum representation dimension) For any tournament T, there exists H (bi..... hr) E R2()(T)+1) such that T H).
7

---

Published as a conference paper at ICLR 2022
1
3
Figure 2: A simple tournament to illustrate that the quantity (T) need not be same as the size the minimum feedback are set. All edges go from left to right except the ones in red. See Remark 2 in Section 7 for details.
Remark 1: The above theorem says that one can always obtain an representation H in dimension d == (T())) that induces T. The bound gets tighter for tournaments with smaller feedback sets, which is what one might typically expect in practice. Note that even for some tournaments that may have a large feedback are set, the associated flip class might contain a tournament with a smaller feedback arc set.
Remark 2: We note that in general (T()) is not necessarily the cardinality of the minimum feedback are set among all tournaments in the flip class of T. Instead μ(T) captures the cardinality of the set of nodes involved in any feedback are set. To see why these two could be different, consider the tournament in Figure
2 Here, Ja = [6 1 2 3 4 5] is the permutation minimizing the feedback are set. Let d [ 3 6]. Note that F. 2, (G T) [[1, , 2) 2. However | = 3, yet ((as: T) = [6} = 1. Thus, d gives tighter upper bound on the dimension needed to represent T.
APPLICATIONS OF THE RESULTS
8.1 CONNECTIONS TO SIGN RANK
The sign rank of a matrix G E {+1,-1]mxa exists matrix M E Rmxn of rank d that satisfies sign( (M) = G Here sigm(z) and otherwise. breakthrough result on the lower bound on the sign rank was given by Forster & Simon (2006). However, good upper bounds have been harder obtain. We show below how Theorem also translates to an upper bound on the sign rank of any sign matrix G.
defined the smallest integer d such that there if > O
Theorem 12. Let G E {+1, -1]mxn be an arbitrary sign matrix. Let T be any tournament on + n nodes. Let S f1...., m) and let edge orientations of the cut(S, in T be determined by G Then sign-rank( G) S ((p(T)++ +1
We argue that the the above result can give significantly tigher bounds than the bounds in Alon et al. (2016). The simplest example one consider is a locally transitive tournament n nodes. Viewing this as a sign pattern matrix, it is easy to argue that the VC dimension such a matrix is atmost 2. Theorem 5 in Alon et al. (2066) shows that the sign rank is upper bounded by O(vn)) when VC dimension is 2 (For a general hypothesis class of VC dimension d, the upper bound O(n'-á) On the other hand, by definition ((T) for any locally transitive tournament is exactly 0 (and so the upper bound of (T) + exactly and is tight) for any locally transitive tournament which independent of the number of nodes The important reason for this significantly improved bound while|Alon using (T) is that we consider only skew symmetric sign pattern matrices while Alon et al. (2016) look at the worst case (w.r.t representation dimension/sign rank) sign pattern matrices for fixed VC dimension. Our bound reduces the study of sign rank to a more graph theoretic study of the feedback
set problem. It is not clear if the upper bound of (T) + 1) can be improved and leave this to future work.
8.2 CONNECTIONS TO LEARNING FROM PAIRWISE COMPARISONS
Consider a learning to rank problem from pairwise comparisons. Here, set of n items need to be ranked from subset of pairwise comparisons among them. Every pair that is chosen for comparison is compared a fixed number of times. Every time items i and are compared, i is preferred over
'Sign-rank can he defined for any general matrix G Rmxn We restrict to the sign matrices to make the connections to the toumament matrices explicit
8

---

Published as a conference paper at ICLR 2022
with probability P.j. A common and popular model to capture these probabilities is the Bradley- Terry-Luce (BTL) model Bradley& & Terry (1522) where P., = s + 83) for some score vector E R". Note that the model completely specified by the score vector which in turn completely determines the probability preference matrix P. The learning problem is to learn these unknown score vector E R from noisy pairwise comparisons. Once the score vector is learnt, a ranking can be obtained by sorting these scores and the pairwise probabilities of unseen pairs of items can be predicted.
The above BTL model is an example of rank-2 model in the sense that the probability preference matrix P results in a rank 2 matrix under the log- log-odds skew symmetric transformation. Indeed, if we define M,y = log( (2) ). then equivalently M, = log(s:) - ).) It is easy to show that M is a rank skew symmetric matrix. However, the major disadvantage of the BTL model is that it can capture only transitive preferences i.c Ps >> 0.5 and Pa+ > 0.5 = Pkt > 0.5. In real world situations, intransitivity is very common. To achieve intransitivity. the simplest way would be to start with a general rank skew symmetric matrix M and consider the probability matrix that determines the preference probabilities as P.j 1/(1 + exp(-Ms, M,))). Here, the learning problem would be to estimate the two score vectors or equivalently the two dimensional representation for each item. Previous studies (Rajkumar& & Agarwal (2016)) show that this can be learnt using Matrix completion based approaches or maximum likelihood based approaches (Chen & Joachims (2016)). However, what was not known earlier is the structure of tournaments that can be captured using such low rank restrictions which is important to decide on the parameter r. Our work helps modellers make informed decision to choose based explicitly identifying the types of tournaments that can be modelled and subsequently learnt.
We discuss next simple application where modeling ranking from pairwise comparisons problem can benefit from the insights gained using our results. Consider a situation of modelling sports tournaments such as Tennis. Here, one can choose to model the players (nodes) using 2-dimensions where the dimensions corresponds to their offense (forehand) and defense (backhand) strengths respectively. When two players compete, the advantage of the offense strength of player w.r.t the defense of player 2 and vice versa determine the outcome of the match. This is precisely captured by a rank 2 model where the learning problem would be to infer these latent offense/defense strength of each player from outcomes of pairwise competitions. Theorem says that such model would immediately lead to locally transitive tournaments among the players. This structural characterisation now gives insights to the modeller if 2 dimensions are enough to model the players not.
9 REAL WORLD TOURNAMENT EXPERIMENTS
We conducted simple experiments on real world data sets Specifically, we considered 114 real world tournaments that arise in several applications including election candidate preferences, Sushi preferences, cars preferences, etc (source: www. preflib. org). The number of nodes in these tournaments varied from 5 to 23. Out of the 114 tournaments considered, (666.67%) were in fact locally transitive. For these tournaments, the upper bounds and lower bounds given by our theorems matched and was equal to 2. Interestingly, even for the non-locally transitive tournaments, the lower bound still turned out be 2. We computed the upper bound for tournaments of size at most 9 (we did not do it for larger tournaments as this involves brute force search) and found the value to be either or This shows that the upper bounds are usually non-trivial and efficiently approximating it is an interesting direction for future work.
10 CONCLUSION
In this work, we develop theory of tournament representations. We show how fixing the representa- tion dimension enforces, via forbidden configurations, restrictions on the type of tournaments that can be represented. We study and characterize rank tournaments and show forbidden sub-tournaments for the rank d tournament class. We develop upper and lower bounds for minimum dimension needed to represent a tournament. Future work includes attempting to look deeper into some of the conjectures presented and possible strengthening of some of the bounds presented.

---

Published as a conference paper at ICLR 2022
REFERENCES
Noga Alon, Shay Moran, and Amir Ychudayoff.. Sign rank versus vc dimension. In Conference on Learning Theory, pp. 47-80. PMLR, 2016.
Shalabh Bhatnagar, Michael Fu, Steven Mareus, and I-Jeng Wang. Two-timescale simulta- neous perturbation stochastic approximation using deterministic perturbation sequences. ACM Transactions on Modeling and Computer Simulation (TOMACS), 13(2):180-22)) 2003.
Amanda Bower and Laura Balzano. Preference modeling with context-dependent salient features. In International Conference Machine Learning, pp- 1067-1077. PMLR, 2020.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324 345, 1952.
David Causeur and François Husson. A 2-dimensional extension of the Bradley- model for paired comparisons. Journal of statistical planning and inference, 135(2):245-25,, 2005.
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.
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, pp. 227-236. 2016.
Nir Cohen, Marlio Paredes, and Sofía Pinzón. Locally transitive tournaments and the classification of {(1, (112)) -symplecccic metrics on maximal flag manifolds. Illinois Journal of Mathematics, 48(4): 1405-1415, 2004.
David C Fisher and Jennifer Ryan. Tournament games and positive tournaments. Journal of Graph Theory, 19(2):217-236, 1995.
Jürgen Forster. A linear lower bound on the unbounded error probabilistic communication complexity. Journal of Computer and System Sciences, 65(4):612-62) 625, 2002.
Jürgen Forster and Hans Ulrich Simon. On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes. Theoretical Computer Science, 350(1):40-48, 2006.
Alexander Y Klimenko. Intransitivity in theory and in the real world. Entropy, 17(6):4364 4412, 2015.
R Duncan Luce. Individual choice behavior: A theoretical analysis. Courier Corporation, 2012.
Rahul Makhijani and Johan Ugander. Parametric models for intransitivity in pairwise rankings. In The World Wide Web Conference, pp. 3056-3062, 2019.
Arun Rajkumar and Shivani Agarwal. When can we rank well from comparisons of O log(n)) non-actively chosen pairs? In Conference Learning Theory, pp. 1376-1401. PMLR, 2016.
KB Reid and Ezra Brown. Doubly regular tournaments equivalent to skew hadamard matrices.
Journal of Combinatorial Theory, Series A, 12(3):332-338, 1972.
Amos Tversky. Intransitivity of preferences. Psychological review, 76(1):31, 1969.
10

---

Published as a conference paper at ICLR 2022
A APPENDIX
Proof of Theorem
Proof. Assume there is a E F(T) which not forbidden for rank d tournament class. Thus,
HH' (h/ .......... h Rd such that T TH By definition, there must also exist S [x] such that T = Ts( Consider the representation H obtained from H' where h, = hh for all i S and h; hy otherwise. It easy to verify that T TH which is a contradiction to the assumption that T is forbidden configuration for rank d tournaments.
Proof of Proposition 1
Proof. Consider any tournament T. Let T = (oUT)) (T) for an arbitrary node i. By definition T E F(T). Also, T' is R-cone, coned by i.
Proof of Lemma 2
Proof. Consider any representation H that induces tournament R. By assumption of the theorem, H positively spans IRd. Thus, by Farkas' lemma, there cannot exist a v E Rd such that v v"h, > 0 Vi. Note that if R-cone is not a forbidden configuration for rank d tournaments, then there must exist a h Rd such that h Aro > Vi. As A is invertible, one can set = (Arot)?' with the property that v' 0 vi. But this contradicts the conclusion drawn earlier from Farka's s lemma.
Proof of Proposition 2
Proof.
This easily verified by checking all tournaments in F(T) where T is the coned 3-cycle.
Proof of Lemma
Proof. Wlog, assume that 2T 2 2T 2T 1. Then, it must be the case that the counterclockwise
angle between the representation of the corresponding items must be < 180 degrees. However, if the representations (h1, h2, h3) did not positively span R², then by Farka's Lemma, there must be some supporting hyperplane for the representations. However, this would imply at least one of the node pairs {1,, 2), (2, 3), (3, 1)} must necessarily make an angle 2 180 degrees. But this contradicts the assumption that the nodes form a cycle.
Proof of Theorem
Proof. Let be a transitive tournament on n nodes and let T E F(T). Then, there exists some S C [n] such that T' (T). Consider any node i [n]. Define following 4 subset of nodes associated with i: S T, S, T. (S1, S3 T, S, T, S.S Note that each of T(S)) for sets is either completely beats the other completely loses the other. Note that in (s(T) the orientation of the edges across these sets is either flipped as whole or not flipped at all. Thus, exactly of these sets will be part of T and two part of T; (the exact sets among these sets will depend on whether i E S or not), thus preserving the local transitivity property. Thus T' is locally transitive.
to is a transitive nub-tournament and the relationship across S,, for any two
To prove the opposite direction, let T be locally transitive tournament. Let i E [n]] be an arbitrary node. We argue that T' := d (T) ) is transitive tournament. We will show this by arguing that
there does not exist a 3 cycle in T'. Consider any 3-cycle >T b >T >T As T is locally transitive, not all {a, b, c} can be in T Also all {a, b, c} can avoid T as [m] T transitive. Thus least one and most two of {a, b, c) belongs to T (T). This means that the 3-cycle becomes a transitive tournament in T' == ΦT. (T). Thus every cycle in T becomes transitive in T'. Now consider any 3 nodes which forms transitive tournamen >T >T and involves at least one
11

---

Published as a conference paper at ICLR 2022
node and at most two nodes in TØ. Then there are only two cases consider: (1) [n] \ T
and {b, c} T or (2) {a, b} E [n]] TTT and с E T In both these cases, it is easy to verify that the the corresponding tournament in T' is either the transitive tournament b >T>> c >T a or the transitive tournament e >TV PT b. As these are the only possibilities, the result follows by noting that T = prt (T) = T = TT+ (T') and so T E F(T))
Proof of Theorem 6
Proof. Assume T is locally transitive. Then by Theorem 5 it must be in the flip class of some transitive tournament T' i.e. T = =T((T)) for some S S n. It is easy to represent a transitive tournament using rank 2 skew symmetric matrix. Indeed pick any vector E R which is sorted according, to the topological ordering of T'. Let v E IR" be the all ones vector. Then M uv vu" represents T Let M - (H² A for some H' RR2 Then the columns of H' represent TV. Now consider the representation H' obtained from H' where the columns indexed by S are multiplied by -1. This does not change the rank of H' and it can be verified that T T
To prove the other direction, consider any rank 2 skew symmetric matrix M E R"X", Then there must exist u, v E RD such that M uv vu" Consider any node E [m]. Consider three nodes a. b, c such that 1121 > u for j E {a, b. c). Furthermore let tha Uh > U2 ub and ugte >> Ugile. Then by carefully going over all {=] sign possibilities for {u, Na: Up, Ues U/ Var Ub ). one can conclude that it must be the case that 2 > Ue This just shows that TVf transitive. Analogously one can show that T, is also transitive. As was arbitrary, the result follows.
Proof of Theorem 7
Proof. Recall that the classic quick sort algorithm picks pivot node (say 1) and places all nodes that beat the pivot to the right in the ranking and those that lose to the left and then recurses on the left and right subsets. As T is locally transitive, choosing any pivot would correspond to fixing the pivots position and simply returning the ranking (N, ), (N where (N (N,") correspond to the topological ordering of the transitive tournaments T(N and T(N:) respectively. We first argue that changing the pivot only cyclically shifts the final ranking. To see why this is true, consider two pivots and j and their corresponding rankings a¹ and o Without loss of generality, assume that the ranking o² [l,.... n1] and >T j. We argue that there exists an integer such that N, = [ + mod n, (j + 2) mod n, n,..., (j + k)) mod n} (where by convention n mod n = n). As N is transitive, and j is part of it, it must be the case that all the nodes (j 1,.....,, + n) E Nz.. Then to prove the claim, it remains to be shown that the set N; n NJ is either empty or must be the nodes { .} for some / < i. If empty, we are done. If not, assume for the sake of contradiction that there exists three succesive integers la, ls, la < such that Ea, fa <T j but b, >T j. It is easy to verify that this cannot happen as it would lead to T(f Eo fe, j)) being forbidden configuration.
Notice that as every locally transitive tournament is in the flip class of a transitive tournament i.c.. T Øs (T) for some S. one can divide the set of all nodes into 2k 1 groups as follows: Let [L..... .2| be the ordering corresponding to the transitive tournament wlog. Starting from 1, add as many nodes
group such that all the elements belong to either S or S. Once the condition is violated, create a new group and continue the same process. It is not hard to verify that 2k + 1 groups will be formed in this process for some > Moreover, each group would separate two other groups by construction.
We can first show that the items of a single group must appear in consecutive positions one of the optimal rankings. This is proven follows.
Consider there exists an optimal ranking with items which belong to the same group not occurring consecutively. Consider two items belonging to the same group, which have items from other groups present in between them in the ranking. Consider these items to be a1, a2 with 01 present above in the rankings. Consider the number of upsets that the two items are involved in to be ij and u2. If U1 I U2 42 can be placed right after a in the ranking, creating a better or equivalent ranking in terms of upsets. Similarly if un u2, ai can be placed directly above dg in the rankings create
12

---

Published as a conference paper at ICLR 2022
equivalent better ranking. Therefore there exists an optimal ranking which has all items in the
same group consecutively.
This theorem is then reduced to finding ranking of groups, which is proven using induction on k.
Base Case
Consider the base with k = 1. Let there be groups, C, A1, B1. We say that the optimal
ranking cannot be any of the following
CBAA1
4,CB1
B1ACC
since all three rankings can be made better by swapping the second and third ranked groups. Therefore 3 possible optimal rankings are
CAA
A
BІCA
which are cyclic shifts of each other.
Inductive Step
One property of rankings which is useful for the inductive step proof is as follows. Let there be 2k + +1 groups G {g1. 92 ... 12 J. Label the optimal ranking with the condition that gi be placed first in the ranking as R, The ranking R; with removed must be the optimal ranking for G {g: This can be shown using contradiction i.e, if there was a better ranking for G' It. that ranking with 9: appended to the front would be better than R.
now assume the theorem is true for size 2k- instances and aim to prove for the same for size 2k + instances. Consider 9I as the first group in the ranking. This creates a certain number of upsets, for the purposes of ranking the remaining groups, 2 of the remaining groups can be merged into single group. This follows from the observation carlier that cach group also 'separates' two groups. This can be considered an instance of the size 2k problem. Therefore the set of optimal rankings with 91 the first group in the rankings is made up of Φ1 as the first group and cyclic sweep of the remaining items to fill the remaining positions. Therefore the optimal permutation must be among the sets created by considering each of the 2k
groups the first group in the rankings. Let Rig represent the ranking which has group Ji as the first group and the remaining groups present as cyclic sweep from gy. Consider the case of R1 Let x; represent the number of items in group ge. If R1 is better ranking than R4,4 1, it implies that
a+1
2n+1 Σ
Σ
t=
1=
by considering the shift of gi the two rankings. The difference the number upsets between R1,2 and RI, is given by
x2(-rk rk+1
In+2 + Tn43 22n+1) D3(- Dk+1 Fn+3 In+4 ... F2n+1)
Using Equation] D it can be seen that each of the above terms are negative for any j < n + 1, making R1,2 the better ranking. Any group per the ranking must precede the second( otherwise switching them would decrease the upsets). Since either R1 (g,t+1(both counterclockwise orderings) is better than R1, whenever k S n I(Ri, cannot be the optimal ranking when k > 1), and since this can be generalised for any Rs.g, shown that one of the counterclockwiee orderings of the items is the optimal ranking.
cannot be considered as an optimal ranking since the first
We note that the above proof also appeared in ?. However, the insights via flip classes were not present there.
13

---

Published as a conference paper at ICLR 2022
A.0.1 FINDING FORBIDDEN CONFIGURATIONS
Given a tournament and a representation dimension, there is no known method to check whether the tournament can be represented by vectors in the given dimension. The forbidden configurations presented above were found by carefully creating an exhaustive set of cases, and showing each one causes contradiction. The techniques used are presented below.
Proof of Theorem
Proof. Consider the representation of tournaments as given in Subsection 3 noise to each h2 will not change tournament, can deal only with cases in which any size 4 subset of h 2 consists of linearly independent vectors. By using this property, and without loss of generality,
Since adding minor
c + cah2 + cyhs + cah4 = hs
(2)
We can construct cases based on the signs of the coefficients(c:) in the above equation. There 2 = 16 sign patterns/cases for any equation. These cases are filtered by multiplying the entire expression with expressions of the form A Aroth;
h A h, + c2h2 A h, + A A h,- = hg rot h,
(3)
In the above equation, the signs of all expressions of the form h.A rot hy is known from the tournament configuration. Therefore simply comparing the sign of the LHS and RHS for possible values of rules out many cases.
We now use multiple equations together in bid to further filter the remaining cases. Consider the following equations without loss of generality.
e hu 02h2 + cahs + cahs = h5
(4)
by h2 + b2h3 + byh4 + byhς = h6
(5)
h1 + a2h2 + azh3 - anhı h6
(6)
h5 can be eliminated from the first two equations, leaving two expressions of he in terms of h1.... h4- The two sets of coefficients of /j.... ... h4 can be equated, and sign based arguments can eliminate
few more cases. Also, set of 3 tuples can be constructed, with each item representing possible sign
patterns for the 3 equations. Note that this set of 3 tuples does not contain entries which cannot apply simultaneously the 3 equations.
The above elimination step can be considered as filtration procedure given size 6 tuple (h1, f2, h3, f4, h5, hGg by using 3 equations. We can perform a similar filtration step given any size 6 tuple well. Let the equations corresponding to (h1, h2, h3, h4, hs, ht) be E1,1, E1,,, E1,3. Similarly, consider the tuples (h2, h2, h3, h4, kt, ht), (hzz, ha, ht, h5, fig f7), (h1, f22 h3g h4s h6s h7) and their corresponding equations represented by Eg.; where i is the index of the tuple corresponds to and j the index the equation. The above filtration process can be performed on all the tuples, following which an additional filtering step can be performed by using
Σ1, = E
E1, Ea,1
E1,3 = F1,
Σ2 = E3.3
F23 = F4.2
where the equivalence relation represents that the equations are identical. Since identical equations must have identical sign patterns, the sign patterns not present in both sets of possible sign patterns can be filtered out. For the 11-DRT cone, this leaves us with null set, proving that a forbidden configuration.
14

---

Published as a conference paper at ICLR 2022
Proof of Theorem 9
Proof. The result follows the arguments in Forster Simon (006). We note that the arguments in Forster & Simon (2006) work only for non-zero sign matrices. By overloading T to denote the signed adjacency matrix of the corresponding tournament, we can consider the non-zero sign matrix G = T + di ab) where b E (1, - By Gershgorin's circle theorem and exploting the fact that any two rows of doubly regular tournament are orthogonal, one can show that P.)))² < (T)² + 2n - where p; denotes the i-th largest singular value of the corresponding matrix. It then follows from Forster & Simon (2006) that G has an representation in dim dimensions, then it must be the case that
dim Σ (p(())) 2n² n²
Noting that for a doubly regular cone on n nodes, Pa (T). Tt- - Vi, we get
n
dim² dim2-3(n-)))) 1) n² => dim 2
Thus get a matrix M such that (M) G. one needs at least v dimensions i.., rank(M) Z
3-
Now we show that this also is lower bound for representing T. To see this, assume for the sake of contradiction that T has a representation in d dimension where < V Then, there exists H E ddd such that T = T[H]. The diagonal entries of T[ are zero. Now introduce a small enough perturbation E' to H and consider the matrix (H + 1²" A The entries of the perturbation matrix E Rd can be chosen to be small enough such that the sign of the off-diagonal entries of H A rot H is same as that of (H + A not H. However, the diagonal entries of (H-- + E)" A rot H can get an arbitrary sign pattern, say b. Let G be the sign pattern matrix corresponding (H E)" A rot r. By definition, G has representation in dimension d v 3 But this contradicts incquality Thus, it must be the case that T has a representation in dimension least /
Finally, setting n 12d the number of nodes in the doubly regular cone as given in the Theorem, we get that at least 2d dimensions are needed to embed such tournament. The result follows.
Proof of Theorem 10
Proof. The proof is the same arguments as the first part of the proof of Theorem
Proof of Theorem
Proof. Given a tournament T, we first show that we can start with an arbitrary transitive tournament and add enough rank corrections to obtain representation for T. Every addition of a rank 2 matrix will increase the representation dimension by at most 2. The result will follow then by noting that for the choice the transitive tournament which minimizes the number of corrections needed, one needs at most (T) 1) representation dimension.
Let T' be an arbitrary transitive tournament which has a 2 dimensional representation and let M E Baxn be the associated skew symmetric matrix that represents TV. W.l.o.g, assume that Maj > if and only if < j. Define ET( = {i: < kt i <x k). By definition, the feedback are [1, n] is the topological order corresponding to the transitive tournament T'. We start with lo = n and correct the feedback arc errors arising from Ex iteratively. Define A, / //axmaa...... + for some small enough > 0. Let u E R. be such that
set E (T) J (k, Eg (T)) where
u, A Vi E En and = 0 otherwise. Let R" be such that U, A to verify that M++uv" - vu" represents tournament that has the feedback are set (k, E, (T)) i.., the emors in F,, have been corrected. The cost of correcting the error is adding rank 2 skew
0 vi + n. is easy
15

---

Published as a conference paper at ICLR 2022
symmetric matrix which increases the representation dimension by at most 2. One repeat the same procedure for 72 - 1, n2 - 2.... until all errors are corrected.
The upper bound in the theorem follows noting that the above argument works for any transitive tournament and so we can start with the one which has the least number of nodes involved in the feedback arc to minimize the number of extra dimensions needed to represent T.
Proof of Theorem 12
Proof. From Theorem T can represented using at most (T) + 1) dimensions. By construc- tion any representation of T must also represent G. The result follows.
A.0.2 ADDITIONAL FILTRATION FOR VERIFYING 10 NODE FORBIDDEN CONFIGURATION
0
1
1
0
1
-1
-1
1
-1
1
-1
O
-1
1
-1
1
-1
-1
1
T
1
-1
1
-1
-1
0
1
-1
1
-1
-1
-1
0
1 1
1
1
1
-1
-1
-1
Due to the lesser number of constraints present when dealing with 10 nodes instead of 12, additional filtration step is required. The entire procedure described above can be considered as an elimination procedure given tuple T (hi....,y) Also consider that in the final filtration above, set of size tuples is created. These size tuples will represent the possible sign patterns for F1,1, E1,2, F1,3, 2. If a similar procedure is carried tuples will be generated. The filtration this step is based on the fact that the equations F F2, present
T-2 (h2....hs) hg). another set of
Ti the same E1,1, É1. for T2. The sign patterns which in both sets of tuples are filtered out. This type of relationship can be obtained between T2 and T3 (ha..... .h, h2) as well, and in general between any and T, such that T, can be obtained from T; by removing the first entry and adding an entry to the end. Note that the tuples must have unique entries. Therefore 'circular elimination' procedure can be followed, where the T, tuples considered are size subsets of the circular permutations of ..,...ha hg. By following this procedure, all the sign patterns remaining can be eliminated. Using size circular permutations of h hy in the last step does not eliminate all the cases, we believe this is due to nodes I to forming 7-DRT cone, which leads to many climinations. The code for filtration can be found here
corresponding
16


Reviews:
[{"review_id": "pUE59TP-ax", "reviewer": "Reviewer_MMVk", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "I think this paper has a solid theoretical foundation of an interesting problem on tournaments.\n\nMy main concern is if this conference is the right venue since I fail to see the connection to \"learning.\" The authors briefly address applications in Section 7.2, but I think this section should be expanded. Some of the proofs can be moved to the appendices to make space if need be. \n\nMinor errors:\n\n“Recent works have noted that parametric models which assume d dimensional node representations can effectively model intransitive tournaments” are there any citations for this statement? You might want to list them in the introduction where something similar is also mentioned. \n\n\nNo “.” after 2) point at the end of Page 1.\n\nIn the definition of skew symmetric, it would be easy to add A^T = - A\n\nThe name of the Lemma is Farkas’ Lemma, and not Farka’s lemma.\n\nIn the citation of Charbit et al, the “np” should be capitalized. ", "summary_of_the_paper": "A tournament is made by choosing a direction for each of the edges in a complete graph. A tournament can be induced of by skew symmetric matrices M where entries M_{ij} > 0 if and only if (i,j) is an edge. A tournament on n edges can be represented by a set of d-dimensional vectores {h_1, … , h_n} if (h_j)^T A h_i is not zero iff (i,j) is an edge (and A is an appropriate matrix).\n\nThe authors address two questions:\n\n1) What structurally characterizes the class of tournaments that can be represented in d dimensions?\n\n2) Given a tournament T on n nodes, what is the minimum dimension d needed to represent it?.\n\nThe first question is answered by considering structures the authors called forbidden. The authors provide a characterization of these forbidden structures as a union of certain equivalence classes. \n\nThey answer the latter question in part by providing bounds on what said dimension d should be. \n\n", "summary_of_the_review": "Overall, I think the paper should be accepted provided that the authors make more of an effort to relate their results to learning. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "mvJh08SL8ke", "reviewer": "Reviewer_AhwX", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Tournaments are important tools in sports modeling, social preference, etc. A tournament on n nodes is the complete directed graph where every pair of nodes has a directed edge pointing from one vertex to the other. One can represent a tournament as the sign matrix of a rank d matrix. In this work, the authors develop a novel theory for understanding tournament representation. \n\nFirstly, the authors characterize the structure of rank d tournaments using a list of forbidden configurations. These forbidden configurations are formed by the union of so-called flip classes. For rank 2 tournaments, the authors use this framework to describe precisely the forbidden configurations and show that they are actually equivalent to locally transitive tournaments, a class of tournaments closely related to transitive tournaments. The authors also show one forbidden flip class for rank 4 tournaments and also a weaker forbidden flip class for the general rank d case.\n\nSecondly, the authors show both lower and upper bound on the minimum dimension required for tournament representation on n nodes. The lower bound of order sqrt(n) is proved by a variation of the celebrated work of Forster and Simon for sign matrices. The upper bound is given in terms of a parameter named the Flip Feedback Node set of a Tournament introduced by the authors. Such an upper bound also gives new bounds for sign ranks of matrices.\n\nThe results of this paper are overall nice, but I find some of results in the first part slightly weak. Especially for rank-4 and rand-d tournaments the forbidden flip classes are still not totally clear. Also, it is unclear to me if the minimum feedback arc set problem can be solved efficiently for constant rank representable tournaments. Is this problem efficiently solvable when the representation matrix is given? In fact, more discussions about applications of low-rank representations or forbidden flip classes would be appreciated. As a potential direction for improvement or future direction, one can probably also try studying the representation dimension of random tournaments. \n\nDetailed comments:\nPage 2: “We exhibit a lower bound of O(\\sqrt(n))”\nTechnically you should use \\Omega() for lower bound instead of big-O\nPage 4, Definition 3: I think in the first item you should have “for all j \\neq i^*” instead of i\n", "summary_of_the_paper": "This paper provides fundamental theories of tournament representations. The authors study two main questions. First they characterize the class of tournaments that can be represented in d dimensions. Second they give lower and upper bounds on the minimum dimension needed to represent a tournament on n nodes.\n", "summary_of_the_review": "Overall this is a nice paper though I think there is still room for improvements for some parts. Some results are slightly weak and I don’t really see any application for most results. Perhaps the authors should discuss more about the application parts.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "TvyIJI1TlM-", "reviewer": "Reviewer_YSHR", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths:\n- the paper introduces a novel theory of tournament representations, leveraging their specific properties that separate them from sign matrices\n- the connection between representations, flip classes and cones is made clear and nicely leveraged\n- a complete theory of rank 2 tournaments is obtained, which corresponds to the intuitively \"simplest\" tournaments\n\nWeaknesses:\n- motivation: the applications of such tournaments representations, which are much more restrictive than general sign matrices, are never mentioned; the ones in Alon et al. do not apply to this setting\n- interpretability: much attention is given to vector representations $H$ where $H^\\top A^{\\mathrm{rot}} H = M$, but no interpretation of those $h_i$ is given, in terms of how the positions of those vectors relate to the tournament structure. The proof of Lemma 3 would also be easier to understand if the connection between rank-2 representation and angles was made clearer.\n- Theorem 6 is neat, but its connection to the rest of your work is tenuous: the proof only uses the fact that $T$ is locally transitive, and I fail to see any situation where showing that a tournament has rank 2 is easier than showing it's locally transitive\n- the quantity $\\mu(T)$ involves minimizing the feedback vertex set under all $2^n$ possible flips, hence stacking an exponential problem on top of an NP-hard one, known to be very hard to approximate. Maybe this would benefit from an example where the lower bound given by $\\mu(T)$ is better than the ones in Alon et al.", "summary_of_the_paper": "This paper studies the theory of tournament representations, i.e. low-rank matrices $M$ whose sign agrees with the sign matrix of a tournament $T$.\n\nThe authors show several properties of such representations, reducing the study to so called $R$-cones, i.e. tournaments where one vertex beats all others. They also characterize completely rank 2 tournaments, and provide a forbiden class for rank $d$ tournaments.\n\nFinally, they provide an upper bound on the minimum dimension of a presentation of any tournament $T$, in the for of a bound involving minimum feedback arc sets of $T$, and show how this can be extended to sign matrices.", "summary_of_the_review": "This paper introduces a specification of sign matrix representation to tournaments, with some interesting ideas, but the significance and improvements over Alon et al. are not made clear enough to warrant acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "C9NhLV0gKlP", "reviewer": "Reviewer_UVYb", "summary": "", "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": "The goal of connecting dimensional characterization and structural characterization is important and the connection to flip classes very interesting. The results seem to be sound, although I had non-insignificant troubles trying to verify them due to the writing style (see next paragraph on weaknesses)\n\nI think that the paper needs a thorough stylistic rehandling and it is not ready to be published in its present form. The preliminary section does not help to orientate in the dense notation and terminology employed trhoughout the paper: \nConcrete examples: \n- the definition of tournament is not precise (it is the underlying undirected graph to be complete)\n- the notation H={h1,..,hn} \\in R^d is very confusing. You mean each h_i \\in R^d . \n- the description of representation and canonical form of skew-symmetric matrices is confusing also because of the previous point\n- btw, in a preliminary section, also the definition of skew symmetric matrix could find its place, since you are defining other basic concepts too\n- proof of Lemma 2: \"H realizes R\" has never been defined before\n- line after Definition 4: \"3-doubly regular tournament\" is not defined (what is 3); this notation is also used later (e.g., 11-doubly... in Thm 8)\n- Thm 7: the sign of T is not defined. \n- ...\n\nIn conclusion, I think the paper contains some interesting ideas and results however I am not fully satisfied with the clarity of the arguments. I have read and appreciated some of the authors updates and clarifications, following their reply to my questions. Admittedly, the paper needed significant explanations from the authors. I have updated my score which is now less negative but still only marginally above the acceptance. ", "summary_of_the_paper": "The paper studies the relationship between dimensional representation of tournament and their structural characterization. In particular, a relationship is established between rank d tournament and their forbidden configurations in terms of flip classes, introduced by Fisher&Ryan(1995) as a way to partion the set of tournaments of a given order. In addition, the problem of bounding the minimum possible dimension of a representation of a tournament is also investigate and lower and upper bounds are given.", "summary_of_the_review": "It was not possible for me to fully assess the correctness of the claims. The ideas and claims are of interest for the area, however the present form of the presentation is below the bar of acceptance, in my opinion. \n\n[Following the authors' reply] I have read and appreciated some of the authors updates and clarifications, following their reply to my questions. Admittedly, the paper needed significant explanations from the authors. I have updated my score which is now less negative but still only marginally above the acceptance. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper takes a creative step in the theory of tournaments, and it seems plausible that this could lead to interesting follow-ups. The reviewers made many excellent comments and I highly encourage the authors to take ALL of them into account in the revision, it will make the paper much stronger.
Decision: Accept (Poster)