[EM] IRV is summable (a little)

[Buddha Buck]

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:

     ABC
--- 100  (A is beaten by no candidate)
A-- 010 (B is beaten by A only)
-B- 000
AB- 001 (C is beaten by both A and B)
--C 000
A-C 000
-BC 000
ABC 000

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:

30 A>B>C
20 B>C>A
40 C>A>B

(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:

     A  C
-- 30 60
A-  0 30
-C 60  0
AC  0  0

showing C to be the winner.

Correct?