Generalized kings and single-elimination winners in random tournaments

Pasin Manurangsi, Warut Suksompong

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.

Figure 1: A tournament with five alternatives illustrating the concept of k-kings.

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.

Figure 2: A single-elimination tournament bracket where alternative c emerges as the winner despite specific dominance relations.

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

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$$ k = 2 and $$k=3$$ 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