# fixing_knockout_tournaments_with_seeds__941a9a6d.pdf

Fixing Knockout Tournaments With Seeds

Pasin Manurangsi1 and Warut Suksompong2

1Google Research, USA 2School of Computing, National University of Singapore, Singapore pasin@google.com, warut@comp.nus.edu.sg

Knockout tournaments constitute a popular format for organizing sports competitions. While prior results have shown that it is often possible to manipulate a knockout tournament by fixing the bracket, these results ignore the prevalent aspect of player seeds, which can significantly constrain the chosen bracket. We show that certain structural conditions that guarantee that a player can win a knockout tournament without seeds are no longer sufficient in light of seed constraints. On the other hand, we prove that when the pairwise match outcomes are generated randomly, all players are still likely to be knockout winners under the same probability threshold with seeds as without seeds. In addition, we investigate the complexity of deciding whether a manipulation is possible when seeds are present.

1 Introduction Several practical scenarios involve choosing a winner from a given set of candidates based on pairwise comparisons, perhaps most prominently sports competitions. A popular format for organizing such competitions is a knockout tournament, also known as a single-elimination or sudden death tournament, wherein the players are matched according to an initial bracket and play proceeds until the tournament winner is determined. When there are n participating players, a knockout tournament requires arranging only n 1 matches, thereby making it an attractive choice among organizers in comparison to a round-robin tournament, for which Θ(n2) matches are necessary. Moreover, the fact that each player is eliminated after a single loss adds a layer of excitement and ensures that no match is meaningless in a knockout tournament. As efficient and as exciting as knockout tournaments are, they have a clear drawback in that their winner can depend heavily on the chosen bracket. A significant line of work in computational social choice has therefore investigated the problem of when it is possible for the organizers to fix a bracket to help their preferred player win the tournament, given the knowledge of which player would win in any pairwise matchup [Vu et al., 2009; Vassilevska Williams, 2010; Stanton and Vassilevska Williams, 2011; Kim and Vassilevska Williams, 2015; Chatterjee et al., 2016;

Kim et al., 2017; Ramanujan and Szeider, 2017; Aziz et al., 2018; Gupta et al., 2018; Konicki and Vassilevska Williams, 2019; Manurangsi and Suksompong, 2021].1 This problem is known as the tournament fixing problem (TFP). While TFP is NP-complete [Aziz et al., 2018], several structural conditions have been shown to guarantee that a certain player can win a knockout tournament under some bracket, which can be computed efficiently. For example, Vassilevska Williams [2010] proved that if a player x is a king meaning that for any other player y who beats x, there exists another player z such that x beats z and z beats y and x beats at least n/2 other players, then x can win a knockout tournament. Moreover, a number of papers have shown that fixing knockout tournaments is usually easy when the pairwise match outcomes are drawn from probability distributions [Vassilevska Williams, 2010; Stanton and Vassilevska Williams, 2011; Kim et al., 2017; Manurangsi and Suksompong, 2021]. While previous results on TFP have shed light on the manipulability of knockout tournaments, they hinge upon a pivotal assumption that the organizers can choose an arbitrary bracket for their tournament. In reality, the choice of bracket is often much more constrained. In particular, many realworld tournaments assign seeds to a subset of players in order to prevent highly-rated players from having to play each other too early in the tournament. For instance, in ATP tennis tournaments with 32 players, eight players are designated as seeds, and the bracket must be chosen so that the top two seeds cannot meet until the final, the top four seeds cannot meet until the semifinals, and all eight seeds cannot meet until the quarterfinals [ATP Tour, 2022, p. 139]. As such, algorithms that do not take seeds into account may fail to generate a valid bracket for the competition. Do prior results in this line of work continue to hold in the presence of seed constraints, or are knockout tournaments more difficult to manipulate in light of these constraints?

1.1 Our Results Following most real-world tournaments, we assume that the knockout tournament is balanced, and that both the number of players n and the number of seeds are powers of two. We begin in Section 3 by examining structural conditions from the non-seeded setting. Besides the kings who beat

