Rigging Tournament Brackets for Weaker Players

1 Introduction

As a natural way to select a leader, competition is at the heart of life. It is intriguing, both for its participants, and its spectators. Society is riddled with organized competitions called tournaments with well-defined rules to select a winner from a pool of candidate players. Sports tournaments such as the FIFA World Cup and Wimbledon are immensely popular and generate huge amounts of revenue. Elections are another important type of tournaments: a leading party is selected according to some rules using votes from the population.

Two of the most common tournament formats employed in both sports and voting are round-robin and single-elimination. In the former, every pair of players are matched up, and a player's score is how many matches they won. If some player has beaten everyone else, then they are the clear (Condorcet) winner. Otherwise, the winner is not well-defined. However, given the outcomes of a round-robin tournament, there are various methods of producing rankings of the players. The most common definition of the optimal ranking is that it minimizes the number of wins of a lower-ranked player over a higher-ranked player [Slater, 1961]. Although finding such a ranking for a round-robin tournament is NPhard [Alon, 2006], sorting the players according to their number of wins is a good approximation to the optimum ranking [Coppersmith et al., 2006].

Single-elimination (SE) tournaments are played as follows. First, a permutation of the players, called the bracket or schedule is given. According to the bracket, the first two players are matched up, then the second pair of players etc. The winners of the matches move on to the next round. The bracket for this round is obtained by pairing up the remaining players according to the original bracket. If the number of players is a power of 2, the tournament is balanced. Otherwise, it is unbalanced and some players advance to the next round without playing a match. In practice, these byes are usually granted in the first round. Although the winner of an SE tournament is always well-defined, the chance of a particular player winning the tournament can vary immensely depending on the bracket. Arguably, this gives the tournament organizer a lot of power. The study of how much control an organizer has over the outcome of a tournament is called agenda control [Bartholdi et al., 1992].

The most studied agenda control problem for balanced SE tournaments is to find a bracket which maximizes the probability that a given player will win the tournament. The tournament organizer is given the probability that i will beat j for every pair of players i, j. A major focus is to maximize the winning probability of the strongest player under some assumptions 1 (e.g., [Appleton, 1995; Horen and Riezman, 1985; Vu and Shoham, 2010b; 2010a]). Without assumptions on the probabilities, the agenda control problem for an arbitrary given player is NP-hard [Lang et al., 2007; Hazon et al., 2008], even when the probabilities are in {0, 1, 1/2} [Vu et al., 2010]. Moreover, the maximum probability that a given player wins cannot be approximated within any constant factor unless P=NP [Vu et al., 2010]. When the probabilities are all either 0 or 1, the agenda control problem, then called the tournament fixing problem (TFP), is not well understood. One of the interesting open problems in computational social choice is whether a tournament fixing bracket can be efficiently found. Several variants of the problem are NP-hard - when some pairs of players cannot be matched [Vassilevska Williams, 2010], when some players must appear in given rounds [Vu et al., 2010], or when the most "interesting" tournament is to be computed [Lang et al., 2007].

1 A common assumption is monotonicity: the probability of beating a weaker player is at least as high as that of beating a stronger one.

Besides its natural connection to tournament manipulation, TFP studies the relationship between round-robin and single-elimination tournaments. The decision version of TFP asks, given the results of a round-robin tournament and a player A, is A also the winner of some SE tournament, given the same match outcomes? In the area of voting, suppose all votes are in, can we simulate a win for a particular candidate, using single-elimination rules (binary cup)? In this work, we investigate the following question: if we consider a round-robin tournament and a ranking produced from it by sorting the players according to their number of wins, how many of the top players can actually win some SE tournament, given the same match outcomes? What conditions on the round-robin tournament suffice so that one can efficiently rig the SE tournament outcome for many of the top players?

Prior work has shown several intuitive results. For instance, if A is any player with the maximum number of wins in a round-robin tournament, then one can efficiently construct a winning (balanced) SE bracket for A [Vassilevska Williams, 2010]. We extend and strengthen many of the prior results.

