Summability criterion: Difference between revisions

Content added Content deleted

Inline

Revision as of 06:15, 15 May 2020

It has been suggested that this article be merged with Summability criterion (Wikipedia version). (Discuss) Proposed since February 2019.

The summability criterion is a criterion about the vote-counting process of voting systems, which describes how precinct-summable a voting method is (i.e. whether there is a way for two areas to transmit their vote totals and add this up to find the combined vote total, and if so, how easy it is, or if all the votes need to be taken to a centralized counting location to find the combined result). Unlike most other voting system criteria, it does not relate to the end result, only to the process.

Requirements

Informally speaking, the amount of data that has to be transmitted from the precincts should be less than the amount of data on the ballots themselves i.e. it must be more efficient to count the votes in precincts than to bring the votes to a centralized location.

Mathematical requirements

Each vote should map onto a summable array, where the summation operation is associative and commutative, and the winner should be determined from the array sum for all votes cast. An election method is kth-order summable if there exists a constant c such that in any election with n candidates, the required size of the array is at most cn^k. If there is no value of k for which the method is kth-order summable, the method is non-summable.

Strictly speaking, a method is kth-order summable if an election involving $V$ voters and $c$ candidates can be stored in a data structure (a summary) that requires $O(\log(V)\cdot c^{k})$ bits in total, where there exists a summation operator that takes any two such summaries and produces a third for the combined election, and the election method itself can use these summaries instead of ballot sets to produce the same results. This definition closes the obvious loophole of using a few very large numbers to store more data than would otherwise be permitted.

Summability of various voting methods

Methods and their summability levels.
k=1	k=2	k=3	non-summable
Borda count Plurality voting Score voting Approval voting Most forms of MCA	most Condorcet methods, Bucklin MCA-IR, and some forms of MCA-AR STAR voting^[1] Majority Judgment	Iterative Ranked Approval Voting Correlated Instant Borda Runoff	Instant-runoff voting Nanson's method Descending Acquiescing Coalitions

Examples

Summable methods

Points-scoring methods

Positional methods

In plurality voting, each vote is equivalent to a one-dimensional array with a 1 in the element for the selected candidate, and a 0 for each of the other candidates. The sum of the arrays for all the votes cast is simply a list of vote counts for each candidate.

Any weighted positional method can be summed this way, but with different one-dimensional arrays depending on the method.

Median methods

Alternatively, precincts may sum up the number of times each candidate was ranked at each of the $c$ possible ranks. This positional matrix can then be used to compute the result for any weighted positional method after the fact, or for median-based methods like Category:Graded Bucklin methods. This shows a contrast with between median methods and point-scoring methods, where the grade level doesn't matter, only the strength/quality/degree of the grade (i.e. in other methods, two 1/5s are equivalent to one 2/5).

Cardinal methods

Approval voting is the same as plurality voting except that more than one candidate can get a 1 in the array for each vote. Each of the selected or "approved" candidates gets a 1, and the others get a 0.

For example, with Score voting, a voter who votes A:10 B:6 C:3 D:1 is treated as giving a 10 to A, a 6 to B, etc. Comparisons across different score scales can be made by dividing the score by the max score (i.e. instead of a 6, treat it as a 6/10=0.6, etc.) so that a voter who scores a candidate a 3 out of 5 and a voter who scores a candidate a 6 out of 10 can have their scores treated and counted the same without any issues.

Pairwise methods

Some voting methods, such as STAR voting can be made precinct-summable using pairwise information alongside other pieces of information.

Condorcet methods

In Schulze and many other summable Condorcet methods, each vote is equivalent to a two-dimensional array referred to as a pairwise matrix. If candidate A is ranked above candidate B, then the element in the A row and B column gets a 1, while the element in the B row and A column gets a 0. The pairwise matrices for all the votes are summed, and the winner is determined from the resulting pairwise matrix sum. The precincts' matrices may be added together to get the matrix for the whole electorate, just like a precinct's voters' matrices may be added together to get the matrix for that precinct.

For example, a voter who ranks all of the candidates A>B=C>D is treated as, in a matrix, giving:


	A	B	C	D