1For an overview of this line of work, we refer to the surveys by Vassilevska Williams [2016] and Suksompong [2021].

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

at least n/2 players condition that we already mentioned, another basic condition that suffices for guaranteeing that a player can win a knockout tournament is the superking condition [Vassilevska Williams, 2010].2 We show that both of these conditions are no longer sufficient in the seeded setting. Specifically, for any number of seeds, a king who is not one of the top two seeds may not be able to win a knockout tournament even if it can beat all other players except one. Likewise, if there are at least four seeds, then a king who is assigned one of the top two seeds and beats all but one player may still be unable to win. On the positive side, when there are only two seeds, a seeded king who beats at least n/2 + 1 players is guaranteed to be a winner under some bracket, and the bound n/2 + 1 is tight. We also prove similar results for superkings: with two seeds, a superking can always win under some bracket, but as soon as there are at least four seeds, it may no longer be able to win a knockout tournament even if it is one of the top four seeds. We therefore introduce a stronger condition of ultraking and show that an ultraking can win a knockout tournament for any number of seeds. In Section 4, we investigate the problem of fixing knockout tournaments from a probabilistic perspective. In particular, we assume that the pairwise outcomes are determined according to the so-called generalized random model, where player i beats player j with probability pij, and these probabilities may vary across different pairs i, j but are always at least a given parameter p. Our prior work has shown that in the non-seeded setting, as long as p = Ω(log n/n), all players are likely to be knockout winners [Manurangsi and Suksompong, 2021]. We strengthen that result by showing that the same holds even in the seeded setting, regardless of the number of seeds. Combined with our findings in Section 3, this strengthened result shows that even though the presence of seed constraints makes it more difficult to fix tournaments in the worst case, most of the time it does not render manipulation infeasible. Finally, in Section 5, we address the complexity of TFP in the seeded setting. By reducing from TFP in the non-seeded setting, we show that the problem is NP-complete, both when the number of seeds is an arbitrary constant and when it is n/2 (i.e., the highest possible). On the other hand, we provide an algorithm that solves TFP in 2n n O(1) time, thereby generalizing a result of Kim and Vassilevska Williams [2015] from the setting without seeds.

2 Preliminaries As is common in this line of work, we assume that the knockout tournament is balanced and played among n = 2r players for some positive integer r. In the seeded setting, there is a parameter 2 s n, which we also assume (following the vast majority of real-world tournaments) to be a power of two. Among the n players, s of them are assigned seeds 1, 2, . . . , s. The bracket must be set up in such a way that seeds 1 and 2 cannot play each other before the final, seeds 1 through 4 cannot play each other before the semifinals, seeds 1 through 8 cannot play each other before the quarterfinals, and so on. A bracket satisfying these seed constraints is said

2See the definition in Section 2.

to be valid. Observe that s = n is equivalent to s = n/2, so we assume henceforth that 2 s n/2. Notice also that larger values of s only add extra constraints compared to smaller values of s. We refer to the setting without seeds typically studied in previous work as the non-seeded setting. Unless stated otherwise, our results are for the seeded setting. The tournament fixing problem (TFP) asks whether there exists a valid bracket that makes our desired winner x win the tournament; if the answer is positive, we refer to x as a knockout winner. We are given a tournament graph T = (V, E), which indicates the winner of any pairwise matchup. The vertices in V correspond to the n players we will refer to vertices and players interchangeably and there is a directed edge in E from player x to player y whenever x would beat y if they were to play against each other. We use x y to denote an edge from x to y. We extend this notation to sets of vertices: for V1, V2 V , we write V1 V2 to mean that x y for all x V1 and y V2, and V1 y to mean that x y for all x V1. The outdegree of a vertex x is the number of players whom x beats in T. A player x is said to be a king if for any other player y who beats x, there exists another player z who loses to x but beats y. Equivalently, x is a king if it can reach every other player via a path of length at most two in T. A player x is said to be a superking if for any other player y who beats x, there exist at least log n players who lose to x but beat y.3 It is clear from the definitions that every superking is also a king. When constructing a bracket, we will sometimes do so iteratively one round at a time, starting with the first round. In each round, we pair up the players who remain in that round. During this process, it can happen that a seeded player is beaten by an unseeded player, or that a stronger-seeded player (i.e., player with a lower-number seed) is beaten by a weaker-seeded player (i.e., player with a higher-number seed). In such cases, we will think of the (stronger) seed as being transferred from the losing player to the winning player, since the constraints on the losing player s seed apply to the winning player in subsequent rounds. We stress that the concept of a transfer is merely for the sake of constructing a bracket and does not imply that the seeds are actually transferred between players when the actual tournament takes place.

