Maps of Tournaments: Distances, Experiments, and Data

Filip Nikolow, Piotr Faliszewski, Stanisław SzufaarXiv 2026 · arXiv

TL;DR

This paper introduces a visual framework to map the landscape of tournament graphs, projecting complex win-loss structures onto a 2D plane. By introducing a fast, centrality-based distance metric to bypass NP-hard graph comparisons, the authors reveal where real-world sports data and synthetic models sit relative to each other, providing a powerful new tool for empirical research in social choice and AI.

What Problem Does This Paper Address?

Tournaments—represented as complete directed graphs where nodes are players and edges point from winner to loser—are a staple of AI and computational social choice literature. They are used to study everything from round-robin tournament rules to knockout bracket manipulations.

However, conducting systematic experiments on tournaments is notoriously difficult. The space of possible tournament structures is massive and abstract, making it hard for researchers to answer fundamental questions: Are my synthetic tournament models realistic? Am I testing my algorithm on a diverse set of graphs, or a biased subset? This paper addresses this gap by adapting the "map of elections" framework to tournaments, giving researchers a visual, intuitive way to navigate and understand tournament data.

Methods

To build a map, you need to calculate the "distance" between different tournaments and project those distances onto a 2D plane using Multidimensional Scaling (MDS). The authors explore two primary distance metrics:

  1. Graph Edit Distance (GED): The intuitive choice. It counts the minimum number of edge reversals needed to make one tournament isomorphic to another. Unfortunately, computing GED is NP-hard, making it impractical for larger tournaments.
  2. Katz Distance: The authors' novel, polynomial-time alternative. It calculates the Katz centrality vector for each tournament, sorts the values in descending order (to ensure the metric is invariant to player names), and computes the $\ell_1$ distance between the vectors.

To anchor the maps, they define two extreme "characteristic" tournaments: the perfectly hierarchical Ordered Tournament ($T_{ord}$), where the strongest player beats everyone and no upsets occur, and the Rock-Paper-Scissors Tournament ($T_{rps}$), a regular graph representing a multiway cyclical tie.

Datasets

The authors evaluated their framework using several distinct datasets:

  • Size-7 Dataset: A complete set of all 456 unique, nonisomorphic 7-player tournaments.
  • Size-12 Dataset: A curated mix of 368 tournaments generated via uniform random models, Condorcet noise models, strength-based models, and sub-sampled real-world data.
  • Real-World Sports Data: 20 seasons of regular-season NBA data and 17 tournaments from the Polish Sports Bridge Association (both sub-sampled to 12 players for consistency).
  • Election-Derived Datasets: Tournaments generated from the majority relations of voting models (e.g., Impartial Culture).

Key Insights and Ideas

  • Centrality as a Distance Proxy: The Katz-based distance serves as an excellent, highly scalable proxy for GED. As shown in the paper's analysis, it correlates well enough with GED to preserve the core structural relationships of the tournament space while running in a fraction of the time.
Figure 1: Basic insights regarding tournaments. Plot (a) shows a histogram of GED distances between Tord and all RPS tournaments with 11 players, plot (b) compares the GED and Katz distances in the Size-12 dataset (each point is a pair of tournaments, its x coordinate is their GED distance and its y coordinate is the Katz distance), and plot (c) shows PCC of the GED and Katz distances between Tord and 100 tournaments generated using the uniform model, depending on the number of players (for each number of players we repeated the experiment 10 times; the shaded area shows standard deviation).
  • NBA vs. Bridge Dynamics: On the maps, NBA tournaments sit very close to the perfectly transitive ordered tournament ($T_{ord}$), indicating a clear, predictable hierarchy among basketball teams. Conversely, bridge tournaments map closer to the chaotic, cyclical Rock-Paper-Scissors ($T_{rps}$) family. This occurs because bridge tournament scoring rewards high-risk strategies; top teams play aggressively for bonuses, occasionally losing to weaker teams in ways that disrupt a clean hierarchy.
  • The Election Model Bias: Tournaments derived from standard election models (like the Impartial Culture model) cluster tightly near $T_{ord}$. This is highly surprising because uniform random graphs cluster near $T_{rps}$. This warns researchers that using voting data to simulate general tournaments introduces a heavy, potentially unintended structural bias.

Key Results

  • Massive Speedups: Computing the Size-12 map using the exact GED metric took several days on a high-performance server. Using the new Katz distance, it took just 89 seconds.
  • Predicting Algorithm Complexity: The maps proved useful for predicting algorithmic performance. The authors demonstrated that the running time of an ILP solver computing "Slater winners" scales predictably with a tournament's distance from $T_{ord}$ on the map.
  • Knockout Tournament Chaos: In an experiment generating 1,000 random brackets for the Size-12 dataset, the authors found that in 55% of the tournaments, every single player had a mathematical path to victory under at least one bracket configuration.

Limitations and Future Work

The primary limitation of the current Katz distance is that it can only compare tournaments of the exact same size ($n$). Developing a fast, size-independent distance metric remains an open challenge. Additionally, the maps reveal large empty spaces that are currently only populated by brute-force nonisomorphic graph samplers (nauty). The authors note that future work should focus on designing new statistical models capable of naturally generating tournaments to fill these structural gaps.

Summary updated

Abstract

We form a "map of tournaments" by adapting the map framework from the world of elections. By a tournament we mean a complete directed graph where the nodes are the players and an edge points from a winner of a game to the loser (with no ties allowed). A map is a set of tournaments represented as points on a 2D plane, so that their Euclidean distances resemble the distances computed according to a given measure. We identify useful distance measures, discuss ways of generating random tournaments (and compare them to several real-life ones), and show how the maps are helpful in visualizing experimental results (also for knockout tournaments).
BibTeX
@misc{nikolow2026maps,
  author = {Filip Nikolow and Piotr Faliszewski and Stanisław Szufa},
  title = {{Maps of Tournaments: Distances, Experiments, and Data}},
  year = {2026},
  eprint = {2601.18348},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2601.18348},
}
Figure