[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 <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 ).  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/3145c165/attachment-0003.htm>