Generalized Kings and Single-Elimination Winners in Random Tournaments

Pasin Manurangsi, Warut Suksompong

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:

  1. Condorcet Random Model: Assumes a fixed linear ranking where a higher-ranked player beats a lower-ranked one with probability $1-p$.
  2. 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.

Probability thresholds for tournament solutions in random models

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.

Structure of a single-elimination tournament

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

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.
BibTeX
@inproceedings{manurangsi2021generalized,
  author = {Pasin Manurangsi and Warut Suksompong},
  title = {{Generalized Kings and Single-Elimination Winners in Random Tournaments}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/46},
}
Figure