[EM] IRV ballot pile count (proof of closed form)

[robert bristow-johnson]

it might be the case that my "ASCII math" didn't translate okay through the EM list server or in whatever mail client program.  i meant for it to be viewed with a mono-spaced font.

it looks okay on my client (which seems to know how to undo word-wrapping that it put in), but i took a look the email returned by the EM list server, and it appears to have wrapped some of the longer lines of text.  in the future, i have to limit my line length to 70 characters.

the case below allows equality only for the unranked candidates who are tied for last place.  for IRV or STV it's pretty hard to consider equally ranked candidates.  if one marked two candidates equally and their ranking was eventually promoted to the top, where it gets counted, how much does it count for each candidate?  1 vote or 1/2 vote?  i think that is why it is not allowed in the IRV method i am familiar with.

if the ranked ballots were used for Borda (which i don't like) or Condorcet (which i do like), then there are more natural (and fewer) "precinct summable" tallies to keep track of.

this all just started with my anal-retentive need to establish how many IRV piles one would have to maintain to have "precinct summability".  i am still convinced that for 3 candidates, the number is 9 (not 15) and for 4 candidates, you would need 40 piles (it *does* grow pretty rapidly).

--

r b-j                  rbj at audioimagination.com

"Imagination is more important than knowledge."




-----Original Message-----
From: "Kristofer Munsterhjelm" [km-elmet at broadpark.no]
Date: 02/03/2010 14:24
To: "robert bristow-johnson" <rbj at audioimagination.com>
CC: "election-methods List" <election-methods at electorama.com>
Subject: Re: [EM] IRV ballot pile count (proof of closed form)

robert bristow-johnson wrote:
> 
> On Feb 2, 2010, at 2:28 PM, robert bristow-johnson wrote:
> 
>>
>> Warren tells me that
>>
>>     C-1
>>     SUM{ C!/n! }
>>     n=1
>>
>> has a closed form, but didn't tell me what it is.  does someone have 
>> the closed form for it?  i fiddled with it a little, and i can 
>> certainly see an asymptotic limit of
>>
>>     (e-1)(C!)
>>
>> as C gets large, but i don't see an exact closed form for it.  if 
>> someone has such a closed form, would you mind sharing it?
> 
> Okay, I spent a little time working on this and figgered it out.  The 
> fact that the number of distinct piles needed to represent all possible 
> manners of *relatively* ranking C candidates (no ties except unranked 
> candidates are tied for lowest rank) is
> 
>     C-1
>     SUM{ C!/n! }  =  floor( (e-1) C! ) - 1
>     n=1

Now I wonder if there's a closed form for the number of orders with both 
equality and truncation permitted. Since I don't quite get the proof, I 
can't answer, though!