A Theory of Tournament Representations

Arun Rajkumar, Vishnu Veerathu, Abdul Bakey MirICLR 2022

Introduction

In fields ranging from sports modeling and social choice to machine learning, researchers frequently encounter tournaments—complete directed graphs where every pair of participants has a directed edge representing a win/loss or a preference. While real-world tournaments are almost always intransitive (e.g., Rock beats Scissors, Scissors beats Paper, but Paper beats Rock), modeling them efficiently remains a complex challenge.

This paper bridges a crucial gap between graph theory and linear algebra by characterizing which tournaments can be represented in low-dimensional spaces. The authors provide a theoretical foundation for understanding the structural constraints of these representations, revealing that rank-2 tournaments correspond exactly to "locally-transitive" structures—a finding with significant algorithmic implications.

The Challenge of Intransitivity

To model complex, intransitive relationships, researchers often assign $d$-dimensional vectors to each node. Mathematically, a tournament is considered "represented" in $d$ dimensions if there exists a rank-$d$ skew-symmetric matrix where the sign of the entries dictates the direction of the edges (who beats whom).

While algorithms exist to learn these representations from data, the underlying structural constraints have remained opaque. Specifically, if a tournament is known to be rank-2, what does its graph actually look like? Prior to this work, there was no theoretical framework to answer this question.

Methodology: Flip Classes and Forbidden Configurations

To unravel the structure of low-rank tournaments, the authors employ a blend of combinatorial graph theory and algebraic matrix theory, introducing several key concepts:

  • Flip Classes: The study utilizes "cut-equivalence," or flip classes. If you select a subset of nodes and reverse all their incoming and outgoing edges, you have "flipped" the tournament. The authors prove that the ability to represent a tournament in $d$ dimensions is an inherent property of its entire flip class, not just the individual graph.
  • Forbidden Configurations: Drawing a parallel to how planar graphs are defined by the absence of specific subgraphs, the authors identify "forbidden" tournament structures that mathematically cannot exist within a specific rank.
Representable vs. Forbidden Flip Classes

By analyzing these flip classes, the researchers established a bijection between rank-2 tournaments and locally-transitive tournaments. A tournament is locally transitive if, for any given player, the group of opponents they defeated and the group they lost to are both internally consistent (transitive) in their own rankings.

Key Findings and Implications

Rank 2 is Special

The discovery that rank-2 tournaments are exactly locally-transitive is a major breakthrough. It demonstrates that the simplest non-transitive models used in machine learning correspond to a very specific, well-studied graph structure.

Algorithmic Efficiency via Quicksort

Because rank-2 tournaments are locally transitive, the authors show that the traditionally NP-hard "Minimum Feedback Arc Set" problem—finding the best linear ranking with the fewest upsets—becomes efficiently solvable. For these structures, a standard Quicksort-based procedure can find the optimal ranking in $O(n^2)$ time.

Real-World Prevalence

To validate their theory, the authors analyzed 114 real-world tournament datasets sourced from PrefLib.org, covering domains like election preferences, consumer choices (sushi, cars), and sports data (ranging from 5 to 23 nodes). Remarkably, approximately 66.67% (76 out of 114) of these real-world tournaments were found to be locally transitive (rank 2). This high prevalence strongly justifies the use of low-rank models in practical applications.

Hierarchy of Flip Classes

Dimensionality Bounds and Sign-Rank

The paper also establishes rigorous mathematical bounds for tournament representations:

  • Lower Bound: Representing all possible tournaments on $n$ nodes requires at least $d \geq \sqrt{n}$ dimensions.
  • Upper Bound: The authors introduce a new graph parameter, $\mu(T)$ (the Flip Feedback Node Set), which measures the minimum number of nodes involved in "upsets" across an entire flip class. Any tournament $T$ can be represented in $2(\mu(T) + 1)$ dimensions.

These results provide new, graph-theoretic upper bounds on the "sign-rank" of matrices, outperforming previous bounds based on VC-dimension in certain cases.

Limitations and Future Work

While the rank-2 case is now structurally solved, finding the minimum representation dimension for a general tournament remains computationally difficult, as the authors' current upper bound relies on brute-force searches for small tournaments.

Furthermore, while the paper identifies a forbidden configuration for rank 4 (the 11-doubly-regular-cone), a complete structural characterization for ranks $d > 2$ remains an open challenge. The authors suggest that identifying forbidden configurations for higher-rank tournaments is intimately tied to the Hadamard Conjecture, a famous unsolved problem in mathematics. Future work will also need to focus on developing efficient algorithms to approximate the Flip Feedback Node set size $\mu(T)$ for large tournaments, enabling better automated model selection.

Summary updated

BibTeX
@inproceedings{rajkumar2022theory,
  author = {Arun Rajkumar and Vishnu Veerathu and Abdul Bakey Mir},
  title = {{A Theory of Tournament Representations}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
}
Figure