evan_tech

Previous Entry Share Next Entry
Dear Martin,

you wrote:
> Condorcet voting lets you rank the options. I imagine the
> poll code could share the option-reording javascript from
> picpix (if Brad would agree to relicense it as GPL to work
> on LJ, which I can’t see why not). I’m really uncomfortable
> using Perl, especially in knowing when to use references and
> when not to. (You can laugh at my code here. Feedback would
> be welcome. I’m especially concerned about the potential O(n^4)
> algorithm for the, uh, “cloneproof Schwartz Sequential Dropping”
> / “Beatpath Winner”.)

Actually, there is an O(n^3) algorithm.

I have attached the paper “A New Monotonic and Clone-Independent
Single-Winner Election Method.” This paper has been accepted for
publication in “Voting Matters.”

Markus Schulze
His paper is apparently on the method known elsewhere as Beatpath Winner or Cloneproof Schwartzian Sequential Dropping, which is what I tried to implement for LiveJournal. But, as the introduction observes:
...most implementations I have seen were inefficient because the programmers have not understood the Floyd algorithm so that the implementations had a runtime of O(N^5) although the winners of this method can be calculated in a runtime of O(N^3), where N is the number of candidates.
But taking a step back, I really hope we never have an election where N is large enough that the difference between N^3 and N^5 matters... :)