3 Structural Results

In this section, we examine the extent to which structural guarantees from the non-seeded setting continue to hold in the seeded setting. Vassilevska Williams [2010] proved that, without seeds, a king with outdegree at least n/2 is a knockout winner,4 and the same holds for a superking. As we will see, these conditions are largely insufficient for guaranteeing that a player can win in the presence of seeds. We assume throughout this section that our desired winner x is a king. Denote by A the set of players whom x beats,

3Throughout the paper, log refers to the logarithm with base 2. 4We reiterate here that we use the term knockout winner to refer to a player who can win a knockout tournament under some bracket.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

and B = V \ (A {x}) the set of players who beat x. A structure that will be used multiple times in this section is a special tournament graph , defined as follows.

Definition 3.1. A tournament graph T is said to be a special tournament graph if there exists y A such that y B and B (A \ {y}). The edges within each of A and B can be oriented arbitrarily. An illustration is shown in Figure 1.

Figure 1: Illustration of a special tournament graph

When we refer to a special tournament graph, we will use the notation x, y, A, B as in Figure 1. The results of this section are summarized in Table 1.

3.1 Kings of High Outdegree

We begin by observing that in the seeded setting, a king x may not be able to win a knockout tournament even if it beats n 2 other players. This draws a sharp contrast to the nonseeded setting, where beating n/2 other players already suffices [Vassilevska Williams, 2010]. Note that the bound n 2 is also tight: if x beats n 1 players, then it beats every player and can trivially win.

Proposition 3.2. For any n 4 and any s, a king with outdegree n 2 who is not one of the top two seeds is not necessarily a knockout winner.

Proof. Consider a special tournament graph with |A| = n 2, and let z be the unique player in B. Assume that y and z are the top two seeds. Since y is the only player who can beat z, and these two players cannot meet until the final, z makes the final in every valid bracket. Thus, even if the king x makes the final, it will be beaten by z there, which means that x is not a knockout winner.

The construction in the proof above relies on the assumption that x is not one of the top two seeds. We show next that if there are only two seeds and x is one of them, then it can win a knockout tournament as long as it has outdegree at least n/2 + 1. This means that the seed constraint does not make manipulation much harder in this case. To establish this result, we employ a similar algorithm as that of Vassilevska Williams [2010] for the kings who beat at least n/2 players guarantee, but our analysis is more involved due to the seed constraint.

Theorem 3.3. For s = 2 and any n, a seeded king x with outdegree at least n/2+1 is always a knockout winner. Moreover, there exists a polynomial-time algorithm that computes a valid winning bracket for x.

Proof. The case n = 2 holds vacuously, so assume that n 4. Since s = 2, the only constraint is that the two seeds cannot meet before the final. We will simultaneously prove the following two statements by induction on n:

(a) A seeded king x with outdegree at least n/2+1 is always a knockout winner.

(b) For a special tournament graph with seeded king x and |A| = n/2, if the other seed belongs to B {y}, then x is a knockout winner.

