Mixing of regatta competitors

[stockzahn]

Dear all,

we are organizing a regatta, there are 12 competing crews and we have six boats. Therefore the regatta is organized in so-called fleets, each consisting of two races at which six crews (using the six available boats) are participating. We assume to be able to race 10 to 15 fleets (i.e. 20 to 30 races), but of course that depends on the weather, especially the wind. However, of course we intend to have balanced fleets during the entire regatta with respect to the crews racing directly against each other, that means we want to mix the fleets/races to achieve as little difference between the number of direct matches between each of the competitors.

Overall there are $\frac{1}{2} {12\choose 6}=462$ possibilities to assign the twelve crews to two races at with six boats. After 462 fleets every crew had the same number races with each other competitor, if there is only one fleet organized that's of course not possible. Now there is my question: How is it possible to determine how balanced the number of direct encounters between every combination of two crews is after a certain number of fleets raced (10 to 15 in my case).

I tried to write a small code, and for 15 fleets I obtain combinations of (some) two crews which meet 5 times in the same race after 15 fleets, where the maximal number of encounters between (some) two crews is 9. I'm not able achieve smaller differences than 4. The average would be 15 races each crew participates at multiplied with 5 other boats per race divided by the eleven other crews:

$$ \frac{15\;races\cdot 5\;boats}{11\;opponents}\approx 6.8\;encounters$$

Therefore after 15 fleets every crew should meet every other crew directly in a race 6.8 times, which means 6, or more probable, 7 times. With my code I obtain between 5 and 9 times. Are my numbers really the best mixing achievable or is it possible to decrease the difference between the lowest and highest number of encounters? Could you help me to find the this difference mathematically?

Thanks and have a nice morning/afternoon/evening/night - wherever you are,

stockzahn

 

[Dale]

I did something similar for a pinewood derby competition, but we had some slightly different goals. One difference is that the pinewood derby races are held on a track with three fixed lanes, and it is possible that different lanes are more or less favorable. So we made sure that every car would race in every lane an equal number of times.

We also wanted to make the races as competitive as possible, so rather than trying to race every car with all the other cars we tried to race the fast cars against other fast cars and the slow cars against other slow cars. That made the races more exciting to watch.

I used a version of the TrueSkill system which is itself based on the Glicko system.

http://trueskill.org/

 

[stockzahn]

I did something similar for a pinewood derby competition, but we had some slightly different goals. One difference is that the pinewood derby races are held on a track with three fixed lanes, and it is possible that different lanes are more or less favorable. So we made sure that every car would race in every lane an equal number of times.

We also wanted to make the races as competitive as possible, so rather than trying to race every car with all the other cars we tried to race the fast cars against other fast cars and the slow cars against other slow cars. That made the races more exciting to watch.

I used a version of the TrueSkill system which is itself based on the Glicko system.

http://trueskill.org/

Thanks for the link, Dale. Unfortunately that's not my intend, to put the good crews in one race and the bad one in the other. This would distort the result, although of course at championships this is a proper method to divide the field into two groups after something like qualifying races. However, if we change mode one time, the program for sure can be helpful - so thanks again.

 

[Dale]

Unfortunately that's not my intend, to put the good crews in one race and the bad one in the other. This would distort the result,

Actually, it doesn’t distort the result at all. In the TrueSkill method you get a higher rating for beating high-ranked opponents than for beating low-ranked opponents. After even one round you can establish a decent ranking for making further matches competitive.

However, I don’t know much about regattas, so it may be that competitiveness is not an issue. For Cub Scouts we found that everyone has more fun (both the best and worst cars) if the races are close.

Oh, one thing I forgot to mention. The TrueSkill method works better when more skill and less luck is involved. I don’t know if regattas are more skill or luck based.

 

[stockzahn]

Actually, it doesn’t distort the result at all. In the TrueSkill method you get a higher rating for beating high-ranked opponents than for beating low-ranked opponents. After even one round you can establish a decent ranking for making further matches competitive.

However, I don’t know much about regattas, so it may be that competitiveness is not an issue. For Cub Scouts we found that everyone has more fun (both the best and worst cars) if the races are close.

