Double-Elimination Tournaments: Counting and Calculating

Article excerpt

1. INTRODUCTION

Frequently, a researcher wants to choose the best treatment from a set of treatments. A similar situation occurs in sporting events where the best team or player is chosen from a set of teams or players. For convenience I will use the terminology of sports in this article; however, the reader should be aware that all results apply to any situation where paired comparisons are appropriate.

A tournament is a rule that specifies how the teams or players are to be compared to choose a winner or winners. In sporting events it is customary to use the terms games, competitions, and contests interchangeably to represent experimental units. Similarly, the terms teams, players, competitors, and contestants are interchangeable and represent the treatments. I assume that games always result in either a win or a loss; ties are not allowed.

In a knockout tournament games are played until all but one player have been "knocked out," or eliminated. The games must be played in a specific order because the results of the earlier games designate the contestants in later games; a player who is eliminated does not compete again. A single-elimination (SE) tournament is a knockout tournament where teams are eliminated after losing one game, and game winners continue to play until all but one team have been eliminated. This single remaining team is the winner of the tournament. A double-elimination (DE) tournament is a knockout tournament where teams are eliminated after losing two games.

Ladwig and Schwertman (1992) model some DE tournaments using logistic and linear models, but only deal with the familiar eight-team DE tournament. Maurer (1975) works on the problem of SE tournament structures, which are the diagrams one uses in tournaments to specify which games are played. His work is important because it is the first attempt to analyze different tournament structures instead of just considering tournaments of size [2.sup.t]. Chung and Hwang (1978) also consider different sized structures, but they do not fix the tournament draw (the structure with teams identified) ahead of time; rather, they average over all possible draws. Hwang (1982) contributes to the theory of SE tournaments by allowing the assignment of relative strengths, or "seedings," in knockout tournaments to change after each round. Edwards (1991) develops notation and theorems regarding SE tournaments, including a way to calculate the probabilities of teams winning an SE tournament, which appears in Section 3. Schwertman, McCready, and Howard (1991) also give results on calculating probabilities in an SE tournament.

The objectives of this article are to introduce and develop notation and terminology for DE tournaments (Section 2), to calculate the probabilities of teams winning a DE tournament (Section 3), and to count the number of DE tournaments (Section 4).

2. DEFINITIONS AND NOTATION

Tournaments are specified by the initial games to be played and the rules for pairing the winners in the following games. The number of rounds in a tournament is the maximum number of games that any of the teams must play to win the tournament. A bye occurs when a team does not play in a round. One popular type of tournament in sports settings is the classic tournament. A classic tournament is a tournament where the number of teams is a power of two and there are no byes. A tournament structure is that part of a tournament rule which specifies how the contestants will be paired without specifying which contestants will be paired [ILLUSTRATION FOR FIGURE 1 OMITTED].

The tournament structure shows the method in which the winners of games will be paired with other winners or with teams receiving byes. In a tournament structure a slot is one of the horizontal lines with an open left end, as in Figures 1 and 2, and represents the first appearance of a team in a tournament. A tournament draw is a tournament structure where the players have been identified and assigned initial slots. …