4,193
edits
Summability criterion: Difference between revisions
Shuffled some of the prose in the body, adding a bit of restatement of #Mathematical requirements after placing the #Summability levels table in the #Compliance section
(Removed incorrect definition, and wrote a first stab at a very high level summary. There may be some redundancy still.) |
(Shuffled some of the prose in the body, adding a bit of restatement of #Mathematical requirements after placing the #Summability levels table in the #Compliance section) |
||
Line 7:
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 real-time combined vote totals in an understandable way. Some non-summable 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.▼
===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.▼
==Compliance==
Back in 2009, [[English Wikipedia]] stated that the criterion was stated as follows:<ref>An article titled "[[wikipedia:Summability criterion|Summability criterion]]" was deleted from [[English Wikipedia]] in 2009.<nowiki><ref></nowiki>[[English Wikipedia]] AfD for "Summability Criterion": https://en.wikipedia.org/wiki/Wikipedia:Articles_for_deletion/Summability_criterion
Line 23 ⟶ 30:
In many [[Condorcet method]]s, each ballot can be represented as a two-dimensional square array referred to as a pairwise matrix. The sum of these matrices may be reported from each precinct.
=== Summability levels ===
▲==Requirements==
Restating the mathematical requirements above, a method is kth-order summable if an election involving <math>V</math> voters and <math>c</math> 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 precinct-level summaries as "summability levels":
▲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.
▲===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.
{| class="wikitable" align="center" |border="1"
|+Methods and their summability levels.
Line 53 ⟶ 52:
*[[MCA|MCA-IR]], and some forms of [[MCA|MCA-AR]]
*[[STAR voting]]<ref>{{Cite news|title=Compare STAR and IRV - Equal Vote Coalition|url=https://www.equal.vote/star-vs-irv#simplicity|work=Equal Vote Coalition|access-date=2018-11-12}}</ref>
||
*[[Adjusted Condorcet Plurality]]
* [[Correlated Instant Borda Runoff]]
| |||