Generalized Kings and Single-Elimination Winners in Random Tournaments

1 Introduction

Social choice theory is the study of how to aggregate individual preferences and opinions of agents on a set of alternatives in order to reach a collective decision. In many practical situations, the relationship between the alternatives is represented by a dominance relation, which specifies the relative strength of the alternatives in any pairwise comparison. For example, in sports competitions the dominance relation signifies the match outcome when two players or teams play each other, while in elections the relation represents the pairwise majority comparisons among the candidates. The structure consisting of the alternatives and their dominance relation is called a tournament, and the analysis of tournament winner selection methods-also known as tournament solutions-has received significant attention from researchers in the past few decades [Laslier, 1997; Brandt et al., 2016; Suksompong, 2021].

Among the vast array of tournament solutions proposed in the literature, two of the earliest and best-known ones are the top cycle [Good, 1971; Schwartz, 1972; Miller, 1977] and the uncovered set [Fishburn, 1977; Miller, 1980]. An alternative belongs to the top cycle if it can reach every other alternative via a directed path in the tournament. Note that if the tournament contains n alternatives, any such path has length n-1 or less (the length of a path refers to the number of edges in the path). 1 Similarly, the uncovered set-also known as the set of kings [Maurer, 1980]-consists of the alternatives that can reach every other alternative via a path of length at most two. It is clear from the definitions that the uncovered set is always a subset of the top cycle. Moreover, both tournament solutions can be viewed as special cases of a generalized notion of kings called k-kings, which correspond to the alternatives that can reach every other alternative via a path of length at most k. Indeed, the uncovered set is the set of 2-kings, while the top cycle contains precisely the (n - 1)-kings.

Given that tournament solutions are meant to distinguish the best alternatives from the rest, it is natural to ask how selective each tournament solution is. Moon and Moser [1962] and Fey [2008] addressed this question and showed that the top cycle and the uncovered set are likely to include all alternatives when the tournament is large. In particular, their results hold under the uniform random model, wherein each edge is oriented in one direction or the other with equal probability independently of other edges. Saile and Suksompong [2020] extended these results to the generalized random model, in which the orientation of each edge is determined by probabilities within the range [p, 1 - p] for some parameter p ≤ 1/2, and these probabilities may vary across edges. The generalized random model allowed these authors to demonstrate a difference between the two tournament solutionswhile the top cycle almost never excludes any alternative as long as p ∈ ω(1/n), the uncovered set is likely to select all alternatives only when p ∈ Ω(√log n/n), so the two thresholds differ by roughly Θ(√n). This raises the following question: How does the probability threshold change as we transition from k = 2 to k = n - 1? Does it already decrease at around k = √n, or does it remain the same until, say, k ≈ n/2?

In this paper, we show that, perhaps surprisingly, all of the changes in the probability threshold occur when k is constant. In fact, when k = 6, all alternatives are already likely to be k-kings provided that p ∈ ω(1/n), the same threshold as k = n - 1-this significantly strengthens the result of Saile and Suksompong [2020] on the top cycle. For k = 3 and 4, we establish an asymptotically tight bound of p ∈ Ω(logn/n), while for k = 5 we leave the only (small) gap between Ω(log logn/n) and ω(1/n). Besides the generalized random model, we consider a more specific model which has nevertheless been studied in several papers called the Condorcet random model. In this model, there is a parameter p and a linear order of alternatives from strongest to weakest, and the probability that a stronger alternative dominates a weaker one is 1 - p, independently of other pairs of alternatives. 2 For the Condorcet randommodel, we show that the threshold for k = 5 is ω(1/n), whereas the thresholds for other values of k remain tight. Our results are summarized in Table 1 and presented in Section 3. Taken together, they reveal the intriguing facts that (i) the uncovered set is distinctly more selective than k-kings for k ≥ 3; (ii) 3-kings and 4kings are slightly more selective than higher-order kings; and (iii) there is virtually no difference in discriminative power from k = 5 all the way to k = n - 1.

1 The bound n - 1 cannot be improved. To see this, consider a tournament with alternatives x1, . . . , xn such that xi dominates xj if i - j ≥ 2 or j - i = 1. Alternative x1 can reach every other alternative, but it cannot reach xn via a path of length n- 2 or less.

