[EM] Proportional Representation via Approval Voting

[Forest Simmons]

On Sun, 21 Jan 2001, Bart Ingles wrote in part:

> 
> 
> Of course you need to count votes for combinations,
> and not just for individual candidates.  In which case complexity of the
> count is definitely a concern.  Administering the election must be
> manageable, and the process must be explainable to the average voter. 
> Are the results computable in a reasonable amount of time when there are
> large numbers of candidates?  An actual algorithm, along with a runtime
> analysis, would be worth studying.
> 
> 

Suppose, for example, that forty candidates vie to fill ten seats.  The
number of ten member subsets of a set of size forty is less than a
billion.  A modern personal computer could tabulate this many combinations
from a single ballot in about a minute, on the order of the amount of time
the next voter needs to enter his preferences into the computer, so that a
running total for each combination can be kept on each voting machine. 

Adding the totals from a million voting machines would take a few seconds
on a supercomputer (or a network of less than super computers), since
adding totals is ideally adapted to parallel processing.  If the voting
machines are supercomputers, then the various combinations for a given
ballot can be checked in parallel, also, speeding things up in case there
are more candidates and more seats to be filled.

In stead of keeping a running total on the voting machines, one could wait
until all the ballots were entered and eliminate the candidates that did
not meet quota to drastically reduce the number of combinations to be
checked.

If the number of seats to be filled is more than a dozen or so, this
method might not be practical without supercomputer voting machines or
several side conditions that reduce the number of combinations to be
checked.

There might be some clever algorithm that achieves the same result without
having to calculate every combination separately, but I doubt it.

Here's one computational trick that comes in handy when working by hand:

For a given combination, let n1, n2, n3, ... be the respective number of
ballots supporting at least 1, at least 2, at least 3, ... of the
candidates in the combination.  Then the combination's score is n1 + n2/2
+ n3/3 ... .


Forest