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
More information about the Election-Methods
mailing list