Robust draws in balanced knockout tournaments Conference Paper

Author(s): Chatterjee, Krishnendu; Ibsen-Jensen, Rasmus; Tkadlec, Josef
Title: Robust draws in balanced knockout tournaments
Affiliation IST Austria
Abstract: Balanced knockout tournaments are ubiquitous in sports competitions and are also used in decision-making 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 specified winning probability. Second, we present a polynomial-time algorithm for approximating the robustness of a draw for sufficiently 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.
Keywords: Probability; Polynomial-time; Polynomial approximation; Optimization; Polynomial-time algorithms; Artificial intelligence; NP Complete; Polynomials; Sports competitions; Winning probability; omputational problem
Conference Title: IJCAI: International Joint Conference on Artificial Intelligence
Volume: 2016-January
Conference Dates: July 9 - 15, 2016
ISBN: 978-1-57735-770-4
Publisher: AAAI Press  
Date Published: 2016-01-01
Start Page: 172
End Page: 179
Notes: This research was partly supported by Austrian Science Fund (FWF) NFN Grant No S11407-N23 (RiSE/SHiNE), Vienna Science and Technology Fund (WWTF) through project ICT15-003, ERC Start grant (279307: Graph Games), and ERC Advanced Grant (267989: QUAREM).
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work