[EM] IRV is summable (a little)
Roy
royone at yahoo.com
Tue Sep 4 08:22:31 PDT 2001
One of the commonly cited problems of IRV is that it is not summable:
to process the ballots, they must be re-read, or a count must be made
of the ballots matching each possible ballot, which requires N!
figures to be kept.
That's not quite true. It is only necessary to remember which
candidates (if any) are ranked ahead of a candidate to know whether
and when votes for him should be counted. The order of the candidates
ahead of him are not important. That means that IRV ballots are
summable in a total of N * 2^N figures. A fair improvement over N!.
(Actually, it's N * 2^(N-1), but that gets clumsy to implement).
One implementation would be to have a bit-vector of one bit per
candidate in some predetermined order. When examining a ballot, look
at each candidate and determine which candidates are ahead of her.
Set the bits in the bit vector to represent that, and use the
resulting number as an index into a 2-D array, where the other index
is the position of the candidate being evaluated.
The only figures of interest in tallying are those whose bit-vector
index is (all) zero. Easy enough. When a candidate is eliminated, the
array is searched for all entries where that candidate's bit is on,
and the tallies are added to the counts where that candidate's bit is
off (and all other bits are the same).
More information about the Election-Methods
mailing list