Calculating the Smith set?
Steve Eppley
seppley at alumni.caltech.edu
Sat Apr 13 05:52:06 PDT 1996
I've been trying to post the following for days. The eskimo.com site
has been bouncing a lot of my messages this last week with "unknown
mailer error 14".
-----------------------
The Condorcet tallying algorithm takes so much time that a computer
is needed to tally large elections. The time is roughly proportional
to .5 tVC(C-1))
where t is the time it takes to tally one pairing of one voter
(around a millisecond on a fast PC, I'd guess, and falling),
V is the number of voters,
and C is the number of candidates.
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.
--Steve
More information about the Election-Methods
mailing list