[EM] Some myths about voting methods

Paul Kislanko kislanko at airmail.net
Sat Jun 6 14:39:50 PDT 2009


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.

 


-----Original Message-----
From: election-methods-bounces at lists.electorama.com
[mailto:election-methods-bounces at lists.electorama.com] On Behalf Of
Kristofer Munsterhjelm
Sent: Saturday, June 06, 2009 2:58 PM
To: Paul Kislanko
Cc: election-methods at electorama.com
Subject: Re: [EM] Some myths about voting methods

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.
----
Election-Methods mailing list - see http://electorama.com/em for list info





More information about the Election-Methods mailing list