Finding the optimal draw of a balanced knockout tournament for a player

Balanced knockout tournaments are one of the most common formats for sports competitions, and are also used in elections and decision-making. Such tournaments can be represented by a balanced binary tree in which the leaves correspond to the players. A balanced knockout tournament is conducted in the following fashion. Players that correspond to sibling leaf nodes play a match against each other. The winner of the match proceeds up the tree to the next round. The winner of the balanced knockout tournaments is the player who reaches the root node.

Example 1: One of the balanced knockout tournament of which I have fond memories is the one on four teams that represents the semi finals and final of the 1992 cricket world cup. South Africa and New Zealand who lost their respective semi-finals were eliminated whereas Pakistan and England contested the final in Melbourne.

It has long been observed that the draw (the way players/teams are paired up) of a balanced knockout tournament can significantly affect the outcome of the tournament. This phenomenon is explained in the next example.

Example 2: Consider the following pairwise comparisons between four tennis players based on their career head to head record in Table 1. +1 means that the row player has a winning head to head record against the column player and in this example let us (unreasonably) assume that in a pairwise match, the player with the better head to head record will win. If we make this assumption, then Federer will only win a balanced knockout tournament on the four players if Nadal plays Davydenko in the first round. Thus we can see that a suitably scheduled draw can affect the winner of the tournament. If Nadal plays Federer or Djokovic in the first round (semi-final), then Nadal will also go on to win the overall tournament.

Although this issue of the "significance of the draw"  has received much interest in mathematics, economics, and statistics, it was only in 2009 [VAS09] that a very natural computational problem was first formulated:  

Does there exist a draw in which a given player wins the balanced knockout tournament? 

We refer to the problem as TFP (Tournament Fixing Problem). The problem need not be seen in a negative light as some malicious tournament organizer trying to pave the way for his favorite player. The problem is also used in post tournament analysis and to gauge the relative strengths of the players and to analyze "what could have happened". The paper of Vu et al.  has received considerable received interest in the AI literature and was followed up with some interesting work [SV11a, SV11b, W10a]. Although generalizations of TFP have been examined, the complexity of TFP has remained an open problem (see for example the blog post).

Recently, in a paper [AGM+14] with colleagues at the  ADT group, NICTA ---- Serge Gaspers,  Simon Mackenzie, Nicholas Mattei, Paul Stursberg (visiting from TU Munich) and Toby Walsh --- we have shown that TFP is NP-complete. The result has some interesting corollaries. If we consider a probabilistic model in which a player has a certain probability of winning against another player, then we obtain the corollary that unless P = NP, there exists no polynomial- time algorithm that approximates the maximum possible winning probability of a player within any given factor. A second corollary is that unless NP = RP, there exists no FPRAS for the problem of counting the number of draws in which a player wins.

We complement the result mentioned above by showing that there are two natural cases in which TFP can be solved in polynomial time. In the first case, the players can be divided into a constant number of player types. It appeals to the scenario where players can be divided into groups based on similar intrinsic ability. In the second case, there is a linear ordering on the ability of players with a constant number of exceptions where a player with lower ability beats a player with higher ability. 

References

[AGM+14] H. Aziz, S. Gaspers, S. Mackenzie, N. Mattei, P. Stursberg and T. Walsh. Fixing a Balanced Knockout Tournament. AAAI 2014 (forthcoming)

[SV11a] Stanton, I., and Vassilevska Williams, V. 2011. Manipulating stochastically generated single-elimination tournaments for nearly all players. In Proceedings of 7th In- ternational Workshop on Internet and Network Economics (WINE), 326–337. 

 
[SV11b] Stanton, I., and Vassilevska Williams, V. 2011. Rigging tournament brackets for weaker players. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), 357–364. 

[VAS09] Vu, T.; Altman, A.; and Shoham, Y. 2009. On the complexity of schedule control problems for knockout tournaments. In Proceedings of the 8th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 225–232. 

[W10a] Vassilevska Williams, V. 2010. Fixing a tournament. In Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI), 895–900. AAAI Press.