# robust_draws_in_balanced_knockout_tournaments__376558dd.pdf

Robust Draws in Balanced Knockout Tournaments

Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Josef Tkadlec

IST Austria {krish.chat,ribsen,jtkadlec}@ist.ac.at

Balanced knockout tournaments are ubiquitous in sports competitions and are also used in decisionmaking and elections. The traditional computational question, that asks to compute a draw (optimal draw) that maximizes the winning probability for a distinguished player, has received a lot of attention. Previous works consider the problem where the pairwise winning probabilities are known precisely, while we study how robust is the winning probability with respect to small errors in the pairwise winning probabilities. First, we present several illuminating examples to establish: (a) there exist deterministic tournaments (where the pairwise winning probabilities are 0 or 1) where one optimal draw is much more robust than the other; and (b) in general, there exist tournaments with slightly suboptimal draws that are more robust than all the optimal draws. The above examples motivate the study of the computational problem of robust draws that guarantee a speciﬁed winning probability. Second, we present a polynomial-time algorithm for approximating the robustness of a draw for sufﬁciently small errors in pairwise winning probabilities, and obtain that the stated computational problem is NP-complete. We also show that two natural cases of deterministic tournaments where the optimal draw could be computed in polynomial time also admit polynomial-time algorithms to compute robust optimal draws.

1 Introduction

Balanced knockout tournaments (BKTs). A Balanced knockout tournament (BKT) consists of N = 2n players (for some positive integer n) and is played in n rounds. In every round each remaining player plays a (win/lose) game with some other remaining player and the loser is eliminated (removed from the tournament). In the end, only one player remains and is declared the winner. The whole process can be visualised on a balanced binary tree (over N leaves) with players starting at the leaves and winners advancing to the parent. Such tournaments are used in many sports such as tennis, elections and other decision making processes.

Draws in BKT. For a given set of N players, the tournament can be played in many different ways based on how we draw the players in the ﬁrst round (i.e., on which leaf they are placed in the balanced binary tree). Even if we consider the draws that correspond to isomorphic labeled binary trees as equivalent, the number of draws grows rapidly in N, precisely, there are N! 2N 1 draws. As a numerical example, for a Grand Slam tournament in tennis with N = 128, the number of distinct draws is at least 10177 and even if we rank the players and require that, for any k, the top 2k of them do not meet until the last k rounds, we have at least 10144 distinct draws. Computational problems. The traditional computational problem that has been extensively studied is related to obtaining draws that are most favorable for a distinguished player [Vu et al., 2009; Aziz et al., 2014; Stanton and Williams, 2011a]. The input consists of an N N comparison matrix P that speciﬁes the probabilities Pij of player i beating player j in a single match, and a distinguished player i . The input, along with a draw, deﬁnes the winning probability that the distinguished player wins the whole tournament. If the comparisons matrix contains 0 s and 1 s only, a draw gives a unique winner. The probabilistic (resp. deterministic) tournament ﬁxing problem (PTFP) (resp. TFP) asks whether there exists a draw such that the winning probability for the distinguished player i is at least q (resp., player i is the winner). The TFP and PTFP problems are desired to be hard, as otherwise the tournament could be manipulated by choosing the draw that favors a speciﬁc player. Previous results. It was shown in [Vu et al., 2009] that given an input comparison matrix and a draw, the winning probability for a player can be computed by a recursive procedure in O(N 2) time (i.e., in polynomial time). Since a candidate draw for the PTFP problem is a polynomial witness, an NP upper bound follows for both the PTFP and the TFP problem. An NP lower bound for the PTFP problem was shown in [Vu et al., 2009; Williams, 2010], and ﬁnally the TFP problem was shown to be NP hard in [Aziz et al., 2014]. Hence both the PTFP and the TFP problems are NP-complete. Moreover, in [Aziz et al., 2014] two important special cases have been identiﬁed (namely, constant number of player types, and linear ordering among players with constant number of exceptions) where all the winning draws for player i can be computed in polynomial time for deterministic tournaments.

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16)

Robustness question. The previous works focused on the computational problems when the pairwise winning probabilities are precisely known. However, in most practical scenarios, the winning probabilities in the comparison matrix are only approximation of the real probabilities. Indeed, in all typical applications, either the probabilities are obtained from past samples (such as games played) or uniformly selected from a small subset of samples (such as in elections). The probabilities obtained in these ways are always at best an approximation of the real probabilities and subject to small errors. This leads to the natural question about robustness (or sensitivity) of optimal draws for probabilistic tournaments (or winning draws in deterministic tournaments) in the presence of small errors in the pairwise winning probabilities. Formally, given a comparison matrix P, and a small error term ", we consider all comparison matrices P 0 where each entry differs from P by at most ". We refer to the above set as the "- perturbation matrices of P. For a draw, we consider the drop of the draw as the difference between the winning probability for the distinguished player i for P and the inﬁmum of the winning probability of the "-perturbation matrices. Our results. We study the computational problems related to robust draws in TFP and PTFP. Our main contributions are:

