[EM] number of possible ranked ballots given N candidates

[Paul Kislanko]

I believe the N! + 2^N - 1 is what you want. And yes, that should work.
 
And double yes to I'm glad someone's working on a way to model the different
methods from a universal ballot format. It should make it easier to see the
differences between Condorcet-based methods.


  _____  

From: rjbrown at gmail.com [mailto:rjbrown at gmail.com] On Behalf Of rob brown
Sent: Wednesday, December 14, 2005 3:18 PM
To: Paul Kislanko
Cc: Election Methods Mailing List
Subject: Re: [EM] number of possible ranked ballots given N candidates


Thanks.  I think the number I was looking for is the "if equal rankings are
allowed", since I am considering truncation a special case of equal
rankings.  In other words, if there are 6 candidates, I would consider the
following two ballots to be identical: 

A>B>C
A>B>C>D=E=F

the first just being a "shorthand" way of expressing the second.

And I suppose this should be obvious, but just to make sure, I consider the
following two ballots identical: 

A>B=C
A>C=B

And of course 
A>B>A
is an invalid ballot.

Given that, N! + 2^N -  1 is the correct answer?

BTW Paul are you happy I'm working with ways of using actual ballot data vs.
just the matrix? ;) 

-rob


On 12/14/05, Paul Kislanko <kislanko at airmail.net> wrote: 

The number of full ranked ballots is just the number of permutations of N
alternatives = N!
 
If equal ranknigs are allowed, it's N! + 2^N - 1
 
If truncation is allowed it is approximately N! * e
 
And if both truncation AND equal rankings are allowed it's approximately N!
* e + 2^N - 1
 


  _____  

From: election-methods-bounces at electorama.com
[mailto:election-methods-bounces at electorama.com] On Behalf Of rob brown
Sent: Wednesday, December 14, 2005 2:30 PM
To: Election Methods Mailing List
Subject: [EM] number of possible ranked ballots given N candidates



Condorcet voting methods typically preprocess ballots into a pairwise
matrix, which is convenient because the tabulation methods have a
significantly reduced set of "input data" vs. having to process all
individual ballots.  This is particularly convenient if we wish to allow the
"2nd stage" of tabulation to happen on the client, such as in javascript on
a web page (for instance, I have been building a javascript vote tabulator
which, if provided with a matrix, can do the processing client side:
http://www.karmatics.com/voting/testharness.html
<http://www.karmatics.com/voting/testharness.html> ).  If we have to process
all ballots, this could be inconvenient because all ballots must now be
delivered to the client, which could be bulky if their are a large number of
voters.  In other words, the quantity of input data of a matrix is
determined by the number of candidates, while ballot data is determined by
the number of voters. 

Unfortunately, as Paul K has pointed out, the pairwise matrix is "lossy", as
you can never retrieve the actual ballots from it.  Whether the voting
method itself actually uses this data or not, people who want to see how
everyone actually voted, and possibly do various statistical analysis on it,
are limited in what they can do because they cannot see all the data. 

Since I am now exploring methods that rely directly on ballot data, rather
than on the matrix, I especially interested in finding a convenient
non-lossy way to compress the ballot data.  This compression will not only
make it convenient to pass the data around (such as delivering it to a
client side javascript application), it can also potentially make it much
more efficient to batch process. 

So lets say I have the following ballot data:

A>B>C=D
A>C=D>B
D>B
A>B>C=D
D>B

Since there are two pairs of identical ballots, this can obviously be
compressed into 

2: A>B>C=D
1: A>C=D>B
2: D>B

As the number of ballots becomes large (say, in the thousands or tens of
thousands), this becomes quite significant.  Given N candidates, there is a
fixed number of possible unique ballots, capping the quantity of data.  It
will still be more data than the pairwise matrix, but far less than having
to store each ballot as a separate piece of data. 

My question is, what is this number?  I'm sure I could work it out but I'm
sure someone has already done it....

Thanks,
-rob




-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20051214/8bad8921/attachment-0003.htm>