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.
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:
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] 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
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 - 1If truncation is allowed it is approximately N! * eAnd 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 candidatesCondorcet 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
