Why it saves time

[Steve Eppley]

>DEMOREP1 at aol.com writes:
>> If the office were to be U.S. President in 1996, there would be
>> around 106,000,000 ballots. With a mere 10 candidates there are a
>> possible 45 combinations. 45 x 106,000,000 = 4,770,000,000 pairs to
>> be put in a mega array.

Mike Ossipoff replied:
>No. It's only necessary to keep 90 numbers in an array & tally those,
>based on each ballot's pairwise preferences. Those 90 numbers are
>how many people have voted A over B, & how many have votes B over A,
>for each of the 45 pairs.
>
>No matter how many voters there are, the counting computer only needs
>those 90 numbers.

Right.  The ballots don't need to be stored in an array.  Only the
candidate pairing counters need to be arrayed.  The ballots, which
are processed sequentially (each incrementing up to 45 of the 90
counters), can be stored on tape or some more modern mass storage
(which doesn't need to be as fast as RAM).

>> Is more than 1 supercomputer needed?

>No. No supercomputer is needed. You could use a low RAM pocket
>computer, or programmable calculator, or, when the results for
>the 45 pairs of candidates are in, you could do it without any
>computer at all. Of course a Condorcet count is easier with
>a computer, but any pocket computer or programmable calculator
>could do it, since it only requires storing 90 numbers.

I disagree with this, if Mike is writing about Condorcet and not 
Smith.  A huge amount of computing time is needed to tally the 
Condorcet ballots, even though little storage is needed.  However, 
it doesn't have to be done on supercomputers since the ballots can be 
processed in parallel on thousands of PCs.  With only 10 candidates, 
the compute-time isn't too high, but the time increases as the square 
of the number of candidates.

Tally Time is roughly V x p(C) x T / P
where V = number of voters
      C = number of candidates
      p(C) = number of pairings = sum of i as i goes from 1 to C-1
      T = time to tally one pairing of one ballot
      P = number of parallel computers.

With
  V=100,000,000
  C=10   ==>  p(C) = 1+2+3+4+5+6+7+8+9 = 45
  T is estimated to be about 10 microseconds on a recent model PC.
  Suppose P = 1 computer.
The tally time is roughly 45,000 seconds, or about half a day.

If my estimate of T is too low by an order of magnitude, then this 
tally might take 5 days.

Increase C by a factor of 10 (to 100 candidates), and the time would
increase by about a factor of 100 (to 50 days, or 500 if my T
estimate was low).  But the ballots could be divvied up among
hundreds or thousands of cheap computers. 

Here's a quote from Peter C. Ordeshook in _Game Theory and Political 
Theory_ (1986), p.89: 
  "As an implementable procedure, however, exhaustive pairwise voting
  to find and elect a Condorcet winner is impractical in mass
  elections, and since it seems reasonable to require that democratic
  voting procedures select Condorcet winners if they exist, scholars
  have proposed a variety of voting schemes as alternatives to
  plurality rule.  But the problem with most analyses of these
  alternatives is that they take inadequate account of the possibility
  that voters might misrepresent their preferences and candidates
  might change their campaigns under different rules.  Although
  reforms might or might not perform better than plurality rule, the
  analysis remains incomplete unless it recognizes the consequences of
  Theorem 2.3 [Gibbard-Satterthwaite]."

I think that in the decade since Ordeshook wrote that, the
improvements in computer technology, the drop in computer costs, and
interconnection of computers using the internet makes Condorcet now
practical for the Presidential election.  (He has an office about a
block from where I live; maybe I'll get a chance to talk with him
about this.) 

--Steve