1. Examples. We present several illuminating examples for

TFP and PTFP related to robustness. First, we show that there exist deterministic tournaments where for one winning (or optimal draw) the drop is about N "

2 , whereas for another winning draw the drop is about log N . In other words, one winning draw is much more robust than the other. Second, we show that there exist probabilistic tournaments with suboptimal draws that are more robust than all the optimal draws. Motivated by the above examples we study the computational problem of robust draws, i.e. determining the existence of draws that guarantee a speciﬁed winning probability with a drop below a speciﬁed threshold.

2. Algorithm. We present a polynomial-time algorithm to

approximate the drop for a given draw for small " > 0 (informally, for " where higher order terms of " such as "2, "3 etc. can be ignored).

3. Consequences. Our algorithm has a number of consequences. First, it establishes that the computational problem of robust draws for small is NP-complete. Note that while the PTFP and TFP are existential questions (existence of a draw), the robustness question has a quantiﬁer alternation (existence of a draw such that for all -perturbation matrices the drop is small), yet we match the complexity of the PTFP and TFP problem. Second, our polynomial-time algorithm along with the result of [Aziz et al., 2014] implies that for the two natural cases of [Aziz et al., 2014], the most robust winning draw (if one exists) is polynomial-time computable.

Detailed proofs omitted due to lack of space is available in [Chatterjee et al., 2016]. Signiﬁcance as risk-averse strategies. As mentioned, BKTs are often used as sports tournaments. After a draw is ﬁxed, the winning probabilities determine the betting odds. Since the

comparison matrix can only be approximated, a risk-averse strategy (as typically employed by humans) corresponds to the notion of robustness. The notion of robustness has been studied in many different contexts, such as for sensitivity analysis in MDPs [Puterman, 1994; Filar and Vrieze, 1997] as well as for decision making in markets [Rockafellar, 2007]. Our algorithm provides a risk-averse approximation for balanced knockout tournaments, for low levels of uncertainty in the probabilities.

1.1 Related Work The most related previous works are: (a) [Vu et al., 2009], who showed that for a ﬁxed draw the probability distribution over the winners can be computed in O(N 2) time; and (b) [Aziz et al., 2014], who determined the complexity of TFP and found special cases with polynomial-time algorithms. Besides that, [Williams, 2010] identiﬁed various sufﬁcient conditions for a player to be a winner of a BKT; [Stanton and Williams, 2011b] considered the case when weak players can possibly win a BKT; [Stanton and Williams, 2011a] studied the conditions under which the tournament can be ﬁxed with high probability. The problem of fair draws was studied in [Vu and Shoham, 2011]; and the problem of determining the winner in unbalanced voting trees was considered in [Lang et al., 2007; 2012]. If only incomplete information on the preferences is known, then computing the winner with various voting rules has been studied in [Xia and Conitzer, 2011; Aziz et al., 2012]. The problem of checking whether a round-robin competition can be won when all the matches are not yet played has been studied in [Kern and Paulusma, 2004; Gusﬁeld and Martel, 2002].

As compared to the existing works we consider the problem of robustness for TFP and PTFP which has not been studied before.

2 Preliminaries In this section we present the formal deﬁnitions and previous results.

2.1 Deﬁnitions For the basic deﬁnitions we very closely follow the notations of [Aziz et al., 2014]. Deﬁnition 1 (Comparison matrices). For N 2 N, let [N] := {1, . . . , N}. Consider N players numbered 1 to N. A comparison matrix is an N N matrix P such that for all 1 i 6= j N we have 0 Pij 1 and Pij + Pji = 1. The entry Pij of the comparison matrix expresses the probability that if players i, j play a match, player i wins. Note that the entries Pii are not deﬁned. A comparison matrix is deterministic if Pij 2 {0, 1} for all i, j 2 [N] with i 6= j. Deﬁnition 2 (Draws). Let N = 2n for some integer n. For σ a permutation of [N], an n-round ordered balanced knockout tournament T([N], σ) is a binary tree with N leaf nodes labelled from left to right by σ. All ordered balanced knockout tournaments that are isomorphic to each other are said to have the same draw. They are represented by a single (unordered) balanced knockout tournament T([N], σ), where σ is again a permutation of [N]. The set of all draws is denoted by .