In addition to k-kings, we also consider the set of single-elimination winners, which are alternatives that can win a (balanced) single-elimination tournament under some bracket, where the match outcomes in the single-elimination tournament are determined according to the dominance relation in the original tournament. 3 Kim et al. [2017] showed that all alternatives are likely to be single-elimination winners in the Condorcet random model as long as p ∈ Ω(logn/n), and this bound is tight. 4 For the generalized random model, they established an analogous statement in the range p ∈ Ω(√log n/n). We close this gap by proving that even for the generalized random model, p ∈ Ω(log n/n) already suffices for all alternatives to be single-elimination winners with high probability; moreover, a winning bracket for each alternative can be computed in polynomial time. Our result, which can be found in Section 4, further lends credence to the observation that real-world tournaments can be easily manipulated [Mattei andWalsh, 2016].

2 The uniform random model corresponds to taking p = 1/2. For any p, the Condorcet random model with parameter p is a special case of the generalized random model with the same p. Hence, a positive result for the generalized random model carries over to the Condorcet random model, while a negative result transfers in the opposite direction.

3 Following prior work on single-elimination tournaments, we assume that the number of alternatives is a power of two.

4 If p ∈ o(logn/n), the weakest alternative dominates o(logn) alternatives in expectation; this is insufficient since winning log2 n matches is required to win a single-elimination tournament.

Finally, in Section 5, we move beyond the question of when all alternatives are likely to be selected by a tournament solution, and instead ask when this is the case for a large or small number of alternatives. For the uncovered set, even though p ∈ Ω(√log n/n) is required in order for all alternatives to be chosen with high probability [Saile and Suksompong, 2020], we show that most of them are already likely to be included as long as p ∈ Ω(logn/n). This threshold is exactly where the transition occurs: if p ∈ O(logn/n), we prove that the uncovered set almost surely contains only a small fraction of the alternatives. Furthermore, for any k ≥ 3, we establish that a large fraction of alternatives are likely to be k-kings provided that p ∈ ω(1/n). These results illustrate the probability range under which each tournament solution is discriminative, and again exhibit a clear difference between the uncovered set and higher-order kings.

1.1 RelatedWork

Tournament solutions have been extensively studied for the past several decades; we refer to the surveys by Laslier [1997] and Brandt et al. [2016]. There are several containment relations among common tournament solutions. For example, the Copeland set, Slater set, Markov set, and Banks set are all contained in the uncovered set, which is in turn contained in the top cycle-this provides a range of options in terms of discriminative power and other properties. Even though kkings admit a simple and elegant definition generalizing the top cycle as well as the uncovered set, and have attracted interest from graph theorists [Petrovic and Thomassen, 1991; Tan, 2006; Brcanov and Petrovic, 2010], as far as we know, they have not been studied in the social choice context until recently. Kim and Vassilevska Williams [2015] and Kim et al. [2017] identified conditions under which a 3-king can win a single-elimination tournament. Brill et al. [2020] showed that computing the "margin of victory" of k-kings can be done efficiently for k ≤ 3 but becomes NP-hard for k ≥ 4. Brill et al. [2021] illustrated through experiments that the margin of victory of 3-kings behaves much more similarly to that of the top cycle than to the corresponding notion of the uncovered set; our results therefore complement theirs by exhibiting that analogous behavior can be observed with respect to discriminative power.

As we mentioned earlier, the study of tournament solutions under the probabilistic lens was initiated by Moon and Moser [1962], who showed that the top cycle is likely to choose all alternatives when the tournament is generated by the uniform random model. Fey [2008] and Scott and Fey [2012] established the same property for the uncovered set as well as two other tournament solutions, the Banks set and the minimal covering set, while Fisher and Ryan [1995] showed that the bipartisan set includes half of the alternatives on average. 5 The Condorcet random model has been analyzed, among others, by Frank [1968], Łuczak et al. [1996], Vassilevska Williams [2010], and Kim et al. [2017], with the last paper also proposing the generalized random model. As Saile and Suksompong [2020] pointed out, the Condorcet random model suffers from limitations such as using the same probability for all pairs of alternatives (regardless of the extent to which one alternative is stronger than the other) or not allowing for "bogey teams" (i.e., weak teams that often beat certain stronger teams). The generalized randommodel only assumes that each match is sufficiently random, and therefore does not have these limitations.

Finally, single-elimination tournaments have constituted a popular topic of study in the past decade; see the surveys by Vassilevska Williams [2016] and Suksompong [2021]. In particular, even though the problem of determining whether an alternative can win a single-elimination tournament is known to be NP-hard [Aziz et al., 2018], a wide range of algorithmic and complexity results have been developed by this active line of work.

2 Preliminaries