Contributions. Let Π be an ordering of the players in nonincreasing order of their number of wins in the given round-robin tournament. We consider conditions under which, for large K, the SE tournament can be fixed efficiently for any of the first K players in Π. We are interested in natural and not too restrictive conditions under which a constant fraction of the players can be made to win. If the first player p1 in Π beats everyone else, then p1 wins all SE tournaments. We show that if any player can beat p1, then we can also fix the tournament for the second player p2. We show that for large enough tournaments, if there is a matching onto the top K - 1 players {p1 , . . . , pK-1} in Π from the rest of the players, then we can efficiently find a bracket for which pK wins, where K is as large as 19% of the players.

Graph representation. The outcome of a round-robin tournament has a natural graph representation as a tournament graph: a directed graph in which for every pair of nodes a, b, there is an edge either from a to b, or from b to a. The nodes of a tournament graph represent the players in a round-robin tournament, and an edge (a, b) represents a win of a over b.

Notation and Definitions. Unless noted otherwise, all graphs in the paper are tournament graphs over n vertices, where n is a power of 2, and all SE tournaments are balanced. In Table 1, we define the notation that will be used in the rest of this paper. For the definitions, let A ∈ V be any node, let X, Y ⊆ V be such that

Consider a tournament graph G = (V,E). We say that A ∈ V is a king over another node x ∈ V if either (A, x) ∈ E or there exists y ∈ V such that (A, y), (y, x) ∈ E. A king in G is a node A which is a king over all x ∈ V \ {A}. We say that set S covers a set T if for every t ∈ T there is some s ∈ S so that (s, t) ∈ E. Thus N out (A) covers the graph if and only if A is a king.

If one can efficiently construct a winning SE tournament bracket for a player A, we say that A is an SE winner. We use the ranking Π formed by sorting the players in nondecreasing order of their outdegree.

We will construct SE tournaments as a series of matchings where each successive one will be over the winners of the previous one. A matching is defined as a set of pairs of vertices where each vertex appears in at most one pair. In our setting, these pairs are directed, so a matching fromX to Y will consist only of edges that are directed from X to Y . If an edge is directed from x to y, then we refer to x as a source. Further, given a matching M from the sets X to Y , we will use the notation X \M to refer to the vertices in X that are not contained in the matching. A perfect matching from X to Y is one where every vertex of X is matched with a vertex of Y and |X| = |Y |. A perfect matching in a set S is a perfect matching from some S′ ⊆ S to S \ S′ .

2 Motivation and Counterexamples

We will now discuss the motivation for our assumptions on the graph. We will look at some necessary and sufficient conditions for the top K players to win an SE tournament. We begin with an example.

Consider the transitive tournament graph G with nodes v1 , . . . , vn, where vi beats all nodes vj for j > i. Then v1 is the winner of all SE tournaments on G. Now, take any perfect matching from {v1 , . . . , vn/2} to {vn/2+1 , . . . , vn} and reverse these edges to create a back-matching. This gives each node from the weaker half of G a win against some node from the stronger half. The new outdegree ranking only swaps vn/2 and vn/2+1, however now the top n/2 - 1 players are SE winners: each of these nodes still beats at least n/2 other players, and the back-edges of the matching also make each one also a king. Prior work showed that this condition is sufficient for these players to be an SE tournament winner [Vassilevska Williams, 2010]. Thus, adding a backmatching to a transitive tournament can dramatically increase the set of winners. Our goal is to understand the impact of such back-edge matchings in general tournaments. As a warm-up, we consider the nodes of second and third highest outdegree. By case analysis, one can show the following theorem.

Theorem 1. Let G be a tournament graph and let A be the node of second highest outdegree. Then A is an SE winner if and only if there is no Condorcet winner in G. If there is a matching onto the top 2 nodes, then the third highest outdegree node is also an SE winner.

