Author(s):

Chatterjee, Krishnendu; IbsenJensen, 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 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 specified winning probability. Second, we present a polynomialtime algorithm for approximating the robustness of a draw for sufficiently small errors in pairwise winning probabilities, and obtain that the stated computational problem is NPcomplete. We also show that two natural cases of deterministic tournaments where the optimal draw could be computed in polynomial time also admit polynomialtime algorithms to compute robust optimal draws.

Keywords: 
Probability; Polynomialtime; Polynomial approximation; Optimization; Polynomialtime algorithms; Artificial intelligence; NP Complete; Polynomials; Sports competitions; Winning probability; omputational problem

Conference Title:

IJCAI: International Joint Conference on Artificial Intelligence

Volume: 
2016January

Conference Dates:

July 9  15, 2016

ISBN:

9781577357704

Publisher:

AAAI Press

Date Published:

20160101

Start Page: 
172

End Page:

179

URL: 

Notes: 
This research was partly supported by Austrian Science Fund (FWF) NFN Grant No S11407N23 (RiSE/SHiNE), Vienna Science and Technology Fund (WWTF) through project ICT15003, ERC Start grant (279307: Graph Games), and ERC Advanced Grant (267989: QUAREM).

Open access: 
yes (repository) 