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?

Steve Eppley
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