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 two cases: 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 completely unpredictable.

  • 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 other players.