Proposed SD Algorithm Defective

[Norman Petry]

I've thought some more about the algorithm I posted, and unfortunately,
although it _usually_ will produce the same result as SD, it won't always.
The problem relates directly to my redefinition of SD.  As I mentioned, my
algorithm implements (correctly, I think) the following procedure:

>"Starting with the weakest defeat, sequentially drop the weakest.  The
first
>candidate to become undefeated who still defeats another candidate is
>the winner."

This definition will _not_ produce the same winner as SD in cases such as
the following:

A>B 60:40
B>C 70:30
C>A 80:20
C>D 53:47
D>E 57:43

Assuming {A..E} are all members of the Smith set, this means that there must
also be ties (50:50) between {A,B} and {D,E} and between C and E.

Using Mike's (true) definition of Sequential Dropping, we would ignore the
weak defeats C>D, and D>E, since these are non-cyclic.  The one main cycle
A>B>C>A would be broken at A>B.  B becomes undefeated and wins.

Using my definition, we begin by eliminating all the minority votes-against
(20,30,40,43,47), then the ties (50).  Now the lowest votes-against is the
defeat C>D = 53, so we break that.  Now candidate D is undefeated, and still
has a defeat against E, so D wins.  Note that if the C>D and D>E defeats had
gotten weaker, rather than stronger as we move along this non-cyclic chain,
i.e.:

C>D 57:43
D>E 53:47

there would have been no problem, since candidates E and D would have been
successively eliminated rather than winning (since they would beat nothing)
and B would win.

Therefore, the algorithm in its present form is unusable.  While it will
almost always produce the same result as SD if the initial set of candidates
are limited to Smith (which was how I first tested it), it will fail much
more frequently if applied to all candidates, since these sets are much more
likely to contain the long, non-cyclic chains of defeats which can cause my
re-definition of SD to fail.

It looks as though I spoke to soon when I said that SD would be easily
implemented.

***

How to fix it?

The key problem with the algorithm is the blind elimination of _all_ weakest
defeats.  While the double-check on potential winners is fine for excluding
"free-floating" candidates (i.e.: those who beat nothing and aren't beaten),
it doesn't work on longer chains.  Therefore the obvious solution is to
check first before eliminating a weak defeat.  Hopefully, this can be done
in such a way that it's not necessary to trace the beat-paths, which would
greatly increase the complexity of the algorithm.

I'll see if I can adapt the algorithm to get around this problem, and will
post a correction if I can get it to work.


Norm Petry


-----Original Message-----
From: Norman Petry <npetry at sk.sympatico.ca>
To: election-methods-list at eskimo.com <election-methods-list at eskimo.com>
Date: August 13, 1998 12:45 PM
Subject: Clarifications re: SD Algorithm


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