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

[Juho]

Actually not all Condocet methods are nicely summable, although all  
typical (commonly used) ones are. For example a method that uses IRV  
if there is no Condorcet winner is not "nicely summable". Maybe  
Condorcet methods that can find the winner based on the pairwise  
comparison matrix only should be classified as one specific subset of  
Condorcet methods. Some methods may add e.g. an explicit (approval)  
cutoff to this, but in most cases this kind of additions are still  
"nicely summable".

Juho



On Feb 3, 2010, at 11:31 PM, robert bristow-johnson wrote:

>
>
> 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!
>
>
> ----
> Election-Methods mailing list - see http://electorama.com/em for  
> list info