Note that even though only statement (a) is needed for this theorem, a proof by induction using statement (a) alone does not work, and we also need statement (b) in order for the induction to go through. We first handle the base case n = 4. Statement (a) holds trivially because x beats all other players. For statement (b), denote by z the unique player in B and by w the player in A besides y. By the assumption of the statement, w is not a seed. We let x play w and y play z in the first round, so that x beats y in the final and wins the tournament. We proceed to the inductive step. Assume that the statements hold for n/2 4; we will prove both of them for n at the same time. Consider the following algorithm. In the first round, we find a maximum matching M from A to B (in the underlying directed graph between A and B) and pair up players according to M. Note that the matching M is always nonempty, and let AM and BM be the players from A and B in the matching, respectively. Among the remaining players, we match x with an unseeded player in A, match players within A arbitrarily, match players within B arbitrarily, and finally, if necessary, match the leftover player in B with the leftover player in A. Denote by A A and B B the players in A and B who remain after this round, respectively. We consider three cases.

Case 1: |A| n/2+2. We have |B| n/2 3, so after matching players according to M, there are still at least five players left in A. This means that we can match x with an unseeded player in A. Since M has size at least 1 and we match one player in A with x, |A | n/4 + 1. Moreover, every player z B \ BM beats every player in A \ AM (otherwise the matching can be enlarged), so since x is a king, z must lose to at least one player in AM. This implies that x is still a king in the remainder tournament. By the inductive hypothesis for statement (a), there exists a winning bracket for x in the remainder tournament, and therefore x can also win the original tournament.

Case 2: |A| = n/2 + 1. We have |B| = n/2 2, so by a similar reasoning as in Case 1, we can match x with an unseeded player in A. If M has size at least 2, then |A | n/4 + 1 and we are done as in Case 1. Assume therefore that M has size 1, which means that the tournament graph is a special tournament graph, with

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

Conditions Knockout winner guarantee Any n 4, any s, not one of the top two seeds, outdegree n 2 No (Proposition 3.2) s = 2, any n, seeded, outdegree n/2 + 1 Yes (Theorem 3.3) s = 2, any n 4, seeded, outdegree n/2 No (Theorem 3.5) Any 4 s n/2, one of the top two seeds, outdegree n 2 No (Proposition 3.6) s = 2, any n, superking Yes (Theorem 3.7) Any 4 s n/2, one of the top four seeds, superking No (Proposition 3.8) Any n and s, ultraking Yes (Theorem 3.10)

Table 1: Summary of our results in Section 3 on whether each set of conditions is sufficient to guarantee that a king can win a knockout tournament under some bracket.

a player y A beating all players in B. In this special case, we add an extra constraint to the algorithm: if the seed besides x belongs to A \ {y}, then we leave this seed to be paired with a player in B in the final step of the algorithm, so that the seed is transferred to B for the next round (since |A| is odd, the final step of the algorithm takes place). This ensures that in the remainder tournament, which also has a special tournament graph, the seed other than x belongs to B {y}. Since |A | = n/4, we are done by the inductive hypothesis for statement (b).

Case 3: |A| = n/2, the tournament graph is a special tournament graph, and the seed besides x belongs to B {y}. In this case, the maximum matching M has size 1. After applying the algorithm for the first round, the remainder tournament still has a special tournament graph, |A | = n/4, and the seed other than x belongs to B {y}. Hence, we are done by the inductive hypothesis for statement (b).

The three cases together complete the induction. Since constructing each round of the bracket takes polynomial time and the number of rounds is logarithmic, the overall algorithm runs in polynomial time.

Interestingly, our next result establishes the tightness of the bound n/2 + 1 in Theorem 3.3 this provides a separation from the n/2 bound in the non-seeded setting. To this end, we will need the following lemma. The case |A| = n/2 1 of the lemma was proven as Claim 2 in the work of Vassilevska Williams [2010], and the same proof applies to the more general condition |A| n/2 1 that we state below.

Lemma 3.4 ([Vassilevska Williams, 2010]). In the nonseeded setting, for a special tournament graph with king x and |A| n/2 1, x is not a knockout winner.

