Proposed SD Algorithm Defective

[Norman Petry]

Here's a sketch of how I think my SD algorithm might be fixed, without
having to trace beat-paths:

1) Repeatedly eliminate any beat-nothing candidates (this would be E, then D
in my example).
2) Check for candidates who beat-something and are not beaten.  Declare
these candidates as winners, and quit.  If there aren't winners, then:
3) Break the weakest defeat(s).  Goto 1.

I'm going away for a few days, but I thought I'd post this quick summary of
the idea in case anyone on the list would like to check it over while I'm
away.


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 10:44 PM
Subject: Proposed SD Algorithm Defective


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