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
More information about the Election-Methods
mailing list