Theorem 3.5. For s = 2 and any n 4, a seeded king with outdegree n/2 is not necessarily a knockout winner.

Proof. Consider a special tournament graph with |A| = n/2, and assume that the other seed w = x belongs to A \ {y}. We prove by induction on n that x is not a knockout winner for this tournament graph. For the base case n = 4, denote by z the unique player in B. Since x cannot play w in the

first round, it must play y in order to progress to the final. However, since z beats w, x will play z in the final and lose. We proceed to the inductive step. Assume that the statement holds for n/2 4; we will prove it for n. In order for x to have a chance of winning the tournament, we must match it with a player from A. This player must be different from y; otherwise no player outside B can eliminate players in B. If we match y with a player in B and pair up the remaining n/2 2 players in B, then n/4 1 players from B proceed to the next round, the tournament graph is still a special tournament graph, and the seeds are still x and a player in A \ {y}, so we may apply the inductive hypothesis. Otherwise, at least n/4 players from B proceed to the next round. If y does not proceed, no player outside B can eliminate players in B and x cannot win, so we may assume that y proceeds. In this case, the tournament graph is again a special tournament graph. Since |B| n/4, we have |A| n/4 1, so Lemma 3.4 implies that x is not a knockout winner. This completes the induction and therefore the proof.

When s 4, we know from Proposition 3.2 that if the king x is not one of the top two seeds, then it may not be able to win even if its outdegree is n 2. A similar construction shows that the same also holds when x is one of the top two seeds, which means that manipulation with s 4 is more difficult than with s = 2. Proposition 3.6. For any 4 s n/2, a king x with outdegree n 2 is not necessarily a knockout winner even if x is one of the top two seeds. The proof of Proposition 3.6, along with all other omitted proofs, can be found in the full version of our paper [Manurangsi and Suksompong, 2022].

3.2 Superkings Next, we consider the superking condition recall that a superking is always a knockout winner in the non-seeded setting [Vassilevska Williams, 2010]. We prove that if there are only two seeds, then a superking can win the tournament regardless of whether it is seeded. This stands in contrast to Proposition 3.2, which shows that a king may not be able to win for any s even if it has outdegree n 2. Theorem 3.7. For s = 2 and any n, a superking x is always a knockout winner. Moreover, there exists a polynomial-time algorithm that computes a valid winning bracket for x.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

On the other hand, when there are at least four seeds, the superking condition is no longer sufficient.

Proposition 3.8. For any 4 s n/2, a superking is not necessarily a knockout winner even if it is one of the top four seeds.

In light of Proposition 3.8, we introduce the following strengthening of a superking, where we replace the parameter log n in its definition by n/2.

Definition 3.9. A player x is said to be an ultraking if for any other player y who beats x, there exist at least n/2 players who lose to x but beat y.

Our next theorem shows that the ultraking condition is sufficient to guarantee that a player can win a knockout tournament in the seeded setting, regardless of the number of seeds.

Theorem 3.10. For any n and s, an ultraking x is always a knockout winner. Moreover, there exists a polynomial-time algorithm that computes a valid winning bracket for x.

We remark that Theorem 3.10 would no longer hold if the parameter n/2 in Definition 3.9 were reduced to n/2 1. Indeed, if s = n/2 and the ultraking x is seeded and beats the other n/2 1 seeded players in A, all of whom beat the n/2 unseeded players in B, then x cannot even win its first-round match in any valid bracket.

4 Probabilistic Results

In this section, we investigate the problem of fixing tournaments from a probabilistic perspective. We work with the so-called generalized random model [Kim et al., 2017; Saile and Suksompong, 2020]. In this model, we are given a parameter p [0, 1/2], and every pair of distinct i, j {1, . . . , n} is assigned a real number pij [p, 1 p], where pij = 1 pji for all i = j. Assuming that the players are x1, . . . , xn, the tournament graph T is then generated as follows: for each pair i = j, player xi beats player xj with probability pij. Our main result of this section is stated below. Following standard terminology, with high probability means that the probability converges to 1 as n .

