# Calculating the Smith set?

Rob Lanphier robla at eskimo.com
Mon Apr 22 01:11:35 PDT 1996

```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

```