[EM] IRV counting with integers to handle multiple candidates at the same preference level

[Kristofer Munsterhjelm]

On 27.01.2022 04:26, Forest Simmons wrote:
> Here's how to make even IRV precinct summable in a practical way, even
> when there are 135 candidates with 135 factorial permutations, and many
> more when you take equal rankings an truncations into account:
> 
> Encode each ballot as a string, just as we do on EM list election
> profiles. Add the ballot strings together algebraically as though each
> string were a variable name. Algebra software easily adds these strings
> together algebraically (as opposed to string concatenation) by
> collecting like terms on the fly. The precinct sums are added together,
> as well, again by collecting like terms. The coefficients of the
> collected terms tell how many ballots in each faction, just as in our EM
> example profiles.
> 
> You don't need to initialize 135 factorial bins, when almost all of the
> would end up empty, anyway!

It has always been known that any method is summable in O(V) space :-)
Summable in the sense of the criterion means more like O(log V) * O(C^k).

Strictly speaking, yes, you could store all the votes on a memory card.
Suppose the election has a billion voters and there are 10 candidates.
We need 22 bits to store the permutation index since log_2(10!) =
21.791... (Arithmetic coding might get you even closer, but ignore for now.)
This times a billion voters gives 22 gigabit = 3 gigabytes, simple and
easy. And that's before compression, so it's a worst bound. Most likely
there are a lot of voters who would vote from left to right or vice
versa, and considerably fewer who would vote far right first, far left
second.

So, if this is easy, then what are the downsides? I guess there are two.
First, that detailed ballot information makes it easier to buy and sell
votes, because you could use the ranking as a signature to prove that
you're voting the way your benefactor wants you to.

Second, transparency: a matrix can be printed out on paper and it's
obvious what it means. A memory card requires a computer, where anything
might happen to your ballot. If observing the process is itself
important, and paper recounts need to be possible, then summable methods
have an advantage.

-km