Summability criterion
The summability criterion (sometimes referred to as "precinct summability" or "batch summability"^{[1]}) is a criterion about the votecounting process of electoral systems. Summability concerns whether a method can be counted in precincts instead of having to be counted at a central location.
Informally, a method is summable if precinct ballots can be reduced to a small summary, and that the center can combine these small summaries to determine the outcome of the election as a whole. This both makes it easier to verify election results and reduces the amount of information that has to be transmitted to a centralized counting location.
Unlike most other voting system criteria, it does not relate to the end result, only to the process.
This is important for elections with many voting jurisdictions to be able to practically transmit their vote totals for tabulation. Summability is important to be able to report realtime combined vote totals in an understandable way. Some nonsummable methods require that the individual ballot images are are transmitted to a centralized counting location to find the combined result.
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. In other words, it must be more efficient to count the votes in precincts than to bring the votes to a centralized location.
The requirements can be split into three conditions:
 Any election can be summarized into a precinct total, and the election method only needs the precinct total to determine the outcome for that precinct.
 The space required for the precinct total must not grow too quickly as one adds new candidates, and should barely grow at all as one adds new voters.
 The summaries can be combined in any order to produce a summary for the election as a whole.
Mathematical requirements
In mathematical terms, the respective conditions can be formalized as following:
 Each vote should map onto a summable array, and the winner should be determined from the array sum for all votes cast.
 An election method is kthorder summable if there exists a constant c such that in any election with n candidates and V voters, the required size of the array is at most cn^{k} log(V) bits.
 The summable arrays can be combined with a summation operation that is associative and commutative.
