Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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).

The authors address two questions:

1) What structurally characterizes the class of tournaments that can be represented in d dimensions?

2) Given a tournament T on n nodes, what is the minimum dimension d needed to represent it?.

The 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. 

They answer the latter question in part by providing bounds on what said dimension d should be. 


main_review: I think this paper has a solid theoretical foundation of an interesting problem on tournaments.

My 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. 

Minor errors:

“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. 


No “.” after 2) point at the end of Page 1.

In the definition of skew symmetric, it would be easy to add A^T = - A

The name of the Lemma is Farkas’ Lemma, and not Farka’s lemma.

In the citation of Charbit et al, the “np” should be capitalized. 
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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)

I 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: 
Concrete examples: 
- the definition of tournament is not precise (it is the underlying undirected graph to be complete)
- the notation H={h1,..,hn} \in R^d is very confusing. You mean each h_i \in R^d . 
- the description of representation and canonical form of skew-symmetric matrices is confusing also because of the previous point
- btw, in a preliminary section, also the definition of skew symmetric matrix could find its place, since you are defining other basic concepts too
- proof of Lemma 2: "H realizes R" has never been defined before
- 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)
- Thm 7: the sign of T is not defined. 
- ...

In 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_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. 

[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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.

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. 

Firstly, 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.

Secondly, 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.

The 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. 

Detailed comments:
Page 2: “We exhibit a lower bound of O(\sqrt(n))”
Technically you should use \Omega() for lower bound instead of big-O
Page 4, Definition 3: I think in the first item you should have “for all j \neq i^*” instead of i

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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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$.

The 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.

Finally, 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.
main_review: Strengths:
- the paper introduces a novel theory of tournament representations, leveraging their specific properties that separate them from sign matrices
- the connection between representations, flip classes and cones is made clear and nicely leveraged
- a complete theory of rank 2 tournaments is obtained, which corresponds to the intuitively "simplest" tournaments

Weaknesses:
- 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
- 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.
- 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
- 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_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.
review_title: null

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)