[EM] Linear summability

robert bristow-johnson rbj at audioimagination.com
Sun Apr 26 21:35:14 PDT 2020

> On April 26, 2020 8:17 AM Kristofer Munsterhjelm <km_elmet at t-online.de> wrote:
> floor( (e-1)×C! - 1) is the number of distinct ballots if truncation
> (but not equal-rank) is allowed.

which is essentially the case for all RCV (the new name for what used to be "IRV") elections i am aware of for government office.
> For summable methods, even though the number of distinct ballots grow
> very quickly, you can make do with only a summary of the data.

i think i would agree, but it's an imprecise definition of summability.  i think what would be better is just state the number of subtotals each precinct needs to tally and report.

if C is the number of candidates, the number of subtotals each precinct must tally and report it:

First-past-the-post:    C
Condorcet-compliant:    C×(C-1)
Instant Runoff Voting:  floor( (e-1)×C! - 1 )

> 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;

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.

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.)

r b-j                  rbj at audioimagination.com
"Imagination is more important than knowledge."

More information about the Election-Methods mailing list