Clarifications re: SD Algorithm
Norman Petry
npetry at sk.sympatico.ca
Thu Aug 13 11:41:05 PDT 1998
One thing I forgot to point out about the algorithm I just posted for
Sequential Dropping (see Re: Goldfish (single-winner method)) is that it
applies the same logic to both majority and _minority_ propositions (such as
D>C 16:32, in the example) as it works its way to a solution. This should
cause no problems, and simplifies the design.
If you'd like an algorithm that considers only majority propositions
(beat-paths), just pre-scan through P and replace all the minority vote
totals with "*" before exercising the main routine. This would probably be
faster, but you'd need to write more code.
***
While I'm clarifying, I should also say that the procedure I posted is
slightly different from the way you'd carry out Sequential Dropping by hand.
According to Mike's rules:
"Starting with the weakest defeat, sequentially drop the defeats that
conflict (by forming a cycle) with larger defeats, till there's an
undefeated alternative."
we should preserve weak defeats that don't cause cycles; this guarantees
that candidates not in the (evolving) Smith set never become undefeated and
cannot possibly win. I found it to be simpler to blindly eliminate the
weakest defeats successively (even if they might be non-cyclic), and check
for the problem this creates _after_ we discover a potential winner. My SD
algorithm is really equivalent to:
"Starting with the weakest defeat, sequentially drop the weakest. The first
candidate to become undefeated who still defeats another candidate is
the winner."
I think these definitions are equivalent, but I'm going to double-check (If
they're not, my algorithm won't always work, so please let me know if you
discover problems).
Norm Petry
More information about the Election-Methods
mailing list