This simple result leads to a larger question. What are the necessary and sufficient conditions for the kth ranked node to win an SE tournament? A natural conjecture is that if there is a perfect matching from V \H(A) to H(A), then A should be able to win.

In Figure 1 we give an example of a tournament and a subset S consisting of the top r + 1 outdegree nodes such that there is a matching of size r from a subset W = {m1 , . . . ,mr} of V \ S into S, but no matching of size r + 1 from V \ S into S. Figure 1 only shows some of the graph edges. The edges within V \ (W ∪ S) are arbitrary, all nodes of S beat all nodes of V \ (W ∪ S), and all nodes of W lose to all nodes of V \ (W ∪S). We can show that any node A /∈ S cannot be an SE winner. p1 only loses to m1 and m1 loses to everyone else so p1 must be matched with m1 in the first round if it is to ever be eliminated. Similarly, for any i ≤ r, each pi must be matched with mi in the first round. Since all of the nodes that could possibly beat pr+1 lose in the first round, no one is left to beat pr+1 and A cannot win. Therefore, the only possible SE winners are contained in S. We have shown that for any r there exists a graph in which there is no matching onto the top r outdegree nodes and the (r + 1)st outdegree node is not an SE winner. From this, we can conclude that the existence of a perfect matching from V \ H(A) into H(A) is, in a sense, necessary, in order for a node A to be an SE winner.

Now suppose that there is a perfect matching in G from V \ H(A) onto H(A). Can we conclude that the bracket can be fixed for A? This turns out not to be true. Consider Figure 2. Here H(A) consists only of k1 and k2. These nodes are only beaten by b1 and b2 respectively, who lose to every other player except A, so bi and ki must be matched in round 1. The ai are symmetric, so without loss of generality we can match A to a1 in round 1. The two remaining nodes, a2 and a3, must also be matched. After round 1 the nodes that survive are A, a3 , b1 , b2. However, A needs to have outdegree at least 2 to survive the next two rounds. As it only has outdegree 1, A cannot win an SE tournament.

A similar problem can arise when the matching comes from N out (A) instead of N in (A). Figure 3 gives an example of a graph construction for any n ≥ 8 for which the node ranked n/2 cannot win any SE tournament even though there is a matching onto H(A) = ∪ki=1hi. Each hi only loses to bi and ∪j>ihj. Each bi only beats ∪j>ibj, except for b1 who also beats c. The problem arises with who to match A to in the first round so that it can win the match. By induction, one can argue that every hi for i > 1 must be matched to bi in round 1. A must be matched to some node in N out (A), but only b1 remains unmatched. This leaves h1 and c who must be matched as well. However, in round 2, all nodes that beat h1 have been eliminated and it is now a Condorcet winner in the induced subgraph. Therefore, it must be the winner of any SE tournament.

A common issue in the above counterexamples is that H(A) is too large while out(A) is too small. Another commonality is that H(A) = Hin (A). Hence a better condition to look for is a matching from V \ Hin (A) onto Hin (A), and not necessarily onto H(A).

Finally, a natural question is, how reasonable is the assumption of the existence of a matching from lower ranked players to higher ranked players? Consider the Braverman-Mossel model [2008] for generating tournament graphs. In this model, one assumes an underlying ranking v1 · · · vn of the players according to skill. The tournament is generated by adding an edge (vi, vj) with probability p if j < i and 1 - p if j > i for p < 12 . This model can be viewed as a transitive tournament with each edge reversed with probability p. A classic result of [Erd˝os and R´enyi, 1964] is that a bipartite graph with n nodes on each side with 2n ln n edges selected uniformly at random contains a perfect matching with high probability. If a graph is generated by the BravermanMossel model with p > 4 lnn n , then we expect there to be n ln n back edges from vn/2 · · · vn to v1 · · · vn/2-1. Therefore, in almost all such tournaments, a backedge matching exists.

3 Main Results

