Round-robin tournament

A round-robin tournament or all-play-all tournament is a type of group tournament in which each participant plays every other participant an equal number of times. In a single round-robin schedule, each participant plays every other participant once. If each participant plays all others twice, this is frequently called a double round-robin. The term is rarely used when all participants play one another more than twice, and is never used when one participant plays others an unequal number of times (as is the case in all of the major United States professional sports). A round-robin tournament with four players is sometimes called a "quad".

The term round-robin is derived from the French term ruban, meaning "ribbon". Over a long period of time, the term was corrupted and idiomized to robin.

In sports with a large number of competitive matches per season, double round-robins are common. Almost all football (soccer) leagues in the world are organized on a double round-robin basis, in which every team plays all others in its league once at home and once away. There are also round-robin chess tournaments; the World Chess Championship was decided in 2005 and in 2007 by an eight-player double round-robin tournament, where each player faces every other player once as white and once as black.

Group tournaments rankings usually go by number of matches won and drawn, with any of a variety of tiebreaker criteria.

Frequently, pool stages within a wider tournament are conducted on a round-robin basis. Examples with pure round-robin scheduling include the FIFA World Cup and UEFA Cup (since 2004–05) in football, the Super 14 of rugby union in the Southern Hemisphere, the Cricket World Cup and many American Football college conferences, such as the Mountain West Conference. The group phase of the UEFA Champions League is contested as a double round-robin, as are most basketball leagues outside the United States, including the regular-season and Top 16 phases of the Euroleague.

Evaluation

In a round-robin format, the element of luck is seen to be reduced, given that all competitors face the same opponents, and a few bad performances need not cripple a competitor's chances of ultimate victory. In English football, although the FA Cup was founded before the Football League, the (round-robin) League champions have always been regarded as the "best" team in the land, rather than the (knockout) Cup winners.

Disadvantages include the existence of games late in the competition between competitors with no remaining chance of success. Moreover, some later matches will pair one competitor who has something left to play for against another who does not. This asymmetry means that playing the same opponents is not necessarily equitable: the same opponents in a different order may play harder or easier matches. There is also no showcase final match. The ability to recover from defeats, while rewarding overall consistency, may also be seen as a crutch for competitors who lack the temperament to handle the pressure of a knockout tournament.

Further issues arise where a round-robin is used as a qualifying round within a larger tournament. A competitor already qualified for the next stage before its last game may either not try hard (in order to conserve resources for the next phase) or even deliberately lose (if the scheduled next-phase opponent for a lower-placed qualifier is perceived to be easier than for a higher-placed one).

Swiss system tournaments attempt to combine elements of the round-robin and elimination formats, to provide a reliable champion using fewer rounds than a round-robin, while allowing draws and losses.

Scheduling algorithm

If $n$ is the number of competitors, a pure round robin tournament requires ${\begin{matrix}{\frac {n}{2}}\end{matrix}}(n-1)$ games. If $n$ is even, then in each of $(n-1)$ rounds, ${\begin{matrix}{\frac {n}{2}}\end{matrix}}$ games can be run in parallel, provided there exist sufficient resources (e.g. courts for a tennis tournament). If $n$ is odd, there will be $n$ rounds with ${\begin{matrix}{\frac {n-1}{2}}\end{matrix}}$ games, and one competitor having no game in that round.

The standard algorithm for round-robins is to assign each competitor a number, and pair them off in the first round …

Round 1. (1 plays 14, 2 plays 13, ... )
 1  2  3  4  5  6  7  
 14 13 12 11 10 9  8

… then fix one competitor (number one in this example) and rotate the others clockwise …

Round 2. (1 plays 13, 14 plays 12, ... )
 1  14 2  3  4  5  6
 13 12 11 10 9  8  7

Round 3. (1 plays 12, 13 plays 11, ... )
 1  13 14 2  3  4  5
 12 11 10 9  8  7  6

… until you end up almost back at the initial position

Round 13. (1 plays 2, 3 plays 14, ... )
 1  3  4  5  6  7  8
 2 14  13 12 11 10 9

If there are an odd number of competitors, a dummy competitor can be added, whose scheduled opponent in a given round does not play and has a bye. The upper and lower rows can indicate home/away in sports, white/black in chess, etc (this must alternate between rounds since competitor 1 is always on the first row). If, say, competitors 3 and 8 were unable to fulfill their fixture in the third round, it would need to be rescheduled outside the other rounds, since both competitors would already be facing other opponents in those rounds. More complex scheduling constraints may require more complex algorithms.

Number of possible results

Let us have $n$ competitors, and a scoring system where no ties are permitted. Let $s_{i}$ be the number of wins scored by competitor $i$ , and let us order them such that $s_{1}\leq s_{2}\leq \cdots \leq s_{n}$ . Thus we define a score vector, $(s_{1},s_{2},\cdots ,s_{n})$ , satisfying the following three conditions:

$0\leq s_{1}\leq s_{2}\leq \cdots \leq s_{n}$
$s_{1}+s_{2}+\cdots +s_{i}\geq {i \choose 2},{\mbox{for }}i=1,2,\cdots ,n-1$
$s_{1}+s_{2}+\cdots +s_{n}={n \choose 2}$

Let $s(n)$ be the number of different score vectors of size $n$ . The sequence $s(n)$ (sequence A000571 in the OEIS) starts as:

1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, ...

It is possible to show that for sufficiently large n:

s(n)>c_{1}4^{n}n^{-{5 \over 2}}

Also:

s(n)<c_{2}4^{n}n^{-{5 \over 2}}

Where: $c_{1}=0.049,\,\,c_{2}<4.858.$

Together these show that:

s(n)\in \Theta (4^{n}n^{-{5 \over 2}}).

Here $\Theta$ signifies an asymptotically tight bound.

Famous round-robin tournaments

Hastings 1895 chess tournament
Nottingham 1936 chess tournament
AVRO tournament (1938)
World Chess Championship 1948
Interzonal and Candidates Tournament of the World Chess Championship 1963
World Chess Championship 2007
USSR Chess Championship (most years)
U.S. Chess Championship (most years)
U.S. Tournament of Champions (debate) (most years)
Corus chess tournament
Linares chess tournament
M-Tel Masters
Dortmund Sparkassen Chess Meeting (most years)
Ring of Honor Round Robin Challenge

Other tournament systems

References

Takacs, Lajos (1991). "A Bernoulli Excursion and Its Various Applications". Advances in Applied Probability. 23 (3): 557–585.

External links

SCHED link to a DOS program to quickly create round robin schedules
Tournament 16 link to a Windows XP program to create round robin schedules and export to HTML.
Round Robin Generator link to an online tool to quickly create a round robin schedule, and export to MS Excel.
Round Robin Discussion Board link to a discussion community and schedules (balanced,cyclic,first-fit,whist).