Theorem 4.1. Let s = n/2 and p 160 ln n/n. With high probability, all players are knockout winners, and a winning bracket for each player can be computed in polynomial time.

As mentioned in Section 2, s = n/2 gives rise to the most restrictive set of constraints, so Theorem 4.1 implies the same result for all other values of s. The theorem also strengthens our previous result in the non-seeded setting [Manurangsi and Suksompong, 2021].5 Moreover, it entails similar results for random models that are special cases of the generalized random model, including the Condorcet random model and the uniform random model .6 The bound p = Ω(log n/n) is tight even in the non-seeded setting: if p = o(log n/n) and

5Modulo the constant factor, which is twice as large as our previous one. 6See, e.g., our prior work [Manurangsi and Suksompong, 2021] for the definitions. We remark here that the parameter p is present in the Condorcet random model but not in the uniform random model.

pij = p for all i > j, then the weakest player is expected to beat fewer than log n players, which is insufficient because a knockout tournament consists of log n rounds. The proof of Theorem 4.1 can be found in the full version of our paper [Manurangsi and Suksompong, 2022]; we provide here a brief sketch. For ease of exposition, we assume that our desired winner x is unseeded. To begin with, we use our prior result from the non-seeded setting [Manurangsi and Suksompong, 2021] to find a winning bracket B for x among the n/2 unseeded players. We then extend this bracket into a full bracket of size n so that after the first round is played, the bracket becomes B. To achieve this, we assign seeds 1 and 2 to the two halves in the first step, and then seeds 2k 1 + 1, . . . , 2k in each step k 2. For each 2 k log n 1, we have the freedom of assigning the 2k 1 seeds to any section of the bracket containing 2n k players with the property that the section has not been assigned any seeded player thus far (there are 2k 2k 1 = 2k 1 such sections). Since we want the bracket to become B after the first round, we must also ensure that each seeded player loses in the first round. To this end, we create a bipartite graph between the seeds 2k 1 +1, . . . , 2k and the unassigned sections, where an edge is present if the seed loses against at least one unseeded player in that section. We then find a perfect matching in this graph and assign these seeds accordingly. The main technical aspect of the proof lies in showing that such a perfect matching is likely to exist. For this, we need to extend the classic result of Erd os and R enyi [1964] on the existence of perfect matchings in random graphs to a larger parameter regime.

5 Computational Complexity

In this section, we turn our attention to the complexity of computing a valid winning bracket for our desired winner. Recall that this problem is NP-complete in the non-seeded setting [Aziz et al., 2018]. We show that the intractability continues to hold in the seeded setting.

Theorem 5.1. For any constant number of seeds s, TFP is NP-complete.

Proof. The problem belongs to NP since a valid winning bracket for our desired winner x can be verified in polynomial time, so we focus on the hardness. We reduce from TFP in the non-seeded setting. For ease of presentation, we will first show the reduction for s = 4 and later explain how to extend it to any constant value of s. Let I be an instance of non-seeded TFP with a set V of n players, one of whom is our desired winner x. We create sets V1 and V2 of players with the following properties:

|V1| = n, and x1 V1 beats all other players in V1.

|V2| = 2n, and x2 V2 beats all other players in V2.

All players in V1 beat all players in V , with the exception that x beats x1.

All players in V2 beat all players in V , with the exception that x beats x2.

All remaining outcomes can be chosen arbitrarily.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

The new instance I consists of n+n+2n = 4n players. The top two seeds are x and x2, and the other two seeds are x1 and an arbitrary player y V2. This completes the description of our reduction; an illustration is shown in Figure 2. Note that the reduction takes polynomial time.

Figure 2: Illustration of the reduction for Theorem 5.1 when s = 4