A tournament T consists of a set V = {x1, . . . , xn} of vertices, also called alternatives, and a set E of directed edges. For any two alternatives xi, xj ∈ V , there exists either an edge from xi to xj or an edge from xj to xi, but not both. The edges represent a dominance relation between the alternatives: an edge from xi to xj means that xi dominates xj, a relation which we denote by xi ≻ xj. The outdegree (resp., indegree) of an alternative xi is the number of alternatives that xi dominates (resp., that dominate xi). We extend the dominance relation to sets of alternatives: for V1, V2 ⊆ V , we write V1 ≻ V2 to mean that x ≻ x′ for all x ∈ V1 and x′ ∈ V2, and V1 ≻ x′ to mean that x ≻ x′ for all x ∈ V1. A set V ′ ⊆ V is called a dominating set if for every x ∈ V \V ′ , there exists x′ ∈ V ′ such that x′ ≻ x.

We can now define the key notions of this paper.

• For any integer k ≥ 2, an alternative is said to be a kking if it can reach every other alternative via a directed path of length at most k.

5 Brandt et al. [2018] showed that any tournament solution that satisfies an attractive property called stability, including the top cycle, the minimal covering set, and the bipartisan set, must choose at least half of the alternatives on average.

• Suppose that n = 2r for some nonnegative integer r. An alternative is said to be a single-elimination winner if it wins a (balanced) single-elimination tournament under some bracket, where the outcome of each match is determined according to the dominance relation. 6

We will consider two random models for generating tournaments. In the Condorcet random model, there is a parameter 0 ≤ p ≤ 1/2. For i < j, alternative xj dominates xi with probability p (so xi dominates xj with probability 1 - p), independently of other pairs of alternatives. In the generalized random model, there is a parameter pi,j for each pair i ̸= j, where pi,j + pj,i = 1. For any pair i, j, alternative xi dominates xj with probability pi,j, independently of other pairs. We will generally allow each probability pi,j to be chosen from the range [p, 1 - p] for a given parameter 0 ≤ p ≤ 1/2. Before a tournament is generated from the generalized random model, the expected outdegree of xi is defined as ∑j̸=i pi,j. Following standard terminology in probability theory, we say that an event whose probability depends on n occurs "with high probability" if the probability that it occurs approaches 1 as n →∞.

We now list two well-known probabilistic statements that will be used multiple times in this paper. The first statement provides an upper bound on the probability that a sum of independent random variables is far from its expectation.

Lemma 2.1 (Chernoff bound). Let X1, . . . ,Xk be independent random variables taking values in [0, 1], and let X := X1 + · · · +Xk. Then, for any δ ∈ [0, 1],

and

The second statement is a simple upper bound on the expression 1 + x.

Lemma 2.2. For every real number x, we have 1 + x ≤ ex .

We end this section with a lemma on the degree of alternatives in a tournament.

Lemma 2.3. Let 1 ≤ r ≤ n. For any tournament T, the average outdegree and the average indegree of the alternatives in any subset of size r are at least (r - 1)/2. Similarly, the average expected outdegree of the alternatives in such a subset is at least (r -1)/2.

Proof. We prove the statement for the average outdegree; the proofs for the average indegree as well as the average expected outdegree are similar. In a subset of alternatives of size r, there are a total of r(r - 1)/2 edges. Hence, the sum of the outdegrees of the r alternatives is at least r(r - 1)/2, implying that their average is at least (r -1)/2.

Unless a base is explicitly specified, log refers to the natural logarithm. All omitted proofs can be found in the full version of our paper [Manurangsi and Suksompong, 2021].

6 See, e.g., [Aziz et al., 2018] for formal definitions.

3 Generalized Kings

Recall the result of Saile and Suksompong [2020] that in the generalized random model, all alternatives are 2-kings (i.e., belong to the uncovered set) with high probability only if p ∈ Ω(√logn/n). For our first result, we show that 3-kings are not as selective: even when p ∈ Ω(logn/n), it is already likely that none of the alternatives is excluded by this set.

Theorem 3.1. Assume that a tournament T is generated according to the generalized random model, and that pi,j ∈ [30 logn/n, 1-30 logn/n] for all i ̸= j. Then with high probability, all alternatives in T are 3-kings.

To prove this theorem, we establish a rather general lemma on the probability of one set dominating another, which will also be useful in our analysis of 5-kings later.

