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