Calculating the Smith set?
Steve Eppley
seppley at alumni.caltech.edu
Tue Apr 16 23:27:40 PDT 1996
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. 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.
--Steve
More information about the Election-Methods
mailing list