Round Robin Tournament Scheduling

Howell matrices

Bill Daly · 6 · 11550

Bill Daly

  • Newbie
  • *
    • Posts: 14
on: August 15, 2009, 11:14:02 PM
I don't know whether anyone is watching this forum, and I don't know how advanced the discussions might be, but I have an interest in what I suspect are called "cyclic" solutions on this site. It will probably take me a fair bit to develop the ideas, so I'll try to break it up into several posts.

I've called the construct I'm interested in a "Howell Matrix" (which I'll abbreviate HM), in recognition of the fact that it was inspired by the Howell Movement used for Duplicate Bridge and invented by Professor Edwin Howell, a mathematics professor at MIT in the 19th century. Howell movements correspond to special cases of HMs, specifically those in which the "tuples" are pairs. An HM has two parameters, its "order" r and its "width" k. The number of rows is rk+1, and with n = rk+1-r, there are kn symbols, for which I will use the digits 0, 1, 2, 3, etc., switching to upper case alphabetical characters after 9, and lower case alphabetical characters after Z. This convention will accommodate up to 62 symbols, which is more than enough for now. The symbols in each row are arranged as n k-tuples, and it is required that each pair of symbols appears together in the same tuple exactly once in the matrix. Since there are kn symbols, the total number of unordered pairs in the matrix is kn(kn-1)/2, and each k-tuple contains k(k-1)/2 unordered pairs, thus there are kn(k-1)/2 in each row. Thus, the number of rows is (kn-1)/(k-1) = rk+1, as assumed. In order for this to make sense, we must have k ≥ 2 and r ≥ 1. Thus, a matrix that can be defined by the following rules is an HM:
  • For some integers r and k, with k ≥ 2 and r ≥ 1, there are rk+1 rows and rk+1-r columns;
  • Each cell contains a k-tuple of symbols, chosen from a set containing k(rk+1-r) distinct symbols;
  • Each symbol appears exactly once in each row;
  • Each unordered pair of symbols appears exactly once within the same k-tuple of the matrix.
Howell movements per se correspond to matrices with k = 2. Kirkman Triple Systems (abbreviated KTS) correspond to matrices with k = 3. Generalized forms of these can usually be represented as HMs.

The definitions above serve for unrestricted HMs. It is possible to impose extra rules to define "cyclic" behavior:
  • The k(rk+1-r) symbols can be divided into k cycles -- one containing a single (fixed) symbol, and k-1 containing rk+1 symbols;
  • There is a permutation of the symbols which fixes the one fixed symbol and permutes the remainder in k-1 cycles of length rk+1 each, such that when applied to any row, it generates the row immediately below it (the top row if the row acted on is the bottom row);
  • The symbols in each row can be arranged so that the successor to any symbol in a row is the symbol immediately below it.
If an HM obeys these rules, then it is a Cyclic Howell Matrix, which I will abbreviate CHM.

It's not obvious that CHMs exist, so in the next post, I'll give a couple of examples.
« Last Edit: August 17, 2009, 04:50:23 PM by admin »


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1140
Reply #1 on: August 18, 2009, 03:47:10 AM
Many thanks for your interesting post.  If I have understood correctly then the cyclic round-robin schedules that you can see by following the "schedules" link at the to this page are all examples of a CHM where k=2 and player 1 is the fixed symbol.  Is that right?

I am looking forward to your next post.


Bill Daly

  • Newbie
  • *
    • Posts: 14
Reply #2 on: August 18, 2009, 04:11:04 PM
Quote
Many thanks for your interesting post.  If I have understood correctly then the cyclic round-robin schedules that you can see by following the "schedules" link at the to this page are all examples of a CHM where k=2 and player 1 is the fixed symbol.  Is that right?

I am looking forward to your next post.
I haven't checked every schedule that you have, but I'd guess that, assuming they are based on cyclic patterns, they would be covered.

I'm trying to get the rest of my messages posted (there are 3 parts), but it may take some time.


wbport

  • Senior Member
  • ****
    • Posts: 129
Reply #3 on: August 19, 2009, 03:24:44 PM
Bill:

Welcome aboard!

I am familiar with the pairing tables created by Johann Berger, a German chessmaster around 1900.  By "seating" consecutive pairing numbers in every other chair within the ribbon, I was able to replicate his tables.  This is an example of the setup and round to round rotation (ignore everything under the blue bar) and that page has a link to my table generator.

The Howell Movement in Duplicate Bridge you referred to seems to be an ordinary round robin except the cards have their own movement.  Perhaps it is like chess RR except no person (pairs in bridge) can sit at the same table more than once?  My own experience in bridge was over 25 years ago and never as a director.

This forum occasionally gets requests for three players in a game (e.g., cutthroat pool) or assigned partners (doubles tennis).  I'll be interested to see your future posts here.


Bill Daly

  • Newbie
  • *
    • Posts: 14
Reply #4 on: August 19, 2009, 06:03:52 PM
Quote
Bill:

Welcome aboard!

I am familiar with the pairing tables created by Johann Berger, a German chessmaster around 1900.  By "seating" consecutive pairing numbers in every other chair within the ribbon, I was able to replicate his tables.  This is an example of the setup and round to round rotation (ignore everything under the blue bar) and that page has a link to my table generator.

The Howell Movement in Duplicate Bridge you referred to seems to be an ordinary round robin except the cards have their own movement.  Perhaps it is like chess RR except no person (pairs in bridge) can sit at the same table more than once?  My own experience in bridge was over 25 years ago and never as a director.

This forum occasionally gets requests for three players in a game (e.g., cutthroat pool) or assigned partners (doubles tennis).  I'll be interested to see your future posts here.
There are two types of pairs movements commonly used for duplicate bridge: the Howell movement and the Mitchell movement. The Mitchell is far and away the more common, since it is the movement usually played with 7 or more tables (14 or more pairs). The Mitchell movement has two "fields", one of which plays exclusively North-South and the other plays exclusively East-West. The North-South pairs remain at the same table for the entire session, while the East-West pairs move to the next higher table after each round -- if there is an even number of tables, then the East-West pairs have to skip a round at some point, to avoid playing the same hands (boards) twice. The boards always move to the next lower table after each round.

The Howell movement is more irregular. There is generally one stationary pair, and the other pairs (always an odd number of them) move in a cycle through various positions, both North-South and East-West, so that there is only one field consisting of all the pairs. However, there is the additional constraint that no pair can play the same boards more than once, which makes it effectively impossible to use a simple round-robin movement. (It's been a long time since I directed a bridge tournament, so I may have forgotten some details.) For example, it is not possible to use the following schedule for 10 pairs:

RoundTable 1Table 2Table 3Table 4Table 5
110-19-28-37-46-5
210-21-39-48-57-6
310-32-41-59-68-7
410-43-52-61-79-8
510-54-63-72-81-9
610-65-74-83-92-1
710-76-85-94-13-2
810-87-96-15-24-3
910-98-17-26-35-4

since it is not possible to arrange a simple board movement to handle it.

There's more than one way to skin a cat, though. The following layout, or something similar, might work:

RoundTable 1Table 2Table 3Table 4Table 5
110-18-69-57-43-2
210-29-71-68-54-3
310-31-82-79-65-4
410-42-93-81-76-5
510-53-14-92-87-6
610-64-25-13-98-7
710-75-36-24-19-8
810-86-47-35-21-9
910-97-58-46-32-1

Even after the board movement issue is resolved, there is then an issue called "balance of comparisons". The issue is this: there are 9 sets of boards, played by each pair, 5 of them in the North-South direction and 5 in the East-West direction. The pairs who play a set of boards in the same direction are scored against each other, so you don't want two pairs to play in the same direction more than the average, since they are then weighted against each other too strongly, and likewise too weakly against some other pair(s). It gets messy very quickly -- suffice it to say that the normal cure for imbalanced comparisons is judicious arrow switches, i.e. on some round(s), the pairs who would normally play North-South plays East-West instead, and vice versa.

The bible of bridge movements is Alex Groner's "Duplicate Bridge Direction", which is more practical than theoretical. It's worth looking at.
« Last Edit: August 20, 2009, 03:59:38 PM by admin »


Bill Daly

  • Newbie
  • *
    • Posts: 14
Reply #5 on: August 20, 2009, 05:24:47 PM
You can find a complete 5-table (10-pair) Howell movement at http://www.admatis.com/bridzs/Letoltheto%20anyagok/5tables-9rounds-18boards.pdf. The gist of it is as follows. Each cell here includes the N-S pair#, the E-W pair#, and the board# in parentheses. The stationary pair is numbered 10 here, and the boards move down 1 table after each round. Note that there are actually 9 boards, with boards 6-9 placed on a "by-stand" (usually a chair) next to table 5. The players at table 5 get their next board from the top of the by-stand stack, while the board last played at table 1 is moved to the bottom of the by-stand stack. The complete game usually consists of 9 rounds of three boards per round, which can be obtained by replacing each board in the schedule with a set of three boards.

RoundTable 1Table 2Table 3Table 4Table 5
17-3 (1)5-2 (2)10-1 (3)9-8 (4)4-6 (5)
28-4 (2)6-3 (3)10-2 (4)1-9 (5)5-7 (6)
39-5 (3)7-4 (4)10-3 (5)2-1 (6)6-8 (7)
41-6 (4)8-5 (5)10-4 (6)3-2 (7)7-9 (8)
52-7 (5)9-6 (6)10-5 (7)4-3 (8)8-1 (9)
63-8 (6)1-7 (7)10-6 (8)5-4 (9)9-2 (1)
74-9 (7)2-8 (8)10-7 (9)6-5 (1)1-3 (2)
85-1 (8)3-9 (9)10-8 (1)7-6 (2)2-4 (3)
96-2 (9)4-1 (1)10-9 (2)8-7 (3)3-5 (4)

I changed Round 9, Table 2 to (4-1) (1) to be consistent with the rest of the patterns in the table -- Richard
« Last Edit: August 20, 2009, 05:25:39 PM by Bill_Daly »