[EM] IRV is summable (a little)
bmbuck at 14850.com
Tue Sep 4 09:39:07 PDT 2001
At 03:22 PM 09-04-2001 +0000, Roy wrote:
>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.
If I understand you, you are suggesting that a 3-candidate ballot A>B>C be
turned into a 8x3 matrix like so:
--- 100 (A is beaten by no candidate)
A-- 010 (B is beaten by A only)
AB- 001 (C is beaten by both A and B)
Each ballot can be turned into such a matrix, and then the the individual
matrices can be summed.
The matrix ends up smaller than the individual ballot tallies when the
number of candidates is 6 or more (720 distinct ballots, versus 384 entries
in the matrix.
Using this method, doing an IRV election with three candidates and ballot
tallies as follows:
(standard IRC method: eliminate B, causing C to win 60 to 30).
We end up with a summed matrix of
A B C
--- 30 20 40
A-- 0 30 0
-B- 0 0 20
AB- 0 0 30
--C 40 0 0
A-C 0 40 0
-BC 20 0 0
ABC 0 0 0
>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).
So that would mean that we look at the first (---) row, and decide to
eliminate B. So we look at the -B- row and add 20 (from column C) to
column C in row ---, and likewise from AB-, add 30 to column C in A--,
right, etc, yielding a matrix that looks like:
-- 30 60
A- 0 30
-C 60 0
AC 0 0
showing C to be the winner.
More information about the Election-Methods