[EM] Linear summability

[Kristofer Munsterhjelm]

On 26/04/2020 04.42, robert bristow-johnson wrote:
> 
> 
>> On April 25, 2020 7:49 PM Kristofer Munsterhjelm <km_elmet at t-online.de> wrote:
>>
>>  
>> Some time ago I was wondering how to prove that a method is nonsummable.
>> Just because we don't know of any way to make e.g. IRV summable doesn't
>> mean there isn't any. I couldn't figure out how you'd definitely exclude
>> every possible polyspace array.
> 
> i don't think there is a way to exclude any meaningfully different ballot ranking.  remember, every candidate unranked is the same as being ranked last.  whether you rank your least-desired candidate the lowest rank or leave that candidate unranked makes no difference.
> 
> maybe a decade ago i posted the formula and a proof that Warren Smith first did that shown the number of ballot piles that are summable as
> 
>   number of piles = floor( (e-1)×C! - 1 )
> 
>   if the number of candidates is C .
> 
> i haven't been able to grok the rest.

Oh, sorry if I was being confusing. I'm not talking about unranked
candidates; as with my differential inequality idea, I've implicitly
been assuming full ranks (i.e. truncation and equal-rank not allowed).
Though there's nothing preventing the method from being applied to a
wider set of ballots - with equal-rank and truncation - I thought I'd
keep things as simple as possible while I explore what *can* be done by
this approach.

floor( (e-1) * C! - 1) is the number of distinct ballots if truncation
(but not equal-rank) is allowed. The corresponding number for equal-rank
(but not truncation) is sum m=1...C (m-1)^C / 2^m. It's recorded in the
OEIS as A000670. Those are RangeVoting puzzles 91 and 110 respectively.
If I recall correctly, if you allow for both equal-rank and truncation,
then the number of distinct ballots is twice the number than when only
equal-rank is allowed (except when there's only one candidate); OEIS's
A000629.

For summable methods, even though the number of distinct ballots grow
very quickly, you can make do with only a summary of the data. If the
method is nonsummable, then those summaries will grow superpolynomially
anyway and so there won't be much of a point.

Though I'm pretty sure IRV is indeed nonsummable, I've never seen a
proof of it; just "obviously, you can't use any known structure to
summarize an IRV election because there isn't enough data there". That
still leaves the possibility open that there is such a precinct subtotal
scheme and we simply haven't found it yet. So my post is an attempt to
find out how to go about settling the issue and showing that it is
indeed impossible to construct such a subtotal.

What I suspect will happen (for IRV) is that depending on the
elimination order, you'd be comparing cross-cutting sums of the
different ballot counts. That is, for every polynomial way to do a
precinct subtotal, some elimination order will require the knowledge of
just a part of what contributes to one of the elements.

But it would still have to be proven, so I should look into how to
calculate the determinant of very large matrices, to show linear
independence. Or use induction. The case of IRV isn't all that
interesting on its own, beyond as (hopefully) showing that my approach
works.