σ = (1, 2, 3, 4) P

Figure 1: A 2-round complete tournament with comparison matrix P. The draw σ gives wp(1, P, σ) = 0.93.

Deﬁnition 3 (Complete tournaments). A complete tournament C(P, σ) is a balanced knockout tournament T([N], σ) together with an N N comparison matrix P. A complete tournament C(P, σ) is called deterministic if the comparison matrix P is deterministic. The complete tournament C(P, σ) is conducted in the following fashion. If two nodes with labels i, j have the same parent in T([N], σ) then players i, j play a match. The winner then labels the parent (i.e. the parent is labeled by i with probability Pij and by j otherwise). The winner of C(P, σ) is the player who labels the root node.

Deﬁnition 4 (Winning probabilities). Given a complete tournament C(P, σ), each player i 2 [N] has a probability, denoted wp(i, P, σ), of being the winner of C(P, σ). This probability can be computed in time O(N 2) via a recursive formulation [Vu et al., 2009]. We denote by mwp(i, P) := maxσ2 {wp(i, P, σ)} the maximum possible winning probability of i in C(P, σ) taken over all draws σ 2 . Given P, and δ 0, a draw σ is called δ-optimal for player i provided that wp(i, P, σ) mwp(i, P) δ. A draw is optimal if it is δ-optimal for δ = 0.

Example 1. Consider a complete 2-round tournament with comparison matrix P and draw σ = (1, 2, 3, 4) as in Figure 1. Then the winning probabilities are

wp(1, P, σ) = 0.729, wp(2, P, σ) = 0, wp(3, P, σ) = 0.171, wp(4, P, σ) = 0.1

and the draw σ is optimal for player 1, as the draws σ0 = (1, 3, 2, 4), σ00 = (1, 4, 2, 3) give wp(1, P, σ0) = wp(1, P, σ00) = 0.

2.2 Previous Results

We now describe the main computational problems and previous results related to them.

Problem 1 (TFP Tournament Fixing Problem). Given a player set N, a deterministic comparison matrix P, and a distinguished player i 2 N, does there exist a draw σ for the player set N for which i is the winner of C(P, σ)?

Problem 2 (PTFP Probabilistic TFP). Given a player set [N], a comparison matrix P, a distinguished player i 2 [N] and target probability q 2 [0, 1], does there exist a draw σ for the player set [N] such that wp(i , P, σ) q?

Theorem 1. ([Aziz et al., 2014; Vu et al., 2009]) The TFP and the PTFP problems are NP-complete.

3 Robustness: Examples and Questions In practical applications of PTFP and TFP, the exact values of the entries in the comparison matrix are not known, but only approximations are obtained. Hence it is of interest to ﬁnd out how sensitive is the winning chance in optimal draws (or near optimal draws) with respect to minor changes in the comparison matrix. We ﬁrst present the basic deﬁnition and then our examples. Finally, we present the computational problems. Deﬁnition 5 ("-perturbation and the "-worst drop). Given a comparison matrix P and " > 0, an "-perturbation of P is any comparison matrix P 0 such that |Pij P 0

ij| " for all 1 i 6= j N. The set of all "-perturbations of P is denoted P(P, "). Given a complete tournament C(P, σ), a distinguished player i , and " > 0, deﬁne the "-guaranteed winning probability wp"(i , P, σ) by

wp"(i , P, σ) = inf P 02P(P,"){wp(i , P 0, σ)}

and the "-worst drop, denoted d"(i , P, σ), by wp(i , P, σ) wp"(i , P, σ). The smaller the drop d"(i , P, σ) the more robust (or more risk-averse) is the draw σ.

3.1 Examples We consider the robustness problem for sufﬁciently small " > 0. Intuitively, sufﬁciently small will allow us to ignore all higher order terms of " such as "2, "3, . . . A formal deﬁnition comes at the end of this section.

First we construct a deterministic tournament with a unique and nonrobust optimal draw. We will use Proposition 1 in Proposition 2. For brevity, the distinguished player will always be the ﬁrst one, i.e. i? = 1. Proposition 1 (Only Nonrobust Optimal Draws). For any 2n = N 2 N, there exists a deterministic n-round tournament (called a hard n-round tournament and denoted Hn) with a comparison matrix P such that for every draw σ which makes player 1 win we have

wp"(1, P, σ) 1 (N 1)" + "2 Q(")