A	---	(A>B) 1	1	1
B	(B>A) 0	---	0	1
C	0	0	---	1
D	0	0	0	---

If some other voter ranked B above A, then that would be added into this matrix by adding a 1 to the B>A cell (i.e. increasing it from 0 to 1), etc.

Category:Condorcet-cardinal hybrid methods require one additional piece of information per candidate: the score for the candidate. This can be stored in the cell comparing the candidate to themselves (i.e. A>A would have candidate A's score).

Non-summable methods

Instant-runoff voting

IRV does not comply with the summability criterion. In the IRV system, a count can be maintained of identical votes, but votes do not correspond to a summable array. The total possible number of unique votes grows factorially with the number of candidates.

Importance of summability

The summability criterion addresses implementation logistics. Election methods with lower summability levels are substantially easier to implement with integrity than methods with higher summability levels or methods that are non-summable. In addition, summability points to the simplicity of understanding how voters' support for candidates influences who wins in the voting method.

Example

Suppose, for example, that the number of candidates is ten.

Under first-order summable methods like plurality or Approval voting, the votes at any level (precinct, ward, county, etc.) can be compressed into a list of ten numbers.
For Schulze, a 10×10 matrix is needed (although only 10x9=90 data values are actually kept).
In an IRV system, however, each precinct would need to send a list of ten numbers, the number of first-place votes for each candidate. The central system would then return to each precinct a candidate to eliminate. Each precinct would then return the first-place votes for each of the nine remaining candidates, and receive another candidate to eliminate. This would be repeated at most 9 times. This is more than the others.

IRV therefore requires more data transfer and storage than the other methods. The biggest challenge in using computers for public elections will always be security and integrity. If N-1 times more data needs to be transferred and stored, verification becomes more difficult and the potential for fraudulent tampering becomes slightly greater.

To illustrate this point, consider the verification of a vote tally for a national office. In a plurality election, each precinct verifies its vote count. This can be an open process where The counts for each precinct in a county can then be added to determine the county totals, and anyone with a calculator or computer can verify that the totals are correct. The same process is then repeated at the state level and the national level. If the votes are verified at the lowest (precinct) level, the numbers are available to anyone for independent verification, and election officials could never get away with "fudging" the numbers. Of course, if verified images of all the ballots are available to the public, then the whole counting process is available to anyone for independent verification, for any voting system.

Recounts

In first-order summable election systems, adding new ballots to the count (say, ballots that were found after the initial count, or late absentee ballots, or ballots that were initially ruled invalid) is as simple as "summing" the original result with the newly-found ballots. Under non-summable systems, though, finding new ballots means all ballots might possibly need to be recounted. This is not a big problem for computer recounts, but manual recounts can be extremely time-consuming and expensive.

Multi-winner generalizations and results

Most block voting methods that are based on summable single-winner methods are also of the same degree of summability in the multi-winner case.

Generally speaking, except for proportional Category:FPTP-based voting methods (which notably include Party list and SNTV), there are no seriously used summable Category:PSC-compliant voting methods.

Ebert's method is summable in $O(c^{2})$ for any number of seats.^[2]

Academic results

Forest Simmons has constructed a color-proportional method that's summable in $O(\log(V)\cdot c)$ for any number of seats.^[3] The same approach can be generalized to make a Droop-proportional method that's fixed-parameter summable in $O(\log(V)\cdot c^{s})$ where $s$ is the number of seats, by keeping a separate count for each solid coalition of size $s$ or less.

It's unknown whether it's possible to construct a Droop-proportional method that's summable in $O(\log(V)\cdot c^{k}\cdot s^{n})$ for constant $k$ and $n$ .

References

↑ "Compare STAR and IRV - Equal Vote Coalition". Equal Vote Coalition. Retrieved 2018-11-12.
↑ "proof that sum of squared loads is precinct-summable". 2020-01-14. Retrieved 2020-04-29.
↑ "answer to puzzle 15". RangeVoting.org. 2007-02-01. Retrieved 2020-02-11.

@@ Line 1: / Line 1: @@
 {{Merge|Summability criterion (Wikipedia version)|date=February 2019}}
-The '''summability criterion''' is a criterion about the counting process of voting systems, which describes how precinct-summable a voting method is (i.e. whether there is a way for two areas to transmit their vote totals and add this up to find the combined vote total, and if so, how easy it is, or if all the votes need to be taken to a centralized counting location to find the combined result). Unlike most other voting system criteria, it does not relate to the end result, only to the process.
+The '''summability criterion''' is a criterion about the vote-counting process of voting systems, which describes how precinct-summable a voting method is (i.e. whether there is a way for two areas to transmit their vote totals and add this up to find the combined vote total, and if so, how easy it is, or if all the votes need to be taken to a centralized counting location to find the combined result). Unlike most other voting system criteria, it does not relate to the end result, only to the process.
+== Requirements ==
+Informally speaking, the amount of data that has to be transmitted from the precincts should be less than the amount of data on the ballots themselves i.e. it must be more efficient to count the votes in precincts than to bring the votes to a centralized location.
+=== Mathematical requirements ===
 Each vote should map onto a summable array, where the summation operation is associative and commutative, and the winner should be determined from the array sum for all votes cast.  An election method is ''kth-order summable'' if there exists a constant ''c'' such that in any election with ''n'' candidates, the required size of the array is at most ''cn<sup>k</sup>''.  If there is no value of ''k'' for which the method is ''k''th-order summable, the method is ''non-summable''.
 Strictly speaking, a method is kth-order summable if an election involving <math>V</math> voters and <math>c</math> candidates can be stored in a data structure (a summary) that requires <math>O(\log(V) \cdot c^k)</math> bits in total, where there exists a summation operator that takes any two such summaries and produces a third for the combined election, and the election method itself can use these summaries instead of ballot sets to produce the same results. This definition closes the obvious loophole of using a few very large numbers to store more data than would otherwise be permitted.
+== Summability of various voting methods ==
-== Multi-winner generalizations and results ==
-Forest Simmons has constructed a color-proportional method that's summable in <math>O(\log(V) \cdot c)</math> for any number of seats.<ref name="RangeVoting.org 2007">{{cite web | title=answer to puzzle 15 | website=RangeVoting.org | date=2007-02-01 | url=https://rangevoting.org/PuzzQWEAns15.html | access-date=2020-02-11}}</ref> The same approach can be generalized to make a Droop-proportional method that's fixed-parameter summable in <math>O(\log(V) \cdot c^s)</math> where <math>s</math> is the number of seats, by keeping a separate count for each solid coalition of size <math>s</math> or less.
-It's unknown whether it's possible to construct a Droop-proportional method that's summable in <math>O(\log(V) \cdot c^k \cdot s^n)</math> for constant <math>k</math> and <math>n</math>.
-[[Ebert's method]] is summable in <math>O(c^2)</math> for any number of seats.<ref>{{cite web | title=proof that sum of squared loads is precinct-summable | date=2020-01-14 | url=https://forum.electionscience.org/t/possible-improvement-to-pamsac-gets-rid-of-cfat/566/19 | access-date=2020-04-29}}</ref>
-== Summable methods ==
 {| class="wikitable" align="center" |border="1"
-|+ Methods and their summability levels.
+|+Methods and their summability levels.
 ! k=1 !! k=2 !! k=3 !! non-summable
 |-
@@ Line 28: / Line 24: @@
 *Most forms of [[MCA]]
 |
 *most [[Condorcet method]]s,
 *[[Bucklin voting|Bucklin]]
 *[[MCA|MCA-IR]], and some forms of [[MCA|MCA-AR]]
@@ Line 37: / Line 33: @@
 *[[Correlated Instant Borda Runoff]]
 ||
 *[[Instant-runoff voting]]
 *[[Nanson's method]]
 *[[Descending Acquiescing Coalitions]]
@@ Line 52: / Line 48: @@
 In [[plurality voting]], each vote is equivalent to a one-dimensional array with a 1 in the element for the selected candidate, and a 0 for each of the other candidates. The sum of the arrays for all the votes cast is simply a list of vote counts for each candidate.
-Any [[weighted positional method]] can be summed this way, but with different one-dimensional arrays depending on the method. Alternatively, precincts may sum up the number of times each candidate was ranked at each of the
+Any [[weighted positional method]] can be summed this way, but with different one-dimensional arrays depending on the method.
+====== Median methods ======
-<math>c</math> possible ranks. This ''positional matrix'' can then be used to compute the result for any weighted positional method after the fact, or for [[Bucklin voting]].
+Alternatively, precincts may sum up the number of times each candidate was ranked at each of the <math>c</math> possible ranks. This ''positional matrix'' can then be used to compute the result for any weighted positional method after the fact, or for median-based methods like [[:Category:Graded Bucklin methods|Category:Graded Bucklin methods]]. This shows a contrast with between median methods and point-scoring methods, where the grade level doesn't matter, only the strength/quality/degree of the grade (i.e. in other methods, two 1/5s are equivalent to one 2/5).
 ===== Cardinal methods =====
 [[Approval voting]] is the same as plurality voting except that more than one candidate can get a 1 in the array for each vote. Each of the selected or "approved" candidates gets a 1, and the others get a 0.
 For example, with [[Score voting]], a voter who votes A:10 B:6 C:3 D:1 is treated as giving a 10 to A, a 6 to B, etc. Comparisons across different score scales can be made by dividing the score by the max score (i.e. instead of a 6, treat it as a 6/10=0.6, etc.) so that a voter who scores a candidate a 3 out of 5 and a voter who scores a candidate a 6 out of 10 can have their scores treated and counted the same without any issues.
 ==== Pairwise methods ====
+{{Main|Pairwise counting}}
 Some voting methods, such as [[STAR voting]] can be made precinct-summable using pairwise information alongside other pieces of information.
 ===== Condorcet methods =====
-See [[pairwise counting]].
 In [[Schulze method|Schulze]] and many other summable [[Condorcet method|Condorcet methods]], each vote is equivalent to a two-dimensional array referred to as a pairwise matrix. If candidate A is ranked above candidate B, then the element in the A row and B column gets a 1, while the element in the B row and A column gets a 0. The pairwise matrices for all the votes are summed, and the winner is determined from the resulting pairwise matrix sum. The precincts' matrices may be added together to get the matrix for the whole electorate, just like a precinct's voters' matrices may be added together to get the matrix for that precinct.
@@ Line 81: / Line 76: @@
 |-
 |A
-| ---
+|  ---
 |'''(A>B)''' 1
 |1
@@ Line 88: / Line 83: @@
 |B
 |'''(B>A)''' 0
-| ---
+|  ---
 |0
 |1
@@ Line 95: / Line 90: @@
 |0
 |0
-| ---
+|  ---
 |1
 |-
@@ Line 102: / Line 97: @@
 |0
 |0
-| ---
+|  ---
 |}
 If some other voter ranked B above A, then that would be added into this matrix by adding a 1 to the B>A cell (i.e. increasing it from 0 to 1), etc.
 [[:Category:Condorcet-cardinal hybrid methods]] require one additional piece of information per candidate: the score for the candidate. This can be stored in the cell comparing the candidate to themselves (i.e. A>A would have candidate A's score).
-==== Median methods ====
-The [[Majority Judgement]] and [[Bucklin]] methods can be made summable by counting the number of voters who gave a candidate each specific grade or rank. This is in contrast to other rated methods, where the grade level doesn't matter, only the strength/quality/degree of the grade (i.e. in other methods, two 1/5s are equivalent to one 2/5).
 === Non-summable methods ===
@@ Line 115: / Line 107: @@
 ===== Instant-runoff voting =====
-IRV does not comply with the summability criterion. In the IRV system, a count can be maintained of identical votes, but votes do not correspond to a summable array. The total possible number of unique votes grows factorially with the number of candidates.
+[[IRV]] does not comply with the summability criterion. In the IRV system, a count can be maintained of identical votes, but votes do not correspond to a summable array. The total possible number of unique votes grows factorially with the number of candidates.
 == Importance of summability ==
@@ Line 121: / Line 113: @@
 The summability criterion addresses implementation logistics. Election methods with lower summability levels are substantially easier to implement with integrity than methods with higher summability levels or methods that are non-summable. In addition, summability points to the simplicity of understanding how voters' support for candidates influences who wins in the voting method.
+=== Example ===
-Suppose, for example, that the number of candidates is ten. Under first-order summable methods like [[plurality voting|plurality]] or [[Approval voting]], the votes at any level (precinct, ward, county, etc.) can be compressed into a list of ten numbers. For [[Schulze method|Schulze]], a 10×10 matrix is needed (although only 10*9=90 data values are actually kept). In an [[IRV]] system, however, each precinct would need to send a list of ten numbers, the number of first-place votes for each candidate. The central system would then return to each precinct a candidate to eliminate. Each precinct would then return the first-place votes for each of the nine remaining candidates, and receive another candidate to eliminate. This would be repeated at most 9 times. This is more than the others.
+Suppose, for example, that the number of candidates is ten.
+* Under first-order summable methods like [[plurality voting|plurality]] or [[Approval voting]], the votes at any level (precinct, ward, county, etc.) can be compressed into a list of ten numbers.
+* For [[Schulze method|Schulze]], a 10×10 matrix is needed (although only 10x9=90 data values are actually kept).
+* In an [[IRV]] system, however, each precinct would need to send a list of ten numbers, the number of first-place votes for each candidate. The central system would then return to each precinct a candidate to eliminate. Each precinct would then return the first-place votes for each of the nine remaining candidates, and receive another candidate to eliminate. This would be repeated at most 9 times. This is more than the others.
 IRV therefore requires more data transfer and storage than the other methods. The biggest challenge in using computers for public elections will always be security and integrity. If N-1 times more data needs to be transferred and stored, verification becomes more difficult and the potential for fraudulent tampering becomes slightly greater.
@@ Line 130: / Line 127: @@
 In first-order summable election systems, adding new ballots to the count (say, ballots that were found after the initial count, or late absentee ballots, or ballots that were initially ruled invalid) is as simple as "summing" the original result with the newly-found ballots.  Under non-summable systems, though, finding new ballots means all ballots might possibly need to be recounted.  This is not a big problem for computer recounts, but manual recounts can be extremely time-consuming and expensive.
+== Multi-winner generalizations and results ==
+Most [[block voting]] methods that are based on summable single-winner methods are also of the same degree of summability in the multi-winner case.
+Generally speaking, except for proportional [[:Category:FPTP-based voting methods|Category:FPTP-based voting methods]] (which notably include [[Party list]] and [[SNTV]]), there are no seriously used summable [[:Category:PSC-compliant voting methods|Category:PSC-compliant voting methods]].
+[[Ebert's method]] is summable in <math>O(c^2)</math> for any number of seats.<ref>{{cite web | title=proof that sum of squared loads is precinct-summable | date=2020-01-14 | url=https://forum.electionscience.org/t/possible-improvement-to-pamsac-gets-rid-of-cfat/566/19 | access-date=2020-04-29}}</ref>
+=== Academic results ===
+Forest Simmons has constructed a color-proportional method that's summable in <math>O(\log(V) \cdot c)</math> for any number of seats.<ref name="RangeVoting.org 2007">{{cite web | title=answer to puzzle 15 | website=RangeVoting.org | date=2007-02-01 | url=https://rangevoting.org/PuzzQWEAns15.html | access-date=2020-02-11}}</ref> The same approach can be generalized to make a Droop-proportional method that's fixed-parameter summable in <math>O(\log(V) \cdot c^s)</math> where <math>s</math> is the number of seats, by keeping a separate count for each solid coalition of size <math>s</math> or less.
+It's unknown whether it's possible to construct a Droop-proportional method that's summable in <math>O(\log(V) \cdot c^k \cdot s^n)</math> for constant <math>k</math> and <math>n</math>.
+== See also ==
+* [[Voting system]]
+* [[Monotonicity criterion]]
+* [[Condorcet Criterion]]
+* [[Generalized Condorcet criterion]]
+* [[Favorite betrayal criterion]]
+* [[Participation criterion]]
 == References ==