# [EM] On IRV compressability

Dave Ketchum 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
twig.
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.

DWK

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
> http://bolson.org/

--
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.

```