To all readers: When I have been posting, I see my own posts as one very long
line, with no line breaks despite the fact that I have used them when I
composed the message. If it looks like that to you also, please advise me of
that unfortunate fact and, is possible, tell me how I shall format my responses
so that they look good on this board. Strangely enough, I have not had that
problem on any other board that I post on. From: [email protected]
Date: Sat, 17 Mar 2012 11:16:51 -0700
To: [email protected]
Subject: [EM] Societal ranking from incomplete pairwise information.
(Pinewood derby.)
Kristofer, (and others too)
If I recall, you were recently experimenting with how to best determine a
winner (or was it a full ranking) from incomplete pairwise information. What
are the methods that you (or others) consider best for that? It seems like
Kemeny would be a good fit (if it weren't computationally prohibitive): for
each pairwise contest you have data on, you just add one point to each possible
societal ranking which agrees with that pairwise contest. If your pairwise
information has a notion of defeat strength, then you can sum the defeat
strengths to get a Borda-like method. Otherwise you can count the pairwise
defeats and have a Copeland-like method. But for those last two each candidate
should have about the same number of contests, right?
Does the Schulze method extend naturally to incomplete data?
In your experimentation, were you the one who decided which pairwise contests
to run or was it decided by some other actor and you just had to live with
whatever data was generated?
A couple weeks ago, I found myself keeping score for a pinewood derby, where
8-11 year old boys race wooden cars down a track. When we thought there were
only 20 entrants, we were going to try to run the entire pairwise matrix (190
races). When 28 boys showed up, that became impossible. I quickly drew up a
racing schedule. Each boy got a number and ended up racing against the next
five and the previous five cars (mod 28). (Then we did a quick tournament
afterwards.)
It occurred to me that it would be better to use the outcomes of the early
races to decide who races against each other in the later races. (Let A>B
signify that A has raced and won against B.) If A>B, A>C, B>D, and C>D, then
there is really no point racing A against D. You really want to use the early
race outcomes to determine which cars are comparable and race those cars
against each other. This increases the information content of each outcome.
It also contributes to the enjoyment by racing cars of the same caliber and
getting every boy a win if possible. I've been thinking about good methods for
attacking this.
One other important constraint is that all cars should have about the same
amount of races, which rules out an "insertion-sort" type algorithm.
If the number of cars is 2^n, then I think the first n rounds are pretty
obvious. For 32 cars, for example: (Assuming no ties)
First round: Just pair them up randomly and race them. There will be 16
winners and 16 losers.Second round: Race the 16 winners against each other
(randomly) and the 16 losers against each other (randomly).
Third round: Race the 8 undefeated cars against each other (randomly), the 8
winless cars against each other (randomly), and the 16 one-and-one cars against
each other (randomly).etc.What you are describing is quite similar to the
Monrad system used in chess tournaments, with the simplification that you do
not have to worry about black or white. However, Monrad works partly because
chess players generally only play one game per day in most competitions, so the
organizers have ample time to calculate the matchups between days. However, in
your competition, that is not the case. You need an algorithm that is fast, and
transparent to the competitors - and their parents. Here is one that should
fit the bill:1. List the competitor names, completely at random.2. Put all
names into a direct elimination bracket of 32. With 28 competitors, there will
be 4 that have a bye to the next round.3. Run the 12 races in the 1st round.
The losers, and the 4 who had byes, are demoted to the round of 16. If a race
concludes with the competitor who is listed lower in the list of stage#1
winning, then the two competitors in that race switch places. If the winner is
the one who is listed higher, they keep their places. In no case should the
competitors not taking part of a race have their listing affected by that
race.4. Run the round of 16, demoting the losers to the round of 8.5. Repeat
stage 4 until there is an ultimate loser. He takes place #28 in the total
tally, and does not compete anymore. His name is taken out of the list in
stage#1.6. Construct a new DE bracket. All competitors who were placed in
odd-numbered placements of the first DE bracket retain their places. Those that
originally were placed in even-numbered places, however, are rotated one step.
Thus, if the 1st round of the 1st DE bracket featured the matchups A-B, C-D,
E-F, .... Y-Z, the 1st round of the 2nd DE bracket will be: A-Z, C-B, E-D,....
Y-X.7. The 1st DE round in this 2nd DE bracket will feature many new matchups.
The losers, those that have no opponent, and the one that is pitted against
#28 are demoted to the DE round-16. The list is updated whenever there is an
upset, as described in stage#3.8. Repeat stages #4-5. If the new bracket
features matchups that already have been competed, the result of the previous
race is recycled, and the race is not redone. This saves time. There will be
many instances of that unless there is a lot of noise in the competitor
performances. Continue until there is an ultimate loser who is placed in the
#27 spot.9. Repeat stages 6-8, with new rotated brackets in the 1st round, and
many recurring matchups in the later rounds. Update the list whenever
necessary. Once there has been 16 brackets, the rotation will have gone full
circle, and there will be many repeat matchups in the 1st DE round in the
subsequent DE brackets. This speeds up the process. Continue until there are
only 4 contestants left, or until there is only time for one bracket.10. Put
all contestants that have survived stages #1-9 into a forward DE bracket. In
this bracket, the surviving contestants are seeded according to the position in
the list, which by now has become more ordered.11. The winners of the 1st DE
round of the DE bracket established in stage #10 are promoted to the 2nd round,
and so on until an ultimate winner is found. The other contestants are ranked
according firstly after in which DE round the lost, and secondly after their
position in the list prior to stage #10. So there! No calculations necessary,
and a run time not larger (in all likelyhood, considerably less) than a full
round robin. Andy Jennings: (Instead of pure randomness, I would avoid racing
cars that had faced each other before if possible.)That is a very good design
criteria when coming up with a competition formula.
----
Election-Methods mailing list - see http://electorama.com/em for list info
