[EM] Societal ranking from incomplete pairwise information. (Pinewood derby.)
km_elmet at lavabit.com
Wed Mar 21 01:02:06 PDT 2012
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
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
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
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...
More information about the Election-Methods