[EM] Trie structure for ballots
km_elmet at lavabit.com
Sat Sep 8 02:34:32 PDT 2012
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 -
Another attempt might involve having two kinds of relations, so
1: A > B
1: A = B
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...
More information about the Election-Methods