05:58 pm, 21 Sep 03

### "Cloneproof Schwartzian Sequential Dropping"

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

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

ex_snej373Hmm, I think this election could use some Cloneproof Swartz[enegger]ian Sequential Dropping...

evann^5: 44840mil.

Ouch.

really hope we never have an election where ... the difference ... matters...I think I (as well as D) would stand by this statement. ;)