[EM] Some myths about voting methods

[Kristofer Munsterhjelm]

Paul Kislanko wrote:
> No, no no no NO. Now you're introducing counting algorithms. Which have to
> have pre-processed the ballots to produce the summary in a compacted format.
> 
> You MUST consider how to use ONE ballot to represent A>B>C in a
> three-candidate race. You cannot do it with less than 6 bits. 
> 
> ONE ballot. Three candidates. Express ONE VOTER's choices with the minimum
> number of bits.  

Alright. I'm going to disregard equal rank so that it may be simple, and 
I'll take the three candidate example.

The first choice of a voter is one of three candidates. The second 
choice of the voter is one of two candidates. The third choice is given, 
because it's whichever candidate remains.

The algorithm is like the one you use to convert a decimal number to a 
hexidecimal number. We can make the observation that a decimal number is 
merely a group of digits that each range from 0..9, inclusive. For the 
above, we have one "digit" which ranges from 0..2, inclusive, and 
another which ranges from 0..1, inclusive. So, for three candidates, 
you'd get:

Start with the set {A, B, C}, and the ballot number b.

Get the remainder when dividing b by 3 - call the remainder r_0. 
Subtract this from b and divide by 3 to get q.
Get the remainder when dividing b by 2 - call the remainder r_1.

If r_0 is 0, then A is the first choice. If r_0 is 1, then B is the 
first choice. If r_0 is 2, then C is the first choice.

Remove that candidate from the set. Now you have a set of two 
candidates. Call those candidates c1 and c2.

If r_1 is 0, then c1 is the second choice, otherwise c2 is the second 
choice.

Remove the second choice from the set. The choice that remains is the 
third choice of the voter.

-

Now we just have to show that this codes all the possible ballots:

b     r_0     r_1     first chosen     second chosen        third chosen
0     0       0       A                B                    C
1     1       0       B                A                    C
2     2       0       C                A                    B
3     0       1       A                C                    B
4     1       1       B                C                    A
5     2       1       C                B                    A

and there we go.