Lemma 3.2. Let T0 be a tournament consisting of n0 alternatives V0 := {x1, . . . , xn0 }, and let q1,1, q1,2, . . . , qn0,1, qn0,2 ∈ [ 10λ n0 , 1] for some 1 ≤ λ ≤ n0 10 . Suppose that we randomly create a set S1 by including each alternative xi independently with probability qi,1, and a set S2 by including each alternative xi independently with probability qi,2. Then, Pr[S1 ∩ S2 = ∅ and S1 ≻ S2] ≤ e-λ .

Lemma 3.2 allows for a short proof of Theorem 3.1.

Proof of Theorem 3.1. Fix a pair of distinct alternatives xi, xj. We first bound the probability that xj cannot reach xi via a directed path of length at most three.

Consider the tournament T 0 defined by restricting T to V 0 := V \ {xi, xj}. Let S1 denote the set of alternatives in V 0 that dominate xi with respect to T, and let S2 denote the set of alternatives in V 0 that are dominated by xj with respect to T . Notice that if S1 ∩ S2 ̸= ∅ or S1 ̸≻ S2, then there is a path of length at most three from xj to xi. Furthermore, from the assumption of the theorem, each alternative belongs to each of S1 and S2 independently with probability at least 30 log n n , which is at least 25 logn |V 0 | for any sufficiently large n. As a result, we may apply Lemma 3.2 with λ = 2.5 logn, which gives

Pr[there is no path of length at most three from xj to xi]

Finally, applying the union bound over all (ordered) pairs of alternatives xi ̸= xj, the probability that some alternative cannot reach some other alternative via a directed path of length at most three is no more than 1/n0.5 , which converges to 0 as n goes to infinity.

Next, we show that in the Condorcet randommodel, if p ∈ Θ(logn/n) and the associated constant is low enough, there is likely to be an alternative that is not a 4-king. Combined with Theorem 3.1, this implies that the bound Θ(logn/n) is asymptotically tight for both 3- and 4-kings in both random models that we consider.

Theorem 3.3. Assume that a tournament T is generated according to the Condorcet random model, and that p ≤ 0.1 logn/n. Then with high probability, there exists an alternative in T that is not a 4-king.

Our results so far demonstrate that k-kings for any k ≥ 3 are much closer to the top cycle (i.e., (n-1)-kings) than to the uncovered set (i.e., 2-kings) in terms of discriminative power. In the remainder of this section, we show that there is virtually no difference in selectiveness between k-kings for k ≥ 6 and the top cycle. We begin by showing that in the Condorcet random model, all alternatives are likely to be 5-kings provided that p ∈ ω(1/n)-this gives a complete characterization of the probability threshold for the Condorcet randommodel.

Theorem 3.4. Assume that a tournament T is generated according to the Condorcet random model, and that p ∈ ω(1/n). Then with high probability, all alternatives in T are 5-kings.

For the generalized random model, we show that as long as p ∈ ω(1/n), all alternatives are likely to be 6-kings.

Theorem 3.5. Assume that a tournament T is generated according to the generalized random model, and that pi,j ∈ ω(1/n) for all i ̸= j. Then with high probability, all alternatives in T are 6-kings.

In light of Theorem 3.5, the only remaining gap in our probability threshold characterization is for 5-kings in the generalized random model. We conjecture that the true threshold is ω(1/n), but our proof of Theorem 3.4 relies on the ordering of the alternatives in the Condorcet random model and cannot be easily extended. Instead, we present a slightly weaker bound of Ω(log logn/n)-this shows that 5-kings are closer to 6-kings than to 4-kings with respect to selective power. To establish this bound, we need a lemma on generalized dominating sets.

Definition 3.6. Given a positive integer r, a set of alternatives D is said to be an r-dominating set of a tournament T if every alternative x /∈ D is dominated by at least r alternatives in D.

Lemma 3.7. For any tournament T and any positive integer r, there exists an r-dominating set of T of size at most r⌈log2 n⌉.

Proof. Let us start with D = ∅ and repeat the following procedure r times: find a minimum dominating set S of the restriction of T on V \ D, and update D to D ∪ S. It is clear that the final set D is an r-dominating set of T. Furthermore, it is well-known [Megiddo and Vishkin, 1988, Fact 2.5] that any tournament has a dominating set of size at most ⌈log2 n⌉, which implies that the final set D is of size at most r⌈log2 n⌉.

We are now ready to establish our result on 5-kings.

Theorem 3.8. Assume that a tournament T is generated according to the generalized random model, and that pi,j ∈ [50(log logn)/n, 1-50(log logn)/n] for all i ̸= j. Then with high probability, all alternatives in T are 5-kings.

