# Calculating the Smith set?

Bruce Anderson landerso at ida.org
Thu Apr 18 19:43:56 PDT 1996

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

```