[EM] Trie structure for ballots

[Kristofer Munsterhjelm]

I've been coding, on and off, a program to determine how often criteria 
are failed by voting methods. It uses a GA to devise failure examples 
without knowing exactly how to construct those failure examples - for 
instance, for monotonicity failure, it just uses the score of the 
original winner as a fitness function to minimize.

Since it uses a GA, it's quite slow. To help with this, I've arranged 
the ballots in a trie structure so that going through the actual ballots 
can be made quicker. Consider a ballot set like:

1: A > B.
1: A > C.
1: B > A.

This has the structure:

At first level: Root (3 voters)
At second level (Root -> *): A (2 voters), B(1 voter)
At third level: Root -> A -> *: B (1 voter), C (1 voter)
At third level: Root -> B -> *: A (1 voter).

(In reality, there are two numbers for each node. The first number is 
the cumulative - number of ballots starting with the path so far - and 
the second is exact - number of ballots of exactly this type. That way, 
one can encode both A > B and A > B > C without the system confusing one 
for the other. However, in the example above, all votes are truncated to 
two ranks, so as to not make the example harder to understand, I've 
omitted the "exact" numbers.)

It's easy to see that counting these would be easier for Plurality 
because it only needs to go through each first-level node, of which 
there are at most the number of candidates. IRV can also be made quicker 
by keeping pointers that are advanced when a candidate drops out.

Now, this seems to work well enough for ordinary ranked ballots with 
truncation. However, equal-rank is another matter, and that's where I'll 
ask. How would you implement equal-rank in this system?

The most straightforward attempt would be to map all combinations of 
equal-rank ballots to nodes, something like

1: A > B
1: A = B

has nodes A and A=B below the root. However, as the number of candidates 
increases, the number of possible equal-rank configurations also do so - 
very quickly.

Another attempt might involve having two kinds of relations, so

1: A > B
1: A = B

becomes

root -> (A)
(A) -> (B at lower level), (B at same level),

where one doesn't store B=A, just A=B and keeps convention that all 
equal ranks must be sorted,

but wouldn't that confuse the cumulative count for A? Or would one have 
to keep both a cumulative count of only those at a lower level (1 in the 
example above) and for both those at a lower level and at the same (2 in 
the example above)? But then the IRV traveling-pointer algorithm would 
get pretty hairy, I think...

Any ideas?