Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Batch summability
open-in-new
<p>In <a href="/facts/Election_science/12cU4LqQ">election science</a>, a voting method satisfies the summability criterion if it is possible to tally election results locally by <a href="/facts/Polling_station/PLnxBpVD">precinct</a>, then calculate the results by adding up all the votes. More formally, the compilation or summation complexity of a <a href="/facts/Voting_system/e6zvx3Bo">voting system</a> measures the difficulty of <a href="/facts/Vote_counting/uw1dWyUX">vote counting</a> for individual <a href="/facts/Polling_station/PLnxBpVD">precincts</a>, and is equal to the smallest number of <a href="/facts/Bit/S972NSaD">bits</a> needed to summarize all the votes. A voting method is called summable if the number of bits grows as a <a href="/facts/PSPACE/RIkAClvG">polynomial function</a> of the number of candidates. </p><p>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. </p><p>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 <a href="/facts/Election_audit/dAF3vBf5">election auditors</a> to identify any evidence of <a href="/facts/Electoral_fraud/Mrud2cLA">electoral fraud</a> with statistical techniques. </p><p>Compilation complexity is also algorithmically useful for computing the <a href="/facts/Backward_induction/x4DwF49D">backward induction</a> winner in <a href="/facts/Stackelberg_game/cpr1PFfw">Stackelberg voting games</a>. </p>