Summability criterion: Difference between revisions

Summability criterion (view source)

Revision as of 12:21, 8 October 2023

13 bytes added , 8 months ago

Did a bit more cleanup based on EM posts, subdividing the full criterion into three conditions.

VisualWikitext

Kristomun

1,220

edits

Revision as of 02:31, 8 October 2023 (view source) RobLa (talk \| contribs) (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) Tag: Visual edit ← Older edit		Revision as of 12:21, 8 October 2023 (view source) Kristomun (talk \| contribs) (Did a bit more cleanup based on EM posts, subdividing the full criterion into three conditions.) Newer edit →
Line 9: ==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=== 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''. In mathematical terms, the respective conditions can be formalized as following: 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. # 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''. ==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