We are now ready to introduce our main result. As the proof is quite technical, we will first provide an intuitive sketch, some of the necessary Lemmas, and a more detailed account of the key part of our proof. Please refer to [Stanton and Vassilevska Williams, 2011] for the full version of this Section.

We present two main results. The first generalizes the idea of a king, and shows that if a node A is a king except for some subset and A beats many nodes that beat a king of that subset, then A is an SE winner.

Lemma 1 (Kings Except for a T subset). Let A be a node in a tournament G and let T be a subset of N in (A) of size |T| = 2k for some k. Suppose that A is a king in G \ T and |N out (A)| ≥ |N in (A)|. Let t be a king in T with outdegree in T at least ⌊|T|/2⌋. Suppose that |N in (t) ∩ N out (A)| ≥ |T |. Then A is an SE winner.

The key observation in proving Lemma 1 is that t can win an SE tournament over just the subgraph consisting of T in log |T | rounds. At the same time, there are at least |T | nodes in N out (A) that beat t. In the worst case, these cannot eliminate any other nodes in N in (A) so they must be matched against each other for log |T | rounds as well. However, given the size, we are guaranteed that at least 1 will survive to eliminate t. At this point, A will be a king of high outdegree over the induced subgraph. The technical details of the proof proceed by induction on the size of T . Lemma 1 is used in the proof of our main theorem below. We highlight its use in the intuitive sketch.

We now address the main question of this paper - what can we show when a matching from V \ Hin (A) to Hin (A) exists?

Theorem 2 (Not a King but Matching into Hin (A)). There exists a constant n0 such that for all n ≥ n0 the following holds. Let G = (V, E) be a tournament graph on n nodes, A ∈ V . Suppose there is a matching M from V \Hin (A) onto Hin (A) of size K. If K ≤ (n - 6)/7, then A is an SE winner.

The key restriction in this Theorem concerns the number of higher ranked players who beat a player, not the actual rank of that player. However, we are able to apply the fact that a player of rank k has outdegree at least (n - k - 1)/2 to obtain a nice corollary for large tournament graphs: Any one of the top 19% of the nodes are SE winners, provided there is a matching onto the nodes of higher outdegree.

Corollary 1. There exists a constant n0 so that for all tournaments G on n > n0 nodes the following holds.

Let A be among the top (6n + 7)/31 ≥ .19n highest outdegree nodes. If there is a matching from V \Hin (A) onto Hin (A), then A is an SE winner.

3.1 Intuition

We now give an intuitive sketch about how one might go about proving Theorem 2. The overall strategy of our proof is to set up the first round of the SE tournament, so that all of the high outdegree nodes that beat A are eliminated, and in the remaining tournament, A is a king over almost the entire graph, so that Lemma 1 can be applied.

At first glance, one might try to build the first round by using the existing matching, M, from V \ Hin (A) to Hin (A) and then finding some maximal matching M ′ from N out (A) \ M to N in (A) \ M. The matching M ′ will guarantee that as many elements as possible of N out (A) will survive to compete in the second round. To complete round 1, the potentially remaining nodes in N out (A) \ (M ∪ M ′ ) should be matched amongst themselves, and the same for N in (A) \ (M ∪M ′ ) in a matching called M ′′ .

A is initially a king in G over any node with no larger outdegree than it (i.e. V \ Hin (A)). However, if we do not create the matching M ′′ above carefully A may no longer be a king over the sources of M. Even worse, some source of M may lose all of the nodes that can potentially beat, and might become a Condorcet winner in the graph induced by the winners of round 1. This is demonstrated in Figure 4. In this example, we would like to fix the bracket for P2, the second strongest player. P3 can beat P1, but only Pn-1 and Pn beat P3. If we use any matching of N out (P2) that does not match Pn with Pn-1, P3 will be a Condorcet winner in round 2, and P2 cannot win.

