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