[EM] Some myths about voting methods

[Paul Kislanko]

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.  

-----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:18 PM
To: Paul Kislanko
Cc: election-methods at electorama.com
Subject: Re: [EM] Some myths about voting methods

Paul Kislanko wrote:
> The number of possible votes is not the same as the amount of information
in
> a single ballot. With 3 candidates, there are indeed 8 possible ballots,
but
> any one ballot can be encoded in 3 bits, since any particular choice
> requires only that many to represent it.
> 
> Ranked ballots require 2 bits per alternative (01 = 1st, 10 = 2nd, 11 =
3rd)
> so the minimum ballot representation is six bits, twice as much
information
> as is contained in an approval ballot.

That argument is not true, as such. All you need to store a ballot in a 
way that can be recognized is an enumeration. In the worst case, when 
you only have the enumeration, recovering the actual ballots will be 
very slow, but it's feasible.

In the three candidate case, you can map Approval ballots to integers 
(and back) by simply using the Approval vote as a bitfield 
representation, i.e.

0 <-> 000
1 <-> 001
2 <-> 010
3 <-> 011

and so on.

For ranked votes, it's no different:

0 <-> A > B > C
1 <-> A > C > B
2 <-> B > A > C
3 <-> B > C > A
4 <-> C > A > B
5 <-> C > B > A

So if a hundred people voted A > B > C and ten voted B > A > C, you 
could compress that down to:

(100, 0)
(10, 2)

Now, this does show that there's more raw information in an Approval 
ballot than in a ranked ballot (if no ties nor equal rank is permitted); 
however, it doesn't by itself mean that that information is useful. Of 
course, that objection can be turned right back at us for num candidates 
 > 3, in which case it's ranked ballots that have the upper hand, raw 
information wise.

For an extreme of how raw information may not actually make a 
difference, consider a ballot that's "rank the candidates, then specify 
a random number". Say the random number is used for a tie break, in some 
manner. Then there's a lot of raw information (the number of unique 
votes depend on the range of the random numbers), but the random number 
part only makes a difference in the case of a tie (which would happen 
infrequently).

Also, if one permits ranked ballots to rank multiple candidates equally 
or to truncate (which we can treat as "equal rank last", unless there's 
an approval cutoff), Approval votes are a subset of the ranked votes 
permitted, and therefore, there will always be more ranked votes than 
Approval votes. Since the methods we are discussing here usually permit 
equal-rank, I don't see the strength of the argument regarding raw 
numbers of ballots.

For Range ballots, say WLOG that it's integer Range, the minimum range 
is 1 and the maximum is x, and there are y candidates. Then there are 
x^y different Range ballots. For any predefined number of candidates, 
you can set x so that the number of unique Range ballots exceeds the 
number of unique preferential ballots. Keeping x static, there will, 
however, be another y at which the number of unique preferential ballots 
exceed the number of Range ballots (for that x) again.

If one doesn't permit equal-rank or truncation, the numbers are
y=2    x^2 = 2!   x =  1.42
y=3    x^3 = 3!   x =  1.81
y=4    x^4 = 4!   x =  2.21

y=10   x^10=10!   x =  5
y=18   y^18=18!   x =  7.55
y=25   x^25=25!   x = 10
y=100  x^100=100! x = 38

etc.

For equal rank, the relevant count is the number of total preorders, and so:

y=2    x^2 = 3    x = 1.3
y=3    x^3 = 13   x = 2.35
y=4    x^4 = 75   x = 2.94

y=10   x^10 =           102247563     x =  6.32
y=18   x^18 = 3385534663256845323     x = 10.70

and so on.
----
Election-Methods mailing list - see http://electorama.com/em for list info