[EM] Completion methods for Smith Sets

[Michael Rouse]

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