[EM] IRV proponents figure out how to make IRV precinct-summable
km-elmet at broadpark.no
Sun Mar 22 12:42:18 PDT 2009
Raph Frank wrote:
> On Wed, Mar 18, 2009 at 10:26 AM, Kristofer Munsterhjelm
> <km-elmet at broadpark.no> wrote:
>> 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.
> 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.
More information about the Election-Methods