Robust Draws in Balanced Knockout Tournaments

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 first 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 specifies the probabilities Pij of player i beating player j in a single match, and a distinguished player i⇤ . The input, along with a draw, defines 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 fixing 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 specific 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 finally 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 identified (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.

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 infimum 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 logN · ✏. 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 specified winning probability with a drop below a specified 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 quantifier 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].

Significance as risk-averse strategies. As mentioned, BKTs are often used as sports tournaments. After a draw is fixed, 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 RelatedWork

The most related previous works are: (a) [Vu et al., 2009], who showed that for a fixed 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] identified various sufficient 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 fixed 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; Gusfield 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 definitions and previous results.

2.1 Definitions

For the basic definitions we very closely follow the notations of [Aziz et al., 2014].

Definition 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 defined. A comparison matrix is deterministic if Pij 2 ¶0↪ 1♦ for all i↪ j 2 [N] with i 6= j.

Definition 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 ⌃.

4

Definition 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.

Definition 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

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 find out how sensitive is the winning chance in optimal draws (or near optimal draws) with respect to minor changes in the comparison matrix. We first present the basic definition and then our examples. Finally, we present the computational problems.

Definition 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, define the "-guaranteed winning probability wp"(i⇤ ↪ P↪ σ) by

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 sufficiently small " > 0. Intuitively, "sufficiently small" will allow us to ignore all higher order terms of " such as "2 ↪ "3 ↪ ▷ ▷ ▷ A formal definition 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 first 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

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, satisfies

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

9

16

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 logN - 1), for sufficiently 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

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) fulfil 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 find one "- perturbation that reduces the winning chance of player 1 sufficiently. 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 first n - 1 rounds is pn-1 = 1 - (2n-1 - 1)" + "2Q0 (") for some polynomial Q0 ("). The probability of winning the final is then always 1 - " which altogether gives

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 first 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

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

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

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 first 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 + 12 (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,

We claim that:

• ÷ Pmb = 0▷5- 12 ".
• 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.
• For any optimal draw σ, the draw σ0 = (1↪ ▷ ▷ ▷ ↪ 2n ) satisfies wp"(1↪ P↪ σ) < wp"(1↪ P↪ σ0 ) for all sufficiently small " > 0.

Indeed:

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

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 final (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 final. Hence his winning chance is at most 0▷62 < wp(1↪ P↪ σ) for all sufficiently 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

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▷512 "↪ 0▷5 + 12 ") match by a (0▷5 + 12 "↪ 0▷5 - 12 ") match. Then by Lemma 1 we have

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 sufficiently 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,
• ÷ Pmb = 0▷49.
• ÷ Psm = Psb = 0,

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

• ÷ P ⇤ 1s = 0▷98, P ⇤ 1m = 0▷38, P ⇤ 1b = 0▷58,
• ÷ P ⇤mb = 0▷51
• ÷ P ⇤ sm = Psb = 0,

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 first five 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 b d"(i⇤ ↪ P↪ σ) of the drop d"(i⇤ ↪ P↪ σ) is the linear term of this polynomial. Since higher order terms of " are ignored, the number b d" is really only an approximation of d". However, for all c < N, if " is sufficiently small (smaller than cN -2 ), then b d" is within ◦c" of d", so the approximation is tight. Formally, we consider the following problems.

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 d"(i⇤ ↪ P↪ σ)  s", for all " > 0 sufficiently small?

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) b d"(i⇤ ↪ P↪ σ)  c", for all " > 0 sufficiently small?

(b) b Note that the drop computation is an infimum over all "- perturbation matrices, and thus represents a universal quantification. Thus in contrast to the TFP and the PTFP problems which have only existential quantification over draws, the robustness problem has a quantifier alternation of existential and universal quantifiers.

4 Algorithms

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

Theorem 2. Given a comparison matrix P (deterministic or probabilistic), sufficiently small " > 0, distinguished player i⇤ and a draw σ, the value b d"(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 satisfies that either ♣P 0 ij - Pij ♣ = " or P 0 ij 2 ¶0↪ 1♦.

Proof. For a fixed 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(N-1 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 d"(i⇤ ↪ P↪ σ).

that matter for the sake of determining b 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

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

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 b d"(i⇤ ↪ P↪ σ) = c". We now show that crucial matches can be found efficiently.

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 · logN) = O(N logN).

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 fixed Pij we can express it as

We show that in order to maximize b d"(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, thematch isn't crucial (i.e. the "-perturbation d"(1↪ P↪ σ)),

of Pij doesn't influence b to get b d"(1↪ P↪ σ) = Pi↪j ♣↵ij♣. Since all ↵ij can be found in polynomial time by extending the recursive procedure for finding 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 b d"(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 sufficiently small " > 0. Then for every draw σ we have b d"(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 fixing 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 sufficiently 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 (RiSE/SHiNE), Vienna Science and Technology Fund (WWTF) through project ICT15-003, ERC Start grant (279307: Graph Games), and ERC Advanced Grant (267989: QUAREM).