| Main index | Tournaments index | About author |
Julian D. A. Wiseman, June 2003 and April 2004
Abstract: Some number of players wish to play an individual-pairs tournament, in which each partners each other once and hence opposes each other twice. How can this be arranged?
Contents: Introduction; Presentations and file formats; Technical notes (unfairness measure, permuting players); Also see.
Publication history: Earlier versions of some of the designs here have previously been made available in paper form by Dr Nicholas F. J. Inglis, for the use of ETwA and CUTwC tournament organisers. This is believed to be the only publication on the web. Usual disclaimer and copyright terms apply.
Quick individual-pairs links: complete list; pure 4 5 8 9 12 13 16 16* 17 20 21 24 25; mixed 3 7 9 11 15 19 23; asymmetric 6 10 14 18 22 26.
i ii iii
1 E+G:I+J L+A:B+H C+F:D+K
2 L+D:E+K F+I:G+C H+J:A+B
3 I+A:J+F K+B:D+E L+G:H+C
4 C+E:G+H L+J:K+F A+D:B+I
5 L+B:C+I D+G:E+A F+H:J+K
6 G+J:H+D I+K:B+C L+E:F+A
7 A+C:E+F L+H:I+D J+B:K+G
8 L+K:A+G B+E:C+J D+F:H+I
9 E+H:F+B G+I:K+A L+C:D+J
10 J+A:C+D L+F:G+B H+K:I+E
11 L+I:J+E K+C:A+H B+D:F+G
|
Twelve players (or teams) are all to play a pairs-style tournament, in which each game consists of one partnership against another. This can be done by having each player partner each of the others exactly once, and hence oppose each of the others exactly twice. Each player has to play eleven games, so this tournament requires at least eleven rounds. With three games happening simultaneously, there must be at least three venues. On the right can be found an example 12-player individual-pairs at three venues venues over eleven rounds.
Individual pairs are not possible for all numbers of players. To see this start by calculating, for any given number of players, the number of possible partnerships. Each game in a tournament uses two of these partnerships, so if the number of partnerships is odd, an individual pairs cannot be produced for that number of players.
The calculation can be altered by allowing self-partnering. But self-partnering makes sense only in non-aerobic games in which turns are taken by players who may confer. So it works in the likes of tiddlywinks, croquet, snooker, and billiards. But self-partnering doesn’t work in games such as bridge and doubles tennis. An individual pairs tournament in which every game is two-versus-two is said to be ‘pure’, and one which includes self-partnering is said to be ‘mixed’.
In a pure individual pairs tournament with n players, there are n(n–1)/2 partnerships. This is even iff n is 0 or 1 modulo 4. In a mixed individual pairs tournament with n players, in which each player self-partners once, there are n(n–1)/2+n partnerships. This is even iff n is 0 or 3 modulo 4. This result continues to hold if each player self-partners any odd number of times. If players self-partner an even number of times, then n must be either 0 or 1 modulo 4.
So pure individual pairs are possible if n is 0 or 1 modulo 4; mixed individual pairs are possible if n is 0 or 1 or 3 modulo 4; and if n is 2 modulo 4 then neither type is possible.
Pure individual-pairs tournament designs are published for various numbers of players from four to twenty-five: 4, 5, 8, 9, 12, 13, 16, (and in another version, 16*), 17, 20, 21, 24, and 25. Mixed individual-pairs tournament designs are published for various numbers of players from three to twenty-three: 3, 7, 9, 11, 15, 19, and 23. Asymmetric individual-pairs tournament designs are published for various numbers of players from six to twenty-six: 6, 10, 14, 18, 22 and 26. Also see the complete list of individual-pairs links.
The precise meaning of some of the terms can vary according to the game being played.
Players are labelled with upper-case roman letters: A, B, C, D, etc.
The specific meaning of the word ‘venue’ will depend on context. In snooker or billiards, a venue refers to a particular table; in tiddlywinks (for which these tournament designs were originally devised), to a particular mat; in tennis to a court; in croquet to a lawn or to a set of balls; and in other games to a location or set of equipment as appropriate. Venues are labelled with lower-case Roman numbers: i, ii, iii, iv, etc.
Several games happen simultaneously during a round, each of which is labelled with an Arabic numeral: 1, 2, 3, 4, etc.
A particular game might be described as ‘A+B:C+D’, meaning that player A is partnering B against C and D (in a particular round and at a particular venue). This is sometimes abbreviated to ‘AB:CD’. However, ‘A+B:C+D’ is not necessarily the same game as ‘C+D:A+B’. In tiddlywinks, the left team should take the dominant corners. In games in which one team starts, left starts or deals first. In general, the left team should have the advantage.
It is intended that other symmetries should also be meaningful. So, in games in which this is meaningful, ‘A+B:C+D’ could have a different order of play to ‘A+B:D+C’, the order being first+third:second+fourth. In games such as doubles tennis this might apply to the serve order. In tiddlywinks, it is suggested that the tournament organiser chooses which of the two dominant corners is to be taken by the first player, so differentiating ‘A+B:C+D’ from ‘B+A:D+C’. In other games it is for the tournament organiser to determine the meaning of left-versus-right, of the play order, and of the residual symmetry. To encourage consistency, tournament organisers are invited to inform the author of any conventions which may be agreed.
Each of these individual-pairs tournaments is published in a number of different presentations and file formats.
Embedded in the master HTML file for each size of individual-pairs is a PRE-formatted text grid, giving the description of which game takes place in each round at each venue. This is also available in a separate text file.
A similar description of the game schedule is available in PDF, with versions optimised for A4, A3 and US Letter (USL).
A game schedule is also available as a table, with one player per column and one round per row, showing the venue to which that player should be going. The players for that game are shown in small characters in the corners of the cell, and hence this format is particularly appropriate for games played on a rectangular surface.
A score-sheet is available in PDF, again in A4, A3 and USL. Players go both horizontally and vertically; enter into each cell the score achieved by the player of that row when partnering the player of that column. Each cell shows the game description, as well as the round and venue.
A more detailed score-sheet is available in PDF (in A4, A3 and USL), with extra columns into which a player’s running total of scores may be entered. With a large number of players the extra columns can crowd the page. The running-total cells show the description of the game just played.
Both the less- and more-detailed score sheets are also available in ‘blank variants’, which don’t have the game descriptions in the cells, and so can be used with other tournament cells.
Finally, each tournament is available in a machine-readable text format, with one row per game. Each row is in the form RR V A+B:C+D, where RR is the round, V is the venue (for ease of machine-readability exceptionally shown in ‘Arabic’ numerals rather than lower-case Roman numbers), and A+B:C+D is the game description. It is from this file that the others are generated: readers sending improved tournament designs are asked to do so in this format.
The construction of the symmetric individual pairs relies on a branch of mathematics called design theory. The following paragraph, by Matt Fayers of The Department of Pure Mathematics and Mathematical Statistics at The University of Cambridge, assumes some knowledge of design theory.
An individual pairs tournament is referred to in the mathematical literature as a whist tournament, and the existence of a whist tournament for any number of player congruent to 0 or 1 mod 4 was proved by Baker in 1975[*1] using a variety of construction techniques. For practical purposes, it is often easiest to find lots of possible whist tournaments by seeking cyclic formats. For 4n+1 players, this means indexing the players and the rounds by the integers modulo 4n+1 (so they start at zero), and choosing the games in round 0 and then decreeing that if A+B:C+D is a game in round 0, then (A+i)+(B+i):(C+i)+(D+i) is a game in round i. Of course, the first round must be chosen in such a way that this produces a whist tournament, but the necessary and sufficient condition on the first round is a simple one based on the differences (mod 4n+1) between the partners and opponents in the various games. For 4n players, a similar procedure is adopted, but here we cycle mod 4n–1 and label one of the players ∞ (with the usual convention that ∞+i=∞). In fact, an analogous procedure can be used for any group of order 4n+1 or 4n–1; in the case of 9 players, this is necessary, since there is no cyclic whist tournament for 9 players, although there is one based on the elementary abelian group of order 9. To assign games to venues is a rather different problem. In the case of 4n+1 players, we might dictate that the game (A+i)+(B+i):(C+i)+(D+i) happens at the same venue as A+B:C+D; this guarantees that each player plays exactly four times at each venue, but also guarantees that three players stay at the same venue between consecutive rounds, even if the rounds are re-ordered. For 4n players, adopting this procedure would keep player ∞ at the same venue throughout, and so is only useful when ∞ is a ‘dummy’ player used in a tournament for 4n–1 players (whoever partners the dummy actually self-partners). When there really are 4n players, some shuffling of games between venues is necessary. The number of possibilities is unwieldy, so the approach used here is to label the venues 0,…,n–1, and then assign games to venues for round 0 and dictate that if A+B:C+D happens in round 0 at venue j, then (A+i)+(B+i):(C+i)+(D+i) happens in round j at venue j+i (reduced mod n). In short, games were shifted one place to the right each round. This guarantees that player ∞ plays three times at one venue and four times at each of the others, and it is then a matter of trying various arrangements of the games in round 1 to try to prevent players staying at the same venue between games and to try to ensure that each of the other players has a reasonably even distribution between venues.
This done, it is still possible to permute the players, with the objective of minimising that which is here called ‘unfairness’. In the symmetric tournaments each player partners everybody once, and opposes everybody twice, so a player would consider it a terrible waste to partner the best-ranked player, A, who is the current world champion, against the two worst ranked players. The partnering of A would be, in some sense, wasted on easy opponents. And likewise, it would be highly desirable to partner the worst ranked player against A+B: it gets out of the way a terrible partner and one of the two oppositions against the two top players, for the loss of one game rather than three. So we would like the combinations of opponents and partners to be chosen fairly, and we start by assigning a numerical score to each player: the worst is 1, the second-worst 2, and so on up to A who scores n. For each player, the average of the values of the other players is calculated, and for player Z this is written (Z). The relative advantage in game W+X:Y+Z for player Z is therefore (Z)+Y-X-W, and for each player the total of these is zero. So the total of the cubes of the relative advantages is calculated, knowing that if a player’s games are fairly distributed, then its sum of cubes will be near zero. The variable that is minimised is then the weighted sum of the squares of these sums of cubes; giving a greater weight to better players by weighting the outer summation by the players’ numeric values. For large numbers of players (above 16), it is possible that the absolute minimum has not been found. When there is self-partnering, there is a slight adjustment to the scoring, so that in W+X:Z+Z the relative advantage of Z is 2(Z)-X-W.
i ii iii
1 A:H D+F:E+J B+C:G+I
2 E:G J+I:H+F C+A:B+D
3 C:F I+E:J+B H+A:D+G
4 G:I B+H:C+J E+D:A+F
5 J:C F+I:A+G B+E:H+D
6 H:E A+D:B+I C+F:J+G
7 D:J E+A:I+C G+H:F+B
8 C:A D+J:G+B F+E:I+H
9 F:B E+G:J+A D+I:H+C
10 I:D G+C:E+H A+B:F+J
11 B:E F+G:C+D J+H:I+A
|
Much of the work of the construction of the symmetric tournaments was done by the mathematics within design theory. The asymmetric tournaments do not have this mathematical base, and for ≥10 players these designs are built by a cascade of optimisations.
If every pair of players partners, there are an odd number of pairs. So instead one pair of two special players do not partner; all other pairs do. In the 10-player example on the right, C and E never partner. So that there are no byes; there is one venue at which singles games are played; and the special players play singles thrice, the others twice.
The first optimisation scatters the all-pairs-but-one over the doubles games, and re-arranges to ensure that no player appears more than once in any round. Pairs are then re-arranged within rounds to ensure that most pairs oppose as nearly to twice as possible. For ≥10 players, each pair of players oppose at least once at doubles, and no more than thrice at singles and doubles together. For ≥18 players, further optimisation might result in a slight improvement. (This technique was suggested by Dr Ed Wynn, then of the University of Birmingham.)
The second optimisation permutes the rounds, and within each round, permutes the games (not the pairs) across venues. The object is to minimise consecutive play at the same venue, and to even the out the numbers of times each player appears at each venue. Ideally, players would never play consecutively at the same venue, but this is achieved only for ≥18 players. Playing consecutive games at the same venue allows a player to become accustomed to that venue’s idiosyncrasies, giving a small advantage. So if there must be consecutive play at the same venue, the optimisation ensures that, in each game, the same number of players in each team were at the same venue in the previous round. Subject to this, it is also desirable that players visit each venue approximately equally, and (again for ≥18 players) each player visits each doubles venue at least three times, and at most five times. For all numbers of players, the sum of the squares of the differences from four has been minimised.
Within a game, it is still possible to switch the right and left sides. Some pairs of players oppose thrice, and left and right sides have been switched to ensure that for any such pair, each player plays at least once (and hence no more than twice) from each side. For the singles games, each special player plays once from one side and twice from the other, and the non-special players play once from each side. Many pairs of players oppose twice, and ideally these oppositions would be once from each side. This is provably not possible, but the number of exceptions has been minimised.
Similarly for play order as for left and right: those that oppose thrice at doubles play either twice before and once after, or once before and twice after. For pairs of players who oppose twice at doubles, as many as possible play once before and once after.
This leaves a remaining symmetry, in that 1st+3rd:2nd+4th can be exchanged for 3rd+1st:4th+2nd. In tiddlywinks it is natural to assign a corner to each particular position, so this symmetry has been used to minimise the number of occasions in which a player plays twice consecutively in the same position at the same venue. For 6 and 10 players this happens only once, and for ≥14 not at all (though for ≥18 players it follows from the no-consecutive-play-at-same-venue property). This minimised, it is then natural to ensure that, at each venue considered in isolation, the number of times each player has each position is balanced, in the usual sum-square sense. That done, it is still possible to apply the transformation to all the games at any particular venue, and this is done to balance the total over the venues of the number of times each player has each position.
It remains to permute the players. Recall that, in the symmetric tournaments each player partners everybody once and opposes everybody twice, so a player’s average opponent and average partner are not changed by permuting the players. But this isn’t true for the asymmetric designs. So the same numerical scores are assigned to each player: the worst is 1, the second-worst 2, and so on up to A who scores n. Again, for each player the average of the values of the other players is calculated, and for player Z this is written (Z), and as above, the relative advantage in game W+X:Y+Z for player Z is therefore (Z)+Y-X-W. These are totalled for each player (uncubed, unlike before), and the weighted sum of the squares of these sums is minimised, where the weights are, again, the players’ numeric values. For large numbers of players (above ≥18), it is possible that the absolute minimum has not been found. It is therefore this minimisation which determines which are the two special players.
Designs for other sizes of tournaments—though requiring much more work from the user—can be found at Durango Bill's Bridge Probabilities and Combinatorics.
*1 R. Baker, ‘Whist Tournaments’, Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Num. 14, 89-100.
| Main index | Top | About author |