The failure of this example motivates our approach. We begin our construction of round 1 as before. We use the perfect matching M from V \ Hin (A) to Hin (A) andM ′ , a maximal matchingM ′ fromN out (A) \ M to N in (A) \ M. At this point, we want to guarantee that as many of the sources of M as possible are still covered by winners of round 1. We start by finding the set T of sources of M that are not currently beaten by some source in M ′ , or by A. Because these nodes are all of lower outdegree than A, we can argue that there is some subset S which is a subset of N out (A) \ (M ∪ M ′ ) that covers T. We use a greedy approach (Algorithm 1) to match up the nodes of S in round 1 so that the winners of this matching cover as many nodes of T as possible. We are able to show (in Lemma 2) that the set U of nodes of T that are not covered by the first round winners from S is very small: it has size at most O(√|T|). This will allow us to show that we can eliminate U in later rounds.

We design the next rounds using Lemma 1. To do this, we use the largest outdegree node t in T and find a set P, the size of which is a power of 2, that contains both t and U. The final requirements of Lemma 1 are that A beats at least as many first round winners outside P as it loses to (which we show using Theorem 3) and that the number of nodes from N out (A) that beat t and survive round 1 is at least |P|. To fulfill this last requirement, we add an extra iteration (for q = 1) in Algorithm 1 which constructs the first round matching of S so that enough nodes that beat t survive round 1.

Figure 5: The construction of the sets Si and Bi in Theorem 3.

Summary. We create the first round of the tournament by using M, a maximal matching M ′ from the remaining nodes of N out (A) to the remaining nodes of N in (A), and a greedily selected perfect matching M ′′ on S. Many sources of M ′′ beat t, and almost all of T is covered by the sources of M ′′ . This does not fully specify the first round matching. A few nodes may remain unmatched, specifically N in (A) \ (M ∪M ′ ), N out (A) \ (M ∪M ′ ∪ M ′′ ) and A itself. The final details are included in the proof sketch at the end of this section. The goal of the first round matching is to ensure that the requirements of Lemma 1 are met and the remaining rounds of the tournament can be completed so that A wins.

3.2 Technical details.

With the above overview of the proof technique, we now introduce the necessary lemmas. As an SE tournament is a series of log n matchings, these lemmas are about the existence of matchings with desirable properties. The first is a very general result that can be specfically applied to lower-bound how large a matching can be found from N out (A) to N in (A) \ Hin (A).

Theorem 3 (Large Matching). Let h ∈ Z, possibly negative. Let S and B be disjoint sets such that ∀X ⊂ B, |E(S, X)| ≥ (|X| 2 ) -h|X|. Then there exists a matching between S and B of size at least |B|-2h-1 .

2

Proof. Recall that M is a maximal matching from a set S to a set B if and only if there are no augmenting paths from the unmatched elements of S to the unmatched element of B. Our proof will proceed by using the large number of edges from S to any subset X of B to lowerbound the size of the matching.

Let M be a maximal matching from S to B. We refer to the sources of M as S′ and the sinks as B′ . We itera-

Algorithm 1 Greedy Matching

• 1: Input: G = (V,E) a tournament and S, T ⊂ V , t ∈ V ; Output: Matching M
• 2: Let A1 = N in S (t), U1 = T, i = 1, L0 = ∅, M = ∅.
• 3: for q = 1, 2 do
• 4: while |Ai| ≥ 2 do
• 5: Let xi, yi ∈ Ai have larger outdegree to Ui than all the other elements in Ai; xi beats yi.
• 6: M ←M ∪ {(xi, yi)}
• 7: Li ←Li-1 ∪ {yi}
• 8: Ui+1 ←Ui \N out (xi)
• 9: Ai+1 = ∪v∈Ui+1 N in Ai (v) \ Li
• 10: i ← i + 1
• 11: end while
• 12: Ai = ∪v∈Ui N in S (Ui)
• 13: end for

tively build up a family of sets Sj and Bj that consist of augmenting paths from the unmatched nodes in B.

