Clarifications re: SD Algorithm

[Norman Petry]

Mike,

You wrote:

>I hadn't thought of how it would be programmed, or written
>as a precise algorithm. Checking for cycles sounds like quite
>a programming task. Is it one of those things that becomes
>un-computable when the number of candidates becomes large,
>like the traveling salesman mileage-minimization problem when
>the number of cities becomes large?

It's actually not that bad.  For example, I've written an algorithm for the
Schulze method which recursively traces beat-paths.  Even with large numbers
of candidates, I think this algorithm should be able to find an answer in
milliseconds on an average PC (Schwartz set computation _is_ giving me a
headache though, I must admit).  Writing a similar algorithm for the
Sequential Dropping method might be even simpler (although I've not done
it).

The algorithm I did develop for SD (which as I mentioned elsewhere, is
defective) tried to avoid beat-path tracing.  Had it worked, the advantage
would not so much have been speed, as ease of verification.

I think that due to the very limited data requirements of most pairwise
methods, even the most sophisticated (such as Schulze) should be very
practical to implement on small computers.


Norm Petry

-----Original Message-----
From: Mike Ositoff <ntk at netcom.com>
To: election-methods-list at eskimo.com <election-methods-list at eskimo.com>
Cc: ntk at netcom.com <ntk at netcom.com>
Date: August 13, 1998 2:26 PM
Subject: Re: Clarifications re: SD Algorithm


>
>If you sequentially drop weakest defeats, without regard to whether
>they conflict with stronger ones, till something is unbeaten
>that beats something else, then, in a public election where there
>are no pairwise ties, and where therefore anything unbeaten beats
>something else, isn't that going to give the same result as
>plain Condorcet(EM)?
>
>I hadn't thought of how it would be programmed, or written
>as a precise algorithm. Checking for cycles sounds like quite
>a programming task. Is it one of those things that becomes
>un-computable when the number of candidates becomes large,
>like the traveling salesman mileage-minimization problem when
>the number of cities becomes large?
>
>Mike
>