<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=us-ascii">
<META content="MSHTML 6.00.2900.2769" name=GENERATOR></HEAD>
<BODY>
<DIV dir=ltr align=left><SPAN class=566083021-14122005><FONT face=Arial
color=#0000ff size=2>I believe the N! + 2^N - 1 is what you want. And yes, that
should work.</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=566083021-14122005><FONT face=Arial
color=#0000ff size=2></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=566083021-14122005><FONT face=Arial
color=#0000ff size=2>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.</FONT></SPAN></DIV><BR>
<BLOCKQUOTE
style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #0000ff 2px solid; MARGIN-RIGHT: 0px">
<DIV class=OutlookMessageHeader lang=en-us dir=ltr align=left>
<HR tabIndex=-1>
<FONT face=Tahoma size=2><B>From:</B> rjbrown@gmail.com
[mailto:rjbrown@gmail.com] <B>On Behalf Of </B>rob brown<BR><B>Sent:</B>
Wednesday, December 14, 2005 3:18 PM<BR><B>To:</B> Paul Kislanko<BR><B>Cc:</B>
Election Methods Mailing List<BR><B>Subject:</B> Re: [EM] number of possible
ranked ballots given N candidates<BR></FONT><BR></DIV>
<DIV></DIV><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="PADDING-LEFT: 1ex; MARGIN: 0pt 0pt 0pt 0.8ex; BORDER-LEFT: rgb(204,204,204) 1px solid">
<DIV dir=ltr align=left><SPAN><FONT face=Arial color=#0000ff 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 face=Arial color=#0000ff
size=2></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN><FONT face=Arial color=#0000ff size=2>If equal
ranknigs are allowed, it's N! + 2^N - 1</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN><FONT face=Arial color=#0000ff
size=2></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN><FONT face=Arial color=#0000ff size=2>If
truncation is allowed it is approximately N! * e</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN><FONT face=Arial color=#0000ff
size=2></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN><FONT face=Arial color=#0000ff 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 face=Arial color=#0000ff
size=2></FONT></SPAN> </DIV><BR>
<BLOCKQUOTE
style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: rgb(0,0,255) 2px solid; MARGIN-RIGHT: 0px">
<DIV lang=en-us dir=ltr align=left>
<HR>
<FONT face=Tahoma size=2><B>From:</B> <A
onclick="return top.js.OpenExtLink(window,event,this)"
href="mailto:election-methods-bounces@electorama.com"
target=_blank>election-methods-bounces@electorama.com</A> [mailto:<A
onclick="return top.js.OpenExtLink(window,event,this)"
href="mailto:election-methods-bounces@electorama.com"
target=_blank>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 onclick="return top.js.OpenExtLink(window,event,this)"
href="http://www.karmatics.com/voting/testharness.html"
target=_blank>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></BLOCKQUOTE></BODY></HTML>