<span>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:
<br><br>A>B>C<br>A>B>C>D=E=F<br><br>the first just being a "shorthand" way of expressing the second.<br><br>And I suppose this should be obvious, but just to make sure, I consider the following two ballots identical:
<br><br>A>B=C<br>A>C=B<br><br>And of course <br>A>B>A<br>is an invalid ballot.<br><br>Given that, N! + 2^N - 1 is the correct answer?</span><br><br>BTW Paul are you happy I'm working with ways of using actual ballot data vs. just the matrix? ;)
<br><br>-rob<br><br><div><span class="gmail_quote">On 12/14/05, <b class="gmail_sendername">Paul Kislanko</b> <<a href="mailto:kislanko@airmail.net">kislanko@airmail.net</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div dir="ltr" align="left"><span><font color="#0000ff" face="Arial" size="2">The number of full ranked ballots is just the number of
permutations of N alternatives = N!</font></span></div>
<div dir="ltr" align="left"><span><font color="#0000ff" face="Arial" size="2"></font></span> </div>
<div dir="ltr" align="left"><span><font color="#0000ff" face="Arial" size="2">If equal ranknigs are allowed, it's N! + 2^N -
1</font></span></div>
<div dir="ltr" align="left"><span><font color="#0000ff" face="Arial" size="2"> </font></span></div>
<div dir="ltr" align="left"><span><font color="#0000ff" face="Arial" size="2">If truncation is allowed it is approximately N! *
e</font></span></div>
<div dir="ltr" align="left"><span><font color="#0000ff" face="Arial" size="2"> </font></span></div>
<div dir="ltr" align="left"><span><font color="#0000ff" face="Arial" size="2">And if both truncation AND equal rankings are allowed it's
approximately N! * e + 2^N - 1</font></span></div>
<div dir="ltr" align="left"><span><font color="#0000ff" face="Arial" size="2"></font></span> </div><br>
<blockquote style="border-left: 2px solid rgb(0, 0, 255); padding-left: 5px; margin-left: 5px; margin-right: 0px;">
<div dir="ltr" align="left" lang="en-us">
<hr>
<font face="Tahoma" size="2"><b>From:</b> <a href="mailto:election-methods-bounces@electorama.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">election-methods-bounces@electorama.com</a>
[mailto:<a href="mailto:election-methods-bounces@electorama.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">election-methods-bounces@electorama.com</a>] <b>On Behalf Of </b>rob
brown<br><b>Sent:</b> Wednesday, December 14, 2005 2:30 PM<br><b>To:</b>
Election Methods Mailing List<br><b>Subject:</b> [EM] number of possible
ranked ballots given N candidates<br></font><br></div><div><span class="e" id="q_1082afe520a631be_1">
<div></div>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: <a href="http://www.karmatics.com/voting/testharness.html" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://www.karmatics.com/voting/testharness.html
</a>
). 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. <br><br>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. <br><br>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. <br><br>So lets say I have the following ballot
data:<br><br>A>B>C=D<br>A>C=D>B<br>D>B<br>A>B>C=D<br>D>B<br><br>Since
there are two pairs of identical ballots, this can obviously be compressed
into <br><br>2: A>B>C=D<br>1: A>C=D>B<br>2: D>B<br><br>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. <br><br>My question is, what is this
number? I'm sure I could work it out but I'm sure someone has already
done it....<br><br>Thanks,<br>-rob<br><br></span></div></blockquote>
</blockquote></div><br>