Proposed SD Algorithm Defective

[Blake Cretney]

--

On Wed, 26 Aug 1998 10:50:34   David Catchpole wrote:
>If this is a Condorcet completion method, I might remind people that where
>a paradox of voting occurs, exclusion of candidates who beat no-one cannot
>break a paradoxical schedule of preferences. If the Simpson Set is the
>set of candidates who do beat someone else, then any resolution of the
>paradox leading from a candidate's exclusion must come from that set
>
>On Tue, 25 Aug 1998, Norman Petry wrote:
>
>> Blake,
>> 
>> You wrote:
>> 
>> >I think the best bet for an SD algorithm is
>> >Repeat
>> >    Eliminate everything not in the Simpson set
>> >    Break lowest defeat
>> >Until only one candidate is left
>> 
>> I'm not familiar with the Simpson Set.  Could you please post a definition?
>> 
>> TIA,
>> 
>> Norm Petry
>> 
>> 
That must have been one of my more confusing postings.  First I called the Smith set the Simpson set, then I didn't define what I meant by iteratively removing non Smith set members.  Anyway, here's a better try at it.  I'll define a new set called the Smith+ set.

The Smith+ set is the smallest non-empty set of candidates such that no candidate in the set has a loss or tie against any candidate outside the set, unless the loss or tie has been broken, or the candidate has been eliminated.

The "broken" concept is the one from SD.  Losses are declared to be broken, and candidates eliminated following this procedure.  Of course, they all start unbroken and uneliminated.

Repeat
        Eliminate all candidates not in the Smith+ set
        Break the smallest pair-wise victory/defeat

This all started because I wanted to find an efficient way to do SD.  SD says that a link should be broken only if it is part of a cycle.  I assumed that a link is part of a cycle, if and only if it is not part of a one-way beat path.  Therefore to make sure that only cycles were removed, I recommended using the Smith set to effectively lock all one-way beat paths by eliminating the defeated.

However, some links that are part of one-way beat paths, and therefore protected by my system, are also part of cycles and therefore breakable under SD.  My system therefore needs a different name, so I'm calling it "beat-path sequential dropping" or BPSD.

Beat Paths and BPSD

If there is a beat path from A to B, but none from B to A, then B will be eliminated by the first step of reducing to the Smith+ set.

If there is a beat path from A to B, and a path from B to A, and B to A contains a lesser victory than any in the A to B path, this link will be broken before any link in A to B, because links are broken sequentially.  If all paths from B to A contain a lesser victory than any in the A to B path, they will all be broken for the same reason.  This will result in a one way path and the elimination of B by the Smith+ step.  Of course, it is possible that both A and B may be eliminated by a different one-way beat path before this occurs.  The point is that B cannot win.

So, a candidate can only win over all if it has a greater beat path against every other candidate, or there is no such candidate.



-----== Sent via Deja News, The Discussion Network ==-----
http://www.dejanews.com/  Easy access to 50,000+ discussion forums