We claim that x can win in the original instance I if and only if it can win in the new instance I . ( ) Suppose that x can win in I. To construct a winning bracket for x in I , we use the winning bracket for x in I as one quarter, put the players from V1 in the other quarter in the same half as x, and put the players from V2 in the opposite half to x in such a way that x2 and y are in different quarters. Notice that the constructed bracket satisfies the seed constraints. In the resulting tournament, x progresses to the semifinals by winning its bracket for I, x1 progresses to the semifinals by winning its quarter, and x2 progresses to the final by winning its half. Hence, x beats x1 in the semifinals and beats x2 in the final, and therefore wins the tournament. ( ) Suppose that x can win in I , and consider its winning bracket. We claim that x s quarter must contain exactly the players from V . Indeed, it cannot contain x1 or x2 due to seed constraints, and if it contains players from (V1 V2) \ {x1, x2}, then since all of these players beat all players in V , the winner of x s quarter will be from (V1 V2) \ {x1, x2}, and in particular not x. Hence, the bracket of x s quarter is a winning bracket for x in I. This completes the NP-hardness proof for s = 4. To extend it to any constant number of seeds s = 2t (including s = 2), we use a similar construction. Starting with a non-seeded TFP instance I of n players, we create sets V1, V2, . . . , Vt of size n, 2n, . . . , 2t 1n. For each 1 i t, Vi contains a player xi who beats all other players in Vi, and all players in Vi beat all players in V except that x beats xi. The new instance I consists of 2tn players. The seeds are assigned as follows:

The top two seeds are x and xt.

The next two seeds are xt 1 and a player in Vt.

The next four seeds are xt 2, a player in Vt 1, and two players in Vt.

The last 2t 1 seeds are x1, a player in V2, two players in V3, four players in V4, . . . , and 2t 2 players in Vt.

If x can win in I, then we can construct a bracket in I so that after winning its subtournament from I, x beats x1, x2, . . . , xt in the last t rounds to win the tournament for I . Conversely, if x can win in I , a similar argument as in the case s = 4 shows that the section of the bracket containing x s first log n rounds must contain exactly the players from V ; this yields a winning bracket for x in I. Finally, since s is constant, the reduction takes polynomial time.

The problem remains intractable when the number of seeds is the maximum possible.

Theorem 5.2. For s = n/2, TFP is NP-complete.

Despite these hardness results, we present an algorithm that solves TFP in 2n n O(1) time in the full version of our paper [Manurangsi and Suksompong, 2022]. The algorithm extends a corresponding one by Kim and Vassilevska Williams [2015] to the seeded setting and matches its running time, which is also the current best in the non-seeded setting.

6 Conclusion and Future Work

In this paper, we have investigated the problem of fixing a knockout tournament in the ubiquitous setting where a subset of the players are designated as seeds. Our results exhibit both similarities and differences in comparison to the setting without seeds. On the one hand, the decision problem of whether a certain player can be made a tournament winner remains computationally hard, and manipulation is still feasible in the average case. On the other hand, a number of structural conditions that guarantee that a player can win in the non-seeded setting cease to do so in the seeded setting.7

While the seed constraints that we studied in this work are both common and natural, some real-world tournaments employ more restrictive versions of constraints. For example, in World Snooker Championships which are competed among 32 players, 16 of whom are seeds the bracket is set up to ensure that if the top four seeds all make it to the semifinals, the first seed will play against the fourth seed and the second against the third; analogous conditions apply to the quarterfinals as well as the round of 16.8 With these constraints, the only freedom in choosing the bracket is in pairing seeded players with unseeded players in the first round. Another notable example is the seeding used in Grand Slam tennis tournaments, which involve 128 players and 32 seeds. While the constraints for the semifinals and quarterfinals are the same as those that we studied, additional constraints are imposed in the rounds of 16 and 32. For instance, in the round of 16, the bracket must be set up so that seeds 9 12 fall in different eighths from seeds 1 4 [Grand Slam Board, 2021, p. 26]. Studying the extent to which manipulation is still possible in such tournaments is an interesting avenue for future research.

