[EM] Completion methods for Smith Sets
Michael Rouse
mrouse at cdsnet.net
Mon Jun 18 16:06:20 PDT 2001
At 12:03 PM 6/18/2001 -0400, you wrote:
To me, while it does satisfy the Condorcet Criterion, it has some of the
same drawbacks as IRV, although on a smaller scale.
>Here's my understanding of your technique (unfortunately, I'm at work,
>and my copy of your original message describing it is at home, so this is
>from memory):
>
>A. If there is a Condorcet winner, select it.
>B. If there isn't a Condorcet winner, strike[1] all candidates not in the
>Smith Set from the ballots
>C. Rank the remaining N candidates by:
> C1: selecting the plurality winner,
> C2: selecting the plurality winner counting ranks 1-2 as identical,
> other than already selected candidates
> ...
> CN-1: selecting the plurality winner counting ranks 1-N-1 as
> identical, other than already selected candidates
> CN: select the remaining candidate.
>D. Strike the Nth candidate on the ranking found in step C from the ballots.
>E: If there is more than one candidate remaining, go to step C.
>
>[1] By 'strike from the ballots', I mean to remove an option from the
>ballots, and readjust the rankings from there. If a ballot ranked A
>first, B second, and C third, striking A would result in a ballot that
>ranks B first and C second.
Your memory is correct!
>The problem is that step C requires examining every ballot at least
>once. If this is a public election, that could require examining and
>recounting possibly millions of ballots. With large numbers of
>candidates, the number of possible rankings grows hyper-exponentially, and
>even 13 candidates under consideration would yield more possible rankings
>than the population of the Earth. There is no way to represent ranking
>data in the aggregate; re-examining the entire collection of ballots is
>the only way to go.
>
>This is a major logistical nightmare, although it isn't as bad in your
>proposal as it is in IRV, since you immediately restrict the field to just
>the Smith Set.
>
>I've not seen many IRV supporters mention this issue, but it isn't one to
>forget.
You are correct that it would take a huge number of ranking/recounting
steps compared to most other methods (excluding IRVing, of course). If I
were somehow to appear before our Founding Fathers here in the U.S. and
could suggest only one method for them to enshrine in the Constitution, I
would choose Approval voting, since Approval is no harder than Plurality
yet produces a superior result. It would be far too computationally
intensive to suggest *any* pairwise method, or even a Borda count, at least
until there was a working Babbage engine or equivalent.
Nowadays, with computing so cheap, I think this method is feasible even
without cutting the test group down to the Smith set. Say we have 24
candidates for President and 100 million votes. The Borda count would look
at one ranking order of candidates, and probably use one multiplication and
one addition operation on each candidate; at 1 gigaflop -- which is desktop
PC range -- this would produce the result almost in real time. Nanson's
method would need 23 times as many rankings, reducing the number of
additions and multiplications with each step: 23/24 + 22/24 + ... + 2/24 +
1/24, which is equivalent to (23+1)/24 + (22+2)/24 +...+(13+11)/24 +
(12)/24 or roughly 11.5 times as many operations, which is well within
reasonably range (in case you are wondering, I'm just pairing off the ends
to make it easier to figure out things).
Using just my "standard" method on the 24 candidates, it would take as long
to calculate as 23+22+21...+3+2+1 standard plurality elections, which
equals 11*24+12 or 276 elections. If each plurality election took a second
at one gigaflop, this would take a little less than five minutes. If we cut
down the comparison group to the Smith set, it would probably be much shorter.
The inverse method and the "Crosscut" method (combined standard and inverse
method) would be where the enormous numbers of calculations might bog
things down, at least if we didn't limit it to Condorcet/Smith sets. The
inverse set would be (23+22...+2+1) + (22+21...+2+1)+...+(2+1)+(1). Since
that's a tetrahedral number, we can find the total by 1/6*n*(n+1)*(n+2) =
1/6*23*24*25 =2300 plurality elections. Combining the two methods --
2300(inverse) +276(standard) +23(last place comparisons), and we are
looking at the equivalent of roughly 2600 plurality elections among 100
million people. Without any form of optimization, that should take less
than an hour -- no need to use an election at home screen saver for
distributed computing (though that would be utterly cool! <grin>). As a
comparison, for statistical analysis Warren D. Smith ran 100,000 elections
using 30 different election methods, though with far fewer candidates and
voters than a general election would have. We would need plenty of RAM to
store all of the results with my method, but a dual Athlon motherboard with
two gigs of RAM and an 80 gig hard drive should be sufficient for most
methods with the proper coding.
If I messed up by an order of magnitude or two on my answers (which is
possible, since I did most of the math in my head), just grab one of
Lawrence Livermore's or Sandia's supercomputers for election day, or
convince IBM to come out with a "Blue Borda" supercomputer. :) That should
do the trick.
Mike Rouse
mrouse at cdsnet.net
More information about the Election-Methods
mailing list