Calculating the Smith set?

[Mike Ossipoff]

One thing for sure is that, as you said, determining the Smith set won't
be any problem for a computer--only for the programmers will there be any
work.

I have to admit that I haven't yet written a program to determine the
Smith set. But though it might not be so easy to write, what's for sure
is that it will be very quick & easy for the computer to do.

It's just that I haven't taken on the project of finding the most
efficient way for a computer program to determine the Smith set--or
_any_ efficient way for it to do it.

It seems to me that there's a shortcut, in public elections, where there
are no pairwise ties: The members of the Smith set beat more alternatives
than non-members do. Maybe, since the members of the Smith set beat
everything outside the set, we could also say that, in any election,
even one with pairwise ties, the members of the Smith set are beaten
by fewer alternatives than anything outside the set. You can see that
I haven't dealt with this problem before now. So we could rate the
alternatives according to how many alternatives beat them, and then
find if there's anything not beaten by the highest-scoring alternative,
and if there's anything not beaten by that...etc., to find new Smith
set members. And every time we find one, we can also admit to the set
every alterntive not beaten by more alternatives than it is. 

If anything in the above paragraph is wrong, it's because I haven't
really dealt with this procedure before tonight.

Of course rating the alternatives according to how many other alternatives
beat them would require doing all the pairwise comparisons, something that,
ideally, we might like to avoid. But it wouldn't take any appreciable
time on the computer to do all the pairwise comparisons. But maybe there's
a good way that could save some time by not doing that. I don't know.

Anyway, I've sketched out one procedure for determining the Smith set.


Mike











--