If there is no value of k for which the method is kthorder summable, the method is nonsummable.
Compliance
Back in 2009, English Wikipedia stated that the criterion was stated as follows:^{[2]}
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.^{[3]}
Here at electowiki, we believe the following methods comply with the summability criterion:
 Plurality voting (also known as "chooseone voting") — In plurality voting, the number of ballots for each candidate may be counted, and these totals reported from each precinct.
 Approval voting — Though each ballot may contain votes for more than one candidate, the sum of all values for each candidate may be found at each precinct and reported.
 Borda count — Though each ballot contains votes for more than one candidate, and these votes may have different values, the sum of all values for each candidate may be found at each precinct and reported.
 Score voting — Though each ballot contains votes for more than one candidate, and these votes may have different values, the sum of all values for each candidate may be found at each precinct and reported.
 Most Condorcet methods (e.g. Schulze method, Ranked Pairs) — these can generally be added into a twodimensional array
 Some Condorcet hybrids (e.g. Nanson's method, Majority Choice Approval)
As noted in William Poundstone's book Gaming the Vote, InstantRunoff Voting does not comply.^{[4]} Potthoff also observes that IRV is not summable.^{[5]}
In many Condorcet methods, each ballot can be represented as a twodimensional square array referred to as a pairwise matrix. The sum of these matrices may be reported from each precinct.
Summability levels
Restating the mathematical requirements above, a method is kthorder summable if an election involving voters and candidates can be summarized in a data structure such as a list or a matrix with "k" dimensions. Such a data structure obviates the need to transmit full ballot images from precincts in order to determine the winner of an election. The table below describes the number of dimensions required in precinctlevel summaries as "summability levels":
k=1  k=2  k=3  nonsummable 




Examples
Summable methods
Pointsscoring methods
Positional methods
In plurality voting, each vote is equivalent to a onedimensional 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 onedimensional arrays depending on the method.
Median methods
Alternatively, precincts may sum up the number of times each candidate was ranked at each of the possible ranks (or grades). This positional matrix can then be used to compute the result for any weighted positional method after the fact, or for medianbased methods like graded Bucklin methods. This shows a contrast between median methods and pointscoring methods, where the grade level doesn't matter, only the strength/quality/degree of the grade (i.e. in pointsscoring 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 are precinctsummable using voter's pairwise preference order alongside the total score received for each candidate.
Condorcet methods
In Schulze and many other summable Condorcet methods, each vote is equivalent to a twodimensional 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.
Nonsummable methods
Instantrunoff 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.
It is possible to reduce the amount of data required to call an IRV election by instead storing a Plurality count for all ways to eliminate some subset of the candidates. This gives an array of elements; but that is still not polynomial.
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 nonsummable. 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 firstorder 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 firstplace votes for each candidate. The central system would then return to each precinct a candidate to eliminate. Each precinct would then return the firstplace 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 N1 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 firstorder 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 newlyfound ballots. Under nonsummable 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 timeconsuming and expensive.
Multiwinner generalizations and results
Generalized criteria
There's no one extension of the summability criterion for multiple winners, because the summability criterion only considers two variables (the number of voters and the number of candidates), whereas there's one more variable for a multiwinner method: the number of seats. One possible extension of the summability criterion is as follows:^{[9]}
 Weak summability: Suppose that the number of seats is fixed. Then the method should be summable in terms of the number of candidates and the logarithm of the number of voters, as a singlewinner method is. However, the amount of information required may increase exponentially with the number of seats.
 Strong summability: There must exist a summary that passes summability (i.e. bits in total) which can, after being compiled, be used to determine the outcome for the multiwinner method for any number of seats.
Results
Unless otherwise specified, these results pertain to strong summability.
Any method that requires no more than bits for seats, with and being constants, passes strong summability.
Most block voting methods that are based on summable singlewinner methods are also of the same degree of summability in the multiwinner case, and strongly so.
Generally speaking, except for proportional Category:FPTPbased voting methods (which notably include Party list and SNTV), there are no seriously used summable Category:PSCcompliant voting methods.
Proportional approval voting is weakly ksummable with bits, where k is the number of winners.
Forest Simmons has constructed a colorproportional method that's summable in for any number of seats.^{[10]}
It's unknown whether it's possible to construct a strongly summable Droopproportional method.
Notes
Many voting methods that are summable to some degree can be manually summed in a harder way. For example, Score voting can be counted using a form of Pairwise counting that takes degree of preference into account.
Amount of votecounting work
Summability focuses on the amount of data that has to be captured, but not necessarily the amount of work required to capture it. For example, when doing pairwise counting, an election featuring a ballot that ranks a candidate last requires as many marks to count as if the same ballot had been cast without the lastranked candidate. Yet in practice, the votecounters must still take some time to check that that candidate is indeed lastranked, meaning some work is done even while no data was produced.
Number of data value types versus number of data values
Summability focuses to a large extent on the number of data value types, not just the amount of data overall that has to be captured. This can make a difference in certain cases; for example, the regular pairwise counting approach only requires data value types to be captured for all ballots, whereas the Negative votecounting approach for pairwise counting requires value types. This is because the latter not only records preferences in each pairwise matchup, but also the number of ballots ranking each candidate. Yet, depending on implementation, the negative counting approach actually has the same upper bound on number of data values to capture as the regular approach, and in practice could require fewer.
Counting first choices
Some voting methods can be counted like Approval voting when counting:
 Approvalstyle ballots (a ballot that maximally supports some candidates and doesn't support any other candidates),.
 More generally, the 1st choices of a ballot can be counted like Approval for any ballots that rank one (or possibly more) candidates 1st, but show some support for some other candidates, (This means the ballot's support for its non1st choice candidates may be harder to count).
reducing the amount of work otherwise necessary to count them. For example, Condorcet methods can have this done using a certain implementation of the Negative votecounting approach for pairwise counting, or simply by using Pairwise counting#Counting first choices separately.
Twoway communication
Some nonsummable methods can be counted using twoway communication, which is when the precincts both transmit and receive information to and from the central votecounting authorities during the counting process.
Most sequential Cardinal PR require less twoway communication and/or centralized counting work than most other PR methods.
See also
 Voting system
 Monotonicity criterion
 Condorcet Criterion
 Generalized Condorcet criterion
 Favorite betrayal criterion
 Participation criterion
References
 ↑ "Q: Are STAR Voting ballots "summable," or do they require centralized tabulation?". STAR Voting. Retrieved 20221225.
 ↑ An article titled "Summability criterion" was deleted from English Wikipedia in 2009.<ref>English Wikipedia AfD for "Summability Criterion": https://en.wikipedia.org/wiki/Wikipedia:Articles_for_deletion/Summability_criterion Before the page was deleted from Wikipedia, it was copied to Electowiki. Those with the correct permissions can see the edit history on English Wikipedia.
 ↑ Note that this blockquote was copied to electowiki before it was deleted from English Wikipedia. There were other changes may have been made after the article was copied from wikipedia:Summability criterion to Summability criterion (Wikipedia version). Please see the edit histories for each page to determine who authored the passage you are interested in.
 ↑ Gaming the Vote, Why Elections Aren't Fair (and What We Can Do About It), William Poundstone, New York: Hill and Wang, 2008, p. 170.
 ↑ Potthoff, Richard F. (20110831). "Simple manipulationresistant voting systems designed to elect Condorcet candidates and suitable for largescale public elections". Social Choice and Welfare. Springer Science and Business Media LLC. 40 (1): 101–122. doi:10.1007/s0035501105893. ISSN 01761714.
 ↑ Hogben, G. (1913). "Preferential Voting in Singlemember Constituencies, with Special Reference to the Counting of Votes". Transactions and Proceedings of the Royal Society of New Zealand. 46: 304–308.
 ↑ Nanson, E. J. (1882). "Methods of election". Transactions and Proceedings of the Royal Society of Victoria. 19: 197–240.
 ↑ "Compare STAR and IRV  Equal Vote Coalition". Equal Vote Coalition. Retrieved 20181112.
 ↑ Munsterhjelm, K. (20110724). "Weighted voting systems for proportional representation". Electionmethods mailing list archives.
 ↑ "answer to puzzle 15". RangeVoting.org. 20070201. Retrieved 20200211.
See also
 Voting system
 Monotonicity criterion
 Condorcet Criterion
 Generalized Condorcet criterion
 Favorite betrayal criterion
 Participation criterion
Some parts of this article are derived with permission from text at http://electionmethods.org
This page was migrated from the "Summability_criterion" page on wiki.electorama.com. To view the authors prior to the migration, view the "Summability_criterion" page edit history prior to 20181001 