Let S1 be the subset of S′ which contains all nodes with edges to B \ B′ . Let B1 be the nodes matched to S1 by M. Now, we inductively define Sj as the nodes in S′ \ ∪j-1 i=1 Si that have edges to Bj-1, where Bj-1 are the nodes matched to Sj-1 by M.

This process can be repeated up to some index J + 1 such that there are no more nodes in S′ \ ∪Ji=1Si with edges to BJ. Let ¯ S = ∪i≤JSi and ¯B = (B \ B′ ) ∪ (∪i≤JBi).

First, note that there are no edges from S \ S′ to ¯B since M is maximal. If there were, we would have an augmenting path. Therefore, all edges into ¯B come from ¯ S. The number of edges from ¯ S into ¯B is at most | ¯B|| ¯ S| (the number of edges in a complete bipartite graph) and at least | ¯B|(| ¯B| - 1 - 2h)/2 by the Theorem statement. Thus, we can conclude that

Theorem 3 is used in the proof of Theorem 2 to argue about a lower bound on the size of N out (A) after the first round. An example application of this theorem is to set S to N out (A) and B to N in (A)\(M∪Hin (A)). Here, the conditions of the Theorem are met: we can show that for every subset X, E(S,X) ≥ (|X| 2 ) + |X| because every vertex in B beats A and is of lower outdegree than A.

The other very important part of our proof is Algorithm 1. As mentioned earlier, it is a greedy way of creating a matching in a set S such that the sources cover many elements in a set T. It iteratively finds the source in S that covers the most uncovered elements of T and matches it with a vertex that it beats. The first iteration of the loop deals with an element t that is a king over T . This loop only considers the subset of S that beats t and guarantees that at least half of the nodes that beat t in S

are preserved as sources. At any time in the algorithm, Ui is the set of the nodes that are currently not covered by the sources of the matching M, Ai is the set of sources that beat any element in Ui, and Li is the set of nodes that lose in M and are excluded from Ai.

We want to lower-bound the size of the generated cover. The main idea of the proof is that we initially have many edges from S to T, and specifically at least (|X|+1 2 ) to each X ⊆ T. If we consider the first pair (x1 , y1) added to M, then we can say x1 covers k elements of T. Therefore, we now need to cover only a subset of size |T| - k which has at least (|T|-k 2 ) edges into it. However, this may include edges from y1. When we remove y1, we may lose up to |T| edges. The key observation is that for the pair (x2 , y2), y2's outdegree is upper-bounded by x1 so we are able to bound the number of edges lost by the matching as the number of vertices currently covered plus |T|. We then show that there will always be enough edges and sources to increase the size of the matching until at most 2√|T| + 1 nodes remain uncovered.

Lemma 2. Let G = (V,E) be a tournament graph. Let S ⊆ V and T ⊆ V be disjoint sets such that for all X ⊆ T, the number of edges from S to X is at least (|X|+1 2 ). Let t ∈ V be given. Algorithm 1 generates a matching, M, in S such that at least |T| - 1 - 2√|T | nodes in T are beaten by at least one source in M and at least (inS(t) - 2)/2 of the sources also beat t.

Proof. We need to define some additional concepts for the proof. The first is the set of covered nodes at iteration i, Ci, where C1 = ∅. Ci is exactly T \ Ui (so |T| = |Ci| + |Ui|). Let di = |Ci+1| - |Ci| be the number of new nodes covered by iteration i. Our goal is to lowerbound the size of |Ci| when the algorithm quits.

Consider the first execution of the WHILE loop. Let i0 be the iteration at which the loop exits. This loop greedily covered T but only used vertices that also beat t. We will lower-bound the number of edges that remain from all unmatched sources in S (the set Ai0 ) to Ui0 . At this point, |Ci0 | = ∑i0 j=1 dj. The number of edges from Li0 to Ui0 is at most |T| - |Ci0 | + ∑i0-1 j=1 dj ≤ |T | since we picked the nodes so that outUi (yi) ≤ outUi-1 (xi-1) = di-1, and outUi0 (y1) ≤ |Ui0 |. Thus we can obtain a lower bound on the number of edges between Ai0 and Ui0 : |E(Ai0 ,Ui0 )| ≥ (|Ui0 |+1 ) - |T |.

