Summability criterion: do I have this right?
Hi folks,
I've made a change to electowiki's "Summability criterion" article:
https://electowiki.org/wiki/Summability_criterion
Here's the chunk that I added:
For batch summability to be true, the following must be true:
- Say that candidates "A", "B", and "C" run against each other in an
arbitrary election using single-winner electoral system "S"
- Say that candidate "A" wins in batch "X" (or precinct "X") when
ballots are tabulated using single-winner electoral system "S"
- Say that candidate "A" wins in batch "Y" (or precinct "Y") when
ballots are tabulated using single-winner electoral system "S"
- Therefore, candidate "A" must win when batches "X" and "Y" of
ballots are tabulated using single-winner electoral system "S" for "S" to
be "batch summable" (and thus, pass the "summability criterion")
(end of definition)
Am I correct? I'm trying to come up with a definition that is easy enough
for a layperson to understand, but is also accurate. I realize that this
definition only captures a subset of elections that demonstrate summability
problems, but this seems (to me) like the core of the problem with
summability.
Rob
All methods require counting at the precincts & at Central.
Runoff & STAR require information be sent from Central back to the
precincts where an additional count is done, whose results are again sent
to Central for another count.
RCV is like Runoff & STAR, but the process is repeated. More times, but not
really a qualitative difference.
On Thu, Oct 5, 2023 at 21:46 Rob Lanphier roblan@gmail.com wrote:
Hi folks,
I've made a change to electowiki's "Summability criterion" article:
https://electowiki.org/wiki/Summability_criterion
Here's the chunk that I added:
For batch summability to be true, the following must be true:
- Say that candidates "A", "B", and "C" run against each other in an
arbitrary election using single-winner electoral system "S"
- Say that candidate "A" wins in batch "X" (or precinct "X") when
ballots are tabulated using single-winner electoral system "S"
- Say that candidate "A" wins in batch "Y" (or precinct "Y") when
ballots are tabulated using single-winner electoral system "S"
- Therefore, candidate "A" must win when batches "X" and "Y" of
ballots are tabulated using single-winner electoral system "S" for "S" to
be "batch summable" (and thus, pass the "summability criterion")
(end of definition)
Am I correct? I'm trying to come up with a definition that is easy enough
for a layperson to understand, but is also accurate. I realize that this
definition only captures a subset of elections that demonstrate summability
problems, but this seems (to me) like the core of the problem with
summability.
Rob
Election-Methods mailing list - see https://electorama.com/em for list
info
On 10/6/23 06:45, Rob Lanphier wrote:
Hi folks,
I've made a change to electowiki's "Summability criterion" article:
https://electowiki.org/wiki/Summability_criterion
https://electowiki.org/wiki/Summability_criterion
Here's the chunk that I added:
For batch summability to be true, the following must be true:
* Say that candidates "A", "B", and "C" run against each other in
an arbitrary election using single-winner electoral system "S"
* Say that candidate "A" wins in batch "X" (or precinct "X") when
ballots are tabulated using single-winner electoral system "S"
* Say that candidate "A" wins in batch "Y" (or precinct "Y") when
ballots are tabulated using single-winner electoral system "S"
* Therefore, candidate "A" must win when batches "X" and "Y" of
ballots are tabulated using single-winner electoral system "S"
for "S" to be "batch summable" (and thus, pass the "summability
criterion")
(end of definition)
Am I correct? I'm trying to come up with a definition that is easy
enough for a layperson to understand, but is also accurate. I realize
that this definition only captures a subset of elections that
demonstrate summability problems, but this seems (to me) like the core
of the problem with summability.
That sounds more like consistency, so I don't think that's it.
Summability says nothing about what the results should be in precincts -
what it does say is more like this:
Let a "summarizing" be a processing step that can be done to an election
(a set of ballots).
Then for every possible election, the election method should produce the
same winner when given a summary of that election, as when given that
election directly;
the amount of data in the summary should not grow too quickly as the
number of candidates increases;
and there exists a combination algorithm so that if you combine the
summaries for two precincts, you get the same summary as if you gathered
both precincts' ballots directly and then made a summary.
(Just what's meant by "should not grow too quickly" requires mathematics
to explain in more detail.)
Here's an example where Minmax fails Consistency but that shows how
summability works:
Precinct A:
1: A > B > C > D
6: A > D > B > C
5: B > C > D > A
6: C > D > B > A
with Condorcet matrix summary:
-- 7 7 7
11 -- 12 6
11 6 -- 12
11 12 6 --
A wins.
Precinct B:
8: A > B > D > C
2: A > D > C > B
9: C > B > D > A
6: D > C > B > A
with Condorcet matrix:
-- 10 10 10
15 -- 8 17
15 17 -- 9
15 8 16 --
A wins.
If we tally both precincts as one, we get
1: A > B > C > D
6: A > D > B > C
5: B > C > D > A
6: C > D > B > A
8: A > B > D > C
2: A > D > C > B
9: C > B > D > A
6: D > C > B > A
Condorcet matrix:
-- 17 17 17
26 -- 20 23
26 23 -- 21
26 20 22 --
and C wins. So minmax fails consistency.
But note that each cell in the combined election's Condorcet matrix is
the sum of that cell in the precincts' Condorcet matrices; and that you
can determine the minmax social ordering by just using the summary.
That's what summability means.
(Well, we'd also have to prove that the Condorcet matrix grows slowly
enough. But since it's got n^2 cells and the combination operation is
just summing each cell, that follows.)
-km
On 10/6/23 06:45, Rob Lanphier wrote:
Hi folks,
I've made a change to electowiki's "Summability criterion" article:
https://electowiki.org/wiki/Summability_criterion
https://electowiki.org/wiki/Summability_criterion
Some further thoughts about that article: I have tried to make the
summability criterion definition very general and information
theoretical. For instance, the definition as listed in the article
doesn't depend on just what the summary combination operator is, as long
as it can't be used to cheat and turn non-summable methods summable.
Perhaps this is more confusing than enlightening - particularly the
parts about growing as log(V) in the number of voters.
In practice, pretty much every summable method I can think of (even
contingent vote, STAR, and majority judgment) use plain old addition to
combine summaries. For instance, combining Condorcet matrices is just
adding the cells in the two matrices together; combining Plurality
counts is also just adding up the votes per candidate; and combining
contingent vote summaries is just one Condorcet matrix and a Plurality
count per.
So maybe it would be better to come up with a simple idea that gets at
the gist of it, and then have a technical nitty-gritty section to patch
up all the loopholes... perhaps with examples for each method what their
summaries are (Condorcet matrices, positional counts, etc). But I'm not
sure how to do that; my prior answer is probably still a bit too
cumbersome to give an intuitive idea.
It's too bad we don't have any feedback from "mere readers" of
Electowiki... it's hard to know what level of detail to write at.
-km
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.
Rob
On Fri, Oct 6, 2023 at 2:19 PM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:
On 10/6/23 06:45, Rob Lanphier wrote:
Hi folks,
I've made a change to electowiki's "Summability criterion" article:
https://electowiki.org/wiki/Summability_criterion
https://electowiki.org/wiki/Summability_criterion
Some further thoughts about that article: I have tried to make the
summability criterion definition very general and information
theoretical. For instance, the definition as listed in the article
doesn't depend on just what the summary combination operator is, as long
as it can't be used to cheat and turn non-summable methods summable.
Perhaps this is more confusing than enlightening - particularly the
parts about growing as log(V) in the number of voters.
In practice, pretty much every summable method I can think of (even
contingent vote, STAR, and majority judgment) use plain old addition to
combine summaries. For instance, combining Condorcet matrices is just
adding the cells in the two matrices together; combining Plurality
counts is also just adding up the votes per candidate; and combining
contingent vote summaries is just one Condorcet matrix and a Plurality
count per.
So maybe it would be better to come up with a simple idea that gets at
the gist of it, and then have a technical nitty-gritty section to patch
up all the loopholes... perhaps with examples for each method what their
summaries are (Condorcet matrices, positional counts, etc). But I'm not
sure how to do that; my prior answer is probably still a bit too
cumbersome to give an intuitive idea.
It's too bad we don't have any feedback from "mere readers" of
Electowiki... it's hard to know what level of detail to write at.
-km
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:
- Any election can be boiled down to a summary that contains all the
data the method requires to call the election, - The storage space required for the summary doesn't grow too quickly
as you add new candidates or voters, - 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
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@lists.electorama.com on behalf of Kristofer Munsterhjelm km_elmet@t-online.de
Sent: Friday, October 6, 2023 8:05 PM
To: Rob Lanphier roblan@gmail.com
Cc: election-methods@lists.electorama.com election-methods@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:
- Any election can be boiled down to a summary that contains all the
data the method requires to call the election, - The storage space required for the summary doesn't grow too quickly
as you add new candidates or voters, - 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=0https://electorama.com/em for list info
On 10/7/23 06:26, James Faran wrote:
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?
Yes, the current mathematical standard defined in the Electowiki article
is "polynomial in candidates, logarithmic in voters" for just the reason
you mentioned: the number of voters increases much more quickly than the
number of candidates. Strictly speaking, I suppose polylogarithmic could
also work, but nobody has ever made such a summary so I shouldn't
complicate matters too much.
Perhaps something like "should grow slowly in the number of candidates
and even more slowly in the number of voters". But even that's adding
more detail to a brief summary.
In any case, my idea was that the summary should be brief, and then
questions like "what does slow mean" can be answered by pointing at
the mathematical definition, or by a longer elaboration that first
explains the justification (e.g. "there will be more voters than
candidates"), and then does a rigorous definition.
-km
Thanks everyone for weighing in on this topic, and thanks Kristofer for
fixing up my previous inaccurate summary on electowiki. After Kristofer
made his changes, I followed up with some shuffling of the prose in the
body of the article. It's far from perfect, but I think the article is
better than it was last week:
https://electowiki.org/wiki/Summability_criterion
We should also consider making similar changes over on English Wikipedia,
since that article hasn't gotten a lot of love since I restored it in
January 2022.
https://en.wikipedia.org/wiki/Summability_criterion
I suspect I'm not the only one who has conflated the "Summability
criterion" and the "Consistency criterion". Here's a link to the latter:
https://electowiki.org/wiki/Consistency_criterion
If I'm right, it may be useful to explain the relationship between
"consistency" and "summability" to electowiki readers.
Even as a longtime advocate for Condorcet compliance, I have to concede
that approval voting beats strict Condorcet winner compliance with regards
to consistency and simplicity. It's much easier to imagine real-time
results consumable by mainstream voters from talking-head newscasters as
they report on election night than it is to imagine what this looks like
with methods that fail the consistency criterion.
Rob
On Sat, Oct 7, 2023 at 2:51 AM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:
On 10/7/23 06:26, James Faran wrote:
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?
Yes, the current mathematical standard defined in the Electowiki article
is "polynomial in candidates, logarithmic in voters" for just the reason
you mentioned: the number of voters increases much more quickly than the
number of candidates. Strictly speaking, I suppose polylogarithmic could
also work, but nobody has ever made such a summary so I shouldn't
complicate matters too much.
Perhaps something like "should grow slowly in the number of candidates
and even more slowly in the number of voters". But even that's adding
more detail to a brief summary.
In any case, my idea was that the summary should be brief, and then
questions like "what does slow mean" can be answered by pointing at
the mathematical definition, or by a longer elaboration that first
explains the justification (e.g. "there will be more voters than
candidates"), and then does a rigorous definition.
-km