Calculating the Smith set?

Bruce Anderson landerso at ida.org
Mon Apr 15 22:35:41 PDT 1996


I just thought of the following algorithm.  (Others may have known of it for a 
long time, I don't know.)

Suppose there are n candidates.  Label these candidates from X1 through Xn in 
any manner provided that, if 1 <= i < j <= n, then Xi has at least as many 
pairwise wins as Xj.  (Pairwise ties are allowed to occur, but Xi must have as 
many or more wins, not wins plus ties, than Xj here.)  Then, clearly, X1 is the 
unique Smith winner if and only if X1 has (n-1) pairwise wins (and 0 pairwise 
losses).

Now, for any integer k such that 1 <= k <= n, let Sk = {X1, X2, ..., Xk}.  Then, 
for any integer m such that 2 <= m <= n, Sm is the unique set of Smith winners 
if and only if:  1) none of S1, S2, ..., S(m-1) is the unique set of Smith 
winners,  2) the total number of pairwise wins by all of the members of Sm is 
greater than or equal to m(n-m), and  3) the total number of pairwise losses by 
all of the members of Sm is less than or equal to m(m-1)/2.

As I said, I just now thought of this, and I do NOT have a proof that it's true. 
 But if it is true, it gives a relatively efficient algorithm for calculating 
the set of Smith winners.

Bruce



More information about the Election-Methods mailing list