2 Let j > i0 be any round in the second WHILE loop. As above, |Cj| = |Ci0 | + ∑jk=i0+1 dk and the number of edges fromLj to Uj is at most

We can lower-bound the number of usable edges from Aj to Uj as

The second WHILE loop exits when |Aj| ≤ 1. Therefore, when the algorithm finishes, |Aj| ≤ 1 and |E(Aj , Uj )| ≤ |Uj | = |T | - |Cj |. We have:

This can be simplified as follows.

That is, the number of covered nodes is at least |T|- 1 - 2√|T|. After round i0 we have at least i0 sources in M covering t and at least inS(t) - 2i0 - 1 nodes of N in S (t) that were not used in creating the rest of the matching because they did not cover any element of Ui0 . Match these among themselves to obtain at least i0+⌊(inS(t)- 1 - 2i0)/2⌋ ≥ (inS(t) - 2)/2 sources of the matching that are inneighbors of t. Complete the matching M from S to S by matching the rest of the nodes of S arbitrarily.

The bounds on the greedy matching algorithm are only positive if |T| > 5. We don't want our bounds in Theorem 2 to depend on the size of the matching into Hin (A). In the full version, we fix this problem with a technical lemma that allows one to artifically boost the size of T to guarantee that the above process will always work.

Now we give a more technical proof of Theorem 2. Although the proof has most of the key details, it does not contain all of them. In particular, it assumes that that the indegree of node A coming from the sources of M is large enough. This assumption is lifted in the full version of the paper.

Proof sketch of Theorem 2: This proof proceeds by constructing the first round matching in stages. First, we will use M, the matching given by the theorem statement, and construct M ′ , a maximal matching. Next, we show how to match A and construct the covering of the sources of M using Algorithm 1. Finally, we argue that the constructed first round matching satisfies the requirements of Lemma 1.

For simplicity, let A = N out (A) and B = N in (A). We divide the sources of M onto Hin (A) into two sets, AT and BT , where AT are the sources of M in A while BT are the sources in B. We can also divide Hin (A) into two sets, H1 and H2, where H1 are the nodes matched to AT and H2 are matched to BT byM. In order to later argue about the size of matchings, let |AT | = |H1| = h and |BT | = |H2| = k. This means that K, the size of M is exactly k + h.

Let Brest = B \ (BT ∪ Hin (A)) be the nodes who beat A and are not part of M. Take M ′ to be any maximal matching from A \ AT to Brest. We want to argue about the size of M ′ by using Theorem 3. First, note that |Brest| = |B| - k -K. Now, since we removed AT , of size h, we can only say that every node b in Brest has at least outB(b)+1-h inneighbors fromA\AT . Therefore, by Theorem 3, |M ′ | ≥ (|B|-K-k2h + 2 - 1)/2 = (|B| - 2K - h + 1)/2. We will use this fact later when arguing about the outdegree of A after the first round.

Finally, note that Brest consists only of lower ranked nodes than A, so every node in Brest has some source of M ′ or AT as an inneighbor.

(Matching A to some node.) Consider the currently unmatched portion of A. Call this Arest = A\(AT ∪M ′ ). If there is some a′ ∈ Arest, then match A to a′ . If Arest is empty, then we can argue that |M ′ | > 1 since |A\AT | = |A| - h ≥ (n - K)/3 - h ≥ (n - 4K)/3 > 1. Since M ′ > 1, we can dislodge any edge (a′ , b′ ) fromM ′ and match A to a′ . After removing a′ , the lower bound for |M ′ | goes down by 1: |M ′ | ≥ (|B| - 2K - h - 1)/2.

