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

[Kristofer Munsterhjelm]

On 03/19/2012 02:39 PM, Peter Gustafsson wrote:
> 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.

Perhaps it is caused by Hotmail sending your mail as HTML? In HTML, 
plain line breaks don't count, just like more than one space in a row 
doesn't count.

I'm not sure how you would go about setting Hotmail to use plain text 
instead of HTML, as I have not used Hotmail myself. You could, if you 
don't find it too much trouble, use a dedicated mail program and connect 
it to Hotmail's POP3 server. I use Thunderbird, myself. As an additional 
advantage, the dedicated mail programs usually support EM's quotation 
style (with greater-than symbols and your own response immediately after 
the relevant quoted text, instead of all at top or all at bottom) better.

> 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.

 From reading about the Swiss system on Wikipedia, it seems that it 
gives a clear idea of who the winners and losers are, but not so much 
the middle. Is that true of your suggestion, too?

That might be an interesting question to make more general, actually. If 
we have transitivity (no rock-paper-scissors setting), then how many 
matchups do we need to get a social ordering? But we already know that. 
It's O(n log n) to find the ranking and O(n) to find the winner, because 
the problems are equivalent to sorting and selecting from an unordered 
list, respectively.

But with noise or intransitivity, it's harder to tell. I'm not sure how 
to formalize the problem of selection/ranking under noisy conditions. If 
one can't decide which matchups will be done, the best approach is 
probably something like Kemeny. If one /can/, on the other hand...