[EM] Linear summability

[Kristofer Munsterhjelm]

On 27/04/2020 06.35, robert bristow-johnson wrote:
> 
> 
>> On April 26, 2020 8:17 AM Kristofer Munsterhjelm <km_elmet at t-online.de> wrote:
>>
>> Though I'm pretty sure IRV is indeed nonsummable, I've never seen a
>> proof of it;
> 
> you have to define what "nonsummable" means.  of course it's
> "summable" (in a sense of the word) but the number of subtotals each
> precinct must tally and report is very large as the number of
> candidates, C, grows.  FPTP it's O(C).  Condorcet it's O(C^2).  IRV
> it's O(C!), which is a lot more than O(C^2) as C grows.
My definition is: A method is summable (in the restricted sense here) if
the number of numbers (elements of the vector or array) required for a
precinct subtotal grows as a polynomial function of the number of
candidates in the election.

Plurality is summable because it's O(C). Matrix Condorcet methods like
Ranked pairs are (at most) O(C^2). There are even some methods out there
that are (at most) O(C^3).

I suspect, but haven't proven, that DSC is O(2^C). I suspect, but
haven't proven, that IRV is O(C!). Neither of those are summable if I'm
right. What I was trying to do with the linear summability idea is to
find a way to go from "suspect" to "have proven".

Note that the "suspect" is very strong. I would be very surprised if my
suspicions were wrong. I just have to prove it to be *absolutely* sure :-)

I know that IRV is definitely O(C!) when it's counted the "obvious" way.
But that's no proof that there's no sophisticated counting approach that
beats this bound. That's why I've said "at most" for the claims above,
too: that there's an algorithm that does Ranked Pairs in O(C^2) doesn't
mean there doesn't exist one that does it in O(C). However, again, I
very strongly suspect that the O(C^2) bound is *exact*.

> Now with this virtually Condorcet-compliant IRV-BTR method, that I am
> actively lobbying both the Vermont state legislature and the
> Burlington city council to adopt, would still be IRV so the
> individual ballot records would still have to be securely
> transported to the central tallying location for the kabuki dance we
> call the "single transferable vote" to take place, but since it's
> virtually Condorcet, the precincts can report the C×(C-1) subtotals
> that can be summed and *if* there is a Condorcet Winner, we will know
> who it is from the sums of the C×(C-1) subtotals.  (the IRV-BTR is,
> in my opinion, *virtually* Condorcet-compliant because, since it is
> STV, there can be no equal rankings of candidates on the ballot.)

Yes, that's true.

I wonder if it would be a good idea to point at this "speculative"
precinct summability as a benefit of BTR-IRV compared to ordinary IRV,
or if it would get in the way of the central point, which is that
BTR-IRV avoids center squeeze.

(As far as I know, the standard way to extend IRV to do equal-rank is to
count the first preferences fractionally, but I don't know of any public
elections that have been conducted by such rules.)