Abstract
Tournaments can be used to model a variety of practical scenarios including sports competitions and elections. A natural notion of strength of alternatives in a tournament is a generalized king: an alternative is said to be a $k$-king if it can reach every other alternative in the tournament via a directed path of length at most $k$. In this paper, we provide an almost complete characterization of the probability threshold such that all, a large number, or a small number of alternatives are $k$-kings with high probability in two random models. We show that, perhaps surprisingly, all changes in the threshold occur in the range of constant $k$, with the biggest change being between $k=2$ and $k=3$. In addition, we establish an asymptotically tight bound on the probability threshold for which all alternatives are likely able to win a single-elimination tournament under some bracket.
Introduction: Defining Strength in Tournaments
In social choice theory and sports modeling, a tournament is a directed graph where every pair of participants has exactly one directed edge between them, representing a win/loss relationship. To identify the most dominant participants, researchers often look for "kings." A participant is a $k$-king if they can reach every other participant in the tournament in at most $k$ steps.
As shown in Figure 1, different alternatives exhibit varying levels of "kinghood." While alternatives $a, b,$ and $d$ are 2-kings, $c$ requires three steps to reach certain nodes, and $e$ cannot reach others at all. Traditionally, the uncovered set (2-kings) and the top cycle (those who can reach everyone in any number of steps) have been the primary focus. However, a massive gap in "selectivity" exists between these two: it takes a much higher probability of "upsets" for everyone to be a 2-king than for everyone to be in the top cycle. This research explores the middle ground: how does the threshold for "everyone is a king" change as $k$ moves from 2 to $n-1$?
The "Constant k" Collapse
The study employs rigorous probabilistic analysis across two mathematical models: the Condorcet Random Model (assuming a linear "true" ranking with upset probability $p$) and the Generalized Random Model (where win probabilities are bounded within $[p, 1-p]$).
One might expect the threshold for everyone becoming a king to decrease gradually as $k$ grows. Instead, the authors discovered a "constant $k$" collapse. Almost all the significant changes in probability thresholds occur at very small path lengths ($k \le 6$). By the time $k$ reaches 6, the threshold is already identical to that of the top cycle ($k=n-1$).
A particularly sharp transition occurs between $k=2$ and $k=3$. 2-kings are significantly more selective; the probability required for everyone to be a 2-king is $\Omega(\sqrt{\log n / n})$. Once the path length is extended to just $k=3$, this threshold drops significantly to $\Omega(\log n / n)$.
Single-Elimination Vulnerability
Beyond generalized kings, the paper investigates single-elimination tournaments. A common question in tournament design is whether a specific participant can be "rigged" to win by choosing a favorable bracket.
The researchers established an asymptotically tight bound for this phenomenon. In the generalized model, if the upset probability $p$ is at least $\sim \log n / n$, every participant is likely to be a potential winner under some specific bracket. This confirms that single-elimination formats are highly susceptible to manipulation if the pairwise win probabilities are known to the organizer.
Conclusion and Future Directions
This work provides a near-complete characterization of the boundaries of strength in random tournaments. The findings suggest that 3-kings or 4-kings might offer a more balanced "middle ground" for tournament solutions than the extremely selective uncovered set or the overly inclusive top cycle. Future research may apply these theoretical thresholds to real-world sports data to determine where typical "upset noise" falls on this mathematical spectrum.
Summary updated