(Creating a matching of Arest \ {a′ }).) We now use Algorithm 1 to cover BT . Let S = Arest \ {a′ } and T be the subset of BT consisting of the nodes that do not have inneighbors among the sources of M ′ and AT . For simplicity in this proof we assume that |T| and hence |BT | is large enough.

Every subset X of the nodes of T has at least (|X| 2 ) + 2|X| - |X| = (|X| 2 ) + |X| inneighbors in S since each node in X can have lost at most one inneighbor, a′ . Let t ∈ BT be the node with highest outdegree in BT . Run Algorithm 1 on S, T, t. This outputs a matching M ′′ on the nodes of S that covers all of T except for a subset, U, of size at most 1 + 2√|T|. There are also at least inS (t)/2 - 1 sources of M ′′ that beat t. This completes the first round matching. Let G′ be the graph induced by the surviving nodes.

(Handling U.) We will construct P, a subset of T, such that P contains U, and t is a king over P who beats at least half of P. We selected t so that it is a king in T. Therefore, there is a subset of at most |U| nodes in its outneighborhood in T that cover U. We can add these nodes together with enough other nodes of N out T (t) to P so that |P| is a power of 2 and t is a king in P that beats at least half of P. This is possible since U is very small compared to T .

We can assume that the size of P is 2c where 2c is the closest power of 2 greater than 3 + 4√|T|, as we may need as many as |U| ≤ 1 + 2√|T | extra nodes added to P to guarantee that t is a king over P. We can further conclude that |P| ≤ 5 + 8√|T| since we can at most double 3 + 4√|T | to make |P | be a power of 2.

From Algorithm 1 we know that at least inS(t)/2 - 1 ≥ (|BT | - 1)/4 - 1 inneighbors of t from S are in G′ . Since we assumed that BT is large enough, we have (|BT | - 1)/4 - 1 ≥ 5 + 8√|T |. Hence there exists a subset of the surviving nodes of N in S (t) of size at least |P|. The requirements of Lemma 1 are satisfied if outG′ (A) ≥ inG′ (A). We prove this below and thus show that A is an SE winner.

(Showing that outG′ (A) ≥ inG′ (A).) The number of nodes of N out (A) that survive the first round is at least

⌊(|A| + |M ′ | + |AT | - 1)/2⌋. The number of nodes of N in (A) that survive is at most ⌈(|B|-|AT |-|M ′ |)/2⌉. It suffices to show that |A| + |M ′ | + |AT | - 1 ≥ |B| - |AT |-|M ′ |. Recall that |M ′ | ≥ (|B|- 2K-h-1)/2 so we must only show that |A|+|B|-2K-h+2h-2 ≥ |B|, or that |A| - 2K + h - 2 ≥ 0. Since |A| ≥ (n -K)/3 it suffices to show that (n -K) ≥ 6K + 6, or that K ≤ (n - 6)/7, which is true by assumption.

4 Conclusions

In this paper, we have shown that the existence of backmatchings can allow for an SE tournament to be manipulated in favor of any of the top 19% of players. The Braverman-Mossel model for tournament generation shows that back-matchings exist even when the noise in each match is very low (O( log n n )). The question of the computational difficulty of manipulating SE tournaments in favor of a specific player remains open, but our result shows that many common examples can be efficiently manipulated in polynomial time using any algorithm for maximum matching. The fastest algorithms for matching run in ˜O(m√n) time ([Micali and Vazirani, 1980] reimplementing [Edmonds, 1965]) and in ˜O(n2.376 ) time [Mucha and Sankowski, 2004]. Possible future work includes finding even more general conditions under which a winning bracket can be found for a player, as well as trying to reduce the dependence our method has on the number of players.

Acknowledgments

The authors are grateful for the detailed comments from the anonymous reviewers. The first author was supported by the NDSEG and NSF Fellowships. The second author was supported by the National Science Foundation under Grant #0937060 to the Computing Research Association for the CIFellows Project. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation or the Computing Research Association.