Swiss teams math question?
#1
Posted 2009-February-21, 11:45
The question I'm trying to answer is something like this. Suppose we have a bunch of teams. We are trying to select the top X teams (probably X=4 or 8) to advance to a knockout phase. We're going to play a bunch of rounds scored on the VP scale, at the end of which we select the top X teams in the standings -- we don't want to have some complicated formula determining the top teams because people like to know where they stand.
What we want to know is, what is the best way to determine the pairings in order to maximize the chances that the "best" X teams end up in the top X positions? Assume that we are not going to play enough rounds to run a full round-robin. Some of the options seem to be:
(1) Swiss, with or without repeated pairings.
(2) Random matches, with or without repeated pairings.
(3) Divide into groups in some random way, run a full round-robin in each group.
(4) Some scheme where we periodically eliminate the bottom half of the field.
(5) Some scheme where we try to equalize "strength of opposition" on the fly.
(6) Some kind of double-elimination scheme.
(7) Some combination of the above.
Maybe there are more options I haven't thought of too.
a.k.a. Appeal Without Merit
#2
Posted 2009-February-21, 11:53
Divide into X# of 8 team brackets and run a round robin, then cut the bottom half of each bracket, and rematch each bracket... The only problem is that this could be very time consuming depending on your # of teams... I'd suggest for say 32 teams:
4 8 team brackets, cutting the bottom half
2 8 team brackets, rearranged for as few playbacks as possible; cutting the bottom half
1 8 team bracket, cutting the bottom half again
KO phase for 2 rounds
You may need to increase the # of teams in one bracket in the beginning, and modify your original cuts... But this is a pretty fair way to run it imo.
#3
Posted 2009-February-21, 11:53
#4
Posted 2009-February-21, 12:14
#5
Posted 2009-February-21, 12:37
#6
Posted 2009-February-21, 12:47
Perhaps it is only a psychological difference. But, if I was qualifying 8 and was doing a simulation to determine how many matches had to be played in order to be x% confident that the best 8 teams qualified, I would instead see how many matches had to be played in order to be x% confident that the best 6 teams qualified. If the participants knew this, I think there would be less grumbling about the randomness of the last couple of qualifiers.
#7
Posted 2009-February-21, 12:50
hrothgar, on Feb 21 2009, 01:37 PM, said:
Yeah I'm aware of this thread. But it seemed to be more about ways to modify the scoring system so that the overall ranks would reflect the caliber of opposition (after the fact) rather than modifying the pairing method for matches. This was interesting in principle, but I don't think it's realistic for most events, where people want the standings based on victory points and not on some complex mathematical formula.
a.k.a. Appeal Without Merit
#8
Posted 2009-February-21, 13:47
awm, on Feb 21 2009, 09:50 PM, said:
hrothgar, on Feb 21 2009, 01:37 PM, said:
Yeah I'm aware of this thread. But it seemed to be more about ways to modify the scoring system so that the overall ranks would reflect the caliber of opposition (after the fact) rather than modifying the pairing method for matches. This was interesting in principle, but I don't think it's realistic for most events, where people want the standings based on victory points and not on some complex mathematical formula.
Even if you don't want to use the scoring methods recommended in that thread, the basic methodogy would seem to be valuable.
Moreover, it would seem relatively easy to modify Gerben's code to test different pairing methods rather than different round lengths.
One important point:
You're looking at a scheme that will qualify X teams. One of your design metrics is that you want to maximize the chance that the the X teams that qualify are the X best teams. I'm not sure whether this is necessarily the right goal:
As a practical example: You might want to qualify 8 teams, but maximize the chance that the top 4 teams are located in that mix...
#9
Posted 2009-February-21, 14:20
And my opinion about this problem is (1) without repetitions. Two things though, the amount of teams and rounds has to be set and the first pairing is VERY important, rank the teams according to their points (according to the rank of the country, world, whatever) and have the best team play against the worse, the second best against the second worst and so on. You should have the best at the top after some number of rounds.
wyman, on 2012-May-04, 09:48, said:
rbforster, on 2012-May-20, 21:04, said:
My YouTube Channel
#10
Posted 2009-February-21, 14:27
The way they do it (or at least did it until recently):
They have 12 teams and put them in 2 groups of 6 (A and B ). In these groups they play a round robin (5 matches per team). The best 3(?) advance. A new group of six is formed (A1, A2, A3, B1, B2 and B3).
The A teams have already played each other and the B teams have already played each other. The results of these earlier matches are counted in this round robin. Thus, the A teams only have to play the B-teams (an additional 3 matches). After that, the final is played by the highest two teams (or maybe there is a semifinal 1-4 and 2-3 first, but you get the idea).
The way this might work for bridge with 32 teams:
Make 4 groups of 8: A-D play a round robin (7 matches)
The top 4 teams advance: A1-A4 and B1-B4 get into group E, C1-4 and D1-4 get into group F. In group E, A teams only play B teams. Similarly, in group F, C teams only play D teams. (4 additional matches). Again, the first four advance.
Again, you need only 4 additional matches to complete the round robin for the best 8 teams. This means that you have a winner after 15 matches.
Of course, it is important to play all matches over the same number of boards. I could imagine that you would make the matches longer during the tournament. In that case, I think you will have to let the A teams meet each other again for some additional boards.
As an example, I could think that you play 7 8-board matches on day 1 (56 boards for the first round robin). Then, on day 2 you start by letting the qualified A teams play each other again in 3 8-board matches. Now, these teams have played 16-board matches against each other. Then, you let them play the B teams in 4 16-board matches (88 boards for the second round robin).
For the last round robin you could go to 32 board matches in a similar way. Or you could stay with 16 board matches and have cross finals amongst the top 4 teams (with carry over).
Rik
The most exciting phrase to hear in science, the one that heralds the new discoveries, is not “Eureka!” (I found it!), but “That’s funny…” – Isaac Asimov
The only reason God did not put "Thou shalt mind thine own business" in the Ten Commandments was that He thought that it was too obvious to need stating. - Kenberg
#11
Posted 2009-February-21, 17:27
1-2, 3-4, 5-6, 7-8
1-8, 2-3, 4-5, 6-7
1-6, 2-5, 3-8, 4-7
1-4, 2-7, 3-6, 5-8
#12
Posted 2009-February-21, 18:02
Another question: As phrased, you will be successful if you pick out the best k and unsuccessful if you do not. This approach means that ending with the first, second, third and fifth best teams is just as bad as ending withe the ninth, tenth, eleventh and twelfth best teams. An alternative would be to try for a method that gives a very high chance that the four selected teams would be in the top six in actual merit. Going for this goal might require accepting a somewhat lower chance of getting the exact four best. If that makes sense.
It's an interesting problem with many ways to refine it. Since it would appear to have many applications beyond bridge I assume it has been studied, but I know nothing about it. I may bring it up with some mathematical friends.
#13
Posted 2009-February-21, 18:18
kenberg, on Feb 22 2009, 03:02 AM, said:
Another question: As phrased, you will be successful if you pick out the best k and unsuccessful if you do not. This approach means that ending with the first, second, third and fifth best teams is just as bad as ending withe the ninth, tenth, eleventh and twelfth best teams. An alternative would be to try for a method that gives a very high chance that the four selected teams would be in the top six in actual merit. Going for this goal might require accepting a somewhat lower chance of getting the exact four best. If that makes sense.
It's an interesting problem with many ways to refine it. Since it would appear to have many applications beyond bridge I assume it has been studied, but I know nothing about it. I may bring it up with some mathematical friends.
Might want to look at Spearman's rho
#14
Posted 2009-February-21, 18:32
#15
Posted 2009-February-21, 19:06
helene_t, on Feb 21 2009, 06:27 PM, said:
1-2, 3-4, 5-6, 7-8
1-8, 2-3, 4-5, 6-7
1-6, 2-5, 3-8, 4-7
1-4, 2-7, 3-6, 5-8
Isn't this sort of like getting one overall winner from a Mitchell?
#16
Posted 2009-February-22, 00:54
Quote
You'd have to be careful about this, or you could end up in the Bridge World dreaded sportsman dumping. Where you would rather lose your last match by a close score than win it because you don't want a bubble team with a big carry over to advance.
Quote
A simple scoring function would be to just sum the ranks of the 4 teams that made it. Ideal would be a total of 10 (1+2+3+4), but your 1,2,3,5 would get 11 while 7,8,10,12 would score 37. If, rather than rank, you have some empirical measure of team strength you could do the sum of the strength of the top 4 teams (by real team strength) minus the sum of the strength of the teams that finished in the top 4 spots. For a simulation I'd think this would be the best measure, as this is the amount you are trying to minimize.
I think the fairest way is going to be the way that awm doesn't like from the OP, which is to calculate the results for the unplayed matches like the zermlo incomplete tournaments algorithm does.
Overall for structure you are trying to balance playing as even a strength of schedule with making sure that the results are meaningful (by eliminating the weak teams). If you have many more teams then the top k spots you are qualifying then I think the ideal is to play as many short matches as possible, random drawing - not swiss, and then make a pretty big cut. I'm not sure if it is best to cut to 4*k and then do 2 rounds of KO to get the top k teams (a different issue is if you also want to rank the k teams or just qualify the k teams - effects if you need 2 more rounds of KO), or maybe to 3*k and then do 2 rounds where the first is a 3 way with 2 survivors. It depends on the size of the field and how close each team is in skill, but intuitively it feels like the top k teams should be able to finish no worse than 3*k place in a normal "swiss" when they aren't being punished with a harder strength of schedule the way a swiss does.
#17
Posted 2009-February-22, 04:19
Let 1..n represent the n-th best team in the field, the team with the lover number wins.
The worst thing that can happen is to match up teams:
First round: 1-2, 3-4, 5-6, 7-8, ... (n-1) - n
2nd round: 1-3, 2-4, 5-7, 6-8, .....(n-2) - n
At the end of round 2 the 4-th and the 8-th best teams are among the double losers.
If you continue the swiss tourney they can hardly recover and if they can, the teams overtaken in the last round will feel that hey have been treated unfair, because they had stronger opponents in the last rounds.
What I would suggest is to play 2 seating round with randomly assigned opponents, prior to the swiss tourney. Forget about VP's it's just win or lose. The result of these 2 rounds is only used for seating, all points are reset to 0. Seat the 2 time winner against randomly assigned 2 time loser, without repeating a seating match. Randomly assign the big group who won and lost one match. Don't assign matches between teams that played each other in the seating process before half of the swiss rounds are over.
#18
Posted 2009-February-22, 05:17
orlam, on Feb 22 2009, 01:32 AM, said:
My idea is similar: dividing RANDOMLY into SMALL groups is one of the worst methods.
One way of getting the random factor out is to give every team a value according to the players' rankings in competition (division + position). When you divide in groups, you make sure that you don't get one group with all top teams.