Oh, one thing I forgot to mention. The TrueSkill method works better when more skill and less luck is involved. I don’t know if regattas are more skill or luck based.

Okay, I understand what you mean. As already mentioned especially at regattas with many competitors a similar modus is applied and it would be worth trying once, but in this case unfortunately that's not an option. Goal (of the organizers) is to find fleet well-balanced so that every crew meets every other crew in a direct match as equally frequently as possible.

 

[pbuk]

What you need is someone with an interest both in combinatorics/non-linear optimization and sailing. That'll be someone like me then!

I haven't got an answer for you at the moment, but I'll give you a couple of pointers:

• For regatta round robins my first port of call is usually the http://www.sailing.org/27298.php.
• I don't think that goes far enough for this problem though, so a good start point is the 2015 paper Constructing Sailing Match Race Schedules: Round-Robin Pairing Lists, and if that doesn't help its references may.

I think the solution here is probably an heuristic based on selecting for the next pair of flights from the 462 possibilites the one that best balances the number of individual pairings. I might sketch something up if I have time.

 

[pbuk]

Actually, it doesn’t distort the result at all. In the TrueSkill method you get a higher rating for beating high-ranked opponents than for beating low-ranked opponents. After even one round you can establish a decent ranking for making further matches competitive.

However, I don’t know much about regattas, so it may be that competitiveness is not an issue. For Cub Scouts we found that everyone has more fun (both the best and worst cars) if the races are close.

Oh, one thing I forgot to mention. The TrueSkill method works better when more skill and less luck is involved. I don’t know if regattas are more skill or luck based.

Regattas are intended to be based as much on skill as possible - and the idea of scheduling races where they must be split into flights like this is literally to reduce the 'luck of the draw'. Generally, first place overall will be awarded to the boat that has the highest mean position. If you split the fleet into two fixed groups according to skill, there will be a big difference in skill between the 1st place in the first group and 1st place in the second. As stockzahn says, this is sometimes done deliberately and the groups are then usually called "Gold Fleet", "Silver Fleet" etc. with prizes awarded for 1st place and runners up in each fleet.

I wasn't familiar with TrueSkill: it looks like an excellent way of running sailing competitions. However sailing is governed mainly by ancient rules (and mainly by ancient people) and I don't expect to see TrueSkill replacing Appendix A of the Racing Rules of Sailing any time soon!

[Edited for more details of sailing regattas]

 

[pbuk]

Given that there are only 6 boats, is it important that the races are organised in pairs so that each crew participates in exactly 1 flight in each pair? There may be a better solution if you remove this constraint.

 

[Dale]

For regatta round robins my first port of call is usually the http://www.sailing.org/27298.php.

Usually, to get an even mixing of something, some form of round robin is appropriate. So that sounds like a good start. Especially if it is something that has an authoritative source which is appropriate for a traditional competition.

 

[stockzahn]

What you need is someone with an interest both in combinatorics/non-linear optimization and sailing. That'll be someone like me then!

I haven't got an answer for you at the moment, but I'll give you a couple of pointers:

• For regatta round robins my first port of call is usually the http://www.sailing.org/27298.php.
• I don't think that goes far enough for this problem though, so a good start point is the 2015 paper Constructing Sailing Match Race Schedules: Round-Robin Pairing Lists, and if that doesn't help its references may.

I think the solution here is probably an heuristic based on selecting for the next pair of flights from the 462 possibilites the one that best balances the number of individual pairings. I might sketch something up if I have time.

Thanks for the hints and your effort, it's a good idea to have a look at the World Sailing standards, so thanks for the hints and the links. Of course, now that I have to solve the problem, I also would be interested in the math, or to be more precise, if there is a relatively easy solution or estimation to find a good balance. Nevertheless for practical reasons and the actual regatta, it for sure is advantageous to relate to the World Sailing system. So thanks again for your response.

 

[stockzahn]

Given that there are only 6 boats, is it important that the races are organised in pairs so that each crew participates in exactly 1 flight in each pair? There may be a better solution if you remove this constraint.

