Re: [EM] number of possible ranked ballots given N candidates

[rob brown]

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 <[EMAIL PROTECTED]> 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: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]] 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 ).  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

----
election-methods mailing list - see http://electorama.com/em for list info