Kristofer, (and others too)<div><br></div><div>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?</div>
<div><br></div><div>Does the Schulze method extend naturally to incomplete data?</div><div><br></div><div>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?</div>
<div><br></div><div>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.)</div>
<div><br></div><div>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.</div>
<div><br></div><div>One other important constraint is that all cars should have about the same amount of races, which rules out an "insertion-sort" type algorithm.</div><div><br></div><div>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)</div>
<div><br></div><div>First round: Just pair them up randomly and race them. There will be 16 winners and 16 losers.</div><div>Second round: Race the 16 winners against each other (randomly) and the 16 losers against each other (randomly).</div>
<div>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).</div><div>etc.</div><div><br></div>
<div>(Instead of pure randomness, I would avoid racing cars that had faced each other before if possible.)<br></div><div><br></div><div>After five rounds, you have one undefeated car, 5 cars with four wins, 10 cars with three wins, 10 cars with two wins, 5 cars with one win, and one car with zero wins.</div>
<div><br></div><div>In each round, you're basically dividing the cars into tiers based on their win-loss record and then racing cars in the same tier against each other randomly. And, for at least the first n rounds, there will always be an even number of cars in each tier. This is equivalent to a pure binary tournament that has a losers' bracket as well as a two-loss bracket, a three-loss bracket, etc. .</div>
<div><br></div><div>The question is what to do if you want to run more than n rounds, or if the number of cars is not exactly a power of two. I think the idea of dividing them into tiers (or brackets) and racing them against other cars in the same tier is still good, but using just their win-loss record is not enough. Lots of tiers will have an odd number of cars, so we need to know which are the best and worst cars in each tier and have a few inter-tier races.</div>
<div><br></div><div>So we can think of it as needing to come up with a secondary sort criterion to use inside the win-loss tiers.</div><div><br></div><div>Or we can generalize and say that after each round we just come up with a full societal ranking and then race the first against the second, the third against the fourth, the fifth against the sixth, etc. So I'm back to needing to know the best way to come up with a societal ranking from incomplete pairwise data.</div>
<div><br></div><div>Thoughts?</div><div><br></div><div>~ Andy</div>