7Our negative results in Section 3 also apply to the conditions put forth by Kim et al. [2017, Thm. 2.1], since these conditions generalize both the superking and the king of high outdegree conditions. 8See wikipedia.org/wiki/2021 World Snooker Championship.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

Acknowledgments

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

[ATP Tour, 2022] ATP Tour. 2022 ATP Official Rulebook. http://www.atptour.com/en/corporate/rulebook, 2022. Accessed 2022-01-10.

[Aziz et al., 2018] Haris Aziz, Serge Gaspers, Simon Mackenzie, Nicholas Mattei, Paul Stursberg, and Toby Walsh. Fixing balanced knockout and double elimination tournaments. Artificial Intelligence, 262:1 14, 2018.

[Chatterjee et al., 2016] Krishnendu Chatterjee, Rasmus Ibsen-Jensen, and Josef Tkadlec. Robust draws in balanced knockout tournaments. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), pages 172 179, 2016.

[Erd os and R enyi, 1964] Paul Erd os and Alfr ed R enyi. On random matrices. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 8:455 461, 1964.

[Grand Slam Board, 2021] Grand Slam Board. 2021 Official Grand Slam Rulebook. http://www.itftennis.com/media/ 5986/grand-slam-rulebook-2021-f.pdf, 2021. Accessed 2022-01-10.

[Gupta et al., 2018] Sushmita Gupta, Sanjukta Roy, Saket Saurabh, and Meirav Zehavi. When rigging a tournament, let greediness blind you. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pages 275 281, 2018.

[Kim and Vassilevska Williams, 2015] Michael P. Kim and Virginia Vassilevska Williams. Fixing tournaments for kings, chokers, and more. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pages 561 567, 2015.

[Kim et al., 2017] Michael P. Kim, Warut Suksompong, and Virginia Vassilevska Williams. Who can win a singleelimination tournament? SIAM Journal on Discrete Mathematics, 31(3):1751 1764, 2017.

[Konicki and Vassilevska Williams, 2019] Christine Konicki and Virginia Vassilevska Williams. Bribery in balanced knockout tournaments. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 2066 2068, 2019.

[Manurangsi and Suksompong, 2021] Pasin Manurangsi and Warut Suksompong. Generalized kings and singleelimination winners in random tournaments. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pages 328 334, 2021.

[Manurangsi and Suksompong, 2022] Pasin Manurangsi and Warut Suksompong. Fixing knockout tournaments with seeds. Co RR, abs/2204.11171, 2022.

[Ramanujan and Szeider, 2017] M. S. Ramanujan and Stefan Szeider. Rigging nearly acyclic tournaments is fixedparameter tractable. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pages 3929 3935, 2017. [Saile and Suksompong, 2020] Christian Saile and Warut Suksompong. Robust bounds on choosing from large tournaments. Social Choice and Welfare, 54(1):87 110, 2020. [Stanton and Vassilevska Williams, 2011] Isabelle Stanton and Virginia Vassilevska Williams. Manipulating stochastically generated single-elimination tournaments for nearly all players. In Proceedings of the 7th International Workshop on Internet and Network Economics (WINE), pages 326 337, 2011. [Suksompong, 2021] Warut Suksompong. Tournaments in computational social choice: Recent developments. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pages 4611 4618, 2021. [Vassilevska Williams, 2010] Virginia Vassilevska Williams. Fixing a tournament. In Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI), pages 895 900, 2010. [Vassilevska Williams, 2016] Virginia Vassilevska Williams. Knockout tournaments. In Felix Brandt, Vincent Conitzer, Ulle Endriss, J erˆome Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, chapter 19, pages 453 474. Cambridge University Press, 2016. [Vu et al., 2009] Thuc Vu, Alon Altman, and Yoav Shoham. On the complexity of schedule control problems for knockout tournaments. In Proceedings of the 8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 225 232, 2009.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)