Batch summability

In election science, a voting method satisfies the summability criterion if it is possible to tally election results locally by precinct, then calculate the results by adding up all the votes. More formally, the compilation or summation complexity of a voting system measures the difficulty of vote counting for individual precincts, and is equal to the smallest number of bits needed to summarize all the votes. A voting method is called summable if the number of bits grows as a polynomial function of the number of candidates. Often, a group has to accept a decision, but not all the votes can be gathered together in a single location. In such a situation, we need to take the votes of the present voters and summarize them such that, when the other votes arrive, we can determine the winner. The compilation complexity of a voting-rule is the smallest number of bits required for the summary. A key advantage of low compilation complexity is it makes it easier to verify voting outcomes. Low compilation complexity lets us summarize the outcome in each voting-station separately, which is easy to verify by having representatives from each party count the ballots in each polling station. Then, any voter can verify the final outcome by summing up the results from the 1000 voting stations. This verifiability is important so that the public trusts and accepts the results.…

In election science, a voting method satisfies the summability criterion if it is possible to tally election results locally by precinct, then calculate the results by adding up all the votes. More formally, the compilation or summation complexity of a voting system measures the difficulty of vote counting for individual precincts, and is equal to the smallest number of bits needed to summarize all the votes. A voting method is called summable if the number of bits grows as a polynomial function of the number of candidates. Often, a group has to accept a decision, but not all the votes can be gathered together in a single location. In such a situation, we need to take the votes of the present voters and summarize them such that, when the other votes arrive, we can determine the winner. The compilation complexity of a voting-rule is the smallest number of bits required for the summary. A key advantage of low compilation complexity is it makes it easier to verify voting outcomes. Low compilation complexity lets us summarize the outcome in each voting-station separately, which is easy to verify by having representatives from each party count the ballots in each polling station. Then, any voter can verify the final outcome by summing up the results from the 1000 voting stations. This verifiability is important so that the public trusts and accepts the results. The publicly released information from each precinct can be used by independent election auditors to identify any evidence of electoral fraud with statistical techniques. Compilation complexity is also algorithmically useful for computing the backward induction winner in Stackelberg voting games. Let r be a voting rule: a function that takes as input a list of n ranked ballots, representing the preferences of n voters, and returns an outcome. There are some k<n voters whose votes are known. A compilation function is a function f that takes as input a list of k ranked ballots and returns some output such that, given any number u := n-k of additional ranked ballots, the output of r on the entire set of ballots can be computed exactly. The compilation complexity of a rule r is the worst-case number of bits in the output of the most efficient compilation function f. This number is typically a function of n (the number of voters), k (the number of known votes), and c (the number of candidates). However, we focus on c alone for simplicity, as we are usually interested in the case with a very large number of unknown votes.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1330450179 under CC BY-SA 4.0; modifications have been made.