[EM] Summability criterion: do I have this right?

[James Faran]

I'm not certain about the second item.  My worry is the following method that someone must have thought of before me and rejected.

Given any single ballot, we can use it to create the pairwise matrix.  The entries will be +1, 0, or -1. From that pairwise matrix we can reconstruct the preference order given on the ballot. Concatenate all such pairwise matrices. This "summary", an n by n by v array, has size on the order of n^2*v, where n is the number of candidates and v the number of voters. The combination of these is by concatenation in the "v" direction of the array.  This is quadratic in n (just as good as a pairwise method) and linear in v (pairwise methods are logarithmic in v). Plurality is linear in n and logarithmic in v (when v gets bigger we just have to increase the number of digits used to describe the totals). The point is that this method transfers complete ballot information, yet clearly is not a method one would want to use.  And we certainly, in avoiding discussion of polynomial growth, don't want to suddenly need to explain logarithmic growth.

As v has a tendency to get bigger than n, I think "polynomial in n" and "logarithmic in v" might be a good standard.  (A rough calculation leads me to believe this method beats just listing the number of ballots of each of the n! types when (n-2)! > v, so is only really a help when n is large.  For 10^7 voters, I think n=14 might do it.)  All in all, as it stands the second point is good enough. We'd just want to avoid responding to a "What does that mean?" question with "You don't want to know," or "You wouldn't understand." However, for studying the question, a more precise definition is needed, lest every method be "summable".  Should the amount of calculation time needed to analyze the "summary" come into it?

In item 3., perhaps "combined in any order" would work.  In my mind that covers both associativity and commutativity.

Sorry if none of this makes sense.  Late night thoughts.

Jim Faran
________________________________
From: Election-Methods <election-methods-bounces at lists.electorama.com> on behalf of Kristofer Munsterhjelm <km_elmet at t-online.de>
Sent: Friday, October 6, 2023 8:05 PM
To: Rob Lanphier <roblan at gmail.com>
Cc: election-methods at lists.electorama.com <election-methods at lists.electorama.com>
Subject: Re: [EM] Summability criterion: do I have this right?

On 10/7/23 01:44, Rob Lanphier wrote:
> Hi Kristofer,
>
> Thanks for the thoughtful responses.  It was a long time ago that I
> learned (not to my surprise) that most Wikipedia users only read the
> summary of an article (i.e. the portion before the table of contents),
> and frequently they only skim that.  So, here's the Wikipedia article
> about Summability:
>
> ...and here's what is stated in the summary:
>
>     /Each vote should be able to be mapped onto a summable array, such
>     that its size at most grows polynomially with respect to the amount
>     of candidates, the summation operation is associative and
>     commutative and the winner could be determined from the array sum
>     for all votes cast alone./
>
> /
> /
> The good news: that's almost certainly more accurate than what I added
> to the summary on electowiki (which apparently more accurately describes
> the "Consistency criterion" than it does the Summability criterion).
> The bad news: most peoples' eyes glaze over when they hear math nerds
> explain the difference between "grows polynomially" and "grows
> exponentially".  By the time we start talking about big-O notation,
> they've already fled.
>
> Is there a TERSE way of describing the summability criterion that is
> both accurate and doesn't use jargon like "summable array", "associative
> and commutative", and "grows polynomially".  It's OKAY if one uses
> jargon if one can explain that jargon to a layperson in a single
> sentence, but it's not great.  Just assume you're explaining the concept
> to someone that barely passed American high-school algebra.

That's what I'm having trouble thinking up. I would say what needs to be
conveyed is that a method is summable if:

1. Any election can be boiled down to a summary that contains all the
data the method requires to call the election,
2. The storage space required for the summary doesn't grow too quickly
as you add new candidates or voters,
3. and the summaries can be combined (added up) to get the summary for
the combined election.

That's about as short as I could make the conditions. The "grows
polynomially" part is a formalization of the second condition; the
"commutative and associative" part relates to the third condition.

My language is definitely far from perfect, but perhaps it'll help guide
others who'd like to try to write a good summary of what summability means.

-km
----
Election-Methods mailing list - see https://nam12.safelinks.protection.outlook.com/?url=https%3A%2F%2Felectorama.com%2Fem&data=05%7C01%7Cjjfaran%40buffalo.edu%7C86446f1d0ab347a052d508dbc6c92a0e%7C96464a8af8ed40b199e25f6b50a20250%7C0%7C0%7C638322339532625531%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=3X8y40ita8aRglwFJLKQO5ZvlLWZXHpI3yJkitvVtkQ%3D&reserved=0<https://electorama.com/em> for list info
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20231007/6a5377bb/attachment-0001.htm>