for some integer polynomial Q(").

Intuitively, the polynomial Q stores higher order terms (from "2 on). The proof uses a construction from [Aziz et al., 2014, Lemma 1]. The tournament, illustrated in Figure 2, has the property that exactly one draw makes player 1 win and if any single match changes outcome then player 1 loses. All these facts follow by easy induction arguments.

Next we present a concrete numerical example to illustrate Proposition 1. Example 2. There exists a deterministic 6-round tournament with a comparison matrix P such that any draw σ, which makes player 1 win, satisﬁes

wp0.01(1, P, σ) < 0.54, wp0.05(1, P, σ) < 0.07, wp0.1(1, P, σ) < 0.02.

By Proposition 1, the 6-round hard tournament with comparison matrix P has only one draw σ = (1, . . . , 64) that makes player 1 win. Let P 0 be the "-perturbation where we adjusted every (0,1) match into an (", 1 ") match. We recursively

Figure 2: A hard 4-round tournament H4. Each broken line connects nodes that are eventually labelled by the same player. Except for the depicted exceptions, each player beats all players to their left.

Figure 3: An unbalanced 4-round tournament U4. The players in the right subtree beat everyone from the left subtree but the player 1.

compute wp(1, P 0, σ) = 1 63" + 2 147 483 648"63 and plug in " 2 {0.01, 0.05, 0.1} to get numbers less than 0.54, 0.07, 0.02, respectively.

We now use Proposition 1 to show that there exist deterministic tournaments where for one winning draw the drop is approximately N"

2 , whereas for a different winning draw the drop is approximately "(2 log N 1), for sufﬁciently small ". In other words, some winning draws can be much more robust than other winning draws.

Proposition 2 (Robust and Nonrobust Optimal Draws). For any 2n = N 2 N, n 2, there exists a deterministic n-round tournament (called an unbalanced n-round tournament and denoted by Un) with a comparison matrix P and draws σ, σ0 such that wp(1, P, σ) = 1 = wp(1, P, σ0) and

wp"(1, P, σ) 1 " N/2 + "2 Q("),

wp"(1, P, σ0) > 1 " (2n 1)

for some integer polynomial Q(").

Proof. Take an (n 1)-round hard tournament with players 1, 2, . . . , 2n 1. Add 2n 1 more players numbered 2n 1 + 1 through 2n who all lose to player 1 but beat all the players 2 through 2n 1 (see Figure 3). Then we claim that σ = (1, 2, . . . , 2n) and σ0 = (2n, 2, 3, . . . , 2n 1, 1) fulﬁl the statement of the proposition.

Clearly, player 1 wins both C(P, σ) and C(P, σ0). To upper bound wp"(1, P, σ) it is enough to ﬁnd one "- perturbation that reduces the winning chance of player 1 sufﬁciently. Let P 0 again be the comparison matrix obtained by

replacing each (0, 1) match by an (", 1 ") match. By Proposition 1, the probability of player 1 winning her ﬁrst n 1 rounds is pn 1 = 1 (2n 1 1)" + "2Q0(") for some polynomial Q0("). The probability of winning the ﬁnal is then always 1 " which altogether gives

wp"(1, P, σ) [1 (2n 1 1)" + "2Q0(")] (1 ")

= 1 2n 1" + "2Q(")

for some polynomial Q(").

For wp"(1, P, σ0), no matter which P 00 2 P(P, ") we take, players 2n and 1 win their ﬁrst n 1 matches with probability at least (1 ")n 1 each and then player 1 beats player 2n with probability at least 1 " again, giving

wp"(1, P, σ0) (1 ")2n 1 > 1 (2n 1)".

We now illustrate Proposition 2 with a numerical example. Example 3. There exists a deterministic 6-round tournament with a comparison matrix P and draws σ, σ0 such that wp(1, P, σ) = 1 = wp(1, P, σ0) and

wp0.01(1, P, σ) < 0.73 < 0.89 < wp0.01(1, P, σ0),

wp0.05(1, P, σ) < 0.23 < 0.56 < wp0.05(1, P, σ0),

wp0.1(1, P, σ) < 0.08 < 0.31 < wp0.1(1, P, σ0).

Indeed, take the unbalanced 6-round tournament with comparison matrix P and the draws σ = (1, 2, . . . , 64), σ0 = (64, 2, 3, . . . , 63, 1). By Proposition 2, player one wins both C(P, σ) and C(P, σ0). Consider the "-perturbation P 0 of P that replaces each (0, 1) match by an (", 1 ") match. Then for any " > 0 we have

wp"(1, P, σ) wp(1, P 0, σ) = p5 (1 ") =

= 1 64" + + 2 147 483 648"64

which, after plugging in " 2 {0.01, 0.05, 0.1}, gives the desired inequalities.

On the other hand, the proof of the Proposition 2 implies that for any " > 0 we have wp"(1, P, σ0) (1 ")11 which gives the remaining inequalities.

Probabilistic setting. Proposition 1 and Proposition 2 concern the deterministic setting. In a deterministic setting, if a draw is not optimal (i.e., winning), then the player loses with probability 1 (hence the notion of δ-optimality, for δ > 0 is not relevant). We now consider the probabilistic setting and show that there are combinations of δ and " such that a certain δ-optimal draw gives a better "-guarantee than any optimal draw. In other words, near optimal draws can be more robust than all optimal draws. Proposition 3. There exists a tournament with comparison matrix P and a distinguished player i and there exist δ, " > 0 and a δ-optimal draw σ0 such that for all optimal draws σ we have wp"(i, P, σ) < wp"(i, P, σ0).

For proving Proposition 3 we use an auxiliary lemma. Let a big vs. small tournament with players [2n] have the comparison matrix P such that each of the players in {2n 1+ 1, . . . , 2n} ( big players) beats each of the players in [2n 1] ( small players) with the same probability p 2 (0.5, 1).

Lemma 1. The draws that maximize the probability of a big player winning the big vs. small tournament (the big-optimal draws) are precisely those that pair up big players and small players in the ﬁrst round (so-called mixed draws). Moreover, for p = 0.5 + ", the probability b(P) of a big player winning in such a draw equals b(P) = 0.5 + 1

2(n + 1)" + "2 Q(") for some polynomial Q(").

Proof. The proof of the lemma is technical but straightforward induction argument.

Proof. (of Proposition 3) Consider an (n + 1)-round tournament with players [2n+1]. Call players {2, 3, . . . , 2n} small, players 2n + 1, . . . , 2n + 2n 1 medium and players 2n + 2n 1 + 1, . . . , 2n+1 big. For s small, m medium, and b big, let the comparison matrix P satisfy:

P1s = 1, P1m = 0.4, P1b = 0.6,

Psm = Psb = 0,

Pmb = 0.5 1

We claim that:

1. The draws optimal for player 1 are those that have all the

small players in one half and the medium players paired up with the big players in the other half.

2. For any optimal draw σ, the draw σ0 = (1, . . . , 2n) sat-

isﬁes wp"(1, P, σ) < wp"(1, P, σ0) for all sufﬁciently small " > 0.

1. Let σ be a draw of the desired form. By Lemma 1, we have

wp(1, P, σ) =

4(n + 1)" + "2Q(")

4(n + 1)" "2Q(")

20(n + 1)" + "2R(").

for some polynomials Q("), R(").

Since there are 2n 1 < 2n small players, player 1 has to face a medium or big player in the ﬁnal (provided he made it that far). Now let be a draw optimal for player 1 and suppose it contains a medium or big player in the left half. Then the player 1 has to face at least one more such player before the ﬁnal. Hence his winning chance is at most 0.62 < wp(1, P, σ) for all sufﬁciently small " > 0, and is not optimal. All the small players are therefore in the left half. For the right half, we want to maximize the probability of a big player winning it. By Lemma 1, this is accomplished by the mixed draws.

2. Let σ be optimal. Note that since σ and σ0 only differ in the right subtree, the inequality

wp"(1, P, σ) < wp"(1, P, σ0)

holds if and only if the minimum possible probability b"(σ) of a big player winning the right half of C(P , σ), taken over all P 2 P(P, "), is less than the minimum possible probability

b"(σ0) of a big player winning the right half of C(P 0, σ0), taken over all P 0 2 P(P, ").

For σ, consider the "-perturbation that replaces each (0.5 1 2", 0.5 + 1

2") match by a (0.5 + 1

2") match. Then by Lemma 1 we have

b"(σ) = 0.5 1

4(n + 1)" "2Q(")

for some polynomial Q(").

On the other hand, for all P 0 2 P(P, ") a big player certainly wins the right half of the right subtree of C(P 0, σ0) (since that subtree only consists of big players), hence

For n 2 and all sufﬁciently small " > 0 we then get the desired b"(σ) < b"(σ0) and thus in turn wp"(1, P, σ) < wp"(1, P, σ0).

We again illustrate this with a numerical example. Example 4. Consider a 6-round tournament with players [64]. Call players {2, 3, . . . , 32} small, players 33, . . . , 48 medium and players 49, . . . , 64 big. For s small, m medium, and b big, let the comparison matrix P satisfy:

P1s = 1, P1m = 0.4, P1b = 0.6, Psm = Psb = 0, Pmb = 0.49. Consider σ = (1, 2, . . . , 32, 33, 49, 34, 50, . . . , 48, 64) and σ0 = (1, . . . , 64). Then it is straightforward to compute mwp(1, P) = wp(1, P, σ) > 0.506 and wp(1, P, σ0) = 0.502 < mwp(1, P) so σ0 is not optimal for player 1. However, wp0.02(1, P, σ) < 0.429 < 0.432 < wp0.02(1, P, σ0). Indeed, for σ, the 0.02-perturbation P of P satisfying

1s = 0.98, P

1m = 0.38, P

1b = 0.58, P

sm = Psb = 0, P

mb = 0.51 yields wp0.02(1, P, σ) < wp(1, P , σ) < 0.429.

On the other hand, consider the draw σ0 and take any P 0 2 P(P, 0.02). Player 1 wins his ﬁrst ﬁve matches with probability at least 0.985. Then he beats every medium (resp., big) player with probability at least 0.38 (resp., 0.58) and the probability that a big player wins the right half is at least 0.51 0.02 = 0.49. Overall, wp(1, P 0, σ) 0.985 (0.49 0.58 + 0.51 0.38) > 0.432.

3.2 Computational Questions We extend the TFP and PTFP problem with robustness and we focus on the question of approximating the "-worst drop d"(i , P, σ).

Denote by (P) = min{Pij|Pij 6= 0} the smallest nonzero value in the comparison matrix (if P is deterministic then (P) = 1). It is straightforward to see that for " , the "-guaranteed winning probability wp"(i , P, σ) is a polynomial in " whose constant term is wp(i , P, σ). For such ", our approximation bd"(i , P, σ) of the drop d"(i , P, σ) is the linear term of this polynomial. Since higher order terms of " are

ignored, the number bd" is really only an approximation of d". However, for all c < N, if " is sufﬁciently small (smaller than c N 2), then bd" is within c" of d", so the approximation is tight. Formally, we consider the following problems.

Problem 3 (RTFP). The Robust Tournament Fixing Problem (RTFP): Given a player set [N], a deterministic comparison matrix P, a distinguished player i 2 N and c 2 N, does there exist a draw σ for the player set N such that (a) player i is the winner of C(P, σ); and (b) bd"(i , P, σ) c", for all " > 0 sufﬁciently small?

Problem 4 (RPTFP). The Robust Probabilistic Tournament Fixing Problem (RPTFP): Given a player set [N], a comparison matrix P, a distinguished player i 2 [N], target probability q 2 [0, 1] and s 2 R, does there exist a draw σ for the player set [N] such that (a) wp(i , P, σ) q; and (b) bd"(i , P, σ) s", for all " > 0 sufﬁciently small?

Note that the drop computation is an inﬁmum over all "- perturbation matrices, and thus represents a universal quantiﬁcation. Thus in contrast to the TFP and the PTFP problems which have only existential quantiﬁcation over draws, the robustness problem has a quantiﬁer alternation of existential and universal quantiﬁers.

4 Algorithms

The aim of this section is to prove the following theorem.

Theorem 2. Given a comparison matrix P (deterministic or probabilistic), sufﬁciently small " > 0, distinguished player i and a draw σ, the value bd"(i , P, σ) can be computed in polynomial time.

We start with a lemma stating that if we are allowed to perturb by ", perturbing by less is not worth it.

Lemma 2. For every C(P, σ) with a distinguished player i and any " > 0 there exists an "-perturbation P 0 of P that gives the worst possible winning probability wp(i , P 0, σ) = wp"(i , P, σ) for player i and that for each 1 i 6= j N satisﬁes that either |P 0

ij Pij| = " or P 0

ij 2 {0, 1}.

Proof. For a ﬁxed draw σ, the winning chance wp(i , P, σ) can be expressed using variables Pij, 1 i 6= j N. Since each combination of outcomes of the matches determines if i won or not, this expression is a polynomial and is linear in each of the Pij s. If we view P(P, ") as a subset of R(

2 ) with 1 metric, then the minimum of the function wp(i , P 0, σ) over the set P(P, ") is attained on the boundary. Hence the result follows.

4.1 Deterministic setting

First we focus on the deterministic case. If a player doesn t win a tournament we say he lost. Consider a complete deterministic tournament C(P, σ) with winner i and let " 2 (0, 1). Lemma 2 gives Corollary 1.

Corollary 1. The value wp"(i , N, P, σ) is attained for a matrix P 0 with some (0, 1) matches altered into (", 1 ") matches and the remaining matches left intact.

Crucial matches. Denote by S" the set of (0, 1) matches such that altering them to (", 1 ") matches gives P 0 2 P(P, ") satisfying wp(i , P 0, σ) = wp"(i , P, σ). A (0, 1) match is called crucial if replacing it (and it only) by a (1, 0) match makes i lose. Denote the set of crucial matches by C. The next lemma says that the crucial matches are the only matches that matter for the sake of determining bd"(i , P, σ). Lemma 3. Suppose C(P, σ) is won by player i . Replace some subset S of (0, 1) matches by (", 1 ") matches to get P 0 2 P(P, "). Suppose c of those |S| = s matches are crucial. Then wp(i , P 0, σ) = 1 c " + "2Q("), for some polynomial Q(").

Proof. We account for three scenarios: (A) All matches play out as before; (B) a single crucial match becomes an upset; (C) a single non-crucial match becomes an upset. For appropriate polynomials Qi("), i = 1, 2, 3, 4, the chances of this happening are

(A) (1 ")s = 1 s " + "2Q1(")

(B) c"(1 ")s 1 = c" + "2Q2(")

(C) (s c)"(1 ")s 1 = (s c)" + "2Q3(")

Since i wins in (A) and (C) and loses in (B), we have

1 c" "2Q4(") wp"(i , P 0, σ) 1 c" "2Q2(")

where Q4(") = Q1(") + Q3("). The result follows.

Lemma 3 yields the following corollary. Corollary 2. Let C(P, σ) be a deterministic tournament with winner i and c crucial matches and let " 2 (0, 1). Then

bd"(i , P, σ) = c". We now show that crucial matches can be found efﬁciently. Lemma 4. Given a complete deterministic tournament C(P, σ), there exists an O(N log N) algorithm that computes the number of crucial matches.

Proof. Going from below, at each node of the tournament (including the root) we store the winner of the corresponding subtournament. Since N 1 matches are played in total, this takes O(N).

Now imagine a single match corresponding to a subtree S was switched. In order to determine if the original winner still wins we might need to recompute the winners of all the subtournaments containing S. Since the depth of the tree is log(N), there are at most log(N) such tournaments and recomputing the winner of each takes constant time. Overall we get the running time O(N + N log N) = O(N log N).

This proves the deterministic case of Theorem 2.

4.2 Probabilistic setting The idea is similar to the deterministic case. By Lemma 2, we want to adjust each match in one of the two directions as much as possible. Since wp(1, P, σ) is a polynomial linear in each Pij, for any ﬁxed Pij we can express it as

wp(1, P, σ) = ij Pij + βij.

We show that in order to maximize bd"(1, P, σ),

if ij > 0, we adjust Pij to max{0, Pij "},

if ij < 0, we adjust it to min{1, Pij + "},

if ij = 0, the match isn t crucial (i.e. the "-perturbation

of Pij doesn t inﬂuence bd"(1, P, σ)),

to get bd"(1, P, σ) = P

i,j | ij|. Since all ij can be found in polynomial time by extending the recursive procedure for ﬁnding the winning probabilities, we establish Lemma 5 that covers the probabilistic case of Theorem 2.

Lemma 5. Let C(P, σ) be a complete probabilistic tournament. Then bd"(1, P, σ) can be computed in polynomial time.

4.3 Consequences

Our main result has a number of important consequences which we present below.

Corollary 3. The RTFP and the RPTFP problems are NPcomplete.

Proof. The hardness result is an easy consequence of the NPhardness of the TFP problem [Aziz et al., 2014], which is obtained as follows. Consider the RTFP problem (which is a special case of RPTFP problem) with c = N + 1 with sufﬁciently small " > 0. Then for every draw σ we have

bd"(i , P, σ) c"; and hence the answer to the RTFP problem is yes iff the answer to the TFP problem is yes. Hence both RTFP and RPTFP problems are NP-hard. Since every draw is a polynomial witness, both conditions (a) and (b) for RPFTP can be checked in polynomial time by the results of [Vu et al., 2009] and Theorem 2, respectively.

In [Aziz et al., 2014] two important special cases are considered for TFP, namely, tournaments where there are constant number of types of players, and tournaments with linear ordering on players with constant number of exceptions. For both the cases, polynomial-time algorithms are presented in [Aziz et al., 2014] to enumerate all winning draws. In combination with Theorem 2 it follows that the most robust winning draw can also be approximated in polynomial time.

Corollary 4. For the two special cases of TFP from [Aziz et al., 2014], the most robust winning draw (if a winning draw exists) can be approximated in polynomial time.

5 Conclusion

We studied the problem of robustness related to ﬁxing draws in BKT. We presented several illuminating examples related to the robustness properties of optimal and near optimal draws. We established polynomial-time algorithm to approximate the robustness of draws for sufﬁciently small " > 0. As a consequence, for the robustness of draws, we establish NP-completeness in general and polynomial-time algorithms for special cases. Interesting directions of future work are (a) computation of robustness when " > 0 is not small; (b) higher order uncertainties, such as uncertainty in " or different " s for different matches; and (c) the robustness question in other forms of tournaments.

Acknowledgements. This research was partly supported by Austrian Science Fund (FWF) NFN Grant No S11407N23 (Ri SE/SHi NE), Vienna Science and Technology Fund (WWTF) through project ICT15-003, ERC Start grant (279307: Graph Games), and ERC Advanced Grant (267989: QUAREM).

References [Aziz et al., 2012] Haris Aziz, Paul Harrenstein, Markus

Brill, J erˆome Lang, Felix A. Fischer, and Hans Georg Seedig. Possible and necessary winners of partial tournaments. In International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2012, pages 585 592, 2012. [Aziz et al., 2014] Haris Aziz, Serge Gaspers, Simon Mackenzie, Nicholas Mattei, Paul Stursberg, and Toby Walsh. Fixing a balanced knockout tournament. In Proceedings of the Twenty-Eighth AAAI Conference on Artiﬁcial Intelligence, July 27 -31, 2014, pages 552 558, 2014. [Chatterjee et al., 2016] Krishnendu Chatterjee, Rasmus Ibsen-Jensen, and Josef Tkadlec. Robust draws in balanced knockout tournaments. Arxiv Co RR 1604.05090 http://arxiv.org/abs/1604.05090, 2016. [Filar and Vrieze, 1997] J. Filar and K. Vrieze. Competitive

Markov Decision Processes. Springer-Verlag, 1997. [Gusﬁeld and Martel, 2002] Dan Gusﬁeld and Charles U.

Martel. The structure and complexity of sports elimination numbers. Algorithmica, 32(1):73 86, 2002. [Kern and Paulusma, 2004] Walter Kern and Dani el Paulusma. The computational complexity of the elimination problem in generalized sports competitions. Discrete Optimization, 1(2):205 214, 2004. [Lang et al., 2007] J erˆome Lang, Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, and Toby Walsh. Winner determination in sequential majority voting. In IJCAI 2007, Proceedings of the 20th International Joint Conference on Artiﬁcial Intelligence, Hyderabad, India, January 6-12, 2007, pages 1372 1377, 2007. [Lang et al., 2012] J erˆome Lang, Maria Silvia Pini, Francesca Rossi, Domenico Salvagnin, Kristen Brent Venable, and Toby Walsh. Winner determination in voting trees with incomplete preferences and weighted votes. Autonomous Agents and Multi-Agent Systems, 25(1):130 157, 2012. [Puterman, 1994] M. L. Puterman. Markov Decision Processes. J. Wiley and Sons, 1994. [Rockafellar, 2007] R Tyrrell Rockafellar. Coherent approaches to risk in optimization under uncertainty. Tutorials in operations research, INFORMS, 2007. [Stanton and Williams, 2011a] Isabelle Stanton and Virginia Vassilevska Williams. Manipulating stochastically generated single-elimination tournaments for nearly all players. In Internet and Network Economics - 7th International Workshop, WINE 2011, pages 326 337, 2011.

[Stanton and Williams, 2011b] Isabelle Stanton and Virginia Vassilevska Williams. Rigging tournament brackets for weaker players. In IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artiﬁcial Intelligence, pages 357 364, 2011. [Vu and Shoham, 2011] Thuc Vu and Yoav Shoham. Fair seeding in knockout tournaments. ACM TIST, 3(1):9, 2011. [Vu et al., 2009] Thuc Vu, Alon Altman, and Yoav Shoham.

On the complexity of schedule control problems for knockout tournaments. In 8th International Joint Conference on Autonomous Agents and Multiagent Systems AAMAS 2009, pages 225 232, 2009. [Williams, 2010] Virginia Vassilevska Williams. Fixing a tournament. In Proceedings of the Twenty-Fourth AAAI Conference on Artiﬁcial Intelligence, AAAI 2010, 2010. [Xia and Conitzer, 2011] Lirong Xia and Vincent Conitzer.

Determining possible and necessary winners given partial orders. J. Artif. Intell. Res. (JAIR), 41:25 67, 2011.