AI Glossary / Graphs and symbolic AI / Intermediate
Tournament
Definition
A tournament is a directed graph with exactly one directed edge between each pair of distinct vertices. It represents a complete set of pairwise outcomes with no ties, where the direction records which member of each pair wins or is preferred.
What it means
The graph-theoretic term comes from competitions in which every participant meets every other participant. If A defeats B, draw A → B. Every different pair must have exactly one such direction; missing results, tied results and two opposite edges do not fit a simple tournament.
The vertices need not be athletes. They can represent candidate models, plans or alternatives compared pairwise. The important requirement is the complete one-way relationship between every pair.
A tournament does not necessarily describe a consistent ranking. A can defeat B, B defeat C and C defeat A. This cycle is allowed and is often the most informative part of the model. The glossary entry concerns this graph structure, not every event commonly called a tournament.
How it works
For n vertices, a tournament has n(n−1)/2 directed edges, because each unordered pair contributes exactly one. Its out-degree counts how many other vertices that vertex defeats under the chosen edge convention.
An acyclic tournament is transitive and admits a ranking consistent with every edge. A general tournament may have cycles, so no ordering can respect all pairwise outcomes. A vertex that defeats every other vertex, when one exists, is a Condorcet winner under a preference interpretation.
Every finite nonempty tournament has a directed Hamiltonian path: an ordered sequence visiting each vertex once with an edge from each vertex to the next. Such a path does not assert that every earlier vertex defeats every later one. NetworkX provides tournament-specific checks and algorithms, whose graph assumptions should be verified before use.
Three practical examples
- A model-evaluation study represents a decisive pairwise comparison for every pair of candidate systems and examines preference cycles.
- A decision-support exercise builds a tournament from complete strict pairwise preferences among proposed designs.
- A graph-theory class contrasts a round-robin outcome graph with an incomplete comparison graph that is not a tournament.
Think of it this way
Think of a scoreboard that includes one winner for every head-to-head pairing. Arrows preserve those individual outcomes instead of forcing them immediately into a single league table.
The analogy has limits. Real competitions may include draws, repeated matches or missing fixtures. A graph that keeps those details may require a different representation. Turning a draw into an arbitrary arrow changes the evidence rather than merely changing its format.
Worked example
A cycle inside complete comparisons
Consider four candidates A, B, C and D. The six edges are A → B, B → C, C → A, A → D, B → D and C → D. The edge count is 4 × 3/2 = 6, and every pair appears exactly once, so this is a tournament.
A, B and C each have out-degree two; D has out-degree zero. There is no candidate that defeats all three others. The cycle A → B → C → A prevents any total ranking from respecting every result.
A, B, C, D is nevertheless a directed Hamiltonian path because its consecutive edges exist. It does not mean A defeats C: the graph says the opposite. Removing B → C would leave only five edges and an unobserved pair, so the graph would cease to be a tournament. These properties follow directly from the listed edges.
Illustrative case study
Fictional case: Cedar Evaluation compares four answer-generation systems. Reviewers choose a preferred answer for each pair on an aggregated test set and convert the decisive outcomes into a directed graph.
The team initially interprets a Hamiltonian path as a universally valid best-to-worst ranking. Inspecting the other edges reveals a cycle among three systems. It also notices that some underlying comparisons were tied before an arbitrary tie-break was applied.
The report is revised to retain the underlying scores and distinguish decisive outcomes from unresolved pairs. The team uses the tournament model only for the version that satisfies its assumptions and explains that the resulting path preserves consecutive victories, not every pairwise preference. No real model superiority is asserted.
Common misconceptions and mistakes
- Every tournament has a universal winner. Cycles can prevent any vertex from beating all others.
- A Hamiltonian path is a fully consistent ranking. It only guarantees directed edges between consecutive vertices in the path.
- Any directed comparison graph is a tournament. The complete, exactly-one-direction requirement must hold for every distinct pair.
Business use
Tournament graphs help teams examine pairwise evaluation results without hiding nontransitivity. They can reveal that a choice depends on which alternative it is compared against, or that an aggregate ranking loses important relationships.
Before applying tournament algorithms, specify what an edge means and how ties, uncertainty and missing comparisons are treated. Retain the original measurements. If pairwise outcomes are noisy, an arrow is an estimate rather than an immutable fact; report that uncertainty instead of giving the graph more authority than its evidence supports.
People also ask
Can a tournament contain a directed cycle?
Yes. A three-vertex cycle is a basic example.
Is a knockout bracket a tournament graph?
Usually not in this mathematical sense, because most pairs never play each other.
Can edge weights be included?
They can record additional information such as a margin, but the underlying one-edge-per-pair structure still defines whether the graph is a tournament.
Check your understanding
Three alternatives satisfy A → B, B → C and C → A. Is this a tournament, and does it have a vertex that defeats every other vertex?
Answer: It is a tournament because all three pairs have exactly one direction. It has no universal winner because each vertex wins once and loses once.
Related terms
- Directed graph
- Cycle
- Ranking
- pairwise comparison
- Condorcet winner
- Hamiltonian path
- transitive tournament
Learn next
Read pairwise comparison and Hamiltonian path. Draw all six edges for four alternatives and check whether your preferred ranking agrees with every edge. If it does not, identify exactly which comparison it contradicts.
More in Graphs and symbolic AI
- Topological sort - A topological sort is an ordering of every vertex in a directed acyclic graph such that each directed edge goes from an earlier vertex to a later one.
- Total functions - Total functions assign exactly one output to every input in their stated domain.
- Total Turing Test - The total Turing Test is an expanded behavioral test that includes perceptual and physical interaction as well as conversation.
- Tractability - Tractability describes whether a computational problem can be solved with manageable resources.
- Trail - A trail is a record of reversible changes made during a search or computation, used to restore an earlier state when backtracking.
- Training curve - A training curve plots a model's measured performance against progress through training, such as optimization steps or epochs.
Sources
NetworkX, tournament algorithms and graph definition: https://networkx.org/documentation/stable/reference/algorithms/tournament.html
NetworkX, tournament validation: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.tournament.is_tournament.html
NetworkX, directed Hamiltonian path for tournaments: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.tournament.hamiltonian_path.html
Relevant official documentation was read. The four-vertex example was checked from its explicit edge list; no library execution or real evaluation result is claimed.
Previous: Totally Random Trees Embedding Next: Tower