[EM] On IRV compressability

[Dave Ketchum]

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.