Evan Martin (evan) wrote in evan_tech,
Evan Martin

"Cloneproof Schwartzian Sequential Dropping"

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

  • blog moved

    As described elsewhere, I've quit LiveJournal. If you're interested in my continuing posts, you should look at one of these (each contains feed…

  • dremel

    They published a paper on Dremel, my favorite previously-unpublished tool from the Google toolchest. Greg Linden discusses it: "[...] it is capable…

  • treemaps

    I finally wrote up my recent adventures in treemapping, complete with nifty clickable visualizations.

  • Post a new comment


    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.