Paul Kislanko wrote:
All fairly interesting, but whatever that algorithm is is "off topic."
Show me an algorithm that can take ONE ballot as input and return one of the
permutations of {A B C} using 3 or fewer bits.
Several people have noted that one can list all 6 permutations in order and
assign each a number as in
1 = A>B>C
2 = B>C>A
3 = C>A>B
4 = B>A>C
5 = A>C>B
6 = C>B>A
so since 6 = '110' it requires only 3 bits to record the voters' choices.
BUT, and this is important, there are 6! possible relations of {1,2,..6} ->
{x>y>z} so in order for one to retrieve the ranked order from a ballot the
ballot must include the specification of WHICH of the 720 possible
arrangements was used to form the ballot.
At the very least the table requires 3 bits for the left-hand side of the
table and six bits for the right hand side so using the "table lookup" trick
requires 18 bits to be added to the 3 bits in the {1,2,...3} code or 24 bits
per ballot.
Simple. Just use lexicographical order. Thus, all we'd need to know is
the fact that the candidates are A, B, and C, and the ballots would
always be listed in the order
000 = A>B>C
001 = A>C>B
010 = B>A>C
011 = B>C>A
100 = C>A>B
101 = C>B>A
----
Election-Methods mailing list - see http://electorama.com/em for list info