Proof. Define a tournament T ′ on alternatives x1, . . . , xn so that for each pair i ̸= j, we have xi ≻ xj if pi,j > 1/2. Then, our tournament T is generated by reversing the edges of T ′ so that the edge between xi and xj is reversed with probability qi,j := min{pi,j, 1 - pi,j} ≤ 1/2, independently of other edges. For each alternative x, let I(x) denote the set of alternatives that dominate x in T ′ .

Let r = ⌈1.1 log2 n⌉, and let D and Dinv be a minimum r-dominating set of the tournament T ′ and its "inverse" constructed by reversing all edges in T ′ , respectively. From Lemma 3.7, we have |D|, |Dinv| ≤ r⌈log2 n⌉, which is at most 2.3(log n)2 for any sufficiently large n.

We define the following three events in T :

• E1: For every xm ̸∈ D, there exists xi ∈ D such that xi ≻ xm.
• E2: For every xℓ ̸∈ Dinv, there exists xj ∈ Dinv such that xℓ ≻ xj .
• E3: For every xi ∈ D and xj ∈ Dinv, there exists a directed path of length at most three from xj to xi.

Similarly to the proof of Theorem 3.4, when E1, E2, and E3 all occur, every alternative is a 5-king. As a result, it suffices to show that each of the three events occurs with high probability.

For E1, we have

where the first inequality follows the union bound and the fourth inequality from the fact that D is an r-dominating set in T ′ . An analogous argument shows that E2 also occurs with high probability.

Finally, consider E3. Since both D and Dinv are of size O((logn)2 ), by the union bound, it suffices to show that for each fixed pair xi ∈ D and xj ∈ Dinv, a path of length at most three from xj to xi exists with probability 1-o(1/(log n)4 ).

To prove this, consider the tournament T 0 defined by restricting T to V 0 := V \ (D ∪ Dinv). Let S1 denote the set of alternatives in V 0 that dominate xi with respect to T , and let S2 denote the set of alternatives in V 0 that are dominated by xj with respect to T . Notice that if S1 ∩ S2 ̸= ∅ or S1 ̸≻ S2, then there is a path of length at most three from xj to xi. Furthermore, from the assumption of the theorem, each alternative belongs to each of S1 and S2 independently with probability at least 50 log logn n , which is at least 45 log logn |V 0 | for any sufficiently large n. As a result, we may apply Lemma 3.2

with λ = 4.5 log log n, which gives

which concludes our proof.

4 Single-EliminationWinners

In this section, we consider single-elimination winners and derive a tight bound of Ω(logn/n) for the generalized random model, thereby strengthening the bound Ω(√logn/n) of Kim et al. [2017] and matching their bound for the Condorcet random model. As in previous work on this subject, we assume for simplicity that n = 2r for some positive integer r, so r = log2 n. In order to construct a winning bracket, a useful notion is that of a "superking", introduced by Vassilevska Williams [2010].

Definition 4.1. Given a tournament T , an alternative x is said to be a superking if for every alternative x′ such that x′ ≻ x, there exist at least log2 n alternatives x′′ such that x ≻ x′′ and x′′ ≻ x′ .

Lemma 4.2 (Vassilevska Williams [2010]). In any tournament, every superking is a single-elimination winner, and its winning bracket can be computed in polynomial time.

Before we proceed to our result, let us briefly recap the proofs of the two aforementioned results by Kim et al. [2017], and explain why they cannot be used to establish our desired strengthening. In order to show that all alternatives are single-elimination winners with high probability when p ∈ Ω(√logn/n), these authors showed that all alternatives are likely to be superkings in this range; it is not difficult to verify that this condition no longer holds when p ∈ o(√logn/n). For the Ω(logn/n) bound in the Condorcet random model, they argued that the weakest alternative x is likely to dominate one of the top n/6 alternatives, and constructed a winning bracket for this latter alternative y among the top half of the alternatives, so that x can play y in the final round and win the single-elimination tournament. Since there is no clear notion of strength in the generalized random model (indeed, all alternatives may be roughly equally strong, with no linear order), this approach also does not work for our purpose.

At a high level, our proof proceeds by choosing r = log2 n alternatives that our desired winning alternative x dominates. In order to ensure that x can play against these alternatives in the r rounds, we partition the r alternatives along with the remaining alternatives into subsets of size 1, 2, . . . , 2r-1 , so that the r alternatives are superkings in the respective subtournament and can therefore win a single-elimination tournament with respect to their subset by Lemma 4.2.

