Calculating the Smith set?

[Rob Lanphier]

On Mon, 15 Apr 1996, Bruce Anderson wrote:
> 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.

I think you are on to something here.  Actually, there is a really simple
provable property that can be used to prove all sorts of wacky methods:

   If the Smith set is comprised of n members, where n is a non-zero
   integer, all members of the Smith set will have n-1 or fewer
   combined defeats and ties.  All those outside of the Smith set will
   have at least n defeats.

Rob Lanphier
robla at eskimo.com
http://www.eskimo.com/~robla