Summability criterion: Difference between revisions
→Summability levels: fix mistaken move of Bucklin
(Noting that the "summability criterion" is frequently referred to as "precinct summability") |
(→Summability levels: fix mistaken move of Bucklin) |
||
| (7 intermediate revisions by 3 users not shown) | |||
Line 1:
{{wikipedia|Summability criterion}}
The '''summability criterion''' (sometimes referred to as "'''precinct summability'''" or "'''batch summability'''"<ref>{{Cite web |title=Q: Are STAR Voting ballots "summable," or do they require centralized tabulation? |url=https://www.starvoting.org/summable |access-date=2022-12-25 |website=STAR Voting |language=en}}</ref>) is a criterion about the vote-counting process of [[Electoral system|electoral systems]]
==Compliance ==▼
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 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.▼
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 ''kth-order 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<sup>k</sup> 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 ''k''th-order summable, the method is ''non-summable''.
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 15 ⟶ 37:
*Some Condorcet hybrids (e.g. [[Nanson's method]], [[Majority Choice Approval]])
As noted in William Poundstone's book ''[[Gaming the Vote]]'', [[Instant-Runoff Voting]] does not comply.<ref>''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.</ref> Potthoff also observes that [[IRV]] is not summable.<ref name="Potthoff 2011 pp. 101–122">{{cite journal | last=Potthoff | first=Richard F. | title=Simple manipulation-resistant voting systems designed to elect Condorcet candidates and suitable for large-scale public elections | journal=Social Choice and Welfare | publisher=Springer Science and Business Media LLC | volume=40 | issue=1 | date=2011-08-31 | issn=0176-1714 | doi=10.1007/s00355-011-0589-3 | pages=101–122}}</ref>
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===
{| class="wikitable" align="center" |border="1"
|+Methods and their summability levels.
Line 39 ⟶ 53:
*[[Approval voting]]
*Plurality-based [[Party-list proportional representation|Party list PR]]
*[[Majority Judgment]]{{Note|Requires O(k * n) space, where k is the number of possible ratings and n is the number of votes.}}
*[[Single non-transferable vote]]
*Most forms of [[MCA]]
|
*most [[Condorcet method]]s
*Borda-elimination ([[Baldwin's method|Baldwin]]<ref>{{Cite journal|last=Hogben|first=G.|date=1913|title=Preferential Voting in Single-member Constituencies, with Special Reference to the Counting of Votes|url=http://rsnz.natlib.govt.nz/volume/rsnz_46/rsnz_46_00_005780.html|journal=Transactions and Proceedings of the Royal Society of New Zealand|series=|volume=46|issue=|pages=304–308|via=}}</ref> and [[Nanson's method|Nanson]]<ref name="sumNanson">{{Cite journal|last=Nanson|first=E. J.|date=1882|title=Methods of election|url=https://archive.org/details/transactionsproc1719roya/page/197|journal=Transactions and Proceedings of the Royal Society of Victoria|volume=19|pages=197–240|via=}}</ref>)
*[[Bucklin voting|Bucklin]]▼
*[[MCA|MCA-IR]], and some forms of [[MCA|MCA-AR]]
▲*[[Bucklin voting|Bucklin]]
*[[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]]
||
*[[Benham's method]]
Line 61 ⟶ 74:
==Examples==
=== Summable methods===
====
=====Positional methods=====
Line 79 ⟶ 92:
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]] are precinct-summable using voter's pairwise preference order alongside the total score received for each candidate.
=====
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 91 ⟶ 104:
|+
!
!
!B
!C
!
|-
|
| ---
| '''(A>B)''' 1
|1
|1
|-
|B
| '''(B>A)''' 0
| ---
| 0
|1
|-
|C
|0
|
| ---
|1
|-
|
|0
|0
Line 126 ⟶ 139:
=====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 [[Space_of_possible_elections|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 <math>2^c</math> ways to eliminate some subset of the candidates. This gives an array of <math>2^{c-1}c - 2^c + 1 = O(2^cc)</math> elements; but that is still not polynomial.
==Importance of summability==
Line 135 ⟶ 150:
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.
Line 147 ⟶ 162:
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==
===
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 multi-winner method: the number of seats. One possible extension of the summability criterion is as follows:<ref>{{cite web|url=http://lists.electorama.com/pipermail/election-methods-electorama.com/2011-July/092996.html|title=Weighted voting systems for proportional representation|website=Election-methods mailing list archives|date=2011-07-24|last=Munsterhjelm|first=K.}}</ref>
*
*
===
Unless otherwise specified, these results pertain to strong summability.
Line 165 ⟶ 180:
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, and strongly so.
Generally speaking, except for proportional [[:
[[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>
Line 181 ⟶ 196:
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 last-ranked candidate. Yet in practice, the vote-counters must still take some time to check that that candidate is indeed last-ranked, 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 <math>n^2-n</math> data value types to be captured for all ballots, whereas the [[Negative vote-counting approach for pairwise counting]] requires <math>n^2</math> 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:
Line 198 ⟶ 211:
Most sequential [[Cardinal PR]] require less two-way communication and/or centralized counting work than most other [[PR]] methods.
==See also==
*[[Voting system]]
*
*[[Condorcet Criterion]]
*[[Generalized Condorcet criterion]]
Line 207 ⟶ 220:
*[[Participation criterion]]
==
<references />
==See also==
*[[Voting system]]
*[[Monotonicity criterion]]
*[[Condorcet Criterion]]
| |||