Proposed SD Algorithm Defective

[Norman Petry]

With a couple of slight changes, the algorithm idea I posted a few days ago
is _close_ to being an accurate implementation of SD.  Here's how the steps
should be listed:

1) Check for any unbeaten candidates.  If 1 or more, then quit.
2) Repeatedly eliminate beat-nothing candidates (E, then D in example).
3) Break the weakest defeat(s).  Goto  step 1.

The algorithm I posted earlier was similar.  However, I realised it's
essential when using this approach to check for unbeaten candidates first.
This ensures that a Condorcet winner at the head of a chain of defeats is
not eliminated before it is found to be a winner.  Also, this version is
improved, in that it isn't necessary to check if candidates beat-something
when testing for winners.

This algorithm outline is easily implemented in a manner similar to that
shown for my earlier, defective version of SD.  Short of tracing beat-paths,
it's the closest I've been able to get to SD.  Unfortunately, it's still
just a (very close) approximation.  It will produce a different result from
SD in situations such as the following:

A>B 10
B>C 7
C>A 11

D>E 8
E>F 9
F>D 6

B>D 5

{D,E,F} > {A,B,C} 1

In this example, Mike's version of SD will first eliminate the strength 1
beat-paths, then break F>D.  This will leave one remaining cycle, which is
broken at B>C.  This leaves C at the head of the chain, so C wins.

Using my algorithm, we first determine that there are no unbeaten
candidates, then eliminate strength 1 beats.  Since all remaining candidates
still beat something, there are no eliminations, and B>D is broken next,
since it's the weakest defeat.  This leaves 2 small, 3-candidate cycles.
F>D is the weakest defeat, so it's broken.  Since D is now an unbeaten
candidate, it wins.

I think the situation described above is likely a very rare occurrence, so
this method might be a useful approximation.  In fact, this example is
similar to one posted by Mike earlier that demonstrated lack of complete
clone independence in SD.  In those rare situations, SD doesn't produce
particularly good results anyway (compared to Schulze), so this
non-recursive algorithm might be just as good in practice.

In any case, I've only been able to obtain a 100% accurate implementation of
SD by using a (recursive) beat-path tracing algorithm.  It's not long or
difficult either, but would inevitably be slower than this version in cases
where there are a large number of candidates.


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 14, 1998 9:10 AM
Subject: Re: Proposed SD Algorithm Defective


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