Calculating the Smith set?

[Bruce Anderson]

On Apr 13,  5:52am, Steve Eppley wrote:
> Subject: Calculating the Smith set?
> Okay, computers are cheap so Condorcet's method is more viable now
> than it was in the Marquis' century.  It's also possible to use
> parallel processing if necessary, since the voters' ballots can
> easily be divvied up.  (The CxC matrices can be added together at 
> the end.)
> What about calculating the Smith set?  Is this time negligible in
> comparison to tallying all the pairings?  What's a good algorithm? 
> I presume it's much quicker than the pairwise tallies, since it's
> independent of the number of voters, but I want to doublecheck. 
>-- End of excerpt from Steve Eppley

In my very limited explorations so far, I've found that there is no clear 
relationship between "data requirement" and "computational effort."  Some voting 
methods, like plurality (with a most-seconds, most-thirds, etc. tie-breaker), or 
single-winner STV/Hare, do not require much computational effort even though 
(or, perhaps, because) they have high data requirements.  Condorcet's method has 
medium data requirements and Copeland's method has low data requirements, but 
this seems completely irrelevant to computational effort -- they seem (to me) to 
be about equal to each other computationally and both would be easy to do with a 
suitably programmed modern computer.  However, as Steve notes for Condorcet, 
both are, in general, very tedious to do my hand.  Like Condorcet's method, 
Kemeny's method has medium data requirements, but, quite unlike Condorcet and 
Copeland, Kemeny's method can require more computational effort than can be 
provided by the world's currently most powerful computers when there are many 
(say, 20 or more) Smith winners.

As Steve notes, Smith has low data requirements.  (I'm using Fishburn's (1977) 
definitions here, for those who want to quibble.)  However, I don't see an 
"easy" way to calculate, in general, the Smith winners.  (There are some easy 
special cases.)  Specifically, using the algorithms I am aware of, it seems 
easier to calculate both the Copeland winners and the Condorcet (method) winners 
than it is to calculate the Smith winners.  Maybe that's just because I am not 
aware of better algorithms.  But it also might be, in fact, harder to calculate 
Smith winners than it is to calculate winners according to some voting methods 
that have medium or high data requirements, even though Smith has a low data 
requirement.

Bruce