Theorem 4.3. Assume that a tournament T is generated according to the generalized random model, and that pi,j ∈ [80 logn/n, 1-80 logn/n] for all i ̸= j. Then with high probability, all alternatives in T are single-elimination winners, and a winning bracket of each alternative can be computed in polynomial time.

5 Number of Kings

So far, we have addressed the question of when each tournament solution is likely to select all alternatives, i.e., the case where the solution is decidedly not useful. In this section, we move beyond this question (which is also the focus of several previous works) and ask when a small or large number of alternatives are chosen. Our first result shows that even though p ∈ Ω(√log n/n) is required for the uncovered set to choose all alternatives with high probability [Saile and Suksompong, 2020], the smaller threshold of p ∈ Ω(logn/n) suffices in order for most of the alternatives to be included.

Theorem 5.1. Assume that a tournament T is generated according to the generalized random model, and that pi,j ∈ [50 logn/n, 1-50 logn/n] for all i ̸= j. Then with high probability, at least 0.9n alternatives in T are 2-kings.

Proof. Assume without loss of generality that the alternatives before the tournament T is generated are x1, . . . , xn in nonincreasing order of expected outdegree. Let r = ⌈0.9n⌉, and consider any 1 ≤ i ≤ r. We will show that the probability that xi is a 2-king in T is at least 1 - o(1/n). The union bound then implies that with high probability, at least 0.9n alternatives in T are 2-kings.

To show that Pr[xi is a 2-king in T] is at least 1-o(1/n), the union bound again implies that it suffices to prove that Pr[there is no path of length at most two from xi to xj] is at most o(1/n2 ) for each alternative xj ̸= xi.

We henceforth fix 1 ≤ i ≤ r and xj ̸= xi. By Lemma 2.3 on xi, xi+1, . . . , xn, the expected outdegree of xi is at least (n-i)/2, which is at least 0.045n for any sufficiently large n. As a result, for large enough n, we have

We use Lemma 2.2 for the first inequality, and the assumption that the expected outdegree of xi is at least 0.045n for the last inequality. This concludes our proof.

Our next result establishes the asymptotic tightness of the threshold in Theorem 5.1.

Theorem 5.2. Assume that a tournament T is generated according to the Condorcet random model, and that p ≤ 0.1 log n/n. Then with high probability, at most √n log n alternatives in T are 2-kings.

Finally, we show that as long as p ∈ ω(1/n), a large number of alternatives are already likely to be 3-kings (and therefore k-kings for every k ≥ 3). This bound is again tight: when p ∈ O(1/n) and the tournament is generated from the Condorcet randommodel, there is at least a constant probability that the strongest alternative dominates all remaining alternatives (in which case it is the only k-king for each k ≥ 2).

Theorem 5.3. Assume that a tournament T is generated according to the generalized random model, and that pi,j ∈ ω(1/n) for all i ̸= j. Then with high probability, at least 0.9n alternatives in T are 3-kings.

6 Concluding Remarks

In this paper, we have extensively investigated the behavior of generalized kings and single-elimination winners in random tournaments in view of their discriminative power. Our results reveal surprisingly clear distinctions between the uncovered set and k-kings for k ≥ 3, and illustrate why manipulating a single-elimination tournament is often possible in practice despite the problem being NP-hard. All of the bounds that we obtained are asymptotically tight except for the bound for 5-kings in the generalized random model (Theorem 3.8); one could try to close this gap.

An exciting future direction in our view is to study k-kings and single-elimination winners with respect to axiomatic and computational properties, as is commonly done for other tournament solutions [Laslier, 1997; Brandt et al., 2016]. For example, the uncovered set is known to be the finest tournament solution satisfying Condorcet consistency, neutrality, and expansion [Moulin, 1986]. Which axioms does the set of 3-kings satisfy, and can we characterize it by a collection of axioms? One could also study the relationship between these tournament solutions and traditional ones-this was partially done by Kim et al. [2017], who showed for instance that any alternative in the Copeland set or the Slater set can always win a single-elimination tournament. Another possible avenue is to extend our results to other stochastic models for tournaments-several interesting models have been studied experimentally by Brandt and Seedig [2016] and Brill et al. [2021]. Such questions illustrate the richness of tournaments and probabilistic models, which we expect to give rise to further fruitful research.

Acknowledgments

This work was partially supported by an NUS Start-up Grant. We would like to thank the anonymous reviewers for their valuable comments.