[EM] On IRV compressability
davek at clarityconnect.com
Wed Mar 15 23:27:59 PST 2006
In summary, IRV needs more effort for storing data than Condorcet, but it
is not as bad as the "29%" horror story that Brian responds to.
Also, the skipping of less used choices does not work if you are
collecting data as you read the ballots - you do not know which choices
are less used until you have them all in front of you.
I would even compress a bit more:
Make a table of candidates - obvious content is candidate name, including
names of write-ins. Anyway, does not get big even with reasonable
allowance for write-ins.
Make a tree table. While this can have many entries, each one is small:
Candidate name - a pointer to the candidate table.
Candidate count - but ONLY for times this candidate is the end of a
Forward pointer - given A,B,C and A,B,D entry for B must point
forward to chain of C and D.
Side pointer - B above points to either C or D - which must point
sideways to the other.
Tree is not more than 7 bytes of information per entry, which would allow
1428 entries in 10,000 bytes (I assumed no count would exceed 32767 or
65535 - make the count field bigger for bigger districts).
Anyway, many arrangements were only one or two candidates and
many completely overlapped others. Try:
A,B,C,D,E - takes 5 entries in the tree table, no matter how many
voters vote this pattern.
A A,B A,B,C A,B,C,D - as many of these patterns as are voted fit
in above 5 entries.
A,B,C,E A,B,C,E,D - needs 2 entries in addition to above 5 for as
many of these as get voted.
Finally, we are talking of achievable storage volumes.
On Tue, 14 Mar 2006 20:52:56 -0800
Brian Olson wrote:
> How summable or not is an IRV election?
> In pathological theory, it's bad. There are over factorial the number
> of choices possible rankings votes.
> In that Burlington data, I counted 9866 votes but only 562 unique
> rank arrangements.
> VRR/Condorcet would still only require 30 data points to sum up
> intermediate results for 6 choices.
> Take that data point for what you will. If we assume computer
> calculation it doesn't matter. One representation of the total vote
> set is 446082 bytes uncompressed and 10353 bytes after bzip2.
> Brian Olson
davek at clarityconnect.com people.clarityconnect.com/webpages3/davek
Dave Ketchum 108 Halstead Ave, Owego, NY 13827-1708 607-687-5026
Do to no one what you would not want done to you.
If you want peace, work for justice.
More information about the Election-Methods