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