In sports, politics, and social choice theory, tournaments are mathematical structures where every pair of participants has a definitive winner and loser. A central question in this field is how to identify the "best" participant. However, as randomness increases—such as the probability of an "upset" where a weaker player beats a stronger one—the ability of tournament solutions to discriminate between players diminishes. A recent study by Manurangsi and Suksompong explores this phenomenon, characterizing the probability thresholds required for all participants in a random tournament to be considered winners under various definitions.
Tournament Solutions: The $k$-King Concept
The paper focuses on the concept of a $k$-king. A participant is a $k$-king if they can reach every other participant in the tournament graph in at most $k$ steps.
- 2-kings (The Uncovered Set): A player is a 2-king if they beat everyone else directly or beat someone who beats them.
- $(n-1)$-kings (The Top Cycle): A player is a king if there is any directed path from them to all other players.
Historically, there has been a significant gap in the "selectivity" of these two solutions. In tournaments with low upset probabilities, 2-kings are rare, while almost everyone might belong to the top cycle. The authors investigate the transition between these extremes by examining $k=3, 4, 5, \dots$.
Methodology and Random Models
The researchers employed rigorous probabilistic analysis using two primary models:
- Condorcet Random Model: Assumes a fixed linear ranking where a higher-ranked player beats a lower-ranked one with probability $1-p$.
- Generalized Random Model: A more flexible framework where match win probabilities are bounded between $[p, 1-p]$, without assuming a global ranking.
By applying tools such as Chernoff bounds and union bounds, they identified the threshold values of $p$ at which, with high probability, every player in an $n$-player tournament becomes a $k$-king.
Key Results: The Threshold Hierarchy
The study reveals a surprising "constant $k$" effect. Rather than a gradual shift as $k$ approaches $n$, most significant changes in selectivity occur when $k$ is very small.
As shown in the table above, the threshold for $k=2$ is approximately $\sqrt{\log n / n}$. This drops to $\log n / n$ for $k=3$ and $k=4$. Remarkably, by the time $k=6$, the threshold becomes $\omega(1/n)$ in the generalized model, which is identical to the threshold for the $(n-1)$-king (the top cycle). This implies that once a solution allows for 6-step paths, it becomes as inclusive as the most permissive tournament solutions.
Single-Elimination Winners
The authors also addressed single-elimination winners: players who could win the entire tournament if the bracket is optimally arranged for them.
The paper proves that in the generalized random model, if the upset probability $p$ is at least $\Omega(\log n / n)$, every player has a chance to win a single-elimination tournament given a "rigged" bracket. This result highlights the vulnerability of single-elimination formats to manipulation by those who determine the schedule.
Conclusion and Future Directions
The findings suggest that the discriminative power of tournament solutions vanishes quickly as the path length $k$ increases. While the thresholds for most $k$ are now well-understood, a small technical gap remains for $k=5$ in the generalized model. Future research may also explore the axiomatic fairness properties of $k$-kings for $k > 2$ and validate these theoretical thresholds against empirical data from real-world sports and elections.
Full Citation: Manurangsi, P., & Suksompong, W. (2022). Generalized Kings and Single-Elimination Winners in Random Tournaments. arXiv:2105.00193v2 [math.CO].
Summary updated