We consider the optimal design of a tournament to determine the best
of n players, where the best player has some probability greater than half of
beating each of the other players in an individual game. We consider
known win probabilities, where the probabilities that the
best player beats each of the other players in a game are known
(although naturally the identities of the individual players are not
known), and unknown win probabilities.
Within each of the above cases, we consider three models for the
outcomes of games that do not involve the best player:
Adversary Model: The outcome of all games not involving the
best player are under the control of an adversary, i.e., they are
Strong Transitivity Model: This model assumes
there is a a fixed ranking of the players such that a higher-ranked
player always has at least a 50 percent chance of beating a
lower-ranked player in a game, and, for any fixed player, the stronger
the opponent the lower the probability of winning.
Discriminating Model: This is a special case of the strong
transitivity model where, speaking loosely, weaker players are better for
distinguishing between two players.
For each of the above cases and models, we prove upper and lower
bounds on the number of rounds required to determine the best player
with probability 1 - Delta, where our bounds are as a function of
Delta and the advantage of the best player against each of the