[EM] Societal ranking from incomplete pairwise information. (Pinewood derby.)

[Peter Gustafsson]

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: elections at jenningsstory.com
Date: Sat, 17 Mar 2012 11:16:51 -0700
To: election-methods at electorama.com
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.
 		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20120319/0209c53e/attachment-0003.htm>