Calculating the Smith set?
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
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.
More information about the Election-Methods