[EM] IRV proponents figure out how to make IRV precinct-summable

[Kristofer Munsterhjelm]

Raph Frank wrote:
> On Wed, Mar 18, 2009 at 10:26 AM, Kristofer Munsterhjelm
> <km-elmet at broadpark.no> wrote:
>> In
>> effect, one decouples the calculation (determining the winners) from the
>> counting (determining what people actually voted), and one can thus alter
>> one without necessarily having to alter the other.
> 
> Adb's ballot imaging idea takes this to the extreme.  With pattern
> recognition software, you could support virtually any voting method.
> 
> The "counting" process would just produce a list of numbers
> corresponding to each ballot.
> 
> In its most simple form, you would just need a pattern recognition
> program that can recognise the numbers 0 to 9 and maybe also the
> letter X (for "place an X next to your favourite candidate").
> 
> As long as the ballots are designed to make this easy, it shouldn't be
> that difficult a task.  There would be a box provided for each number
> that the voter fills in.
> 
> I wrote some software that is a basic attempt at this.  However, it
> only gives 70% ish accuracy.
> 
> See:
> 
> http://groups.yahoo.com/group/RangeVoting/files/Ballot%20image/
> 
> The circles are used to align the image and the black rectange at the
> top is used to work out where the top of the ballot is.
> 
> I think if there was demand, it should be possible to make this
> software much more accurate, since it doesn't have to worry about most
> of the complexities of handwriting recognition.  It wouldn't have to
> separate out letters as each 'box' would only contain one number and
> there are only 10 possibilities.  Also, since each box would be in a
> known position on the page, it would be able to figure out where each
> letter is located.

Let's look at this in a hierarchical manner. Doing so, we get:

level 0: raw images of the ballots
level 1: parsed ballot data, not summable
level 2: parsed and counted ballots, some summable format (if possible)
level 3: social compromise ballot (social ordering or rating)
level 4: winner/s

Level 4 applies to all methods that determine one or more winners. 
Practically all election methods do this. There is only one level 4 
result - a set consisting of the winners according to the method.

Level 3 applies to those that produce either a social ordering or an 
"aggregate rated ballot" (like a social ordering, but with rating 
instead of ranking). Most methods can be extended to produce a social 
ordering. For instance, all elimination-based methods can do this by 
noting the order of elimination, then reversing that (first eliminated 
is ranked last). As with level 4, there is only one instance of level 3 
data - that which is produced by the final calculation.

Level 2 applies to all summable methods. There may be many instances of 
level 2 data, but by the definition of summability, the chunks are 
limited in size by a polynomial function of the number of candidates.

Levels 1 and 0 apply to all methods, except possibly those that rely on 
sortition (where the order of the ballots matter). In the worst case, 
all voters vote in a different order (and with different ratings, if 
it's a rated system).

Define lg(x) = binary logarithm of x, also nC = number of candidates, nV 
= number of voters.

For level 1, this produces, for a ranked system, min(nC! * lg(nV), 
lg(nC!) * nV) ballots, and for a rated system where the maximum rating 
is y and the minimum rating is x (in steps of 1), min(lg(nV) * 
(y+1-x)^nC, lg(y+1-x) * nC * nV). The point is that either one has a 
format of the type "for each possible rank/rating, list how many people 
voted this way" (thus requiring lg(nV) for the digits), or "for each 
person, list how he voted" (thus requiring lg of [the number of unique 
votes] for the digits).
For level 0, each voter may trivially make a unique mark somewhere so 
that all the ballots are unique. Thus the worst case is simply nV.

-

To get back to what you're saying; yes, it's possible to store raw 
ballot data. For a ranked ballot system and modern storage, level 1 data 
may even be storable for a United States-wide election with 13 
candidates. The eligible US population is 2e8 (roughly speaking), so 
lg(13!) * 2e8 = 6.5 billion bits = 775 MB.

Level 0 data is tougher still, but could be done. The problem is that in 
the worst case, each ballot may be unique. This counts against us both 
in storing and in vote-buying cases (since a voter might mark the ballot 
in some special way to identify himself to the buyer). Obviously, one 
would need a lot of space if the entire ballot is to be imaged, but this 
may be fixed to some extent by only imaging the boxes where the voters 
write the numbers that constitute their rank or rating.

In any case, what appears, and what makes the summability criterion 
useful, is that shipping around level 2 data is much easier than to do 
so with level 1 or level 0 data. The whole point of a voting system 
itself is to do data reduction (hopefully consistent with the qualities 
the public desire of a voting system) - from level 0 to level 3 or 4, 
and further to representation - so that one may deal with the reduced 
data instead of the enormous amount that is the people's opinion. If one 
could deal with the enormous amount, there would be little point, and 
one could just have a direct democracy.