Calculating the Smith set?

[Bruce Anderson]

On Apr 16, 11:27pm, Steve Eppley wrote:
> Subject: Re: Calculating the Smith set?
> Mike, Bruce, and Rob have all pointed out that the candidate with
> fewest pairwise defeats (or was it most pairwise victories?) must be
> in the Smith set.

It's true either way.

> So here's a quick algorithm.  I think I'm just
> restating Rob's and Mike's algorithms in a format which, to me, looks
> straightforward to program:
> 
>    Find the candidate(s) with the fewest pairwise defeats.  (These
>    candidate(s) are guaranteed(?) to be in the Smith set.)  Create 
>    a list named Smith with just these candidate(s).
>  
>    for each candidate Ci in the (growing) Smith list
>       for each candidate Cj
>          if Ci did not pairwise-beat Cj
>             if Cj is not yet in the Smith list
>                append Cj to the Smith list
>             endif
>          endif
>       endfor
>    endfor
> 
> If this algorithm is correct, it should take little time to
> calculate.  It looks like its worst case is on the order of
> N-squared, where N is the number of candidates. 
>-- End of excerpt from Steve Eppley

It may not work--the line "append Cj to the Smith list" is too vague.  I think 
that the following would work, but is NOT efficient:

    Find the candidate(s) with the fewest pairwise defeats.  (These
    candidate(s) are guaranteed to be in the Smith set.)  Create 
    a list named Smith with just these candidate(s).
  
    #1     
    for each candidate Ci in the (new) Smith list
       for each candidate Cj
          if Ci did not pairwise-beat Cj
             if Cj is not yet in the Smith list
                append Cj to the Smith list & go back to #1
             endif
          endif
       endfor
    endfor
 
On Apr 16,  4:55am, Mike Ossipoff wrote:
> Subject: Smith procedure briefly stated
> I'd like to state, more briefly & clearly, the procedure that I suggested
> for determining the Smith set:
> 
> 1. Order the alternatives according to how many alternatives they're
> beaten by.
> 
> 2. The alternative beaten by fewest alternatives is a member of the Smith set
> (as are any several that tie for that distinction).
> 
> 3. Any alternative is a member of the Smith set if it beats or ties
> a member of the Smith set, or if it's beaten by no more alternatives
> than is a member of the Smith set.
> 
> 
> So admit alternatives to the Smith set according to these rules till
> there are no more that qualify.
> 
> ***
> 
> I don't know to what extent Bruce's procedure is like this one, and
> it isn't possible to comment on Bruce's procedure till it's translated
> from the original formulese. But I did notice that Bruce would order
> the alternatives according to how many they beat instead of how many
> they're beaten by. With "pairwise ties" a possibility, as is the case
> in small committee elections, that makes a difference.
-- End of excerpt from Mike Ossipoff

The step:  "Any alternative is a member of the Smith set if it beats or ties a 
member of the Smith set," is too vague--if it is not interpreted correctly, then 
the resulting algorithm could have the same problem that Steve's algorithm has.
The phrase:  "Any alternative is a member of the Smith set ... if it's beaten by 
no more alternatives than is a member of the Smith set" is, at best, a 
tautology.

Here's my proposal:

START
Let n be the number of candidates.
Let LIST be empty.
If n = 1, add the one candidate to LIST and go to #1.

Do for i from 0 to (n-2):
   If there are 1 or more candidates with exactly i pairwise losses, then:
      Add all candidates with exactly i pairwise losses to LIST.
      Let m be the current size of LIST.
      If the total number of pairwise wins by all of the current members of LIST 
         is greater than or equal to m(n-m), and the total number of pairwise 
         losses by all of the current members of LIST is less than or equal to 
         m(m-1)/2, go to #1.
   End if.
End do.

LIST = {all candidates}

#1
Smith set = LIST.
STOP

This algorithm is certainly not vague (assuming that n is a positive finite 
integer), and it seems to me that it would be quite efficient if it is correct. 
 But is it correct?  I can prove that parts of it "work", but not (for now) that 
the whole algorithm is valid.  What do you think?

Bruce