Raph Frank wrote:
On Wed, Mar 18, 2009 at 10:26 AM, Kristofer Munsterhjelm
<km-el...@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.
----
Election-Methods mailing list - see http://electorama.com/em for list info