I'm not sure if I understand your statement correctly. Each fleet consists of two races at which all crews have to be distributed, that means every crew has to participate exactly one time at each fleet (in one of the two races). This is a stringent requirement. I'm not sure about the expressions "flight" and "pair" you are using. Are they the same as my "race" and "fleet" or do they mean something different?

Edit: Do you maybe refer to the match races, where only two boats compete against each other in a so-called flight? Then unfortunately that's not an option since we have six competing crews in in each race.

 

[stockzahn]

Usually, to get an even mixing of something, some form of round robin is appropriate. So that sounds like a good start. Especially if it is something that has an authoritative source which is appropriate for a traditional competition.

After a short look it seems that there are round-robin modes only for one-against-one competitions. Are there also modes containing more players in each match or is the one-against-one scheme typical for round-robin?

 

[pbuk]

I'm not sure if I understand your statement correctly. Each fleet consists of two races at which all crews have to be distributed, that means every crew has to participate exactly one time at each fleet (in one of the two races). This is a stringent requirement. I'm not sure about the expressions "flight" and "pair" you are using. Are they the same as my "race" and "fleet" or do they mean something different?

Edit: Do you maybe refer to the match races, where only two boats compete against each other in a so-called flight? Then unfortunately that's not an option since we have six competing crews in in each race.

My terminology: The regatta consists of 15 races. Each race has 2 flights. Each flight has 6 crews competing in 6 boats.

Your terminology: The regatta consists of 15 fleets. Each fleet has 2 races. Each race has 6 crews competing in 6 boats.

Although the terms fleet, flight, race, start, group etc. are to some extent interchangeable I don't think I have seen the term "fleet" used in the way you have used it, hence my redefinition to terms I have used before, sorry for the confusion this has introduced.

Sticking to your terminology, why is it a stringent requirement that each crew participates exactly once in each fleet? If instead of considering the regatta as 15 pairs of fleets you consider it as 30 separate fleets, it will be much easier to balance pairings.

I have had some time to look at coding this using the simple algorithm I suggested above, and with 15 fleets I also get a range of mixings between 5 (3 pairs of crews) and 9 (2 pairs of crews). This could perhaps be improved upon using a backtracking algorithm.

 

[stockzahn]

My terminology: The regatta consists of 15 races. Each race has 2 flights. Each flight has 6 crews competing in 6 boats.

Your terminology: The regatta consists of 15 fleets. Each fleet has 2 races. Each race has 6 crews competing in 6 boats.

Although the terms fleet, flight, race, start, group etc. are to some extent interchangeable I don't think I have seen the term "fleet" used in the way you have used it, hence my redefinition to terms I have used before, sorry for the confusion this has introduced.

Thanks for the clarification, then I will try to adapt to the official terminology.

Sticking to your terminology, why is it a stringent requirement that each crew participates exactly once in each fleet? If instead of considering the regatta as 15 pairs of fleets you consider it as 30 separate fleets, it will be much easier to balance pairings.

After 15 races (fleets) every crew should have participated at the same number of flights (races) - I think that is a reasonable requirement. And then the order of the flights (races) doesn't matter, I will end up with the same problem independent of the constraint that every crew shall take part at each race (fleet). The advantage though is that the regatta can be easily aborted after each race (fleet) if for example the wind diminishes.

I have had some time to look at coding this using the simple algorithm I suggested above, and with 15 fleets I also get a range of mixings between 5 (3 pairs of crews) and 9 (2 pairs of crews). This could perhaps be improved upon using a backtracking algorithm.

Thanks for your effort, it gives me confidence that you obtain similar results.

 

[pbuk]

After 15 races (flights) every crew should have participated at the same number of flights (races) - I think that is a reasonable requirement. And then the order of the flights (races) doesn't matter, I will end up with the same problem independent of the constraint that every crew shall take part at each race (fleet). The advantage though is that the regatta can be easily aborted after each race (fleet) if for example the wind diminishes.

