Tracking vote-sums (was Re: Electoral College Reform starting wi

[Steve Eppley]

Mike O replied to Don:
>You say that, with 4 candidates, it's necessary to keep track
>of 64 vote-sums. Well, that depends on the method, doesn't it.
>With your Instant-Runoff, that's the case, 

Right.  Pairwise methods lend themselves to parallel processing: each
precinct computer can tally a local NxN pairwise array, then forward
this array so it can be easily added (in a fraction of a second) to
the other precincts' arrays to produce the state's array.  Then the
state can forward its pairwise array to the other states.  There's no
need to forward vote-sums to reach a result if the method is
pairwise.

>and, with lots of candidates it might be more efficient to just
>record the rankings themselves in computer memory.

No, not if "sparse" storage techniques are used.  The combinations
which polled zero votes don't have to be stored, as Don has pointed
out.  It would be much more compact to store the vote-sums than to
store all the rankings, since a vote-sum is just a ranking plus a 
count, and four bytes per count is adequate.  

For example, it's smaller to store "4ABCD " than to store 
"ABCD ABCD ABCD ABCD ".

As a "technocrat", though, I should point out that there's
considerable processing overhead needed to enter the ballots into a
sparse storage format, since for each ballot the corresponding
vote-sum count must be located and incremented.  Locating a
sparsely-stored vote-sum is not a trivial process; probably the best
way would be to maintain a "hash table" index.  (And maybe sort the
structure at the end so the index can be deleted.)

But storage and forwarding are separate problems.  To combine
multistate pairwise tallies, only the compact NxN arrays (one per
state) need to be forwarded to the other states.  To combine
multistate IR tallies, one of the following techniques would 
have to be used:

1. Each state forwards all its "vote-sums" to a big computer which 
will execute the IR algorithm on the entire multistate set of 
vote-sums, or

2. Parallel computers must communicate back and forth, in a manner
which distributes the IR iteration processing.  The messages sent in
each round would be the number of "first choice votes" received by
each candidate during that round, so each computer could calculate
(redundantly, in a sense) which candidate will be eliminated next. 
(The same candidate is eliminated on every computer, of course).

These aren't intractable problems, so multistate IR is feasible.
I hope the states would be wise enough to choose a better method, 
though.

---Steve     (Steve Eppley    seppley at alumni.caltech.edu)