Calculating the Smith set?

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

Calculating the Smith set?

Craig Carey-2
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