Yes it is reasonable that after 30 flights everyone should have participated in 15 - but you have imposed the constraint that after every 2n flights everyone should have participated in n. Relaxing this would make it easier, although I appreciate it does make early termination easier.

Thanks for your effort, it gives me confidence that you obtain similar results.

Initially yes, but I have improved on this e.g.

Race 0 Flight 0 0 1 2 3 4 5 Flight 1 6 7 8 9 10 11
Race 1 Flight 0 0 2 3 9 10 11 Flight 1 1 4 5 6 7 8
Race 2 Flight 0 0 2 3 6 7 8 Flight 1 1 4 5 9 10 11
Race 3 Flight 0 0 1 3 4 8 10 Flight 1 2 5 6 7 9 11
Race 4 Flight 0 0 4 5 7 9 10 Flight 1 1 2 3 6 8 11
Race 5 Flight 0 0 2 4 6 10 11 Flight 1 1 3 5 7 8 9
Race 6 Flight 0 0 2 5 8 9 10 Flight 1 1 3 4 6 7 11
Race 7 Flight 0 0 1 7 8 9 11 Flight 1 2 3 4 5 6 10
Race 8 Flight 0 0 3 4 6 8 9 Flight 1 1 2 5 7 10 11
Race 9 Flight 0 0 3 5 7 10 11 Flight 1 1 2 4 6 8 9
Race 10 Flight 0 0 2 4 5 8 11 Flight 1 1 3 6 7 9 10
Race 11 Flight 0 0 1 5 6 9 11 Flight 1 2 3 4 7 8 10
Race 12 Flight 0 0 1 5 6 8 10 Flight 1 2 3 4 7 9 11
Race 13 Flight 0 0 1 2 6 7 10 Flight 1 3 4 5 8 9 11
Race 14 Flight 0 0 1 2 4 7 9 Flight 1 3 5 6 8 10 11

... with a max. of 8 and a min. of 6 pairings, and I think this can be improved further with backtracking but I have run out of time until next week. My code is in javascript and I will put it up on GitHub if I have time.

 

[stockzahn]

Yes it is reasonable that after 30 flights everyone should have participated in 15 - but you have imposed the constraint that after every 2n flights everyone should have participated in n. Relaxing this would make it easier, although I appreciate it does make early termination easier.

Initially yes, but I have improved on this e.g.

Race 0 Flight 0 0 1 2 3 4 5 Flight 1 6 7 8 9 10 11
Race 1 Flight 0 0 2 3 9 10 11 Flight 1 1 4 5 6 7 8
Race 2 Flight 0 0 2 3 6 7 8 Flight 1 1 4 5 9 10 11
Race 3 Flight 0 0 1 3 4 8 10 Flight 1 2 5 6 7 9 11
Race 4 Flight 0 0 4 5 7 9 10 Flight 1 1 2 3 6 8 11
Race 5 Flight 0 0 2 4 6 10 11 Flight 1 1 3 5 7 8 9
Race 6 Flight 0 0 2 5 8 9 10 Flight 1 1 3 4 6 7 11
Race 7 Flight 0 0 1 7 8 9 11 Flight 1 2 3 4 5 6 10
Race 8 Flight 0 0 3 4 6 8 9 Flight 1 1 2 5 7 10 11
Race 9 Flight 0 0 3 5 7 10 11 Flight 1 1 2 4 6 8 9
Race 10 Flight 0 0 2 4 5 8 11 Flight 1 1 3 6 7 9 10
Race 11 Flight 0 0 1 5 6 9 11 Flight 1 2 3 4 7 8 10
Race 12 Flight 0 0 1 5 6 8 10 Flight 1 2 3 4 7 9 11
Race 13 Flight 0 0 1 2 6 7 10 Flight 1 3 4 5 8 9 11
Race 14 Flight 0 0 1 2 4 7 9 Flight 1 3 5 6 8 10 11

... with a max. of 8 and a min. of 6 pairings, and I think this can be improved further with backtracking but I have run out of time until next week. My code is in javascript and I will put it up on GitHub if I have time.

This is a great result, thank you very much! In the evening I will compare your scheme with the one my code produces, maybe I see where I have to improve it.