[Election-Methods] New improved fla for vote counts to be reported for auditing IRV elections

Kristofer Munsterhjelm km-elmet at broadpark.no
Sat Aug 2 00:14:28 PDT 2008


Kathy Dopp wrote:
> FYI,
> 
> After discussions today with the SF group of activists, I realized
> that my prior fla in my IRV paper for the number of vote counts which
> must be publicly reported in each precinct prior to randomly selecting
> precincts to manually audited (corresponding to the number of possible
> permutations of candidate orderings voters could select, assumes that
> voters are allowed to rank from one up to all N candidates.
> 
> If voters are only allowed to rank say up to 3 candidates, as in the
> SF IRV elections, then the formula changes to:
> 
> given:
> R = the number of possible rankings or IRV rounds
> N = the number of candidates in each election contest
> 
> the total number of permutations and the number of vote counts which
> must be publicly reported for EACH auditable unit is (drum roll):
> 
> the sum from i = 0 to i = R-1 of N!/(i+N-R)!

Well, any election method can be "parallelized" (in quote marks) with a 
superpolynomial amount of information when there are as many choices as 
candidates. Since n! < n^n, it also reduces to a polynomial amount of 
information for a fixed number of choices or rankings (n for one, 
n*(n-1) = O(n^2) for two, and so on).

Thus, if the activists claim that IRV escapes the problem if you do it 
in that way, you can say that that holds for absolutely every kind of 
ranked ballot method that exists - at least for the neutral ones, and 
election systems really should be neutral.

Rated ballots with a granularity permitting k possible ratings for a 
single candidate would have complexity k for a single choice, k^2 for 
two, ..., k^n for a full preference ballot.

At some point, rated or ranked, it becomes easier to simply send every 
voter's preference. An interesting consequence of that would be that 
it'd be possible to "fingerprint" one's own vote to vote-buyers if there 
are a sufficient number of choices, since one could use the extra 
information to make one's own ballot unique, and thus detectable - at 
least if the list of every voter's preference were to be made public 
afterwards.

The activists may say that the ballot data can be transferred easily if 
one uses computerized means: a practical system would pick the lesser 
number of n! and (number of voters), so a strictly ranked Presidential 
election with full turnout (300 million voters) and 10 candidates, would 
need "only" ceil(lg(10!)) * 3e8 bits = 6.6e9 bits, which is slightly 
less than 787 (binary) MB, enough to fit on a DVD.

Still, that doesn't make the system any more summable, and like you say, 
when the "competitors" only have to ship 10^2 values (actually 10^2 - 10 
= 90; Condorcet matrix with diagonal removed), 787 MB doesn't sound so 
impressive after all.



More information about the Election-Methods mailing list